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); 

グラフは次のようになります。 のみ3 6サイクルのが発見されています

[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] 

iは、次のコードで間違って何をしますか？

#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ですが、は検出されません。これはcombination of these two smaller onesです。 methodを作成して、すべてのサイクルを取得し、それらの間に共通のノードがあるかどうかを確認してから、すべてのノードを結合してunionの新しいサイクルを返すことができます。 {1 and 2}から0からpathは、最初のサイクルである第二サイクルにおける{1 and 2}から3からpathがある場合に[0 -> 1 -> 2 -> 0]と[1 -> 2 -> 3 -> 1]、1と2commonにある両方で、次に間違いpath0からに存在します3も同様である。したがって、returnの2サイクルのunionは、AT LEAST ONE NODEを共通に持つ[0 1 3 2 0]とすることができます。