Re: [Boost-users] question regarding Depth First Search algorithm

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 
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_at_[hidden]
> http://listarchives.boost.org/mailman/listinfo.cgi/boost-users