CODEWITHSUNDEEP
pythonnetworkx
Waseem Ahmed
Waseem Ahmed

Reputation: 47

Networkx Graph get sequence number for each node

I am generating directed graphs being produced as below using networkx. How do I number the nodes so that it follows a sequence of lowest to largest and when the node splits into multiple nodes all the following nodes get the same sequence number. conversely, it can also merge multiple nodes to a single node

Current Graph Current Graph

Future Graph Future Graph

Upvotes: 2

Views: 1148

Answers (1)

vurmux
vurmux

Reputation: 10020

What you want to do is called "rank nodes in directed acyclic graph".

Networkx has no build-in function for it (as I know), but it can be done with simple algorithm:

  1. If node has no predecessors, its rank is set to 1.
  2. If node has predecessors, its rank is set to "maximum predecessor rank" plus 1

Here is the example for Networkx graph:

import networkx as nx

# Create graph
G = nx.DiGraph()
G.add_edges_from([
    ('a', 'b'),
    ('b', 'c'),
    ('d', 'e'),
    ('e', 'f'),
    ('f', 'g'),
    ('g', 'h'),
    ('c', 'h'),
    ('i', 'f'),
    ('h', 'j'),
    ('j', 'k'),
])

Let's draw it like your first picture (I advice you to use Graphviz layout for it):

nx.draw(
    G,
    pos=nx.nx_agraph.graphviz_layout(G, prog='dot'),
    node_color='#FF0000'
)

enter image description here

Then we use topological sorting for proper DAG iteration and use upper algorithm:

for node in nx.topological_sort(G):
    if not len(list(G.predecessors(node))):
        G.nodes[node]['level'] = 1
    else:
        G.nodes[node]['level'] = max(
            G.nodes[n]['level']
            for n in G.predecessors(node)
        ) + 1

Then we will have our rank numbers in the "level" variable

>>> G.nodes.data('level')

NodeDataView({'i': 1, 'a': 1, 'g': 4, 'b': 2, 'd': 1, 'j': 6, 'k': 7, 'c': 3, 'e': 2, 'h': 5, 'f': 3}, data='level')

And finally we draw the graph using node ranks as labels:

nx.draw(
    G,
    pos=nx.nx_agraph.graphviz_layout(G, prog='dot'),
    node_color='#FF0000',
    labels={n: G.nodes[n]['level'] for n in G.nodes}
)

Here is the desired result:

enter image description here

Upvotes: 3

Related Questions