Re: [Boost-users] Traversing a graph

Subject: Re: [Boost-users] Traversing a graph
From: Vipin Varma (varma_at_[hidden])
Date: 2011-03-23 06:38:03

Thanks for the reply. Shortest-path, in my context, refers to a path, 
minimum in length 
but not necessarily Eulerian, that starts at a given vertex v_s and ends 
in a different vertex v_d, such that all edges are visited at least once. 
Therefore in graphs with loops this shortest path will necessarily be 
greater than the number of edges.

I found a method of getting such a minimum path length. Essentially a 
virtual edge has to be added 
between v_s and v_d; then relabel these two vertices as odd/even 
taking into account the virtual edge as well. Finally solve the 
chinese-postman-problem on 
the original graph (without the virtual edge) but with the new 
relabellings of odd/even vertices.

On Wed, 23 Mar 2011, Jeremiah Willcock wrote:

> On Mon, 21 Mar 2011, Vipin Varma wrote:
>
>> Hi,
>> 
>> I have a quick question about graph traversal: what is the appropriate 
>> algorithm to be used if I want to find the shortest distance between 2 
>> specified vertices {v_s, v_d} such that every edge on the graph is 
>> traversed at least once? I've already used the breadth_first_search() and 
>> dijkstras_shortest_paths() for other problems wherein v_s = v_d. Seemingly, 
>> these algorithms cannot be used when the source and destination vertices 
>> are dissimilar.
>
> What do you mean by "shortest path" in this context?  Every path that meets 
> the criteria you describe will have exactly |E| edges, where E is the edge 
> set of the graph.  I looked at the Wikipedia page on Eulerian tours, and they 
> show two separate algorithms; which one are you using? Cycle-finding?  In 
> that case, I would recommend DFS since it is likely to use less memory than 
> BFS and they are equally good at finding cycles.
>
> -- Jeremiah Willcock
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>