Re: Newbie question: how to detect cycles in undirected graph

From: alexanderdz_at_[hidden]
Date: 2001-07-25 03:19:32

Hi Jeremy,

--- In boost_at_y..., Jeremy Siek <jsiek_at_r...> wrote:
> On Tue, 24 Jul 2001 alexanderdz_at_y... wrote:
> >
> > I wrote test program which you can find below and found following
> > problems:
> >
> > A. The depth_first_search algorithm always calls back_edge method 
...
> 
> If you record predecessors you can check if the edge passed to
> back_edge() is really a tree edge. Perhaps this check should be 
> encorporated into depth_first_search(). 

  I would like to. Otherwise it require me to dig to the roots of 
graph theory and implementation of concrete algorithms. Which I was 
lazy to do.

> Anyways, here's how you 
> could change your cycle_detector visitor to do this:
> 
> template <class ParentMap>
> struct cycle_detector : public dfs_visitor<>
...
  Thanks! It works.

> > B. The library quite often brings compiler to its knees. For 
> > example, if you comment the line following "// Internal compiler 
> > error if commented out", VC 6 sp5 fails with internal compiler > 
> > error. ...
> 
> I've tried to avoid as many VC++ internal compiler errors as 
> possible, and have spent a lot of time doing this, but I'm afraid I 
> can't dedicate more time to this. Please report internal compiler 
> errors to the VC++ team.

  I'll do that. Unfortunately, it can't help me. Hope to find the 
workaround next time.

> > C. To got compile error in line B if I pass visitor the way 
> > analogous to line A. To be more precise, I can't write line B 
> > following  way, as I did for line A
> >
> >   vertex_processor proc;
> >   depth_first_visit(g, vertices(g).first[1], visitor(proc), ...
> 
> The reason is that the depth_first_visit() function does not use 
> named template parameters, but just normal template parameters. So 
> it is incorrect to pass visitor(proc) to depth_first_visit().
> 
> http://www.boost.org/libs/graph/doc/depth_first_visit.html

  What is the reason having different interfaces for two closely 
related functions?

  Thank you for your help!

  With best wishes,

  Alexander