[Boost-users] Longest path from u to v in a directed weighted graph

[Shaun Jackman]

Hi,

I would like to find the longest path from vertex u to vertex v through
a directed graph with positive edge weights. I know that u and v are
choke points in the graph, in that if you start from vertex u and start
following random edges, you will end up at vertex v in pretty short
order. Is dijkstra_shortest_paths the best function for this purpose?

The vertices reachable from u without travelling through v form a small
subgraph of the total graph. I want to avoid exploring beyond v, and I
definitely don't need to know the distances to vertices beyond v.

Cheers,
Shaun

_______________________________________________
Boost-users mailing list
Boost...@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Murilo Adriano Vasconcelos]

The graph is a DAG? If not, that is a NP-Complete problem and Dijkstra wouldn't help you.

Regards,

Murilo Adriano Vasconcelos
http://murilo.wordpress.com

[Shaun Jackman]

Hi Murilo,

The subgraph between u and v is a DAG — that is the subgraph reachable
from u without travelling through v. The rest of the graph is not
acyclic.

Cheers,
Shaun

[Jeremiah Willcock]

On Thu, 14 Apr 2011, Shaun Jackman wrote:

> Hi Murilo,
>
> The subgraph between u and v is a DAG — that is the subgraph reachable
> from u without travelling through v. The rest of the graph is not
> acyclic.

In that case, there is a dag_shortest_paths algorithm that you can use
(negating the edge weights). You might need to use filtered_graph (with a
prior BFS) to isolate the part of the graph between u and v, or a visitor
in the shortest path algorithm might work instead.

-- Jeremiah Willcock

[Richard Damon]

On 4/13/11 8:11 PM, Shaun Jackman wrote:
> Hi,
>
> I would like to find the longest path from vertex u to vertex v through
> a directed graph with positive edge weights. I know that u and v are
> choke points in the graph, in that if you start from vertex u and start
> following random edges, you will end up at vertex v in pretty short
> order. Is dijkstra_shortest_paths the best function for this purpose?
>
> The vertices reachable from u without travelling through v form a small
> subgraph of the total graph. I want to avoid exploring beyond v, and I
> definitely don't need to know the distances to vertices beyond v.
>
> Cheers,
> Shaun
>

Thinking about this a bit, to find the LONGEST length will by necessity
require every path, because there is no way to trim a set of paths and
say they can't be longer then the current longest. Shortest finding
algorithms can trim the search space since once you get from u to a in
distance d, once your current path is bigger than d you don't need to
check going through a anymore.

Since you say it forms a small DAG, a quick depth first search, keeping
track of the longest path may be best.

--
Richard Damon

[Shaun Jackman]

On Thu, 2011-04-14 at 13:15 -0700, Jeremiah Willcock wrote:
> On Thu, 14 Apr 2011, Shaun Jackman wrote:
>
> > Hi Murilo,
> >
> > The subgraph between u and v is a DAG — that is the subgraph reachable
> > from u without travelling through v. The rest of the graph is not
> > acyclic.
>
> In that case, there is a dag_shortest_paths algorithm that you can use
> (negating the edge weights). You might need to use filtered_graph (with a
> prior BFS) to isolate the part of the graph between u and v, or a visitor
> in the shortest path algorithm might work instead.

Hi Jeremiah,

dag_shortest_paths looks promising. It starts by computing a topological
ordering of the graph, and in fact I already have a topological ordering
of the subgraph in which I'm interested. So, it looks as though I'll
just use the algorithm that computes the longest path from the
topological ordering. It would be nice if this algorithm were factored
so that a user could provide a topological ordering as a parameter.

Thanks,

[Murilo Adriano Vasconcelos]

Hi,

2011/4/14 Shaun Jackman <sjac...@bcgsc.ca>

If you already have a topological ordering of your subgraph, you only need to do one DFS to find the longest path. You can just do a DFS starting from the vertex with in-degree 0 (the root of topological tree) (if your subgraph is not connected, you'll need to do a DFS from each vertex with in-degree 0) and save the maximum depth you find.

Regards,
--