Boost Graph Copy and Removing Vertex

boost graph copy and removing vertex

What's wrong with the naive approach?

As I commented on the other answer, simply removing a vertex by the source vertex-descriptor will not work as expected, because it invalidates all the higher vertices in the mutated copy.

So if you were to remove a second vertex, chances are that you'd be removing a different vertex than the one intended.

What's worse, all the property lookups would be invalid (if done against original property maps).

And for the clincher, none of this would work at all if the vertex descriptor wasn't an integral type to begin with, e.g. when the vertex container selector was something else than boost::vecS (listS, setS etc.).

How to solve it?

The BGL has two primitives that seem applicable here:

  1. Filtered Graphs;

    Here you do not create an actual copy, just create a "filtered view" of the original graph by supplying (optional) vertex and edge filtering predicates.

  2. Subgraphs

    This is most suitable if you want a two-way mutable relation between (nested) parent and child graphs. I.e. if you know while building the graphs what nodes are in which "level" of a graph "hierarchy", you can express that with boost::subgraph<> hierarchies. These will automatically stay in synch; i.e. if you add a node to a child graph, the parent graph will contain it too; if you modify/remove an edge in a child graph, the same changes are "live" reflected in all parent graphs.

In this scenario I think that filtered_graph<> is really close to your need. Here's a demo that writes the graph, and "live-filters" it using a std::set<vertex_descriptor>. The result is visualized using GraphViz:

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <iostream>

using namespace boost;

struct VertexProperties {
    int id;
    std::string label;
};

struct EdgeProperties {
    double weight;
};

using Graph_t = boost::adjacency_list<listS, listS, directedS, VertexProperties, EdgeProperties>;

//////////////////////////////////////////////////
// saving dotfiles for rendering to PNG
#include <boost/graph/graphviz.hpp>

template <typename G>
void save_dot_file(std::string const& fname, G& graph) {
    dynamic_properties dp;
    dp.property("node_id", boost::get(&VertexProperties::id,    graph));
    dp.property("label",   boost::get(&VertexProperties::label, graph));
    dp.property("weight",  boost::get(&EdgeProperties::weight,  graph));

    std::ofstream ofs(fname);
    write_graphviz_dp(ofs, graph, dp);
}

//////////////////////////////////////////////////
// Filtering graphs with a simple vertex filter
#include <boost/graph/filtered_graph.hpp>
#include <boost/function.hpp>

using V        = Graph_t::vertex_descriptor;
using Filtered = filtered_graph<Graph_t, keep_all, boost::function<bool(V)> >;

//////////////////////////////////////////////////
// Demo
int main()
{
    Graph_t g;

    // have a filtered "copy" f that just removes a set of vertices:
    std::set<V> removed_set;
    Filtered f(g, keep_all{}, [&](V v){ return removed_set.end() == removed_set.find(v); });

    // build a demo graph with 3 vertices
    auto u = boost::add_vertex(VertexProperties{ 10, "Ten"    }, g);
    auto v = boost::add_vertex(VertexProperties{ 20, "Twenty" }, g);
    auto w = boost::add_vertex(VertexProperties{ 30, "Thirty" }, g);

    /*auto e1 =*/ boost::add_edge(u, v, EdgeProperties { 0.5 }, g);
    /*auto e2 =*/ boost::add_edge(v, w, EdgeProperties { 1.5 }, g);
    /*auto e3 =*/ boost::add_edge(w, u, EdgeProperties { 2.5 }, g);

    ///////////////////////////////////////
    // save the original graph
    save_dot_file("original.dot", g);

    // empty filter:
    save_dot_file("filtered1.dot", f);

    // removing `v` ("Twenty")
    removed_set.insert(v);
    save_dot_file("filtered2.dot", f);
}

Sample Image

Removing multiple vertices from a boost::adjacency_list graph

For vectorS the descriptors are just as unstable as iterators: they get invalidated on insert/remove. See Iterator and Descriptor Stability/Invalidation

