Re: [Boost-users] Traversing a graph

Subject: Re: [Boost-users] Traversing a graph
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2011-03-23 06:07:02

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