c++ - 复制 Boost 标记图

Question

我希望能够将标记的图形适配器与底层邻接列表一起复制。
以下代码片段与此答案中的代码片段大致相同:
https://stackoverflow.com/a/35640105/9033613 , 除了邻接表使用 setS 而不是 vecS 的事实。我还修改了示例，以便在复制后删除原始图形。

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

现在，如果我使用 vecS 作为顶点描述符，示例按预期工作，但如果我使用 setS 而不是 vecS，由于复制操作实际上并未复制邻接表的底层结构，代码会出现段错误。
我该如何解决这个问题，或者一般来说如何复制上面代码中定义的带标签的图形适配器？

Answer 1

可悲的是，这是labeled_graph 适配器的另一个限制¹。
真正的问题是适配器将原始顶点描述符存储在其内部属性(map)中。在 vecS 的情况下vertex-container-selector，顶点描述符是一个从0开始的整数[0, num_vertices(g)) ，它很高兴地转移到图的相同拷贝。
然而，对于基于节点的顶点容器选择器( listS 、 setS 、...)，顶点描述符是一个不透明的句柄(基本上是一个指针类型双关语到 void* )。显然，这些不会转移到图的拷贝。更糟糕的是，当在拷贝上使用顶点描述符时，您会得到 Undefined Behaviour .如果拷贝的源仍在附近，您可能最终会从 访问顶点存储。错误的图表 .如果图表已经被破坏，你会得到任何其他行为，如果你幸运地崩溃了。
如何解决
恐怕你不能。
我们可以使用 boost::copy_graph在基础 labeed_graph.graph() .我们需要提供一个外部 vertex_index属性图。
然而，这给我们留下了实际复制标签的无法解决的任务。这是无法解决的，因为有 没办法迭代标签，或从顶点描述符中提取它们。而且我们不能添加功能——甚至不能通过子类化——因为 map_type _map;是 private .
让我们无所事事
当然，如果我们可以更改 boost/graph/labeled_graph.hpp声明 friend :

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

我们可能会实现类外的功能:

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

一个微妙的选择是我们将参数拆分到底层图和它们的标签映射中，这样我们就不必指定过多的 friend 模板。为什么？
这是因为我们需要根据标签映射的类型进行调度(如前所述，这将根据顶点索引的性质采取各种形式):

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

有了这些，我们可以将各种重载实现为:

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

请注意，这

注意通用(它应该与 vecS ， listS 等一起使用)

不注重效率

不支持 C++03 编译

现场演示
Live On Wandbox

文件 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>();
 }

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

 // ...

文件 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

打印

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

¹ 见 previous导致 barriers 的剧集