question regarding Depth First Search algorithm
Hi, My name is Pablo Fleurquin.I am a student of M.Sc in Physics at the UIB (Palma de Mallorca, Spain) and I'm also working in the IFISC institute (Institute for Interdisciplinary Science and Complex Systems). I have a question regarding the Depth First Search algorithm. Ihave beenlooking 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 would be gratefully, if you could show me a code for this implementation or a function that does that. Thank you. Pablo Fleurquin P.S: Example 2 is a situation that might happen. If the code can be implemented to eliminate these 2 cycles that share a link it would be greate, if not it will work fine as well.
On Wed, 28 Sep 2011, Pablo Fleurquin wrote:
Hi,
My name is Pablo Fleurquin. I am a student of M.Sc in Physics at the UIB (Palma de Mallorca, Spain) and I'm also working in the IFISC institute (Institute for Interdisciplinary Science and Complex Systems).
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
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
I have an adjacency list, representing a directed graph, written in standard c++ format using vector: *vector<vector<int> >* I want to tranform it to boost *adjacency_list< >* format and then back to *vector<vector<int> >*. Which is the simplest way to do it? Thanks.
on Fri Sep 30 2011, Pablo Fleurquin <pablofleurquin-AT-gmail.com> wrote:
I have an adjacency list, representing a directed graph, written in standard c++ format using vector: vector<vector<int> > I want to tranform it to boost adjacency_list< > format and then back to vector <vector<int> >.
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<vector<int> > may already conform, but I could be mistaken). -- Dave Abrahams BoostPro Computing http://www.boostpro.com
Yes, The thing is I have a whole code that uses vector<vector<int> > and I only need one function from boost library, but this function wont work with vector<vector<int> >. Changing the script to boost sintax will be time consuming because I´m a newbie. So what are my options? 2011/9/30 Dave Abrahams <dave@boostpro.com>
on Fri Sep 30 2011, Pablo Fleurquin <pablofleurquin-AT-gmail.com> wrote:
I have an adjacency list, representing a directed graph, written in standard c++ format using vector: vector<vector<int> > I want to tranform it to boost adjacency_list< > format and then back to vector <vector<int> >.
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<vector<int> > 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:
Yes,
The thing is I have a whole code that uses vector<vector<int> > and I only need one function from boost library, but this function wont work with vector<vector<int> >.
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<vector<int> > 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 <dave@boostpro.com>
on Fri Sep 30 2011, Pablo Fleurquin <pablofleurquin-AT-gmail.com> wrote:
I have an adjacency list, representing a directed graph, written in standard c++ format using vector: vector<vector<int> > I want to tranform it to boost adjacency_list< > format and then back to vector <vector<int> >.
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<vector<int> > 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
Ok, but can you give me a hint, how to write a wrap for this? The function I use is boost::strong_connected_component Thanks. 2011/9/30 Jeremiah Willcock <jewillco@osl.iu.edu>
On Fri, 30 Sep 2011, Pablo Fleurquin wrote:
Yes,
The thing is I have a whole code that uses vector<vector<int> > and I only
need one function from boost library, but this function wont work with vector<vector<int> >.
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<vector<int>
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 <dave@boostpro.com>
on Fri Sep 30 2011, Pablo Fleurquin <pablofleurquin-AT-gmail.com> wrote:
I have an adjacency list, representing a directed graph, written in standard c++ format using vector: vector<vector<int> > I want to tranform it to boost adjacency_list< > format and then back to vector <vector<int> >.
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<vector<int> > 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<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
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 <jewillco@osl.iu.edu> On Fri, 30 Sep 2011, Pablo Fleurquin wrote:
Yes,
The thing is I have a whole code that uses vector<vector<int> > and I only need one function from boost library, but this function wont work with vector<vector<int> >.
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<vector<int> > 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 <dave@boostpro.com>
on Fri Sep 30 2011, Pablo Fleurquin <pablofleurquin-AT-gmail.com> wrote:
> I have an adjacency list, representing a directed graph, written in > standard c++ format using vector: vector<vector<int> > I want to > tranform it to boost adjacency_list< > format and then back to vector > <vector<int> >. > > 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<vector<int> > 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
on Fri Sep 30 2011, Jeremiah Willcock <jewillco-AT-osl.iu.edu> 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 Abrahams BoostPro Computing http://www.boostpro.com
2011/9/30 Dave Abrahams <dave@boostpro.com>
on Fri Sep 30 2011, Jeremiah Willcock <jewillco-AT-osl.iu.edu> 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 Oct 01 2011, Pablo Fleurquin <pablofleurquin-AT-gmail.com> wrote:
on Fri Sep 30 2011, Jeremiah Willcock <jewillco-AT-osl.iu.edu> 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). -- Dave Abrahams BoostPro Computing http://www.boostpro.com
On Sat, 1 Oct 2011, Dave Abrahams wrote:
on Sat Oct 01 2011, Pablo Fleurquin <pablofleurquin-AT-gmail.com> wrote:
on Fri Sep 30 2011, Jeremiah Willcock <jewillco-AT-osl.iu.edu> 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
On Fri, 30 Sep 2011, Dave Abrahams wrote:
on Fri Sep 30 2011, Jeremiah Willcock <jewillco-AT-osl.iu.edu> 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?
It looks like vector_as_graph does exactly that, and so it should work for this application. -- Jeremiah Willcock
participants (3)
-
Dave Abrahams -
Jeremiah Willcock -
Pablo Fleurquin