 # 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
boost::strongly_connected_components.

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

int main()
{
using namespace boost;

int name = {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)),
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,
root_map(&root).
color_map(&color).
discover_time_map(&discover_time));

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]