Boost logo

Boost Users :

Subject: Re: [Boost-users] question regarding Depth First Search algorithm
From: Pablo Fleurquin (pablofleurquin_at_[hidden])
Date: 2011-09-30 02:57:12

Here is the code to eliminate all cycles within a graph, using

#include <boost/config.hpp>
#include <iostream>
#include <vector>
#include <boost/graph/strong_components.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/graph_utility.hpp>

int main()
   using namespace boost;

   int name[9] = {0,1,2,3,4,5,6,7,8};

   typedef adjacency_list < vecS, vecS, directedS > Graph;

   Graph G(9);


   std::cout << "A directed graph with cycles:" << std::endl;
   print_graph(G, name);
   std::cout << std::endl;

   typedef graph_traits<GraphvizGraph>::vertex_descriptor Vertex;
   typedef graph_traits<GraphvizGraph>::vertex_descriptor u;
   typedef graph_traits<GraphvizGraph>::vertex_descriptor v;

   std::vector<int> component(num_vertices(G)),
   std::vector<default_color_type> color(num_vertices(G));
   std::vector<Vertex> root(num_vertices(G));
   int num = strong_components(G, &component[0],

   std::vector<int>::size_type i;
   std::vector<int>::size_type j;

   for(i = 0; i != num_vertices(G); ++i)
      for (j = 0; j != num_vertices(G); ++j)
       if (component[name[i]]==component[name[j]])

   std::cout << "A directed graph without cycles:" << std::endl;
   std::cout << std::endl;

   return 0;

--Pablo Fleurquin

On 09/28/2011 08:11 PM, Jeremiah Willcock wrote:
> On Wed, 28 Sep 2011, Pablo Fleurquin wrote:
>> Hi,
>> I have a question regarding the Depth First Search algorithm. I have
>> been looking at the Boost library page but I'm a newbie with this stuff.
>> Having a directed graph G (that could be a connected graph or not), I
>> want my program to find the cycles within the graph and remove all
>> the edges that are part of them. It doesn't matter which cycle is
>> erased first as long as the result is the graph G without edge that
>> formely were part of a cycle (in other words, the remaining edges are
>> those that doesn´t form cycles) [attached is example1]
>> Intuitively, I am sure that using the depth_first_search() function
>> and recalling it recursively for each "new" graph G "with less"
>> cycles will finally arrive to graph G with no cycles. The problem is
>> that I have the idea, but my knowledge of c++ is not so vast to
>> implement this code.
> I'm not clear on what you're trying to do. Are you trying to remove
> all edges that are in any cycle in the initial graph? Or do you want
> to just remove enough edges to get a graph without any cycles at the
> end? The figures you sent suggest the first case. If you want that,
> one way I'd suggest is to compute the strongly connected components of
> your graph (using boost::strongly_connected_components) and remove any
> edge whose endpoints are in the same component. That will likely give
> you what you want, even handling the case where cycles overlap.
> -- Jeremiah Willcock
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at