Make a subgraph from a Boost Graph Library(BGL)

[Bruce34]

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

/// 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::vecS, boost::vecS,
        boost::bidirectionalS,
        boost::property<boost::edge_index_t , size_t , VertexData>,
        boost::property<boost::edge_weight_t, double, EdgeData> > 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.

[Cubbi]

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:

// simplifying your graph a bit for easier demo
struct VertexData { std::string label; };
struct EdgeData { std::string edge_name; };
typedef boost::adjacency_list<boost::vecS, boost::listS, // <-- listS!
        boost::bidirectionalS, VertexData, EdgeData> Graph;

// ...

    std::unordered_set<Graph::vertex_descriptor> 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);

full live demo: https://wandbox.org/permlink/Z5otTegE13knM40A

[Bruce34]

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.

[Cubbi]

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)

[Bruce34]

@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.