S
S
stayHARD2016-07-26 05:30:47
Python
stayHARD, 2016-07-26 05:30:47

How to find the longest path/path_length in a graph?

Good morning Toaster.
I'm writing a script that uses network - https://networkx.readthedocs.io/
All input data is enclosed in a file. I figured out how to solve all typical tasks, such as building a graph, finding a short path, but I can’t find how to calculate the longest path in a graph.
The input data is for example:
Graph:

N1,N8
N2,N6
N3,N7,N1
N4,N2
N5,N8
N7,N2,N5,N4
N8,N7,N4

Search:
N1, *
In this case, I want to get:
N1,N8,N4,N2,N6 и N1,N8,N7,N2,N6
and actually path_length = 4
That is, you need to find the farthest node from N1 and pave the way to it + calculate the length.
Interested in a solution exclusively with networkx, the rest of the functionality is already written on it.
UPD
all_paths = []
for node in G:
    all_paths.extend(find_paths(G, node, 6))
print all_paths

The above code finds all the paths, for each node in the graph, where the path length is 6.
Recall that I want to find the longest path(s) from a particular node.
Thanks in advance.

Answer the question

In order to leave comments, you need to log in

1 answer(s)
S
sim3x, 2016-07-26
@sim3x

https://networkx.readthedocs.io/en/stable/referenc...
https://networkx.readthedocs.io/en/stable/referenc...

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question