Newbie question: how to detect cycles in undirected graph

From: alexanderdz_at_[hidden]
Date: 2001-07-24 11:17:52

Hi All,

I'm tring to use graph library for the following task:

1. Get from user a new edge(u,v) and its property for undirected 
graph.
2. If edge makes a cycle in the graph, discard it and report error.
3. Add the edge to the graph.
4. If no more edges - do 5.
5. For specified vertex v visit all connected vertices u and modify   
them in accordance with property of edge(u,v)

I wrote test program which you can find below and found following
problems:

A. The depth_first_search algorithm always calls back_edge method of 
visitor. It happens even if graph has two nodes and one edge linking 
them. What is(are) other method(s) of cycle detection?

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. It is 
very disappointing for me. I like this library so much but if I'll 
have it in production code it's killing bug. (Precompiled headers 
and /Gm are off.)

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), ...

   
  Could you please to comment mentioned problems. 

  Thanks in advance.
  Alexander

--------------- CUT HERE ----------------------------
// lot of includes dropped

struct cycle_detector : public dfs_visitor<>
{
  cycle_detector(bool& has_cycle) : _has_cycle(has_cycle) { }

  template <class Edge, class Graph>
    void back_edge(Edge e, Graph& g) { _has_cycle = true; }

protected:
  bool& _has_cycle;
};

struct vertex_processor : public dfs_visitor<>
{
  template <class Vertex, class Graph>		
    void discover_vertex(Vertex u, Graph& g)
    { std::cout << "Discover " << u << "\n";}

  template <class Vertex, class Graph>
    void finish_vertex(Vertex u, Graph& g)
    { std::cout << "      <- " << u << "\n";}

  template <class Edge, class Graph>
    void examine_edge(Edge e, Graph& g)
    { std::cout << " examine edge " << source(e,g) << " "
     << target(e,g) << "\n"; }
};

int main(int argc, char* argv[])
{
  typedef std::pair<int, int> E;
  E edges[] = { E(0,1), E(1,2), E(0,2) };
  const int edges_num = sizeof(edges)/sizeof(edges[0]);

  typedef property<vertex_color_t, default_color_type> VertexProperty;
  typedef adjacency_list<vecS, vecS, undirectedS, VertexProperty >
        Graph;
  Graph g(3, edges, edges + edges_num );

  bool has_cycle = false;

  cycle_detector vis(has_cycle);

  // Line A
  depth_first_search(g, visitor(vis));

  std::cout << "The graph has a cycle now? " << has_cycle << "\n";

  // Internal compiler error if commented out
  typedef property_map<Graph,vertex_color_t>::type Color;

  graph_traits<Graph>::vertex_iterator vi, vi_end;
  for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
    get(vertex_color, g)[*vi] = white_color;

  // Line B
  depth_first_visit(g, vertices(g).first[1], vertex_processor(),
     get(vertex_color, g) );

  return 0;
}
--------------- CUT HERE -----------------------