在保持对按源或目标顶点排序的边的访问的同时反转图形

Question

注意：我更改了问题的标题，因为事实证明以下文字和最小示例不能很好地反映我原来的问题。最初的标题是“在 boost multi-index 容器中交换两个相似的索引”

我正在实现有向图（带有循环和多边），其顶点已编号，我们可以在其中查看按源顶点或目标顶点排序的边。为此，我使用 boost::multi_index_container 来存储每条边，其中有两个有序的 non-unique 成员键提取器：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>

// A directed edge
class Edge {
 public:
  Edge(int s, int t) :
    source(s),
    target(t)
  { }
  
  int source;
  int target;
  
  // For display purposes
  friend std::ostream& operator<<(std::ostream& os, const Edge& edge) {
    os << "(" << edge.source << "," << edge.target << ")" << std::flush;
    return os;
  }
};

// Tags for the multi-index container
struct Source { };
struct Target { };

// Directed graphs with loops and multiple edges, with the possibility of
// viewing the edges sorted by source or by 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 >
    >
  >
>;

// Reverse all the edges of the graph, either in place or creating a copy
//
// QUESTION: Is there a better way to do this?
//
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;
}

// Print every edge of the 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并没有完全编码有向图，因为我们还需要知道总共有多少个顶点.这在实际代码中不是问题，我希望它不会妨碍上面的例子！

Answer 1

首先让我提出一些简化：Live On Coliru

你的图是边列表。您已经可以在 BGL 中直接对这些进行建模：https://www.boost.org/doc/libs/1_77_0/libs/graph/doc/edge_list.html

所以你可以使用：

Live On Coliru

#include <iostream>
#include <list>

#include <boost/graph/edge_list.hpp>

using Vertex = int;
using Edge   = std::pair<Vertex, Vertex>;
using Edges  = std::list<Edge>; // iterator stability like multi-index

using Directed_graph = boost::edge_list<Edges::iterator>;

// Print every edge of the graph
template <typename Graph>
void output(const Graph& g)
{
    for (auto e : boost::make_iterator_range(edges(g))) {
        std::cout << "(" << source(e, g) << "," << target(e, g) << ") ";
    }
    std::cout << std::endl;
}

int main()
{
    Edges EE{{0, 1}, {1, 2}, {1, 3}, {3, 0}};
    Directed_graph G(begin(EE), end(EE));

    std::cout << "Directed graph:" << std::endl;
    output(G);
}

打印

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

多索引混合

假设您可能出于某种原因想要在现有容器之上工作，您可以进行少量更改（尽管需要 std::pair 兼容性）：

Live On Coliru

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

using Vertex  = int;
using VertexP = std::pair<Vertex, Vertex>;

// A directed edge
struct Edge : VertexP {
    using VertexP::VertexP;
    /*
     * // For display purposes
     * friend std::ostream& operator<<(std::ostream& os, const Edge& e) {
     *     return os << "(" << e.first << "," << e.second << ")";
     * }
     */
};

// Tags for the multi-index container

// Directed graphs with loops and multiple edges, with the possibility of
// viewing the edges sorted by source or by target.
using Edges = boost::multi_index_container<
    Edge,
    boost::multi_index::indexed_by<
        boost::multi_index::ordered_non_unique<
            boost::multi_index::tag<struct Source>,
            boost::multi_index::member<VertexP, Vertex, &Edge::first>>,
        boost::multi_index::ordered_non_unique<
            boost::multi_index::tag<struct Target>,
            boost::multi_index::member<VertexP, Vertex, &Edge::second>>>>;

using Directed_graph = boost::edge_list<Edges::iterator>;

// Print every edge of the graph
template <typename Graph>
void output(const Graph& g)
{
    for (auto e : boost::make_iterator_range(edges(g))) {
        std::cout << "(" << source(e, g) << "," << target(e, g) << ") ";
    }
    std::cout << std::endl;
}

int main()
{
    Edges EE{{0, 1}, {1, 2}, {1, 3}, {3, 0}};
    Directed_graph G(begin(EE), end(EE));

    std::cout << "Directed graph:" << std::endl;
    output(G);
}

反向

不过，我想你可能已经想到了多索引mainly/only，因为它的可逆性。 BGL 有 reversed_graph 个适配器。这允许您删除 - 通常 inefficient/inflexible - 模型的 EdgeList 用于存储。

最流行的 BGL 模型是 AdjacencyList，它可以配置为双向访问，所以 reverse adaptor is optimal:

The construction of the reverse_graph is constant time, providing a highly efficient way to obtain a transposed view of a graph.

Live On Compiler Explorer

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/reverse_graph.hpp>
#include <boost/graph/graph_utility.hpp>
#include <iostream>

using Directed_graph =
    boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS>;

int main()
{
    Directed_graph g;
    for (auto [s, t] : {std::pair{0, 1}, {1, 2}, {1, 3}, {3, 0}})
        add_edge(s, t, g);

    print_graph(g, std::cout << "Directed graph:\n" );
    print_graph(make_reverse_graph(g), std::cout << "Reversed graph:\n" );
}

版画

Directed graph:
0 --> 1
1 --> 2 3
2 -->
3 --> 0
Reversed graph:
0 --> 3
1 --> 0
2 --> 1
3 --> 1

当然，上面的output模板函数仍然适用于这个图形模型。

奖励：Bimap

我刚刚发现您可能会喜欢另一个容器：Boost Bimap

看到了Live On Coliru

#include <boost/bimap.hpp>
#include <boost/bimap/multiset_of.hpp>
#include <boost/graph/edge_list.hpp>
#include <iostream>

namespace bb = boost::bimaps;
using Vertex = int;
using Edges  = bb::bimap<bb::multiset_of<int>, bb::multiset_of<int>>;

using Directed_graph = boost::edge_list<Edges::left_map::iterator>;
using Reverse_graph = boost::edge_list<Edges::right_map::iterator>;

// Print every edge of the graph
template <typename Graph>
void output(const Graph& g)
{
    for (auto e : boost::make_iterator_range(edges(g))) {
        std::cout << "(" << source(e, g) << "," << target(e, g) << ") ";
    }
    std::cout << std::endl;
}

int main()
{
    Edges ee{};
    for (auto [s, t] : {std::pair{0, 1}, {1, 2}, {1, 3}, {3, 0}})
        ee.insert({s, t});

    {
        auto& vw = ee.left;
        Directed_graph g(vw.begin(), vw.end());

        std::cout << "Directed graph:" << std::endl;
        output(g);
    }

    {
        auto& vw = ee.right;
        Reverse_graph r(vw.begin(), vw.end());

        std::cout << "Reversed graph:" << std::endl;
        output(r);
    }
}

这也打印

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

在保持对按源或目标顶点排序的边的访问的同时反转图形

Reversing a graph while maintaining access to edges sorted by source or target vertex

c++

boost

boost-graph

boost-multi-index

多索引混合

反向

奖励：Bimap