Thanks Vladimir.
I'm not sure that I've followed well your description. Here is my test
implementation... but it doesn't work.
Please, could you help me to discover the problem?
Thanks in advance,
Giulio
typedef adjacency_list MyGraph;
typedef graph_traits<MyGraph>::vertex_descriptor Vertex;
struct CycleDetector : public dfs_visitor<>
{
CycleDetector(std::vector<Vertex> p,
std::vector<Vertex>& _cycle) :
m_predecessor(p), cycle(_cycle) { }
template
void back_edge(Edge e, Graph& g)
{
Vertex t = target(e, g);
Vertex c = source(e, g);
cycle.push_back(c);
do {
c = m_predecessor[c];
cycle.push_back(c);
} while(c != t);
}
protected:
std::vector<Vertex>& cycle;
std::vector<Vertex> m_predecessor;
};
int main(int,char*[])
{
typedef std::pair 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(3,4));
edges.push_back(Edge(4,0));
MyGraph g(edges.begin(), edges.end(), 5);
std::vector<Vertex> cycle;
std::vector<Vertex> p(num_vertices(g));
CycleDetector vis(p, cycle);
depth_first_search(g, visitor(vis));
for (int i=0; i
something like this?
template
void back_edge(Edge e, Graph& g) {
clinks.push_back(TLink(source(e, g), target(e, g)));
}
where:
typedef std::pair TLink;
vector<TLink> clinks;
Something more like:
struct vis
{
vis(vector_property_map<int> predecessor)
: m_predecessor(predecessor) {}
template<......>
void back_edge(Edge e, Graph& g)
{
vertex_descriptor t = target(e, g);
vertex_description c = source(e, g);
vector cycle;
cycle.push_back(c);
do {
c = m_predecessor[c];
cycle.push_back(c);
} while(c != t);
}
};
On construction, you need to pass the same vector_property_map both to the
visitor and the depth_first_search algorithm.
Yes, this is untested code, sorry :-(
- Volodya
