复制 Boost 标记图

Question

我希望能够将带标签的图形适配器与底层邻接表一起复制。

以下代码片段与本答案中的大部分相同：，除了邻接表使用 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 顶点容器选择器的情况下，顶点描述符是一个从 0 开始的整数 [0, num_vertices(g))，它很乐意转移到图的相同副本。

但是，对于基于节点的顶点容器选择器（listS、setS、...），顶点描述符是一个不透明的句柄（基本上是一个指向 void*).显然，这些不会转移到图形的副本。更糟糕的是，当在副本上使用顶点描述符时，您会得到 Undefined Behaviour。如果副本的源仍在附近，您可能最终会从 错误的图 访问顶点存储。如果图形已经被破坏，你会得到任何其他行为，如果你幸运地崩溃的话。

如何解决

恐怕你不能。

我们可以在基础 labeed_graph.graph() 上使用 boost::copy_graph。我们需要提供外部 vertex_index 属性地图。

然而，这给我们留下了无法解决的实际复制标签的任务。这是无法解决的，因为 没有办法 迭代标签，或从顶点描述符中提取它们。而且我们无法添加功能 - 甚至不能通过 subclassing - 因为 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);

我们可能会在 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;
}

一个微妙的选择是我们将参数拆分为底层图形及其标签映射，这样我们就不必指定过多的朋友模板。为什么？

那是因为我们需要根据标签图的类型进行调度（如前所述，根据顶点索引的性质，它会采取各种形式）：

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 episodes that lead to

复制 Boost 标记图

Copy Boost Labeled Graph

c++

boost

boost-graph

如何解决

让我们不惜一切代价

现场演示