1

I have a directed graph as follows:

enter image description here

I created it with networkx and plotted it with ipycytoscape. The graph is a directed graph. All the edges have One and only one direction.

The question is how to find from a particular node all the paths between that node and node one. Since the graph is directed only paths in which ALL THE DIRECTIONS OF THE EDGES is the same are valid. IN the figure there are two paths between 6 and one. It would be possible at a first glace to thing about the blue path but in that case the direction of the edge 4-6 is different than the other ones.

nodes = [1,2,3,4,5,6,7,8]
children = [[2],[3,4],[5,6],[6,7],[8],[],[8],[]]
G2 = nx.Graph()
G2.add_nodes_from(nodes)
for i,child in enumerate(children):
    for c in child:
        G2.add_edge(i+1, c)
cyto = CytoscapeWidget()
cyto.graph.add_graph_from_networkx(G2, directed=True)
cyto.set_layout(name='dagre', nodeSpacing=10, edgeLengthVal=10)
display(cyto)

What I am looking for is the networks method that gives me the list of paths between two nodes. pseudocode:

for node1 in G.nodes:
for node2 in G.nodes:
list_of_paths = networks_method???(node1,node2)

NOTE: The graph is such that the arrows (directionality) go always from a smaller number to a higher one. 2 can be parent of 3 but never the other way around.

JFerro
  • 3,203
  • 7
  • 35
  • 88

1 Answers1

2

Usually the problem of finding "all paths" can be an exponential task and yield infinite paths. However, you describe a graph from a special subclass of directed graphs: the directed acyclic graphs (DAGs). A DAG is a directed graph G without cycles, i.e., for no node u in G exists a path u->v_1....v_n->u. Since you say all edges go from a smaller number to a higher number, your graph is a DAG.

In this case, a modified DFS search will yield you all possible paths. The topic of "all paths in DAG" were already discussed in the following questions

Sparky05
  • 4,692
  • 1
  • 10
  • 27