Of course the solution described there (using listS) might not apply to your situation.

In that case, rethink your problem, and consider filtering the graph (without actually removing vertices) or mark vertices as deleted. See here for inspiration:

  • Remove 100,000+ nodes from a Boost graph (also the comment by _jv)

boost graph removing edges vs filtered_graph performance

Just use copy_graph on the filtered graph:

  • boost graph copy and removing vertex

removing vertex and all his neighbours from an graph with c++ boost library

Have a look here. remove_vertex will not change any edges. You need to clear_vertex it first.

A general hint: Don't use qualified calls to the boost::graph library, call them unqualified. I'd also suggest Boost.Range to handle the iteration in such simple cases. It keeps the scope cleaner and is a lot prettier.

boost::graph: How to remove in-edges of a previously removed vertex?

The implementation isn't "going through the trouble" - it's just doing anything, because you didn't satisfy the pre-conditions:

void remove_vertex(vertex_descriptor u, adjacency_list& g)

Remove vertex u from the vertex set of the graph. It is assumed that there are no edges to or from vertex u when it is removed. One way to make sure of this is to invoke clear_vertex() beforehand.

I repro-ed your issue slightly more briefly: Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <iostream>

int main() {
    boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS> g(2);

    add_edge(0, 1, g);
    add_edge(1, 0, g);

    print_graph(g, std::cout << "--- Before: ");
        
    remove_vertex(0, g); // remove the first vertex

    print_graph(g, std::cout << "--- After: ");

    // iterate over vertices and print their out_degree. 
    for (auto [it, end] = boost::vertices(g); it != end; ++it)
        std::cout << out_degree(*it, g) << "\n"; // this prints 1
}

Prints

--- Before: 0 --> 1 
1 --> 0 
--- After: 0 --> 0 
1

Fixing It

Let's simply do as the docs say:

clear_vertex(0, g);  // clear edges
remove_vertex(0, g); // remove the first vertex

Now it works: Live On Coliru, printing:

--- Before: 0 --> 1 
1 --> 0 
--- After: 0 --> 
0

BONUS

For more elegance:

// iterate over vertices and print their out_degree. 
for (auto v : boost::make_iterator_range(vertices(g)))
    std::cout << v << " out_degree: " << out_degree(v, g) << "\n";

How does boost::copy_graph's vertex_copy work?

Sidestepping the question for a second, the simplest way to achieve things would be to add the appropriate conversion constructor to the custom property:

struct custom_property {
    custom_property(uint32_t label = 0, float f = 0) : label(label), f(f) {}
    uint32_t label;
    float f;
};

In which case, a simple copy will work:

boost::copy_graph(adj, adj_custom);

See it Live On Coliru

Regarding the vertex copier, it receives the vertex decriptors. To access the vertex properties, you need to have the graph reference:

struct vertex_copier {
    AdjacencyList& from;
    AdjacencyListCustom& to;

    void operator()(AdjacencyList::vertex_descriptor input, AdjacencyListCustom::vertex_descriptor output) const {
        to[output] = { from[input], 0.f };
    }
};

In which case you'd invoke things:

boost::copy_graph(adj, adj_custom, boost::vertex_copy(vertex_copier{adj, adj_custom}));

Again, Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/copy.hpp>
#include <iostream>

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, uint32_t, float> AdjacencyList;

typedef AdjacencyList::vertex_descriptor VertexID;

    struct custom_property {
        //custom_property(uint32_t label = 0, float f = 0) : label(label), f(f) {}
        uint32_t label;
        float f;
    };

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, custom_property, float> AdjacencyListCustom;

struct vertex_copier {
    AdjacencyList& from;
    AdjacencyListCustom& to;

    void operator()(AdjacencyList::vertex_descriptor input, AdjacencyListCustom::vertex_descriptor output) const {
        to[output] = { from[input], 0.f };
    }
};

