Finding Longest Path in a Directed Graph

Questions
,
1

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?

2

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: Longest path problem - Wikipedia

3

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.

4

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,{}]
5

Though it goes along many points, it is not necessarily the longest right?

6

Hi @Sander, you can easily count it, and retrieve it using MaximalBy. FindCycle will show all of then.

7

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}]
8

Hi @Szabolcs, for:

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

{{{2-> 3, 3 → 2}, {1-> 2, 2->1}}}

9

That was really a question to the OP, to make sure we’re on the same page. There could be other interpretations.