Here is the code to eliminate all cycles within a graph, using boost::strongly_connected_components. #include #include <iostream> #include <vector> #include #include #include #include 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 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

on Fri Sep 30 2011, Pablo Fleurquin wrote:

I have an adjacency list, representing a directed graph, written in standard c++ format using vector: vector I want to tranform it to boost adjacency_list< > format and then back to vector .

Which is the simplest way to do it?

Are you *sure* that's what you want to do? The usual thing to do in cases like this is to write the necessary functions and traits so your type conforms to the graph concept needed for your algorithms. (In fact I think vector may already conform, but I could be mistaken). -- Dave Abrahams BoostPro Computing http://www.boostpro.com

On Fri, 30 Sep 2011, Pablo Fleurquin wrote:

Yes,

The thing is I have a whole code that uses vector and I only need one function from boost library, but this function wont work with vector.

Changing the script to boost sintax will be time consuming because I´m a newbie. So what are my options?

I agree with Dave's suggestion: write wrappers to make a vector into a Boost graph, modeling whichever concepts your particular algorithm needs. Which algorithm do you want to use? You can look at its requirements and see what functions you need to implement in order to use it. -- Jeremiah Willcock

2011/9/30 Dave Abrahams

on Fri Sep 30 2011, Pablo Fleurquin wrote:

...

I have an adjacency list, representing a directed graph, written in standard c++ format using vector: vector I want to tranform it to boost adjacency_list< > format and then back to vector .

Which is the simplest way to do it?

Are you *sure* that's what you want to do?

The usual thing to do in cases like this is to write the necessary functions and traits so your type conforms to the graph concept needed for your algorithms.  (In fact I think vector may already conform, but I could be mistaken).

-- Dave Abrahams BoostPro Computing http://www.boostpro.com

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

On Fri, 30 Sep 2011, Pablo Fleurquin wrote:

Ok, but can you give me a hint, how to write a wrap for this?The function I use is boost::strong_connected_component

Look at the documentation page for that algorithm; there is a list of concepts it requires its graph type to model, with links to individual documentation pages for those. Those pages will list which functions you need to implement and how they are supposed to behave. You will also need a graph_traits specialization; the documentation pages will also say what that should look like. -- Jeremiah Willcock

2011/9/30 Jeremiah Willcock On Fri, 30 Sep 2011, Pablo Fleurquin wrote:

Yes,

The thing is I have a whole code that uses vector and I only need one function from boost library, but this function wont work with vector.

Changing the script to boost sintax will be time consuming because I´m a newbie. So what are my options?

I agree with Dave's suggestion: write wrappers to make a vector into a Boost graph, modeling whichever concepts your particular algorithm needs.  Which algorithm do you want to use?  You can look at its requirements and see what functions you need to implement in order to use it.

-- Jeremiah Willcock

2011/9/30 Dave Abrahams

on Fri Sep 30 2011, Pablo Fleurquin wrote:

> I have an adjacency list, representing a directed graph, written in > standard c++ format using vector: vector I want to > tranform it to boost adjacency_list< > format and then back to vector > . > > Which is the simplest way to do it?

Are you *sure* that's what you want to do?

The usual thing to do in cases like this is to write the necessary functions and traits so your type conforms to the graph concept needed for your algorithms.  (In fact I think vector may already conform, but I could be mistaken).

-- Dave Abrahams BoostPro Computing http://www.boostpro.com

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

2011/9/30 Dave Abrahams

on Fri Sep 30 2011, Jeremiah Willcock wrote:

...

On Fri, 30 Sep 2011, Pablo Fleurquin wrote:

...

Ok, but can you give me a hint, how to write a wrap for this?The function I use is boost::strong_connected_component

Look at the documentation page for that algorithm; there is a list of concepts it requires its graph type to model, with links to individual documentation pages for those. Those pages will list which functions you need to implement and how they are supposed to behave. You will also need a graph_traits specialization; the documentation pages will also say what that should look like.

Jeremiah, I could have _sworn_ there was built-in support to make std::vector's usable directly as graphs. Am I mis-remembering? Was it removed?

*Dave, that would be great, the built in support is still there? I tried to follow what Jeremiah told me but it is too advance for me. In future I will be able to do so but I need this done now because I do not have time to deepen these days. I want this code to be written using boost so I start to get used to it. THANKS! *

_______________________________________________

Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

On Sat, 1 Oct 2011, Dave Abrahams wrote:

on Sat Oct 01 2011, Pablo Fleurquin wrote:

...

on Fri Sep 30 2011, Jeremiah Willcock wrote:

...

...

On Fri, 30 Sep 2011, Pablo Fleurquin wrote:

...

Ok, but can you give me a hint, how to write a wrap for this? The function I use is boost::strong_connected_component

Look at the documentation page for that algorithm; there is a list of concepts it requires its graph type to model, with links to individual documentation pages for those.  Those pages will list which functions you need to implement and how they are supposed to behave.  You will also need a graph_traits specialization; the documentation pages will also say what that should look like.

Jeremiah, I could have _sworn_ there was built-in support to make std::vector's usable directly as graphs.  Am I mis-remembering?  Was it removed?

Dave, that would be great, the built in support is still there? I tried to follow what Jeremiah told me but it is too advance for me. In future I will be able to do so but I need this done now because I do not have time to deepen these days. I want this code to be written using boost so I start to get used to it. THANKS! 

Well, it's not documented :(, but it's all in this header: http://www.boost.org/doc/libs/1_47_0/boost/graph/vector_as_graph.hpp You might also read http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/leda_conversion.html which should guide you through the principles that are implemented by that header (but for a different graph type).

There are also files libs/graph/example/vector-as-graph.cpp and libs/graph/example/filtered_vec_as_graph.cpp that show simple uses of vector_as_graph. -- Jeremiah Willcock