2

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?

keskino
  • 23
  • 2
  • 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 Nov 19 '20 at 19:02
  • @joeking 64 LoC is pretty bare-bones for a Boost Graph starter – sehe Nov 19 '20 at 22:16

1 Answers1

3

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

sehe
  • 374,641
  • 47
  • 450
  • 633
  • Doing some coverage testing I found that you'd need to change to unsigned label *as well as* using `vecS` to hit the `random_access_container_tag` case: https://wandbox.org/permlink/rrwasb11Futodxbw - but now I've also tested that :) – sehe Nov 20 '20 at 00:35
  • Thank you for the great explanation @sehe! For now, I feel like creating a new graph and copying all vertices/edges and preventing to copy graph on a sub class sounds like a better option for me even if it's more costly. I can think of using a different graph than labeled graph, I just need to be able to access information on vertices directly by some kind of a fixed label in a graph that is modified along the way. – keskino Nov 20 '20 at 10:06
  • Yeah, I tend to use bundled properties or external propertymaps to manage labels. See e.g. [the gist of this comment](https://stackoverflow.com/questions/35880930/breadth-first-search-on-labeled-graph/35886035#comment59454948_35886035) – sehe Nov 21 '20 at 21:50
  • Perhaps a Bimap is most useful if you want a property that you'll be able to look-up vertices by as well https://stackoverflow.com/questions/26697477/cut-set-of-a-graph-boost-graph-library/26699982#26699982 – sehe Nov 21 '20 at 21:51
  • I'll definitely check that, thanks. In the mean time, I just need to be able to clear the existing graph structure. I've missed the part that the underlying map object is not updated when removing the vertices, and if I understand from your other posts on different questions, it's not possible to remove a single item from the underlying map (which still sounds odd to me). So is there a way to update the underlying map, or remove the map completely during the re-initializiation? – keskino Nov 24 '20 at 11:57
  • Default construction + copy-assignment just work: [`copied = {};` will do](https://wandbox.org/permlink/glvV7jhDIUqAAFmY). Adding some debug tracing we can verify that the cleared `labeled_graph`s `_map` is actually empty: https://wandbox.org/permlink/Aw7dK82tCsqTSZJb (this abuses the `friend` access) – sehe Nov 24 '20 at 12:11
  • I see I posted a wrong link in my [first comment](https://stackoverflow.com/questions/64917207/copy-boost-labeled-graph/64921904?noredirect=1#comment114780687_64921904). Here it is fixed: https://wandbox.org/permlink/gp0cGBT7keHKRj0i Note how this shows how different the space/time trade-off is for integral labels – sehe Nov 24 '20 at 12:17