I need to find a longest path in an unweighted graph from s to t.
I am using NetworkX, which has an algorithm for finding a longest path in a directed, acyclic graph, but I am not able to specify the source and the target nodes.
I have not been able to find any info online, but it seems like such an obvious algorithm to have laying around. Is there any way I can do this?
"[T]he longest path problem is the problem of finding a simple path of maximum length in a given graph."[1]
NetworkX has a simple_paths
module, that contains the function all_simple_paths.
Below is one solution for finding the longest simple paths between two nodes.
from typing import List
import networkx as nx
def longest_simple_paths(graph, source, target) -> List[List]:
longest_paths = []
longest_path_length = 0
for path in nx.all_simple_paths(G, source=source, target=target):
if len(path) > longest_path_length:
longest_path_length = len(path)
longest_paths.clear()
longest_paths.append(path)
elif len(path) == longest_path_length:
longest_paths.append(path)
return longest_paths
G = nx.complete_graph(4)
longest_paths = longest_simple_paths(G, source=0, target=3)
if longest_paths:
print(f"Longest simple path contains {len(longest_paths[0])} nodes")
print(longest_paths)
Longest simple path contains 4 nodes
[[0, 1, 2, 3], [0, 2, 1, 3]]
[1] Wikipedia contributors. "Longest path problem." Wikipedia, The Free Encyclopedia. Available from: https://en.wikipedia.org/wiki/Longest_path_problem. Accessed 8 November 2020.