问题标签 [boost-graph]

我正在广泛使用 adjacency_list< vecS, vecS, bidirectionalS ... >。我一次加载了这么多图表，以至于内存成为问题。我正在进行静态程序分析，并将反汇编二进制文件的调用图和流程图存储在升压图中。因此我可以拥有数万个函数==流程图和一个巨大的调用图。我真的很想在仍然使用 BGL 的同时减少图表的内存使用量。

由于我的图表在加载后是静态的，并且事先知道边和顶点数，我看到了巨大的优化潜力。例如，我想为单个图的所有顶点/边分配一个缓冲区，并让图只将索引存储到该缓冲区中。

更多问题：
1）使用顶点和边属性的内存开销是多少？我有很多。
2）是否有可能说服 BGL 使用收缩来适应成语？据我了解，邻接列表使用 push_back 来添加边。是否可以通过将结果向量与自身的副本交换来减少内存使用？也许通过复制整个图表？
3) 是否可以在 BGL 中使用提升池分配器？据我所知，BGL 目前执行了大量的小分配——出于空间和运行时效率的原因，我真的很想避免这种情况。

是否有人已经构建了针对内存使用优化的 BGL 版本？我应该尝试使用现有的图形结构并使用自定义分配器或类似的东西来增加它，还是编写我自己的实现并尝试保持与 BGL 的接口兼容以便我可以继续使用它的算法？

最好的祝福，

I'm trying to decide between going with a pre-made graph/node network library or to roll my own.

I'm implementing some graph search algorithms which might require some significant customization to the class structure of the node and/or edges.

The reason I'm not sure what to do is that I'm unsure if customization of a pre-made might be more expensive/trouble than making my own in the first place. I'm also curious, but less so, of the performance trade-offs.

Is there anyone out there have direct experience with using one of the libraries out there and have advice based on a success or failure story? I want to hear the worst so that whatever I chose, I know what I'm getting into.

There are only two that I've found in my search so far: The Boost Graph Library (BGL) and GOBLIN. Specific advice on either of these, or suggestions for others is greatly appreciated as well. BGL seems pretty damn arcane. Is it worth struggling through?

假设我找到了符合我的条件的节点，我需要停止搜索。

我应该如何从访问者内部修改顶点的捆绑属性？

我想使用简单的下标图形的方法，但是传递给访问者的图形参数是 const，因此编译器不允许更改。

我可以在访问者中存储对图表的引用，但这似乎很奇怪。

我需要搜索 DAG 图，但我不想在看到所有其他节点都指向它的定向链接之前越过一个节点。

是否存在处理这种特殊情况的现有算法，深度优先搜索和呼吸优先搜索不适用于这种遍历顺序。

IE：

我不想在看到 B 和 C 之前到达 D。

我正在开发一个必须创建图形的软件（使用 boost::adjacency_list）。顶点的增量插入需要非常长的时间。直到现在，我还没有解决这个问题，因为使用 STLport 使这个问题消失了。我现在已将我的工作迁移到 Visual Studio 2008，但不能花时间继续使用 STLport（很难使用 STLport 维护 boost 库的编译）。

我宁愿不将图形顶点存储在列表中，因为我经常使用顶点标识符，就好像它们是整数一样。

我还有什么其他选择可以解决这个问题（在调试和发布模式下）？

我正在寻找一种通过使用键而不是顶点引用本身来访问顶点属性的方法。例如，如果我有

而不是使用

我想拥有

是否存在即用型机制？

我正在研究 boost 图形库的使用，以便将它们应用于我想到的各种网络问题。

在示例中，我一直在查看图形边缘值（“权重”）始终初始化为整数，例如在这些Bellman-Ford和Kruskal算法中，例如：

我的问题是，如果我尝试将权重更改为两倍，我会收到一堆关于转换等的警告消息，到目前为止我还无法弄清楚如何克服。

有没有人看到解决这个问题的方法？

我有一个带有类型边缘的巨大图（即带有类型属性的边缘）。说

边的“类型”是 edge_prop 的成员，并且在 {A,B,C,D} 中有一个值，
我想运行广度优先搜索算法，只考虑 A 或 B 类型的边。
你会怎么做去做？

我对 C++ 模板生疏了，我正在使用 boost 图形库（一个致命的组合）。我在网上搜索过，找不到任何关于如何采用自定义图形结构并将其足够适合 BGL（增强图形库）的直接说明，我可以使用增强图形遍历算法。有足够熟悉图书馆的人来帮助我吗？

编辑：所以，我遇到的主要问题是在哪里可以找到将任意图映射到 BGL 图的总要求的来源。我对模板真的很陌生，所以我很难阅读 BGL 的规范/示例。也许我应该寻找模板的一般来源？