Re: [Boost-users] Confused with Depth-First-Search method, forwardor cross edge found on a undirected graph ?

Subject: Re: [Boost-users] Confused with Depth-First-Search method, forwardor cross edge found on a undirected graph ?
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2013-06-25 15:27:58

On Tue, 25 Jun 2013, lizy10b wrote:

> Hi Jeremiah Willcock,
> Thanks for your reply.
> Another question is the vertex color property also required in undirected_dfs()? or only edge color property is enough?
> Thanks.

There vertex colors are required to know which vertices have already been 
visited; directing each edge is not enough to keep track of that.

-- Jeremiah Willcock
> Â 
> Â 
> 2013-06-25
> 
> _________________________________________________________________________________________________________________________________________________________
> lizy10b
> 
> _________________________________________________________________________________________________________________________________________________________
> 发件人： Jeremiah Willcock
> 发送时间： 2013-06-25  00:44:05
> 收件人： lizy10b
> 抄送： boost-users
> 主题： Re: Re: [Boost-users] Confused with Depth-First-Search method,forwardor cross edge found on a undirected graph ?
> On Tue, 25 Jun 2013, lizy10b wrote:
> > Hi Jeremiah Willcock ,
> >Â ?
> > It seems undirected_dfs() works. I have not燾heck the result according to the graph, but at least there is no
> > forward edge or cross edge output.
> > Attached is the revised cpp file using undirected_dfs() .
> > My question is why edge_color_map(get(edge_color,爂))?is required when calling the undirected_dfs() .
> >Â Thanks
> It looks like what is going wrong with using directed DFS is that edges 
> are examined twice (once in each direction), and so you can have forward 
> edges even in a symmetric graph (which is how undirected graphs are 
> treated in directed-graph algorithms in BGL).  An example is the triangle 
> 0 -- 1 -- 2 -- 0: starting at 0 and processing the edges out of a vertex 
> in numerical order, 0 -> 1 is a tree edge, 1 -> 0 is a back edge, 1 -> 2 
> is a tree edge, 2 -> 0 is a back edge, 2 -> 1 is a back edge, then 0 -> 2 
> is a forward edge.  An undirected DFS would mark 2 -> 0 as a back edge 
> then ignore 0 -> 2 since it is the same as 2 -> 0.  The edge colors in 
> undirected_dfs are used to do this filtering-out of multiple directions 
> for the same edge.
> -- Jeremiah Willcock
> 
>