### Make a subgraph from a Boost Graph Library(BGL)

I have a boost graph library that I define it as below:

 ``1234567891011121314151617181920`` ``````/// vertex properties struct VertexData { std::string label; int num; bool is_leaf=false; }; /// edges properties struct EdgeData { std::string edge_name; double edge_confidence; }; /// define the boost-graph typedef boost::adjacency_list, boost::property > Graph;``````

I make a tree with this graph definition, now I want to make a subgraph that contains all edges and nodes except the leaves. So how I may remove leaves and connected edges in the new subgraph?
I can use property `bool is_leaf=true`, but I don't know how to select them and remove them to make a new graph.

Thank you.
Bruce.
Last edited on
as http://www.boost.org/doc/libs/1_65_1/libs/graph/doc/adjacency_list.html points out, you may want to switch from vecS to listS for the vertex list here.

Here's a try:

 ``12345678910111213141516171819`` ``````// simplifying your graph a bit for easier demo struct VertexData { std::string label; }; struct EdgeData { std::string edge_name; }; typedef boost::adjacency_list Graph; // ... std::unordered_set leaves; remove_edge_if([&](const auto& e){ auto v = target(e, g); if(auto[o1, o2] = out_edges(v, g); o1 == o2) { leaves.insert(v); return true; } else return false; }, g); for(auto& v: leaves) remove_vertex(v, g);``````

Thank you for the reply. Is it possible to make a copy of my vecS graph and convert it to listS, and then make the subgraph, because I want to keep the original vecS graph. I already have built on it other things.

And would you please explain the lines with some comments, I am not beginner in c++ and BGL.

Thanks a lot.
the problem with VertexList = vecS is that each call to remove_vertex() invalidates the whole graph, so you can't do it in single pass. If it's really small, I guess you could live through starting the walk from the beginning for each leaf vertex. Otherwise, you'll have to write a function that builds a second graph while walking the first one, omitting the vertices that are leaves and the edges that lead to them. Or, indeed, copy the whole thing into a listS graph and use the approach from my demo.

In my demo, I used a bit of C++17 for simplicity, but the basic structure is a call to remove_edge_if() with a predicate that first calls target() to get the vertex to which this edge leads, then out_edges() to find out the list of edges that lead out of that vertex. If there are none, it records the vertex descriptor in the set and returns true so that remove_edge_if() can erase that edge. If your is_leaf is reliable, you could just return the value of that, for the target.
Then it's just a loop over the saved vertex descriptors that calls remove_vertex() to erase them (and that's what leads to undefined behavior of a vecS graph). See the doc linked above for the meaning of remove_edge_if(), target(), out_edges(), and remove_vertex() (and vertices() used in the full demo for printing)
Last edited on
@Cubbi thank you. I understand your answer better. However, I decided to use a `boost::filtered_graph<Graph, EdgePredicate, VertexPredicate>`. With this I don't need to convert my graph to a listS, and I can use either the is_leaf flag or boost::degree to remove leaves.
Topic archived. No new replies allowed.