
Boost Users : 
Subject: Re: [Boostusers] question regarding Depth First Search algorithm
From: Pablo Fleurquin (pablofleurquin_at_[hidden])
Date: 20110930 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
>
>
> _______________________________________________
> Boostusers mailing list
> Boostusers_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boostusers
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net