图形增量构建的性能问题

Question

我正在开发一个软件，需要使用boost::adjacency_list创建图表。增量插入顶点非常耗时，此前我没有解决这个问题，因为使用STLport可以让这个问题消失。现在我将工作迁移到了Visual Studio 2008，但是无法继续使用STLport（编译使用STLport的boost库难以维护）。

我不想将图形顶点存储在列表中，因为我经常使用顶点标识符作为整数使用。

除了使用列表之外，我还有哪些选项来解决这个问题（在调试和发布模式下）?

- user259233

Answer 1

您是否事先知道有多少节点？如果是，这将大大缩短图形创建时间。

例如，对于一个具有10,000个节点的图形：

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, > Graph_t;
Graph_t g(10000);

- Tristram Gräbener

---

我可以估算一个上限值。我试图用这个值初始化我的图表，但这又花费了很长时间。不仅在图表创建时需要耗费时间，在图表处理（例如清空）时也同样如此。 - user259233

你怎么称呼“非常长”？ 仅添加顶点需要很长时间，还是包括边缘（在这种情况下，尝试使用边缘列表来处理边缘）也需要很长时间？ 要清空图形，可能创建一个新图形会更容易。 - Tristram Gräbener

Answer 2

template<class OutEdgeListS = vecS, class VertexListS = vecS,.....> adjacency_list;

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

• 对于 vecS 和 listS（使用 push_back() 实现），add_vertex() 的摊销常数时间都是恒定的。然而，当 VertexListS 类型为 vecS 时，这个操作的时间偶尔会很长，因为向量将被重新分配并且整个图将被复制。
• 对于 listS，remove_vertex() 是恒定时间；对于 vecS，它是 O(V + E)。

如上所述，默认值都是 vecS。因此，如果您使用具有更高空间开销的 listS 作为 VertexListS，则可以期望在时间上获得一些改进。

- lalitm

---

Virginie无法使用listS（如问题所述），因为其他地方的代码中使用标识符作为整数。因此，VertexListS必须保持其默认值vecS。 - Benoît

Answer 3

你有没有尝试过对执行时间较长的代码进行分析？你可能会惊讶地发现一些意外的问题（如隐式转换/转换构造函数、比预期更多的比较、数据复制等）。此外，分析还可以让你了解插入算法中哪个部分需要花费大量时间以及纠正它的可能性（例如：更改adjacency_list构造函数参数）。

- Mark B

Answer 4

“我宁愿不将图形顶点存储在列表中，因为我经常将顶点标识符用作整数。”

也许您仍然可以使用列表。只需将顶点索引声明为属性（请参阅http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/using_adjacency_list.html#sec:adjacency-list-properties）。但是，如果删除一个顶点，则可能必须重新编号顶点。此外，如果添加顶点，则必须分配其顶点索引值。”

- J.I.Perotti

---

这并不能神奇地让你通过顶点索引来引用顶点（你需要某种查找到顶点描述符的方式）。 - sehe