问题标签 [boost-graph]

我正在尝试从一组 pair(int,int) 边（其中每个 int 代表一个顶点索引）中定义一个具有无向边的图。每个这样的边缘都有自己的索引。

问题是我希望图的内部顶点索引与原始顶点索引一致。我还希望能够从边缘描述符中提取原始边缘索引。

从http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/using_property_maps.html（外部属性部分）我知道我应该使用以下图形类型：

不幸的是，没有关于如何使用 edge_index_t 属性的解释。

很明显，我可以只使用 map(pair(int,int),int) 但我正在寻找一个更优雅的面向提升的解决方案。

谢谢你，基里尔

我不太清楚为什么在按钮单击处理程序中使用时创建的 edge_array 显示为未定义的标识符还在 cli 管理的东西的混合中使用 boost 非托管代码任何帮助将不胜感激

我目前正在处理图形实现的性能问题。

使用的技术

它是用 C++ 编程的。目前，图是通过 BGL 实现的。

关于图表

托管图是动态且无向的。它有两种结构：很多完全子图和很少的单边。唯一需要的信息是顶点的直接邻域。

问题陈述

一开始，完整的子图很小（大约 10 个顶点）和众多（大约 13k）。BGL 的邻接表实现是完美的。但是现在，它被要求管理几个 5000 个顶点的子图。这意味着 5000x5000 边缘。现在时间和空间上的表现都很差。

被拒绝的解决方案

我的第一个想法是使用 BGL 提供的邻接矩阵实现。但它不允许动态图。为了解决这个限制，有两种解决方案：为动态图提供邻接矩阵的新实现或在静态图中使用可用顶点池。经过反思，我认为这不是一个好主意：空间复杂度仍然是VxV/2。

最终解决方案和问题

所以，这是我的最终解决方案：不要使用 BGL，实现顶点袋来表示完整的子图（不需要边）并直接连接几个单边的顶点。通过这样做，最大子图的空间复杂度下降到它的顶点数，大约为 5000。

1. 你认为最后一个解决方案是好的吗？
2. 如果没有，我可以使用哪种实现？为什么？

更新 1

有关该图的更多信息：该图具有约 100k 个顶点，约 3 个顶点的约 13k 个完整子图，以及约 100 个大小范围 [10-5000] 的完整子图。每个边缘都有捆绑的属性。

更新 2

感谢Salim Jouilli ，我最近了解到节点包是超图的一种坦率方法，其中超边包含在节点的子集中。

更新 3

我已经完成了解决方案的实施。我有效地提高了内存消耗和运行时间：从 6GB 到 24MB，从 50 分钟到 2 分钟 30 分钟。

我有一棵树（在图形意义上）表示一棵树（在物理意义上）。树表示为一个 BGL 邻接表，其中每个顶点包含半径和位置属性，即我的图以以下形式定义

我想在树上执行 DFS 以创建分支列表。附加要求是，每当一个顶点有多个未探索的相邻顶点时，它都会选择具有最大半径的顶点。该规则确保图的遍历顺序代表物理树枝。

似乎 DFS 访问者不支持优先级队列，所以我想知道是否存在通过 A* 获取此信息的替代搜索公式？

或者，我可以通过对顶点进行排序来实现我自己的 DFS 算法，但如果可能的话，我宁愿利用 BGL 框架。

谢谢

-约翰

即使图中没有循环，BGL 的 depth_first_search 算法有时也会对访问者调用 back_edge()。根据后端的定义，并根据 Boost 的DFS 访问者文档，这不应该发生。请注意，只有当 listS 用作顶点和边的表示时，这才是可重现的。

下面的代码示例（应该按原样编译）构造一个具有两个节点和一条边的图。它错误地打印“后边缘”。我在这里做错什么了吗？或者这是一个错误？

在 Mac OS 10.7 上使用 i686-apple-darwin11-llvm-g++-4.2 测试 Boost 1.46.1；
在 Debian 2.6.32-34squeeze1 上使用 gcc 4.4.5 使用 Boost 1.42.0 进行测试。

