Boost.Graph如何合并两个顶点/合约边缘

3 回答

• -1

  半生不熟的快速概念验证

  您可以在 adjacency_list 定义的图表上使用 add_edge() 和 remove_vertex()

  #include <iostream>
  #include <iterator>
  #include <boost/graph/adjacency_list.hpp>
  
  using V = unsigned;
  using E = std::pair<V, V>;
  using G = boost::adjacency_list<boost::vecS, boost::vecS>;
  
  void print_graph(G const& g)
  {
      auto vs = boost::vertices(g);
      for (auto vit = vs.first; vit != vs.second; ++vit) {
          auto neighbors = boost::adjacent_vertices(*vit, g);
          for (auto nit = neighbors.first; nit != neighbors.second; ++nit)
              std::cout << "{" << *vit << "," << *nit << "}" << ", ";
      }
      std::cout << "\n";
  }
  
  void contract_vertices(V b, V a, G& g)
  {
      auto be = boost::adjacent_vertices(b, g);
      for (auto beit = be.first; beit != be.second; ++beit)
          add_edge(a, *beit, g);
      remove_vertex(b, g);
  }
  
  int main()
  {
      // named vertices
      auto const A = V { 1 };
      auto const B = V { 2 };
  
      // construct the graph
      auto e = std::vector<E> { { A, 3 }, { B, 4 } };
      auto g = G { std::begin(e), std::end(e), 4 };
  
      print_graph(g);
      contract_vertices(B, A, g);    
      print_graph(g);
  }
  

  Live example 打印

  {1,3}，{2,4}，{1,2}，{1,3}，

  输出不是您所期望的，因为顶点的标记也会更新以反映 B 的删除，这会导致节点3和4现在标记为2和3 .

  库质量代码的要求

  用于收缩顶点的通用库质量算法 u 和 v 通常应至少考虑以下角落情况

  • 删除（u，v）和（v，u）边缘;

  • 将所有u和v外边缘与公共目标合并;

  • 将所有u和v in-edge与公共源合并;

  • 将剩余的u外边缘移动到v;

  • 将你的其余边缘移到v;

  Boost.Graph为此类操作提供了所有必需的基元： in_edges() ， out_edges() ， add_edge() ， clear_vertex() ， remove_vertex() . 对于无向图，这些项中的一些可以在一个步骤中完成，而对于有向图，通常需要两个步骤 .

  除了这些算法步骤之外，还应该定义合并或移动边缘意义的语义 . 例如 . 他们的 property 会发生什么？这类似于例如合并两家公司：联合公司应该以何种名义运营？

  为什么Boost.Graph（还）没有提供contract_vertices（）

  TL;DR 我不知道 . 但我可以推测 . 主要是，应该指定一个假定的 contract_vertices() 的接口 . 除了要约束的两个顶点以及它们所属的图形类型之外，还应该在边缘属性上定义合并和移动操作 . 从理论上讲，应该可以使用适用于通用算法的模板参数来完成此操作 .

  回复于 2024-05-06T12:28:32+08:00
• -1

  手动执行，您应手动删除每个 b 边，而不是顶点：

  void collapse_vertices(V b, V a, G& g)
  {
      auto be = boost::adjacent_vertices(b, g);
      for (auto beit = be.first; beit != be.second; ++beit)
      {
          add_edge(a, *beit, g);
          remove_edge(b, *beit, g);
      }
  }
  

  给出你想要的 {1,3}, {1,4}, .

  我不知道为什么它不包括在我的知识中（在我的知识中），但是这个功能是什么呢 .

  回复于 2024-05-06T12:28:32+08:00
• 8

  库中没有通用函数，因为通用函数不可能知道在“极端情况”中需要做什么 . 如果顶点X与顶点A和B都有边缘怎么办？该函数是否应该删除X-A，还是应该删除X-B并将X-A移动到X-B？如果从X到A的边（被删除的顶点）具有必须保留或修改的属性，该怎么办？只有应用程序代码知道在删除或移动边时如何处理属性

  正如qble所暗示的那样，“委派”这些决定毫无意义 . 如果关于如何处理已删除边的属性的决定被“委托”给应用程序代码，则应用程序代码将必须查找并循环必须删除的边 . 所以它必须重复与泛型函数相同的工作 . 一旦它完成了每个被删除边的属性，并且不打扰调用泛型函数，它也可以进行边删除本身 .

  回复于 2024-05-06T12:28:32+08:00