int main(int argc, char **argv) {
    AdjacencyList adj;
    VertexID id_0 = boost::add_vertex(0, adj);
    VertexID id_1 = boost::add_vertex(1, adj);
    VertexID id_2 = boost::add_vertex(2, adj);
    VertexID id_3 = boost::add_vertex(4, adj);
    boost::add_edge(id_0, id_1, 1.0f, adj);
    boost::add_edge(id_2, id_3, 2.0f, adj);

    AdjacencyListCustom adj_custom;
    boost::copy_graph(adj, adj_custom, boost::vertex_copy(vertex_copier{adj, adj_custom}));
}

Copy Boost Labeled Graph

This is, sadly, another limitation of the labeled_graph adaptor¹.

The real problem is that the adaptor stores raw vertex descriptors inside its internal properties (map). In the case of vecS vertex-container-selector, the vertex descriptor is an integral 0-based number [0, num_vertices(g)), which happily transfers to identical copies of the graph.

However, for node-based vertex-container selectors (listS, setS, ...) the vertex-descriptor is an opaque handle (basically a pointer type-punned to void*). Obviously, these do NOT transfer to the copy of a graph. Worse, when using the vertex descriptors on the copy you get Undefined Behaviour. If the source of the copy is still around you will probably end up accessing vertex storage from the wrong graph. If the graph was already destructed, you'll get any other behaviour, if you're lucky a crash.

How To Solve It

I'm afraid you can't.

We could use boost::copy_graph on the underlying labeed_graph.graph(). We'd need to supply an external vertex_index property map.

However, this leaves us with the unsolvable task of actually copying the labels. It's unsolvable as there is no way to iterate the labels, or extract them from vertex descriptors. And we can't add the functionality - not even by subclassing - since the map_type _map; is private.

Let's Stop At Nothing

Of course, if we could alter boost/graph/labeled_graph.hpp to declare a friend:

template <typename G, typename L, typename S>
friend labeled_graph<G, L, S> clone_labeled_graph(labeled_graph<G, L, S> const& src);

We might implement the functionality out-of-class:

template <typename G, typename L, typename S>
labeled_graph<G, L, S> clone_labeled_graph(labeled_graph<G, L, S> const& src) {
    labeled_graph<G, L, S> dst;
    graph_detail::clone_labeled_graph(src.graph(), src._map, dst.graph(), dst._map);
    return dst;
}

A subtle choice is that we split out the parameters to the underlying graphs and their label-maps, so we avoid having to specify a plethora of friend templates. Why?

That's because we need to dispatch on the type of the label map (which will take various forms depending on the nature of the vertex index as described earlier):

template <typename Graph, typename Map>
static inline void clone_labeled_graph(Graph const& g, Map const& srcmap, Graph& dst, Map& dstmap) {
    clone_labeled_graph(g, srcmap, dst, dstmap, container_category(srcmap));
}

With that in place, we can implement the various overloads as:

template <typename Graph, typename Map>
static inline void clone_labeled_graph(Graph const& src, Map const& srcmap, Graph& dst, Map& dstmap, random_access_container_tag) {
    copy_graph(src, dst);

    dstmap.resize(srcmap.size());
    for (size_t v = 0; v < srcmap.size(); ++v) {
        put_vertex_label(dstmap, dst, srcmap[0], v);
    }
}

template <typename Graph, typename Map>
static inline void clone_labeled_graph(Graph const& src, Map const& srcmap, Graph& dst, Map& dstmap, unique_associative_container_tag) {
    using V = graph_traits<Graph>::vertex_descriptor;
    std::map<V, size_t> vidx;
    for (auto v : boost::make_iterator_range(vertices(src)))
        vidx.emplace(v, vidx.size());
    auto idmap = boost::make_assoc_property_map(vidx);

    std::map<V, V> corresponding;
    auto o2cmap = make_assoc_property_map(corresponding);

    copy_graph(src, dst, vertex_index_map(idmap).orig_to_copy(o2cmap));

    for (auto const& [label, v] : srcmap) {
        put_vertex_label(dstmap, dst, label, corresponding.at(v));
    }
}

