1
|
10637 Views
|
8 Replies
|
2 Total Likes
View groups...
Share
GROUPS:

# Finding Longest Path in a Directed Graph

Posted 10 years ago
 I have a large, directed, cyclic graph on Mathematica and would like to find the longest path in the entire graph. The graph has numerous separate trees and four total cycles. The cycles in the graph are very small and consist of no more than three nodes each, so I could break the cycles and only lose a marginal amount of accuracy. Is there a way to find the longest path between any two nodes in the graph? A sample of the graph looks like this: {File2 -> File13452,File1 -> File2126, File12 -> File1006, File2788-> File94431, File4 -> File4431, File4 -> File98 ... } with tens of thousands of edges and thousands of weakly connected components. Is there some way Mathematica can find the longest path in a cyclic or acyclic directed graph?
8 Replies
Sort By:
Posted 10 years ago
 What is your definition of path? I'm asking because the terminology is not always used consistently.As an example, what is the answer for this graph? Graph[{1 -> 2, 2 -> 3, 3 -> 2, 2 -> 1}] 
Posted 10 years ago
 Hi @Szabolcs, for: g = Graph[{1 -> 2, 2 -> 3, 3 -> 2, 2 -> 1}]  {{{2-> 3, 3 -> 2}, {1-> 2, 2->1}}}
Posted 10 years ago
 That was really a question to the OP, to make sure we're on the same page. There could be other interpretations.
Posted 10 years ago
 In Mathematica 10 we have the new FindCycle function. Maybe something like this could help: g=Graph[myList]; sg=Subgraph[g,#]&/@WeaklyConnectedComponents[g]; DeleteCases[FindCycle[#,?,?]&/@sg,{}] 
Posted 10 years ago
 Though it goes along many points, it is not necessarily the longest right?
Posted 10 years ago
 Hi @Sander, you can easily count it, and retrieve it using MaximalBy. FindCycle will show all of then.
Posted 10 years ago
 In the old Combinatorica package, documented in "Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica" by Pemmaraju and Skiena, on page 332 they construct the Eccentricity of a vertex as the length of the longest shortest path from a vertex v to any other vertex. They then construct the Diameter as the Max of Eccentricity over all verticies v. Perhaps you can study these and adapt them to your task. << Combinatorica and then ?? Diameter and ?? Eccentricity `I don't know how well this is going to apply to a problem with tens of thousands of verticies and edges.If you are going to do anything substantial with graphs then I'd start with the book. Surprisingly, there are still used copies available that the book vultures have not snapped up and now want a thousand dollars for.
Posted 10 years ago
 I'm pretty sure there is no easy function that can compute the longest path in a graph. And I'm not aware of a function in Mathematica that can help you? Also you should should tell us if you are allowed to 're-use' vertices; can a point be revisited if there are multiple paths going there?Read also more: http://en.wikipedia.org/wiki/Longest_path_problem