Here is the code to eliminate all cycles within a graph, using boost::strongly_connected_components.

#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);
 
  add_edge(0,1,G);
  add_edge(0,2,G);
  add_edge(2,3,G);
  add_edge(2,8,G);
  add_edge(3,5,G);
  add_edge(3,0,G);
  add_edge(4,7,G);
  add_edge(6,5,G);
  add_edge(8,0,G);
 
  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)), discover_time(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],
                              root_map(&root[0]).
                              color_map(&color[0]).
                              discover_time_map(&discover_time[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]])
      {
        remove_edge(name[i],name[j],G);
      }
     }
  }
 
  std::cout << "A directed graph without cycles:" << std::endl;
  print_graph(G,name);
  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@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users