Group Abstract Group Abstract

Message Boards Message Boards

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

Finding Longest Path in a Directed Graph

Pat Dillon
Posted 12 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 12 years ago
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