Notes on using DAGs with Python.

dag.md

NetworkX DAG for Dynamic Groups

• We must pin to networkx==2.6.3 (because of Python 3.7)

Other options

• py-dag https://github.com/thieman/py-dag
• paradag https://github.com/xianghuzhao/paradag
• dagsim https://github.com/uio-bmi/dagsim

Add weighted edges

In [83]: graph.add_weighted_edges_from([(parent, first_child, 10), (parent, second_child, 20), (par
    ...: ent, third_child, 30), (third_child, nested_child, 10)])

Detect a loop (if False)

In [88]: nx.is_directed_acyclic_graph(graph)
True

Show edges

In [90]: list(graph.edges)
Out[90]:
[(<DynamicGroup: parent>, <DynamicGroup: first-child>),
 (<DynamicGroup: parent>, <DynamicGroup: second-child>),
 (<DynamicGroup: parent>, <DynamicGroup: third-child>),
 (<DynamicGroup: third-child>, <DynamicGroup: nested-child>)]

Dump adjacency data (generate)

In [87]: adj = list(nx.generate_adjlist(graph))
Out[87]: adj
['parent first-child second-child third-child',
 'first-child',
 'second-child',
 'third-child nested-child',
 'nested-child']

Parse adjancy to get a Graph instance

In [117]: g2 = nx.parse_adjlist(adj, create_using=nx.DiGraph)

In [118]: nx.is_directed_acyclic_graph(g2)
Out[118]: True

In [119]: g2.edges
Out[119]: OutEdgeView([('parent', 'first-child'), ('parent', 'second-child'), ('parent', 'third-child'), ('third-child', 'nested-child')])

Exporting JSON data

In [123]: nx.tree_data(graph, parent)
Out[123]:
{'id': <DynamicGroup: parent>,
 'children': [{'id': <DynamicGroup: first-child>},
  {'id': <DynamicGroup: second-child>},
  {'id': <DynamicGroup: third-child>,
   'children': [{'id': <DynamicGroup: nested-child>}]}]}

In [130]: nx.node_link_data(graph)
Out[130]:
{'directed': True,
 'multigraph': False,
 'graph': {},
 'nodes': [{'id': <DynamicGroup: parent>},
  {'id': <DynamicGroup: first-child>},
  {'id': <DynamicGroup: second-child>},
  {'id': <DynamicGroup: third-child>},
  {'id': <DynamicGroup: nested-child>}],
 'links': [{'weight': 10,
   'source': <DynamicGroup: parent>,
   'target': <DynamicGroup: first-child>},
  {'weight': 20,
   'source': <DynamicGroup: parent>,
   'target': <DynamicGroup: second-child>},
  {'weight': 30,
   'source': <DynamicGroup: parent>,
   'target': <DynamicGroup: third-child>},
  {'weight': 10,
   'source': <DynamicGroup: second-child>,
   'target': <DynamicGroup: nested-child>},
  {'weight': 10,
   'source': <DynamicGroup: third-child>,
   'target': <DynamicGroup: nested-child>}]}

Tree methods

In [200]: def build_tree(graph, parent, depth=1):
     ...:     nodes = []
     ...:     for child in graph.successors(parent):
     ...:         nodes.append(dict(node=child, descendants=build_tree(graph, child, depth + 1), de
     ...: pth=depth))
     ...:     return nodes
     ...:

In [201]: build_tree(graph, parent)
Out[201]:
[{'node': <DynamicGroup: first-child>, 'descendants': [], 'depth': 1},
 {'node': <DynamicGroup: second-child>,
  'descendants': [{'node': <DynamicGroup: nested-child>,
    'descendants': [],
    'depth': 2}],
  'depth': 1},
 {'node': <DynamicGroup: third-child>,
  'descendants': [{'node': <DynamicGroup: nested-child>,
    'descendants': [],
    'depth': 2}],
  'depth': 1}]

In [187]: list(nx.topological_sort(nx.line_graph(graph)))
Out[187]:
[(<DynamicGroup: parent>, <DynamicGroup: first-child>),
 (<DynamicGroup: parent>, <DynamicGroup: second-child>),
 (<DynamicGroup: parent>, <DynamicGroup: third-child>),
 (<DynamicGroup: second-child>, <DynamicGroup: nested-child>),
 (<DynamicGroup: third-child>, <DynamicGroup: nested-child>)]

Ancestors

In [167]: nx.ancestors(graph, nested_child)
Out[167]: {<DynamicGroup: parent>, <DynamicGroup: third-child>}

Descendants

How do we rebuild the graph from relationships

How to represent in UI