Boost Graph Library - 正好有 N Edges/Vertex 的图

Question

我正在使用 BGL 邻接表来描绘一个非常规则的图，我确切地知道每个顶点都有 N 条边。

这是我的图表定义：

typedef boost::vecS OutEdgeList;
typedef boost::vecS VertexList;
typedef boost::no_property GraphProperties;
typedef boost::vecS EdgeList;

// Graph definition
typedef boost::adjacency_list<
            OutEdgeList,
            VertexList,
            boost::undirectedS,
            VertexProperties,
            EdgeProperties,
            GraphProperties,
            EdgeList
            > Graph;
Graph g;

我使用 vector/vecS 来存储连接，我想通过天真地调用 boost::add_edge 列表将根据需要像向量一样调整大小，大约是其最后大小的两倍。

该图使用了大量 RAM(~12GiB)，当假设 N=9 为 16 个连接保留时，我不想要向量。

有没有像

这样的预初始化邻接列表容器的内存高效方法

for(auto edgesOfVert:edgesOfVerts)
    edgesOfVert.reserve(N);

或者其他利用图形的规律性来节省内存的方法？

感谢您的任何建议！

已编辑：作为一种可能的解决方案，我发现了但我同意 sehe 的观点并考虑保留适量的边缘不雅，因为它试图强制使用不是为特定的数据结构我需要它的任务

Answer 1

真正的解决方案是不使用 boost::adjacency_list。相反，调整您自己的数据结构来模拟您需要的图形概念。

例如，Boost Graph Library 中有一个 grid_graph<> 模型（如果我没记错的话）根本不使用顶点存储，并且确实确切地知道所有顶点之间将存在多少条边提前节点。

您仍然可以使用适用于建模图概念的所有图算法（grid_graph<> 模型 Incidence Graph、Adjacency Graph、Vertex List Graph、Edge List Graph , Bidirectional Graph, Adjacency Matrix).

还可以考虑映射图形内存，这样您就不必 "load it" 完全，甚至不必在任何给定时间将其放入 RAM（不过要注意访问时间，它会全部取决于访问模式和数据布局方式）。

Boost Graph Library - 正好有 N Edges/Vertex 的图

Boost Graph Library - Graph with exactly N Edges/Vertex

c++

vector

boost

boost-graph