Is there an easy way to create hierarchial label names in DiGraph?

Question

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

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?

Answer 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]}