Message Boards Message Boards

1
|
11628 Views
|
8 Replies
|
2 Total Likes
View groups...
Share
Share this post:

Finding Longest Path in a Directed Graph

Pat Dillon
Posted 11 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?
POSTED BY: Pat Dillon
8 Replies
Sort By:

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 BY: Szabolcs Horvát

Hi @Szabolcs, for:

g = Graph[{1 -> 2, 2 -> 3, 3 -> 2, 2 -> 1}]

{{{2-> 3, 3 -> 2}, {1-> 2, 2->1}}}
POSTED BY: Rodrigo Murta

That was really a question to the OP, to make sure we're on the same page. There could be other interpretations.
POSTED BY: Szabolcs Horvát

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 BY: Rodrigo Murta

Though it goes along many points, it is not necessarily the longest right?
POSTED BY: Sander Huisman

Hi @Sander, you can easily count it, and retrieve it using MaximalBy. FindCycle will show all of then.
POSTED BY: Rodrigo Murta
Bill Simpson
Bill Simpson
Posted 11 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 BY: Bill Simpson

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
POSTED BY: Sander Huisman
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Tag limit exceeded
Note: Only the first five people you tag will receive an email notification; the other tagged names will appear as links to their profiles.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract