Boost logo

Boost :

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
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

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.

--------------- 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; }

  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 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 -----------------------

Boost list run by bdawes at, gregod at, cpdaniel at, john at