
Boost : 
From: alexanderdz_at_[hidden]
Date: 20010724 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 
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk