0

I want to create hierarchial mapping of nodes of networkx.DiGraph. It is shown on the right:

enter image description here

import networkx as nx
import matplotlib.pyplot as plt
from networkx.drawing.nx_agraph import graphviz_layout
H = nx.DiGraph([(0, 1), (0, 12), (1, 2), (1, 3), (3, 4), (3, 7), (4, 5), (4, 6), 
                (7, 8), (7, 9), (9, 10), (9, 11), (12, 13), (12, 14)])
kwargs = {'pos': graphviz_layout(H, prog='dot'), 'nodelist':[], 
          'with_labels':True, 'bbox': dict(boxstyle='round,pad=0.7')}

fig = plt.figure(figsize=(20,10))
fig.add_subplot(1, 2, 1)
nx.draw(H, **kwargs)
fig.add_subplot(1, 2, 2)
nx.draw(H, **kwargs, labels=labels)
plt.show()

The value of labels I use in my script is:

{0: (),
 1: (0,),
 2: (0, 0),
 3: (0, 1),
 4: (0, 1, 0),
 5: (0, 1, 0, 0),
 6: (0, 1, 0, 1),
 7: (0, 1, 1),
 8: (0, 1, 1, 0),
 9: (0, 1, 1, 1),
 10: (0, 1, 1, 1, 0),
 11: (0, 1, 1, 1, 1),
 12: (1,),
 13: (1, 0),
 14: (1, 1)}

Is there an easy way to create such kind of labelling in networkx or any other package?

mathfux
  • 5,759
  • 1
  • 14
  • 34
  • It seems like a duplicate question. Please check this out (https://stackoverflow.com/questions/11479624/is-there-a-way-to-guarantee-hierarchical-output-from-networkx). So, you can use `graphviz_layout` to generate the hierarchical structure for the graph. – Hung Du Nov 06 '21 at 00:25
  • @HungDu It doesn't answer my question. I know how to make a layout for my graph. I'm asking how to create labels assuming graph is acyclic instead of doing it manually. – mathfux Nov 06 '21 at 12:52
  • Going left seems to be equivalent to adding a zero, going right adds a one. Is it your intention that the layout determines which branch is labelled "0", and which is labelled "1"? At the moment, without a given layout, the labels seem underconstrained. However, graphviz could have easily returned a layout where left and right are flipped. – Paul Brodersen Nov 09 '21 at 10:40
  • @PaulBrodersen It's alright for left and right to be flipped. `graphviz_layout` is just for easier visualisation of my idea. I'm looking for one-to-one mapping between nodes of any isomorphic graph and tuples of integers that fit an example I gave. – mathfux Nov 09 '21 at 16:05
  • So you don't mind if node 2 gets mapped to (0, 1), (1, 1), or (1, 0), as long as all labels are unique? – Paul Brodersen Nov 09 '21 at 17:02
  • @PaulBrodersen That's right – mathfux Nov 09 '21 at 17:04

1 Answers1

1

This should work for arbitrary trees but could be simplified for binary trees as given in the example.

import networkx as nx

H = nx.DiGraph([(0, 1), (0, 12), (1, 2), (1, 3), (3, 4), (3, 7), (4, 5), (4, 6),
                (7, 8), (7, 9), (9, 10), (9, 11), (12, 13), (12, 14)])

# iterate over nodes starting at the root
order = nx.topological_sort(H)
root = next(order)
labels = {root : list()}

for node in order:
    parent_node = next(H.predecessors(node))
    parent_label = labels[parent_node]

    # check for labeled siblings before creating a new label
    ii = 0
    while parent_label + [ii] in labels.values():
        ii += 1
    labels[node] = parent_label + [ii]

print(labels)
# {0: [], 12: [0], 14: [0, 0], 13: [0, 1], 1: [1], 3: [1, 0], 7: [1, 0, 0], 9: [1, 0, 0, 0], 11: [1, 0, 0, 0, 0], 10: [1, 0, 0, 0, 1], 8: [1, 0, 0, 1], 4: [1, 0, 1], 6: [1, 0, 1, 0], 5: [1, 0, 1, 1], 2: [1, 1]}
Paul Brodersen
  • 11,221
  • 21
  • 38