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

Subject: Re: [Boost-users] [BGL] Longest path from u to v in a directed weighted graph
From: Murilo Adriano Vasconcelos (muriloufg_at_[hidden])
Date: 2011-04-15 09:42:32

Hi,

2011/4/14 Shaun Jackman <sjackman_at_[hidden]>

> 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,
> Shaun
>
> > > On Wed, 2011-04-13 at 17:21 -0700, Murilo Adriano Vasconcelos wrote:
> > >> 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
> > >>
> > >> Em 13/04/2011, às 21:11, Shaun Jackman <sjackman_at_[hidden]> escreveu:
> > >>
> > >>> 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
> > >
>

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,
-- 
Murilo Adriano Vasconcelos
http://murilo.wordpress.com