Re: [Boost-users] Identify cycles in a undirected graph

Subject: Re: [Boost-users] Identify cycles in a undirected graph
From: ddboy40 (ddboy40_at_[hidden])
Date: 2012-03-08 19:25:45

Sorry for the Doble posting,
wast'nt yet register to the mailing list.
Cheers!

hi Folks, I've played around with the following example:

struct detect_loops : public boost::dfs_visitor<>
{
template <class Edge, class Graph>
void back_edge(Edge e, const Graph& g) {
    std::cout << source(e, g)
        << " -- "
        << target(e, g) << "\n";
}
};

int main(int,char*[]) {

typedef std::pair<int,int> Edge;
std::vector<Edge> edges;
edges.push_back(Edge(0,1));
edges.push_back(Edge(1,2));
edges.push_back(Edge(2,3));
edges.push_back(Edge(3,1));
edges.push_back(Edge(4,5));
edges.push_back(Edge(5,0));
edges.push_back(Edge(4,0));
edges.push_back(Edge(5,6));
edges.push_back(Edge(2,6));

typedef adjacency_list< vecS, vecS, undirectedS,
    no_property,
    property<edge_color_t, default_color_type> > graph_t;
 typedef graph_traits<graph_t>::vertex_descriptor vertex_t;

graph_t g(edges.begin(), edges.end(), 7);

std::cout << "back edges:\n";
detect_loops vis;
undirected_dfs(g,
root_vertex(vertex_t(0)).visitor(vis).edge_color_map(get(edge_color, g)));
std::cout << std::endl;

return 0;
}

However, I donot know how and where to place the predeccesor recorder.
Secondly, I actually need but all the cycles, i.e. these may not have only
distinct verterces. i.e some vertices may occur repeated in certain circles.
My example above has 3 distinct cycles I guess and thats wha t the the
back_edge() gives. But, I'll like to have all the hamiltonian cycles (hope
they call it like that ;)). Thanks in advance for the tipps.
Daniel 

--
View this message in context: http://boost.2283326.n4.nabble.com/Identify-cycles-in-a-undirected-graph-tp4370333p4458142.html
Sent from the Boost - Users mailing list archive at Nabble.com.