I want to find all the path that starts from a sequence of nodes, the network looks like this:
DG = nx.DiGraph()
attrs = {(1, 2), (2,3), (2,4), (4,5), (5, 6), (3,6), (6,7)}
DG.add_edges_from(attrs)
What I expect is a list of all path that starts from (1,2,3) and a list (1,2,4):
all_path = [[1, 2, 3], [1, 2, 3, 6], [1, 2, 3, 6, 7]] , [[1, 2, 4], [1, 2, 4, 5, 6], [1, 2, 4, 5, 6, 7], [1, 2, 4, 5]]
Any help would be appreciated!
There's some reading between the lines that you've left for us. For example, are you specifically looking for paths that end in node 7 in this case, or are you just looking for any path that has nowhere else to go (i.e. ends in a node of outdegree zero)? If the path contains a cycle, do we include paths that go around the cycle before ending?
My guess is that what you're really interested in is the set of all simple paths from a given node that end in a node with outdegree zero. With that in mind, here's some code you might find useful.
start = 1
ends = [n for n in DG.nodes if DG.out_degree[n] == 0]
paths = [p for e in ends
for p in nx.all_simple_paths(DG, source = start, target = e)]
print(paths)
Output: [[1, 2, 4, 5, 6, 7], [1, 2, 3, 6, 7]]
If you want paths that start from 1 and end in any other node, you could do the following.
start = 1
paths = [p for e in DG.nodes
for p in nx.all_simple_paths(DG, source = start, target = e)]
print(paths)
Output: [[1, 2], [1, 2, 4], [1, 2, 3], [1, 2, 4, 5, 6], [1, 2, 3, 6], [1, 2, 4, 5, 6, 7], [1, 2, 3, 6, 7], [1, 2, 4, 5]].
If you like, you can take this output and filter down to the paths that start with any 3 nodes. For example,
print([p for p in paths if p[:3] == [1,2,3]])
print([p for p in paths if p[:3] == [1,2,4]])
results in the outputs [[1, 2, 3], [1, 2, 3, 6], [1, 2, 3, 6, 7]] and [[1, 2, 4], [1, 2, 4, 5, 6], [1, 2, 4, 5, 6, 7], [1, 2, 4, 5]].
Alternatively, sorting paths naturally organizes the paths according to their first nodes. In particular, sorted(paths) is the list
[[1, 2],
[1, 2, 3],
[1, 2, 3, 6],
[1, 2, 3, 6, 7],
[1, 2, 4],
[1, 2, 4, 5],
[1, 2, 4, 5, 6],
[1, 2, 4, 5, 6, 7]]
which you could split into two pieces.