（抱歉标题，我想不出一个短于 140 个字符的好标题...）

我正在为 boost::graph 库编写一个图形算法。在我的算法中，我需要保留关于节点的变量、权重和计数器。就我从文档和查看其他人的代码而言，执行此操作的典型方法是将这些属性直接附加到图形并使用属性映射访问它们。

然而，在库函数中，我不希望将特定的读/写映射与图形捆绑在一起，因此我创建了自己的外部属性映射。但是这些需要 a std::map（或等效的），所以我最终创建了 astd::map和 a boost::associative_property_map<std::map>。这样做的好处是我有一个统一的方法来获取我的算法的属性和用户的属性（boost::get），但不利的一面是，我似乎有两个冗余映射。除了提到的一致性之外，这样做还有什么意义吗？我能否以某种方式让属性映射维护它自己的内部映射（我意识到不会增加内存等，但是会少一个成员变量来跟踪每个属性）？

在我目前正在实施的算法中，有这条线（图中u的顶点在哪里，并且Pred(u)所有顶点的边都指向u）：

我翻译成 boost::graph 代码的Pred(u)部分如下：

现在，我正在明确地Do stuff在循环之外做这些事情u，但我想在for循环中做。是否有一些技巧可以创建迭代器，就好像u从返回的一样boost::in_edges？

定义boost::graph如下，我得到所有边的边索引为零。为什么？我究竟做错了什么？

据我从文档和示例中可以看出，这应该有效。

我有一组来自图表的边，并希望使用与任何边共享顶点的所有边来扩展它。我怎样才能用boost::graphs 有效地做到这一点？

我能想出的唯一方法是提取所有源和目标顶点的幼稚解决方案，boost::adjacent_vertices用于获取所有邻接关系，然后使用boost::edge. 有没有更好的方法来做到这一点？

上下文：图顶点是地形三角剖分的质心，边连接对应三角形相邻的顶点（所以有点像对偶图）。我要扩展的边集对应于被阻塞的三角形间路径，并且被阻塞的区域正在扩展。该区域是圆形的，所以我使用上面的幼稚方法看到的大部分边缘已经是集合的一部分。

我正在使用 boost 图形库并尝试初始化 aMutableGraph以开始作为网格的生活。边缘将在以后的生活中添加和删除，所以我认为adjacency_list<vecS,listS,undirectedS>是正确的选择。

我对 BGL 的阅读表明，用这些边缘初始化它的明智方法是boost::grid_graph利用 boost::copy_graphto copy from aboost::grid_graph可以免费为我制作所有初始边缘。我认为这是有道理的——copy_graph从一个模型复制VertexListGraph到一个模型MutableGraph，这正是我所拥有的。

我最初尝试使用 2 参数版本copy_graph，模糊地希望其余的默认值会发生一些明智的事情。事实证明并非如此，grid_graph（由于我无法弄清楚的原因）似乎没有将PropertyMaps 与边或顶点一起使用的工具，因此默认vertex_copy和edge_copy失败（带有编译器错误）复制特性。

由于 2-argument 版本显然看起来不合适，我继续并尝试实现我自己的二元运算符来复制顶点和边。即使使用“无操作”副本，它也不能像我希望的那样工作（即它不能编译）。

我整理了一个说明问题的最小工作示例：

此示例无法编译：

我对该错误的分析是，它似乎试图默认构造 的内部结构的一部分grid_graph，由于某种原因，这对我来说并不是很清楚。（clang 并没有真正告诉我任何我从 g++ 看不到的东西）。

问题：

1. 这是将可变图形初始化为常规网格的正确方法吗？我最初认为这比自己编写函数要容易得多，但现在我不太确定了！
2. 为什么这里的默认值orig_to_copy和/或vertex_index不合适？我假设这两个是错误的原因。（如果有的话，实际上是哪个导致了问题？我无法破译当前错误的根本原因是什么）。
3. 解决此问题的“正确”方法是什么？