networkx. digraph. walking from starting to ending nodes

Question

Having networkx DiGraph presenting following structure: I am trying to find a way to walk through the directed graph from far left nodes (without any incoming edges) presenting data sources from intermediate nodes (having incoming and outgoing edges) presenting operators transforming data to far right edges (having only incoming edges) presenting data destinations. I able to divide initial graph to set of isolated subgraphs (in red frames):

subgraphs = weakly_connected_components(g)

But then I need to find way walk through each of subgraph in the way described above. The problem is that I have different type of graphs: 1 - reverse tree 2 - straight line 3 - reverse tree 4 - few connected reverse trees tree (non reverse tree) also might occur.

E.g. for subgraph 1 I need to pass nodes in following sequence 1.1, 1.2, 1.3 or 1.1, 1.3, 1.2. The exact sequence is not important. The only strict condition is not pass to node 4.7 before getting in 4.1 and 4.5 in subgraph 4 but as mentioned above I need to start walking from nodes without any incoming edges. Could someone suggest any already existing algorithm already implemented in networkx that makes such kind of walking possible? Zero probability of colliding with a loop in graph.

Sample code to build graph on the screenshot:

import networkx as nx
from networkx.algorithms.components import weakly_connected_components

g = nx.DiGraph()
for i in range(0, 23):
    g.add_node(i)

g.add_edge(13,12)
g.add_edge(9, 8)
g.add_edge(3, 10)
g.add_edge(5, 13)
g.add_edge(7, 11)
g.add_edge(9, 14)
g.add_edge(7, 15)
g.add_edge(7, 16)
g.add_edge(17, 18)
g.add_edge(18, 19)
g.add_edge(3, 20)
g.add_edge(3, 22)
g.add_edge(18, 22)
g.add_edge(22, 21)

# removing unused nodes (without edges)
g.remove_node(0)
g.remove_node(1)
g.remove_node(2)
g.remove_node(4)
g.remove_node(6)

# get subgraphs
subgraphs = weakly_connected_components(g)

for subgraph in subgraphs:
    # here I need to iterate nodes in each subgraph 
    # in following sequence - passing dependent node can't
    # be passed before passing it's dependency nodes. For 
    # example, 4.7 can't be passed before 4.1 and 4.5, 4.5
    # can't be passed before 4.4. But no matter which of 4.1
    # and 4.5 will be passed first.

Thank you.

Answer 1

As suggested in the comments, you need to use networkx.topological_sort. topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG).