基于boost multi_index_container的有向图反转低复杂度实现方案问询

注意： 我修改了问题标题，因为以下文本和最小示例和我最初的问题匹配度较低，原标题为"Interchanging two similar indices in a boost multi-index container"

我正在实现支持自环和重边的有向图，顶点为编号形式，需求是可按源顶点或目标顶点排序查看边。目前我使用boost::multi_index_container存储所有边，配置了两个有序、非唯一的成员键提取器：source和target（我认为BGL无法直接实现该需求，如果可以请告知）。

除此之外我还需要反转图的所有边（或生成边全部反转的新图）。目前我的实现方式是遍历原图所有边，将每条边反转后插入新容器，但该方式下boost至少要为其中一个索引重新计算每条边的所有信息，时间复杂度为边数的拟线性。我想知道是否有方法可以让boost复用原有边已计算好的source和target相关信息来放置反转后的边？

最小示例 #

#include <iostream>
#include <vector>

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/member.hpp>

// 有向边定义
class Edge {
 public:
  Edge(int s, int t) :
    source(s),
    target(t)
  { }
  
  int source;
  int target;
  
  // 用于输出展示
  friend std::ostream& operator<<(std::ostream& os, const Edge& edge) {
    os << "(" << edge.source << "," << edge.target << ")" << std::flush;
    return os;
  }
};

// 多索引容器的标签
struct Source { };
struct Target { };

// 支持自环、重边的有向图，可按源顶点或目标顶点排序查看边
using Directed_graph = boost::multi_index_container<
  Edge,
  boost::multi_index::indexed_by<
    boost::multi_index::ordered_non_unique<
      boost::multi_index::tag< Source >,
      boost::multi_index::member< Edge, int, &Edge::source >
    >,
    boost::multi_index::ordered_non_unique<
      boost::multi_index::tag< Target >,
      boost::multi_index::member< Edge, int, &Edge::target >
    >
  >
>;

// 反转图的所有边，可原地操作或生成新副本
// 问题：是否有更优的实现方式？
Directed_graph reverse_graph(Directed_graph& graph) {
  Directed_graph reversed_graph;
  for (const auto& edge : graph) {
    reversed_graph.insert(Edge(edge.target, edge.source));
  }
  return reversed_graph;
}

// 打印图的所有边
void output(const Directed_graph& graph) {
  for (const auto& edge : graph) {
    std::cout << edge << " " << std::flush;
  }
  std::cout << std::endl;
}

int main() {
  Directed_graph G;
  
  G.insert(Edge(0, 1));
  G.insert(Edge(1, 2));
  G.insert(Edge(1, 3));
  G.insert(Edge(3, 0));
  
  std::cout << "Directed graph:" << std::endl;
  output(G);
  
  std::cout << "Reversed directed graph:" << std::endl;
  Directed_graph rG = reverse_graph(G);
  output(rG);
  
  return 0;
}

使用gcc -std=c++11编译后得到如下输出：

Directed graph:
(0,1) (1,2) (1,3) (3,0) 
Reversed directed graph:
(0,3) (1,0) (2,1) (3,1) 

问题总结 #

是否有方法可以实现低于拟线性复杂度的reverse_graph函数？最优目标是常数时间复杂度。

一个可能的优化方向是支持同时携带多个索引的插入提示函数，但我尚未找到对应实现，且就算有该函数我也不确定能否达到常数时间复杂度。

注意： 仅为技术细节说明，上述Directed_graph没有完整编码有向图，还需要记录总顶点数，该问题在实际代码中已处理，不会影响示例逻辑。

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