问题标签 [boost-graph]

在Boost Graph Library的算法文档isomorphism中，声明了命名参数vertex_invariant1并vertex_invariant2以二进制函数作为参数。但是，根据来源，这些参数的默认值为degree_vertex_invariant，这是一个一元函数对象。

我是否遗漏了什么，或者文档有误？

所以我有一些简单的生成器类，它很像这样的数据类型（指针和长度）和像这样的简单服装数据类型渲染器。如何创建一个图表来帮助我将生成的数据传递到我的渲染器中？

目前我做这样的事情来将我的 Char Ptr 传递给数据生成器，然后将结果传递给渲染器：

但是我很想看看是否可以使用 Boost Graph 将表示类的数据映射到某些类作为某些函数的输入并返回该函数的某些其他类？通常有一个“图表”我希望能够调用Graph(MyInstanceOfMyDatatype)并让提升将我的值（以最小的应对）从一个图形元素传递到另一个？

这是一个非常简单的示例，所以它可能看起来图形是多余的，但我希望在我的类之间传递自动值的图形，以防例如有一个生成器和 N 个渲染器 - 在这里我希望图形帮助我，例如提供 N -1 我的班级副本到所有渲染器，除了第一个。

作为 boost 图形库的新手，我发现通常很难梳理出哪些示例与特定示例相关联以及哪些部分是通用的。

作为一个练习，我正在尝试制作一个简单的图形，为顶点分配一个颜色属性，并将结果输出到 graphviz，以便颜色显示为被渲染的颜色属性。任何帮助，将不胜感激！这是我到目前为止所拥有的（更具体的使用问题在这里的评论中）：

为什么我不能编译以下简单的应用程序。如果我将 listS 更改为 vecS ，一切都会正常工作。（我正在使用 boost 1.46.1 和 gcc 4.4.5）

来自 BGL 的示例代码：

什么是color_map，在哪里定义？它记录在哪里？

当前情况：我正在尝试从图像中提取片段。多亏了 openCV 的findContours()方法，我现在有了每个轮廓的 8 个连接点的列表。但是，这些列表不能直接使用，因为它们包含很多重复项。

问题：给定一个包含重复的 8 个连接点的列表，从中提取段。

可能的解决方案：

• 起初，我使用了openCV的approxPolyDP()方法。但是，结果非常糟糕......这是缩放的轮廓：

这是结果approxPolyDP()：（9 段！有些重叠）

但我想要的更像是：

这很糟糕，因为approxPolyDP()可以在“几个段”中转换“看起来像几个段”的东西。但是，我所拥有的是一个点列表，这些点往往会对其自身进行多次迭代。

例如，如果我的观点是：

然后，点列表将是0 1 2 3 4 5 6 7 8 7 6 5 4 3 2 1 9......如果点数变大（> 100），那么approxPolyDP()不幸的是提取的段不是重复的（即：它们相互重叠，但不严格相等，所以我可以' t 只是说“删除重复项”，而不是例如像素）

• 也许，我有一个解决方案，但它很长（虽然很有趣）。首先，对于所有 8 连接列表，我创建一个稀疏矩阵（为了提高效率），如果像素属于列表，则将矩阵值设置为 1。然后，我创建了一个图形，其中节点对应于像素，相邻像素之间有边。这也意味着我在像素之间添加了所有缺失的边缘（复杂性很小，可能是因为稀疏矩阵）。然后我删除所有可能的“正方形”（4 个相邻节点），这是可能的，因为我已经在处理非常薄的轮廓。然后我可以启动最小生成树算法。最后，我可以用 openCV 近似树的每个分支approxPolyDP()

总结一下：我有一个乏味的方法，我还没有实现它，因为它看起来很容易出错。但是，我问你，Stack Overflow 的人：还有其他现有的方法，可能有很好的实现吗？

编辑：澄清一下，一旦我有一棵树，我可以提取“分支”（分支从链接到 3 个或更多其他节点的叶子或节点开始）然后，openCV 中的算法approxPolyDP()是Ramer–Douglas–Peucker 算法，这里是它所做的维基百科图片：

有了这张图，很容易理解为什么当点可能相互重复时它会失败

另一个编辑：在我的方法中，有一些值得注意的地方。当您考虑位于网格中的点（如像素）时，通常，最小生成树算法没有用，因为有许多可能的最小树

与

但两者都是最小生成树

但是，在我的例子中，我的节点很少形成集群，因为它们应该是轮廓，并且已经有一个细化算法可以预先在findContours().

回答 Tomalak 的评论：

如果 DP 算法返回 4 段（从点2到中心的段有两次）我会很高兴！当然，通过良好的参数，我可以达到“偶然”拥有相同片段的状态，并且可以删除重复片段。但是，很明显，该算法不是为它设计的。

这是一个包含太多细分的真实示例：

嗨，我有一个提升图，例如：

问题在于 Edge 类中的递归模板。我需要存储一个顶点向量。

我有一个来自 mygraph 的顶点向量，我对顶点进行拓扑排序。

对顶点“按顺序”进行拓扑排序。那么，比较 v1 和 v2 以测试我的原始顶点向量（v1）是“有序”还是“无序”的最佳方法是什么。

编辑：例如：如果向量 v1 有顶点 {A, B, C} 并且我们有边 (A,B) (C,A)

所以在拓扑排序之后，我将在 v2 中

{出租车}

在某些情况下，我可能无法获得唯一的拓扑顺序，例如，如果我有 (A,C) 作为唯一的边，那么 v2 可能以 {A , B , C} 或 {B , A , C} 结尾

现在我需要查看 v1 和 v2 以确定 v1 和 v2 是否代表相同的订单。

第二次编辑：我尝试了一种方法，它现在有效，请告诉我这是否是一个好方法。

我正在生成一个boost::graph, 大约有 300k 边缘。我在一个循环中创建了一组边，在其中我还计算了边的一些属性。因为我需要所有边来创建图形，所以我还没有访问edge_descriptors 的权限。有没有办法做到这一点，而无需再次通过整个集合？当我创建边缘时，我使用std::pair<int, int>, 这与描述符兼容吗？