BGL - retrieving a subgraph
To describe what I want to do I will use the following graph: digraph G { 0[label="test1"]; 1[label="test2"]; 2[label="test3"]; 3[label="test4"]; 2->0 ; 2->1 ; 3->0 ; 3->2 ; } Now, what I want to do is two things. Both are for vertices such as 2. 2 depends on 0 and 1, it has 3 as its only client. Is there a graph algorithm that will extract those two subgraphs for me? Take any vertex in a directer graph and give me a subgraph of all its descendants or a subgraph for all its ancestors (I imagine those are two different algorithms). I looked at the connected components algorithms and none seemed to apply. Still looking at others but there are a lot of functions. Any ideas to narrow down the search?
On May 21, 2007, at 6:50 PM, Noah Roberts wrote:
To describe what I want to do I will use the following graph:
digraph G { 0[label="test1"]; 1[label="test2"]; 2[label="test3"]; 3[label="test4"]; 2->0 ; 2->1 ; 3->0 ; 3->2 ; }
Now, what I want to do is two things. Both are for vertices such as 2. 2 depends on 0 and 1, it has 3 as its only client. Is there a graph algorithm that will extract those two subgraphs for me? Take any vertex in a directer graph and give me a subgraph of all its descendants or a subgraph for all its ancestors (I imagine those are two different algorithms).
I looked at the connected components algorithms and none seemed to apply. Still looking at others but there are a lot of functions. Any ideas to narrow down the search?
To get all of the descendants, you could just run a breadth-first or depth-first search starting at vertex "2", and then record which vertices were visited. To get the ancestors, you could do exactly the same thing using the reverse graph; see http://www.boost.org/libs/graph/doc/ reverse_graph.html - Doug
Doug Gregor wrote:
To get all of the descendants, you could just run a breadth-first or depth-first search starting at vertex "2", and then record which vertices were visited.
To get the ancestors, you could do exactly the same thing using the reverse graph; see http://www.boost.org/libs/graph/doc/ reverse_graph.html
This fails to compile: typedef boost::adjacency_list < boost::vecS , boost::vecS , boost::bidirectionalS , boost::property<boost::vertex_color_t, boost::default_color_type> , boost::property<boost::edge_weight_t, int>
dependency_graph_t; typedef boost::graph_traits<dependency_graph_t>::vertex_descriptor vertex; struct visitation_tracker : boost::bfs_visitor<> { std::vector<int> & visited; visitation_tracker(std::vector<int> & v) : visited(v) {} template < typename G, typename V > void discover_vertex(V u, G const& g) { visited.push_back(static_cast<int>(u)); } }; std::vector<int> retrieve_client_list(std::string const& cname) const { std::vector<component>::const_iterator fit = std::find_if(components.begin(), components.end(), boost::bind(&component::name, _1) == cname); if (fit == components.end()) throw std::runtime_error(cname + " not found in list of components."); int u = static_cast<int>(std::distance(components.begin(), fit)); std::vector<int> visited; visitation_tracker tracker(visited); boost::breadth_first_search(boost::make_reverse_graph(graph), boost::vertex(u, boost::make_reverse_graph(graph)), boost::visitor(tracker)); return visited; } Errors: 1>c:\projects\utilities\integrator\integrator\dependency_graph.cpp(119) : error C2784: 'subgraph<Graph>::vertex_descriptor boost::vertex(subgraph<Graph>::vertices_size_type,const boost::subgraph<Graph> &)' : could not deduce template argument for 'const boost::subgraph<Graph> &' from 'boost::reverse_graph<BidirectionalGraph,GraphRef>' 1> with 1> [ 1> BidirectionalGraph=dependency_graph_t, 1> GraphRef=const dependency_graph_t & 1> ] 1> c:\boost\include\boost-1_33_1\boost\graph\subgraph.hpp(865) : see declaration of 'boost::vertex' 1>c:\projects\utilities\integrator\integrator\dependency_graph.cpp(119) : error C2784: 'Config::vertex_descriptor boost::vertex(Config::vertices_size_type,const boost::vec_adj_list_impl<Graph,Config,Base> &)' : could not deduce template argument for 'const boost::vec_adj_list_impl<Graph,Config,Base> &' from 'boost::reverse_graph<BidirectionalGraph,GraphRef>' 1> with 1> [ 1> BidirectionalGraph=dependency_graph_t, 1> GraphRef=const dependency_graph_t & 1> ] 1> c:\boost\include\boost-1_33_1\boost\graph\detail\adjacency_list.hpp(2133) : see declaration of 'boost::vertex' 1>c:\projects\utilities\integrator\integrator\dependency_graph.cpp(119) : error C2784: 'Config::vertex_descriptor boost::vertex(Config::vertices_size_type,const boost::adj_list_impl<Derived,Config,Base> &)' : could not deduce template argument for 'const boost::adj_list_impl<Derived,Config,Base> &' from 'boost::reverse_graph<BidirectionalGraph,GraphRef>' 1> with 1> [ 1> BidirectionalGraph=dependency_graph_t, 1> GraphRef=const dependency_graph_t & 1> ] 1> c:\boost\include\boost-1_33_1\boost\graph\detail\adjacency_list.hpp(1848) : see declaration of 'boost::vertex' 1>c:\projects\utilities\integrator\integrator\dependency_graph.cpp(119) : error C2780: 'void boost::breadth_first_search(const VertexListGraph &,graph_traits<G>::vertex_descriptor,Buffer &,BFSVisitor,ColorMap)' : expects 5 arguments - 3 provided 1> c:\boost\include\boost-1_33_1\boost\graph\breadth_first_search.hpp(88) : see declaration of 'boost::breadth_first_search'
I believe I have managed to use breadth first on a reverse graph to get a list of vertices I need. However, I can't seem to create a subgraph. I'm apparently not using an edge mutable graph? Anyway, it pukes up a static assert when I try to create one. 1>c:\boost\include\boost-1_33_1\boost\graph\subgraph.hpp(252) : error C2027: use of undefined type 'boost::STATIC_ASSERTION_FAILURE<x>' 1> with 1> [ 1> x=false 1> ] 1> c:\projects\utilities\integrator\integrator\dependency_graph.cpp(101) : see reference to class template instantiation 'boost::subgraph<Graph>' being compiled 1> with 1> [ 1> Graph=dependency_graph_t 1> ] The code that generates the assert in subgraph.hpp: typedef typename property_map<Graph, edge_index_t>::type EdgeIndexMap; typedef typename property_traits<EdgeIndexMap>::value_type edge_index_type; BOOST_STATIC_ASSERT((!is_same<edge_index_type, boost::detail::error_property_not_found>::value)); My definitions: typedef boost::adjacency_list < boost::vecS , boost::vecS , boost::bidirectionalS , boost::property<boost::vertex_color_t, boost::default_color_type> , boost::property<boost::edge_weight_t, int>
dependency_graph_t; typedef boost::subgraph<dependency_graph_t> subg_t; subg_t subg; The documentation for this library seems to be pretty sparse. I might be able to figure it out from example code, but the file the docs say to look at, examples/subgraph.hpp, doesn't appear to actually exist. How do I create the subgraph I need to create? Thanks...
Noah Roberts wrote:
I believe I have managed to use breadth first on a reverse graph to get a list of vertices I need. However, I can't seem to create a subgraph. I'm apparently not using an edge mutable graph? Anyway, it pukes up a static assert when I try to create one.
I can't believe how difficult using this library has turned out to be. I'm very near just giving up on it entirely. After hours and hours of excruciating pain and suffering I have managed to get everything working that I need except for one thing. Now that I have changed to using subgraphs, as required for being able to retrieve a subgraph at all, I have run into a brick wall. I can't write graphviz output anymore. The function that now gets called when I attempt to requires a graph_name property that just plain isn't there. I can find how to retrieve it by looking in the code that thinks it should be there...but there is nothing anywhere that helps me figure out how to set the damn thing; not in the docs and not anywhere in the code that I can see. So I'm at an impasse unless someone can tell me exactly where in the docs I'm supposed to be able to find this information. Not only that. I know for a fact this thing has a memory leak. The subgraph setup creates a subgraph somewhere inside the parent that I can't get to. I can create subgraph after subgraph but there's no way to destroy them! Looking at the code that creates them it is quite obvious that they are created on the heap and my repeated creation of them is going to pose a problem rather quickly. Quite frankly, I can't understand how this API exists without a method to kill subgraphs. This is a major flaw. Boost is great, but I tell you....some of these libraries could REALLY use some work on the documentation side. I'm going bald trying to figure this damn thing out.
Noah Roberts wrote:
I can't believe how difficult using this library has turned out to be. I'm very near just giving up on it entirely. After hours and hours of excruciating pain and suffering I have managed to get everything working that I need except for one thing. Now that I have changed to using subgraphs, as required for being able to retrieve a subgraph at all, I have run into a brick wall.
I can't write graphviz output anymore. The function that now gets called when I attempt to requires a graph_name property that just plain isn't there. I can find how to retrieve it by looking in the code that thinks it should be there...but there is nothing anywhere that helps me figure out how to set the damn thing; not in the docs and not anywhere in the code that I can see. So I'm at an impasse unless someone can tell me exactly where in the docs I'm supposed to be able to find this information.
Not only that. I know for a fact this thing has a memory leak. The subgraph setup creates a subgraph somewhere inside the parent that I can't get to. I can create subgraph after subgraph but there's no way to destroy them! Looking at the code that creates them it is quite obvious that they are created on the heap and my repeated creation of them is going to pose a problem rather quickly. Quite frankly, I can't understand how this API exists without a method to kill subgraphs. This is a major flaw.
Boost is great, but I tell you....some of these libraries could REALLY use some work on the documentation side. I'm going bald trying to figure this damn thing out.
Ok, all my complaints still apply but I managed to get what I want done. I gave up on subgraphs and instead used filtered graphs. These don't have any of the above problems.
participants (2)
-
Doug Gregor -
Noah Roberts