template <typename Graph, typename Map>
static inline void clone_labeled_graph(Graph const& src, Map const& srcmap, Graph& dst, Map& dstmap, multiple_associative_container_tag) {
    clone_labeled_graph(src, srcmap, dstmap, unique_associative_container_tag{});
}

Note that this

  • takes care to be generic (it should work with vecS, listS etc)
  • does NOT focus on efficiency
  • does NOT support C++03 compilation

Live Demo

Live On Wandbox

  • File main.cpp

     #define BOOST_ALLOW_DEPRECATED_HEADERS
     #include <boost/graph/adjacency_list.hpp>
     #include <boost/graph/copy.hpp>
     #include <iostream>
     #include "labeled_graph.hpp" // adds the friend declaration ONLY
     #include "clone_labeled_graph.hpp" // our out-of-class friend implementation

     template <typename Graph>
     void print(Graph const& g) {
         std::cout << "====\n";
         for(auto v : boost::make_iterator_range(boost::vertices(g))) {
             std::cout << g.graph()[v].i << " --> ";
             for (const auto &e : boost::make_iterator_range(boost::out_edges(v, g))) {
                 const auto &v_t = boost::target(e, g);
                 std::cout << g.graph()[v_t].i << " ";
             }
             std::cout << std::endl;
         }
     }

     template <typename VertexSelector>
     void test_clone_labeled_graph() {
         std::cout << __PRETTY_FUNCTION__ << "\n";
         struct NodeInfo1 { int i; };
         struct EdgeInfo1 { int j; };

         typedef boost::adjacency_list<boost::setS, VertexSelector, boost::bidirectionalS, NodeInfo1, EdgeInfo1> AList;
         typedef boost::labeled_graph<AList, std::string> Graph;

         std::string names[] = { "A", "B", "C" };
         NodeInfo1 props[] = { {11}, {22}, {33} };
         std::unique_ptr<Graph> grid(new Graph(3, names, props));

         /*auto e =*/ add_edge_by_label("C", "B", EdgeInfo1{17}, *grid);

         auto copied = clone_labeled_graph(*grid);
         grid.reset();

         print(copied);

         auto& g = copied.graph();
         // check that properties were copied: vertex B has NodeInfo1 22
         {
             std::cout << "Vertex B NodeInfo1.i after copy: " << g[copied.vertex("B")].i << "\n";
         }

         // edge properties too:
         for (auto e : boost::make_iterator_range(boost::edges(copied))) {
             std::cout << "Edge has property EdgeInfo1 " << g[e].j << "\n";
         }

         std::cout << "Removed A:\n";
         copied.remove_vertex("A");
         print(copied);
     }

     int main() {
         test_clone_labeled_graph<boost::vecS>();
         test_clone_labeled_graph<boost::listS>();
         test_clone_labeled_graph<boost::setS>();
     }

  • File labeled_graph.hpp

     // ...

     namespace boost
     {
     // ...

     template < typename Graph, typename Label, typename Selector = defaultS >
     class labeled_graph : protected labeled_graph_types< Graph, Label, Selector >
     {
         // ...

     private:
         graph_type _graph;
         map_type _map;

         template <typename G, typename L, typename S>
         friend labeled_graph<G, L, S> clone_labeled_graph(labeled_graph<G, L, S> const& src);
     };

     // ...

  • File clone_labeled_graph.hpp

     #include <boost/graph/labeled_graph.hpp>
     #include <boost/graph/copy.hpp>

     namespace boost {

     namespace graph_detail {
         template <typename Graph, typename Map>
         static inline void clone_labeled_graph(Graph const& src, Map const& srcmap, Graph& dst, Map& dstmap, random_access_container_tag) {
             copy_graph(src, dst);

             dstmap.resize(srcmap.size());
             for (size_t v = 0; v < srcmap.size(); ++v) {
                 put_vertex_label(dstmap, dst, srcmap[0], v);
             }
         }

         template <typename Graph, typename Map>
         static inline void clone_labeled_graph(Graph const& src, Map const& srcmap, Graph& dst, Map& dstmap, unique_associative_container_tag) {
             using V = graph_traits<Graph>::vertex_descriptor;
             std::map<V, size_t> vidx;
             for (auto v : boost::make_iterator_range(vertices(src)))
                 vidx.emplace(v, vidx.size());
             auto idmap = boost::make_assoc_property_map(vidx);

             std::map<V, V> corresponding;
             auto o2cmap = make_assoc_property_map(corresponding);

             copy_graph(src, dst, vertex_index_map(idmap).orig_to_copy(o2cmap));

             for (auto const& [label, v] : srcmap) {
                 put_vertex_label(dstmap, dst, label, corresponding.at(v));
             }
         }

         template <typename Graph, typename Map>
         static inline void clone_labeled_graph(Graph const& src, Map const& srcmap, Graph& dst, Map& dstmap, multiple_associative_container_tag) {
             clone_labeled_graph(src, srcmap, dstmap, unique_associative_container_tag{});
         }

         template <typename Graph, typename Map>
         static inline void clone_labeled_graph(Graph const& g, Map const& srcmap, Graph& dst, Map& dstmap) {
             clone_labeled_graph(g, srcmap, dst, dstmap, container_category(srcmap));
         }
     } // namespace graph_detail

     template <typename G, typename L, typename S>
     labeled_graph<G, L, S> clone_labeled_graph(labeled_graph<G, L, S> const& src) {
         labeled_graph<G, L, S> dst;
         graph_detail::clone_labeled_graph(src.graph(), src._map, dst.graph(), dst._map);
         return dst;
     }

     } // namespace boost

Prints

void test_clone_labeled_graph() [with VertexSelector = boost::vecS]
====
11 -->
22 -->
33 --> 22
Vertex B NodeInfo1.i after copy: 22
Edge has property EdgeInfo1 17
Removed A:
====
22 -->
33 --> 22
void test_clone_labeled_graph() [with VertexSelector = boost::listS]
====
11 -->
22 -->
33 --> 22
Vertex B NodeInfo1.i after copy: 22
Edge has property EdgeInfo1 17
Removed A:
====
22 -->
33 --> 22
void test_clone_labeled_graph() [with VertexSelector = boost::setS]
====
11 -->
22 -->
33 --> 22
Vertex B NodeInfo1.i after copy: 22
Edge has property EdgeInfo1 17
Removed A:
====
22 -->
33 --> 22

¹ see previous episodes that lead to barriers


Related Topics

C++ Over Qt:Controlling Transparency of Labels and Buttons

How-To Ensure That Compiler Optimizations Don't Introduce a Security Risk

Copy Object - Keep Polymorphism

Is There Any Function Equivalent to Matlab's Imadjust in Opencv with C++

Why Ld_Preload Doesn't Work for One of Loaded Shared Libraries

Locating iOStream in Clang++: Fatal Error: 'iOStream' File Not Found

How to Construct or Return the Underlying Deque from a Stack

Set System Date and Time Using C++ in Linux

Objects of Different Classes in a Single Vector

Optimal Buffer Size for Write(2)

Volatile Struct = Struct Not Possible, Why

How to Compile Qt as Static

How to Write an C/C++ Application That Writes to a /Var/Log/Myapp Directory

When to Mark a Function in C++ as a Virtual

Does Insertion to Stl Map Invalidate Other Existing Iterator

Dynamically Loading Static Library

Stack Growth Direction

Std::Lower_Bound Slower for Std::Vector Than Std::Map::Find


Leave a reply



Submit