boost graph copy and removing vertex

Question

How do I copy a boost graph into a second boost graph so that I can use the vertex descriptor extracted from the first graph to modify the second one without modifying the first one ?

I have a boost graph g1 from which I extracted a couple of vertex descriptor. Now I want to use this vertex descriptor to do some processing to a copy of g1 named g2. If I use something along the lines of :

g2 = g1;

to copy the graph then I can access the vertex properties of g2 using vertex descriptor extracted from g1 using something like g2[vertex_descriptor] but I cannot remove a vertex from the graph.

boost::clear_vertex(v, _graph);
boost::remove_vertex(v, _graph);

Does nothing to my graph and the vertex is still there.

I know there is a copy_graph function available but I don't really understand (or I don't know how to read) the doc and doing boost::copy_graph(g1, g2) yield a lot of errors :

In file included from /usr/include/boost/graph/adjacency_list.hpp:246:0,
                 from /home/malcolm/AASS/sketch_maker/includes/TopologicalMap/Global.hpp:6,
                 from /home/malcolm/AASS/sketch_maker/includes/MapComparator/Match.hpp:4,
                 from /home/malcolm/AASS/sketch_maker/includes/MapComparator/Hypothese.hpp:4,
                 from /home/malcolm/AASS/sketch_maker/includes/MapComparator/Cluster.hpp:4,
                 from /home/malcolm/AASS/sketch_maker/Test/test_comparisor.cpp:11:
/usr/include/boost/graph/detail/adjacency_list.hpp: In instantiation of ‘struct boost::adj_list_any_vertex_pa::bind_<boost::vertex_index_t, boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, topologicalmap::Place, topologicalmap::Gateway_struct, boost::no_property>, topologicalmap::Place>’:
/usr/include/boost/graph/detail/adjacency_list.hpp:2568:12:   required from ‘struct boost::detail::adj_list_choose_vertex_pa<boost::vertex_index_t, boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, topologicalmap::Place, topologicalmap::Gateway_struct, boost::no_property>, topologicalmap::Place>’
/usr/include/boost/graph/detail/adjacency_list.hpp:2705:12:   required from ‘struct boost::adj_list_vertex_property_selector::bind_<boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, topologicalmap::Place, topologicalmap::Gateway_struct, boost::no_property>, topologicalmap::Place, boost::vertex_index_t>’
/usr/include/boost/graph/properties.hpp:217:12:   required from ‘struct boost::detail::vertex_property_map<boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, topologicalmap::Place, topologicalmap::Gateway_struct, boost::no_property>, boost::vertex_index_t>’
/usr/include/boost/graph/properties.hpp:228:10:   required from ‘struct boost::property_map<boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, topologicalmap::Place, topologicalmap::Gateway_struct, boost::no_property>, boost::vertex_index_t, void>’
/usr/include/boost/graph/detail/adjacency_list.hpp:1688:5:   required by substitution of ‘template<class Config, class Base, class Property> typename boost::property_map<typename Config::graph_type, Property>::const_type boost::get(Property, const boost::adj_list_helper<Config, Base>&) [with Config = boost::detail::adj_list_gen<boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, topologicalmap::Place, topologicalmap::Gateway_struct, boost::no_property>, boost::listS, boost::listS, boost::undirectedS, topologicalmap::Place, topologicalmap::Gateway_struct, boost::no_property, boost::listS>::config; Base = boost::undirected_graph_helper<boost::detail::adj_list_gen<boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, topologicalmap::Place, topologicalmap::Gateway_struct, boost::no_property>, boost::listS, boost::listS, boost::undirectedS, topologicalmap::Place, topologicalmap::Gateway_struct, boost::no_property, boost::listS>::config>; Property = boost::vertex_index_t]’
/usr/include/boost/graph/copy.hpp:353:57:   required from ‘void boost::copy_graph(const VertexListGraph&, MutableGraph&) [with VertexListGraph = boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, topologicalmap::Place, topologicalmap::Gateway_struct, boost::no_property>; MutableGraph = boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, topologicalmap::Place, topologicalmap::Gateway_struct, boost::no_property>]’
/home/malcolm/AASS/sketch_maker/includes/MapComparator/Cluster.hpp:32:150:   required from here
/usr/include/boost/graph/detail/adjacency_list.hpp:2498:29: error: forming reference to void
         typedef value_type& reference;
                             ^
/usr/include/boost/graph/detail/adjacency_list.hpp:2499:35: error: forming reference to void
         typedef const value_type& const_reference;
                                   ^
/usr/include/boost/graph/detail/adjacency_list.hpp:2502:47: error: forming reference to void
           <Graph, value_type, reference, Tag> type;
                                               ^
/usr/include/boost/graph/detail/adjacency_list.hpp:2504:53: error: forming reference to void
           <Graph, value_type, const_reference, Tag> const_type;
                                                     ^
In file included from /home/malcolm/AASS/sketch_maker/includes/TopologicalMap/GraphPlace.hpp:13:0,
                 from /home/malcolm/AASS/sketch_maker/includes/MapComparator/Cluster.hpp:5,
                 from /home/malcolm/AASS/sketch_maker/Test/test_comparisor.cpp:11:
/usr/include/boost/graph/copy.hpp: In instantiation of ‘void boost::copy_graph(const VertexListGraph&, MutableGraph&) [with VertexListGraph = boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, topologicalmap::Place, topologicalmap::Gateway_struct, boost::no_property>; MutableGraph = boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, topologicalmap::Place, topologicalmap::Gateway_struct, boost::no_property>]’:
/home/malcolm/AASS/sketch_maker/includes/MapComparator/Cluster.hpp:32:150:   required from here
/usr/include/boost/graph/copy.hpp:353:57: error: no matching function for call to ‘get(boost::vertex_index_t, const boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, topologicalmap::Place, topologicalmap::Gateway_struct, boost::no_property>&)’
                                   get(vertex_index, g_in), orig2copy[0]),

The error message is bigger than that but I took only the beginning.

Answer 1

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);
}