使用自定义比较器和额外参数设置Typedef

Question

我有一个围绕升压有向图的包装器。每个顶点都有一个整数 id 字段，我想在 typedef 中编写一组按 id 排序的顶点描述符。本质上我有：

struct VertexData {
  int id;
};
typedef adjacency_list<vecS, vecS, bidirectionalS, VertexData> DirGraph;

typedef graph_traits<DirGraph>::vertex_descriptor GraphVd;

class GraphWrapper {
public:
  DirGraph g;
}

我想补充：

typedef std::set<GraphVd> VdSet;

并按

g[vd].id

（即该顶点的 id）排序。我知道 STL 集有自定义比较器，您可以在其中传递结构，但我正在努力访问包装器中的

DirGraph g

变量并对其进行 typedef。

当我尝试做类似的事情时

struct VdCmp {
  VdCmp(GraphWrapper &g) : g(g){};
  bool operator()(const GraphVd &vd1, const GraphVd&vd2) { return g[vd1].id > g[vd2].id }
private:
DirGraph g;
}

那么我如何 typedef 它以在头文件中使用？我必须创建一个

VdCmp

实例，它的构造函数需要

GraphWrapper

，而且我不想在头文件中创建类。

Answer 1

邻接列表允许大量自定义（例如自定义邻接列表存储）。然而，您期望的定制并不是其中的一部分。

实际的顶点存储（决定全局顶点的枚举顺序）是实际上一个存储内部节点的不透明集合 - 恰好包含您想要排序的属性包。如果您使用

setS

作为容器选择器，并且始终使用

std::set<void*, std::less<void*> >

，则无法覆盖它。

您可以使用我最近描述的技巧来近似您想要的行为：如何使用 boost graph 遍历平面图（代表一棵树）以模拟在图的边缘行走

如果您不介意了解未记录的实现细节，您甚至可以使用自己的谓词进行排序

m_vertices

：

住在Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <ranges>
namespace R = std::ranges;

struct VertexData {
    int id;

    constexpr bool operator<(VertexData const& other) const { return id < other.id; }
};

using DirGraph = boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, VertexData>;
using GraphVd  = DirGraph::vertex_descriptor;

int main() {
    DirGraph g;

    GraphVd v1 = add_vertex(VertexData{100}, g);
    GraphVd v2 = add_vertex(VertexData{90}, g);
    GraphVd v3 = add_vertex(VertexData{80}, g);
    GraphVd v4 = add_vertex(VertexData{180}, g);
    /*GraphVd v5 =*/ add_vertex(VertexData{-42}, g);

    add_edge(v1, v2, g);
    add_edge(v1, v3, g);
    add_edge(v2, v4, g);
    add_edge(v2, v1, g);

    print_graph(g, get(&VertexData::id, g), std::cout << " === Before:\n");

    g.m_vertices.sort([&g](GraphVd a, GraphVd b) { return g[a].id < g[b].id; });

    print_graph(g, get(&VertexData::id, g), std::cout << "\n === Sorted vertices:\n");

    for (auto v : boost::make_iterator_range(vertices(g)))
        R::sort(g.out_edge_list(v), std::less{},
                [&g](auto const& out) { return g[out.get_iter()->m_target].id; });

    print_graph(g, get(&VertexData::id, g), std::cout << "\n === Sorted adjacencies:\n");
}

印刷

 === Before:
100 --> 90 80 
90 --> 180 100 
80 --> 
180 --> 
-42 --> 

 === Sorted vertices:
-42 --> 
80 --> 
90 --> 180 100 
100 --> 90 80 
180 --> 

 === Sorted adjacencies:
-42 --> 
80 --> 
90 --> 100 180 
100 --> 80 90 
180 --> 

注意事项

以上假设您知道自己在做什么。例如。如果您使用这种方法并将

vecS

作为顶点容器选择器，那么如果在排序之前边已经存在，您将更改图拓扑。选择

listS

是为了确保排序中顶点的参考稳定性。

此外，该行为将来可能会悄然中断，因为这是使用未记录的接口。

在构建图表之前“仅”对顶点进行排序可能是值得的，以避免这些陷阱/限制。