Copy Boost Labeled Graph

Question

I want to be able to copy labeled graph adaptor together with the underlying adjacency list.

The following code snippet is mostly the same as the one in this answer : https://stackoverflow.com/a/35640105/9033613, except for the fact that the adjacency list is using setS instead of vecS. I've also modified the example so that original graph is removed after being copied.

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

struct NodeInfo1 { int i; };
struct EdgeInfo1 { int j; };

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

void print(Graph& g) {
  auto pmap = boost::get(&NodeInfo1::i, g);
  for(auto v : boost::make_iterator_range(boost::vertices(g))) {
    std::cout << pmap[v] << " --> ";
    for (const auto &e : boost::make_iterator_range(boost::out_edges(v, g))) {
      const auto &v_t = boost::target(e, g);
      std::cout << pmap[v_t] << " ";
    }
    std::cout << std::endl;
  }
}

auto TestCopyGraph(const Graph& grid)
{
  Graph g1 = grid; // just copy-construct
  return g1;
}

int main() {
  std::string names[3] = { "A", "B", "C" };
  NodeInfo1 props[3] = { {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 = TestCopyGraph(*grid);
  print(copied);


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

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

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

Now if I use vecS as the vertex descriptor, example works as expected, but if I use setS instead of vecS, code get a segmentation fault due to the fact that the copy operation does not actually copy the underlying structures of adjacency list. How can I solve this issue, or in general how can I copy a labeled graph adaptor as defined in the code above?

Can you create a smaller example that demonstrates the problem? Try starting as simple as possible - creating a setS or vecS, copy them and try to repro the crash. If not, then can you repro the crash just using an AList alone (not as part of Graph). Etc... Where in the code does it crash? — joeking
@joeking 64 LoC is pretty bare-bones for a Boost Graph starter — sehe

sehe sehe · Accepted Answer · 2020-11-20T00:10:54

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

Copy Boost Labeled Graph

1 Answers

How To Solve It

Let's Stop At Nothing

Live Demo