📋 DAG Demonstration

Compared to nodes in tree, nodes in DAG are able to have multiple parents.

Construct DAG

1. From DAGNode

DAGNodes can be linked to each other in the following ways:

• Using parents and children setter methods

• Directly passing parents or children argument

• Using bitshift operator with the convention parent_node >> child_node or child_node << parent_node

from bigtree import DAGNode, dag_to_dot

a = DAGNode("a")
b = DAGNode("b")
c = DAGNode("c", parents=[a, b])
d = DAGNode("d", parents=[a, c])
e = DAGNode("e", parents=[d])
f = DAGNode("f", parents=[c, d])
h = DAGNode("h")
g = DAGNode("g", parents=[c], children=[h])

graph = dag_to_dot(a, node_colour="gold")
graph.write_png("assets/demo/dag.png")

2. From list

Construct nodes only, list contains parent-child tuples.

from bigtree import list_to_dag, dag_iterator

relations_list = [
   ("a", "c"),
   ("a", "d"),
   ("b", "c"),
   ("c", "d"),
   ("d", "e")
]
dag = list_to_dag(relations_list)
print([(parent.node_name, child.node_name) for parent, child in dag_iterator(dag)])
# [('a', 'd'), ('c', 'd'), ('d', 'e'), ('a', 'c'), ('b', 'c')]

3. From nested dictionary

Construct nodes with attributes, key: child name, value: dict of parent name, child node attributes.

from bigtree import dict_to_dag, dag_iterator

relation_dict = {
   "a": {"step": 1},
   "b": {"step": 1},
   "c": {"parents": ["a", "b"], "step": 2},
   "d": {"parents": ["a", "c"], "step": 2},
   "e": {"parents": ["d"], "step": 3},
}
dag = dict_to_dag(relation_dict, parent_key="parents")
print([(parent.node_name, child.node_name) for parent, child in dag_iterator(dag)])
# [('a', 'd'), ('c', 'd'), ('d', 'e'), ('a', 'c'), ('b', 'c')]

4. From pandas DataFrame

Construct nodes with attributes, pandas DataFrame contains child column, parent column, and attribute columns.

import pandas as pd
from bigtree import dataframe_to_dag, dag_iterator

path_data = pd.DataFrame([
   ["a", None, 1],
   ["b", None, 1],
   ["c", "a", 2],
   ["c", "b", 2],
   ["d", "a", 2],
   ["d", "c", 2],
   ["e", "d", 3],
],
   columns=["child", "parent", "step"]
)
dag = dataframe_to_dag(path_data)
print([(parent.node_name, child.node_name) for parent, child in dag_iterator(dag)])
# [('a', 'd'), ('c', 'd'), ('d', 'e'), ('a', 'c'), ('b', 'c')]

DAG Attributes and Operations

Note that using DAGNode as superclass inherits the default class attributes (properties) and operations (methods).

from bigtree import list_to_dag

relations_list = [
   ("a", "c"),
   ("a", "d"),
   ("b", "c"),
   ("c", "d"),
   ("d", "e")
]
dag = list_to_dag(relations_list)
dag
# DAGNode(d, )

# Accessing children
node_e = dag["e"]
node_a = dag.parents[0]

Below are the tables of attributes available to DAGNode class.

Attributes wrt self	Code	Returns
Check if root	node_a.is_root	True
Check if leaf node	dag.is_leaf	False
Get node name (only for Node)	dag.node_name	‘d’

Attributes wrt structure	Code	Returns
Get child/children	node_a.children	(DAGNode(c, ), DAGNode(d, ))
Get parents	dag.parents	(DAGNode(a, ), DAGNode(c, ))
Get siblings	dag.siblings	(DAGNode(c, ),)
Get ancestors	dag.ancestors	[DAGNode(a, ), DAGNode(b, ), DAGNode(c, )]
Get descendants	dag.descendants	[DAGNode(e, )]

Below is the table of operations available to DAGNode class.

Operations	Code	Returns
Get node information	dag.describe(exclude_prefix="_")	[(‘name’, ‘d’)]
Find path(s) from one node to another	node_a.go_to(dag)	[[DAGNode(a, ), DAGNode(c, ), DAGNode(d, description=dag-tag)], [DAGNode(a, ), DAGNode(d, description=dag-tag)]]
Set attribute(s)	dag.set_attrs({"description": "dag-tag"})	None
Get attribute	dag.get_attr("description")	‘dag-tag’
Copy DAG	dag.copy()	None