修改Boost拓扑排序以同步获取入顶点拓扑序列的技术咨询

选项1：通过Visitor传入数据结构（推荐） #

Boost图算法的Visitor模式就是为遍历过程注入自定义逻辑设计的，完全匹配你的需求场景。

• 步骤1：定义自定义Visitor
  继承boost::default_topological_sort_visitor，重写**finish_vertex**回调（比discover_vertex更合适：此时当前顶点的所有前驱已完成拓扑排序，收集的入顶点序列天然符合拓扑顺序）：

  #include <boost/graph/topological_sort.hpp>
  #include <vector>
  #include <map>
  
  template <typename Graph, typename VertexInListMap>
  struct InTopologyVisitor : public boost::default_topological_sort_visitor {
      InTopologyVisitor(VertexInListMap& in_lists) : m_in_lists(in_lists) {}
  
      template <typename Vertex, typename Graph>
      void finish_vertex(Vertex v, const Graph& g) {
          typename Graph::in_edge_iterator ei, ei_end;
          // 遍历当前顶点的所有入边，收集前驱顶点
          for (boost::tie(ei, ei_end) = in_edges(v, g); ei != ei_end; ++ei) {
              Vertex u = source(*ei, g);
              m_in_lists[v].push_back(u);
          }
      }
  
  private:
      VertexInListMap& m_in_lists;
  };
  

• 步骤2：执行拓扑排序并收集数据
  提前准备存储每个顶点入序列的映射（若顶点是整数类型，用std::vector<std::vector<Vertex>>效率更高），传入Visitor后调用拓扑排序：

  // 假设g是你的DAG图，Vertex是图的顶点类型
  std::vector<Vertex> topo_order;
  std::map<Vertex, std::vector<Vertex>> vertex_in_topology;
  
  InTopologyVisitor<Graph, decltype(vertex_in_topology)> vis(vertex_in_topology);
  boost::topological_sort(g, std::back_inserter(topo_order), boost::visitor(vis));
  

  执行后，vertex_in_topology会按顶点分组存储对应的入顶点拓扑序列。

选项2：使用额外的OutputIterator（适合扁平化场景） #

如果只需要将入顶点关联关系输出为扁平化序列，可采用此方式：

• 步骤1：定义输出型Visitor

  template <typename OutputIter>
  struct InTopoOutputVisitor : public boost::default_topological_sort_visitor {
      InTopoOutputVisitor(OutputIter out) : m_out(out) {}
  
      template <typename Vertex, typename Graph>
      void finish_vertex(Vertex v, const Graph& g) {
          typename Graph::in_edge_iterator ei, ei_end;
          for (boost::tie(ei, ei_end) = in_edges(v, g); ei != ei_end; ++ei) {
              // 写入（当前顶点，前驱顶点）的关联对
              *m_out++ = std::make_pair(v, source(*ei, g));
          }
      }
  
  private:
      OutputIter m_out;
  };
  

• 步骤2：调用拓扑排序

  std::vector<std::pair<Vertex, Vertex>> in_topo_pairs;
  InTopoOutputVisitor<decltype(std::back_inserter(in_topo_pairs))> vis(std::back_inserter(in_topo_pairs));
  boost::topological_sort(g, std::back_inserter(topo_order), boost::visitor(vis));
  

  此方式适合不需要按顶点分组，仅需扁平化存储入顶点关联关系的场景。

关键注意事项 #

• 回调函数选择：绝对避免用discover_vertex，此时顶点的入边尚未处理，收集的前驱无法保证拓扑顺序；finish_vertex是顶点所有后继处理完成后触发，前驱必然已完成拓扑排序，顺序可靠。
• 数据结构优化：若顶点为连续整数，用std::vector<std::vector<Vertex>>替代std::map，直接以顶点索引为下标，性能更优。
• 版本兼容：Boost 1.83的topological_sort完全支持自定义Visitor扩展，符合官方设计规范。

内容的提问来源于stack exchange，提问作者terrabyte