CODEWITHSUNDEEP
c++boostboost-graph
alvaro562003
alvaro562003

Reputation: 698

Does undirected_dfs detect all cycle of graph?

undirected_dfs is supposed to detect "all" cycles of an undirected graph. I implement the "back_edge" and "tree_edge" of the visitor and it found only 3 cycles.

The graph is built with:

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

The graph looks like:enter image description here Only 3 of the 6 cycles are discovered:

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

What do i do wrong in the following code?

#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;
}

Upvotes: 1

Views: 518

Answers (1)

USC.Trojan
USC.Trojan

Reputation: 401

First, notice that any bigger size cycle might be consisted of smaller size cycles. For your case, the smaller size cycles are detected properly. As an example, both [0 -> 1 -> 2 -> 0] and [1 -> 2 -> 3 -> 1] are Discovered but [0 1 3 2 0] is not detected which is the combination of these two smaller ones. You can simply create a method which gets all your cycles and checks if there is any node in common between them, then it combines all the nodes and returns the union new cycle. In both [0 -> 1 -> 2 -> 0] and [1 -> 2 -> 3 -> 1], 1 and 2 are in common, so if there is a path from 0 to {1 and 2} in the first cycle and there is a path from 3 to {1 and 2} in the second cycle, then there is definitely a path from 0 to 3 as well. So it can return the union of the two cycles as [0 1 3 2 0] that has AT LEAST ONE NODE in common.

Upvotes: 2

Related Questions