首页 文章

Boost Graph Library - 具有N个边缘/顶点的图形

提问于
浏览 次
1

我正在使用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);

或者另一种利用图表规律性来节省记忆的方法？

谢谢你的建议！

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

c++ vector boost boost-graph

1 回答

  • 2

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

    例如，Boost图形库中的 grid_graph<> 模型（如果我没记错的话）根本不使用顶点存储，并且确实准确地知道所有节点之前将存在多少边缘 .

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

    还要考虑使图形内存映射，这样您就不必完全“加载”它，或者甚至必须能够在任何给定时间将其装入RAM中（但要注意访问时间，这将取决于访问模式和如何布局数据） .

    回复于

相关问题