I have a DiGraph. The nodes have a string label. I want to assign an integer value to each node. The numbering of the nodes from 1, ..., n should be such that the dependencies are taken into consideration. Example:
Let nodes n1, n2, n3 and n4 be given. The dependency is n1->n2, n1-> n3, n2 -> n3 and n3 -> n4. The predecessors should assume a smaller integer value.
n1 = 1
n2 = 2, because n3 has n2 and n1 as predecessors
n3 = 3, n3 cannot be 2 because n2 is another predecessor of n3
n4= 4
I tried it with the function convert_node_labels_to_integers from networkx. I selected ordering ="sorted". However, I did not understand how it is sorted. Do you know a numbering method where I don't have to do any relabelling? Maybe something like inserting an index reference for each node?
What you are describing is called topological sorting. Available in Networkx via the function nx.topological_sort. Documentation here. Note that topological_sort returns an ordered set of node IDs; you will have to re-label the nodes yourself.