4

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

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

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

4

4 回答 4

2

你事先知道你有多少个节点吗？如果是，这将大大减少图形创建时间。

例如对于具有 10 000 个节点的图：

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, > Graph_t;
Graph_t g(10000);
于 2010-01-26T13:42:19.113 回答
1 
template<class OutEdgeListS = vecS, class VertexListS = vecS,.....> adjacency_list;

OutEdgeListS 和 VertexListS 的选择对通过 boost adjacency_list 实现的图算法的时间复杂度影响很大。

  • add_vertex() 是 vecS 和 listS 的摊销常数时间（用 push_back() 实现）。但是，当 VertexListS 类型为 vecS 时，此操作的时间有时会很长，因为将重新分配向量并复制整个图。
  • remove_vertex() 是 listS 的常数时间和 vecS 的 O(V + E) 时间。

正如您在上面看到的，两者的默认值都是 vecS。因此，如果您将 listS 用于 VertexListS（具有更高的空间开销），您可以期待一些时间改进

于 2010-01-26T14:32:39.710 回答
1

您是否真的尝试过分析需要很长时间才能执行的代码？您可能会感到惊讶并发现一些意想不到的东西（隐式转换/转换构造函数、比预期更多的比较、数据复制等）。此外，分析可能会让您了解插入算法的哪一部分需要很长时间以及纠正它的可能性（例如：更改 adjacency_list 构造函数参数）。

于 2010-02-11T21:52:13.153 回答
0

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

也许您毕竟可以使用 listS 。只需将顶点索引声明为属性（检查http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/using_adjacency_list.html#sec:adjacency-list-properties）。但是，如果您删除一个顶点，您可能需要重新编号顶点。此外，如果添加顶点，则必须为其指定顶点索引值。

于 2011-03-06T06:25:53.617 回答