c++ - undirected_dfs 是否检测图形的所有循环？

Question

undirected_dfs 应该检测无向图的“所有”循环。 我实现了访问者的“back_edge”和“tree_edge”，它只发现了 3 个周期。

图表构建于:

boost::add_vertex(g);  //0
boost::add_vertex(g);   //1
boost::add_vertex(g);   //2
boost::add_vertex(g);   //3
boost::add_vertex(g);   //4

boost::add_edge(0, 1, g);
boost::add_edge(0, 2, g);
boost::add_edge(0, 4, g);
boost::add_edge(1, 2, g);
boost::add_edge(1, 3, g);
boost::add_edge(2, 3, g);
boost::add_edge(2, 4, g);

图表看起来像: 6 个循环中只发现了 3 个:

[0 -> 1 -> 2 -> 0] Discovered
[1 -> 2 -> 3 -> 1] Discovereded
[0 -> 1 -> 2 -> 4 -> 0]Discover
[0 -> 1 -> 3 -> 2 -> 4 -> 0] 
[0 -> 2 -> 4 -> 0]
[0 -> 1 -> 3 -> 2 -> 0]

我在下面的代码中做错了什么？

#include <string>
#include <fstream>
#include <iostream>
#include <stack>  
#include <map>      //pair

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/undirected_dfs.hpp>
#include<boost/graph/properties.hpp>
#include <boost/graph/named_function_params.hpp>            //for named parameter http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/bgl_named_params.html
#include <boost/cstdlib.hpp>                                                    // for exit_success;
#include <boost/utility.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/cstdlib.hpp>
#include <boost/numeric/conversion/cast.hpp>
#include <boost/graph/graphviz.hpp>





//template du graph http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/adjacency_list.html
typedef boost::adjacency_list<
    boost::vecS,                                //OutEdgeList
    boost::vecS,                                //VertexList
    boost::undirectedS                  //Directed
> Graph;

typedef boost::graph_traits < Graph >::vertex_descriptor Vertex;
typedef boost::graph_traits < Graph >::edge_descriptor Edge;



struct detect_loops : public boost::dfs_visitor<>
{
    using colormap = std::map<Graph::vertex_descriptor, boost::default_color_type>;
    colormap vertex_coloring;

    using edgeColorMap = std::map<Graph::edge_descriptor, boost::default_color_type>;
    edgeColorMap  edge_coloring;

    template <class Graph>
    void tree_edge(Edge e, const Graph& g) {
        std::cout << "tree_edge: " << boost::source(e, g) << " --> " << boost::target(e, g) << std::endl;

        edgeVisited.push(e);
        if (vertexVisited.empty()) {
            vertexVisited.push(boost::source(e, g));
        }
        vertexVisited.push(boost::target(e, g));
    }

    template <class Graph>
    void back_edge(Edge e, const Graph& g) {
        Vertex v2;

        std::cout << " Cycle detected with back-edge= " << e << std::endl;
        std::cout << " vertexVisited size= " << vertexVisited.size() << std::endl;

        std::cout << "Cycle end= " << boost::target(e, g) << std::endl;
        //std::cout << "vertexVisited.top= " << vertexVisited.top() << std::endl;
        while ( vertexVisited.top() != boost::target(e, g) )
        {
            std::cout << " Cycle middle=" << vertexVisited.top() << std::endl;
            v2 = vertexVisited.top();
            vertexVisited.pop();
        }
        std::cout << "Cycle starting= " << vertexVisited.top() << std::endl;
        vertexVisited.push(v2);
    }

    //interface to the main.
    std::vector<Vertex> GetCycles() const { return Cycle; }

private:
    std::vector<Vertex> Cycle;

    //std::stack<Edge> visited;
    std::stack<Edge> edgeVisited;
    std::stack<Vertex> vertexVisited;
};

Graph make(Graph &g)
{
    boost::add_vertex(g);  //0
    boost::add_vertex(g);   //1
    boost::add_vertex(g);   //2
    boost::add_vertex(g);   //3
    boost::add_vertex(g);   //4

    boost::add_edge(0, 1, g);
    boost::add_edge(0, 2, g);
    boost::add_edge(0, 4, g);
    boost::add_edge(1, 2, g);
    boost::add_edge(1, 3, g);
    boost::add_edge(2, 3, g);
    boost::add_edge(2, 4, g);

    std::ofstream f("d:\\tmp\\dot\\s13.dot");
    boost::write_graphviz(f, g);
    std::system(  std::string("dot -Tsvg -Grankdir=LR -Nfontsize=24 d:\\tmp\\dot\\s13.dot > d:\\tmp\\dot\\s13.svg").c_str() );
return g;
}

//---------------------------------------------------------
//---------------------------------------------------------
int main()
{
    Graph g;
    detect_loops vis;

    make(g);

    std::ofstream f("d:\\tmp\\s13.dot"); 
    boost::write_graphviz(f, g);
    std::system(
        std::string("dot -Tsvg -Grankdir=LR -Nfontsize=24 d:\\tmp\\s13.dot > d:\\tmp\\s13.svg").c_str()
        );

    boost::undirected_dfs(g, vis, make_assoc_property_map(vis.vertex_coloring), make_assoc_property_map(vis.edge_coloring));
    std::vector<Vertex> vctr = vis.GetCycles();

    return boost::exit_success;
}

Answer 1

首先，请注意任何较大尺寸的循环都可能由较小尺寸的循环组成。对于您的情况，可以正确检测到较小尺寸的周期。例如，[0 -> 1 -> 2 -> 0] 和 [1 -> 2 -> 3 -> 1] 都是 Discovered 但未检测到 [0 1 3 2 0]，这是 这两个较小的组合。您可以简单地创建一个 method 获取所有循环并检查它们之间是否有任何共同节点，然后它组合所有节点并返回 union 新循环。在 [0 -> 1 -> 2 -> 0] 和 [1 -> 2 -> 3 -> 1] 中，1和 2 在 common 中，所以如果存在从 0 到 {1 和 2 的 path } 在第一个循环中，并且在第二个循环中有从 3 到 {1 and 2} 的路径，然后有绝对是从0 到3 的路径。所以它可以返回两个循环的union作为[0 1 3 2 0]，它有AT LEAST ONE NODE共同点。