2

What I need is to store all the edges OR vertices that make a cycle found on a graph. After two days of search on web, the closer that I got is the code that is not working:

struct CycleDetector : public dfs_visitor<> {
CycleDetector(std::vector<Vertex> p, std::vector<Vertex>& _cycle) : m_predecessor(p), cycle(_cycle)  { }

void back_edge(Edge e, Graph const& g)
{
    Vertex t = target(e, g);
    Vertex c = source(e, g);

    std::cout << "(" << t << "," << c << ")" << std::endl;
    std::cout << "Predecessor: " << m_predecessor[c] << std::endl;

    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()
{

//after a routine to create the graph and add_edges

std::vector<Vertex> cycle;
std::vector<Vertex> p(num_vertices(g1));
CycleDetector vis(p, cycle);

depth_first_search(g1, visitor(vis));

for (int i=0; i<cycle.size(); i++)
  std::cout << cycle[i] << ", ";
std::cout << std::endl;

Here is the output of the program. It's a spanning tree with max degree 2. I'm adding an edge on E and H vertices, to proposely create a cycle. I need to detect this cycle and return all the vertices or edges that form it.

Thanks.

Output of the program

4

1 回答 1

1

经过大量搜索和尝试，我想我得到了我需要的东西。我创建了一个地图以将每个节点的父节点存储在深度优先搜索中。对于每个 tree_edge，我存储节点及其父节点。当调用 back_edge 时，我可以检测到一个循环，然后遍历父节点的映射。

我希望它可以帮助

struct MyVisitor : default_dfs_visitor {
MyVisitor(EdgeSet& tree_edges, std::vector<Vertex>& _cycle) : tree_edges(tree_edges), cycle(_cycle) {}

void tree_edge(Edge e, const Graph& g) {
    std::cerr << "tree_edge " << e << std::endl;
    tree_edges.insert(e);
    Vertex t = target(e, g);
    Vertex c = source(e, g);
    m_predecessor[t] = c;


}
void back_edge(Edge e, const Graph& g) {
    if (tree_edges.find(e) == tree_edges.end()) {
        std::cerr << "back_edge " << e << std::endl;
        Vertex t = target(e, g);
        Vertex c = source(e, g);

        std::cout << "(" << name[t] << "," << name[c] << ")" << std::endl;

        cycle.push_back(c);
        do {
        c = m_predecessor[c];
        cycle.push_back(c);
        } while(c != t);
    }
}

private: 
   EdgeSet& tree_edges;
public:
   std::vector<Vertex>& cycle;
   map<Vertex, Vertex> m_predecessor;
};

int main() {

//routine that add the edges and other things

EdgeSet tree_edges;

std::vector<Vertex> cycle;
MyVisitor vis(tree_edges, cycle);
depth_first_search(g1, visitor(vis));

for (int i=0; i<cycle.size(); i++)
  std::cout << cycle[i] << ", ";
std::cout << std::endl;

谢谢！

于 2015-11-16T17:24:05.967 回答