6

如何在 Boost.Graph 中合并两个顶点/合同边？

我需要将边从顶点 A 移动到顶点 B，并删除顶点 A - 是否有任何内置函数？或者也许 adjacency_list 有什么特别之处？

如果没有这样的功能 - 那为什么？我认为这是常见的图形操作。

编辑：我确实知道可以手动完成，但是有一些极端情况（比如保留边缘属性），这就是为什么它是图书馆的好人选。

我最想知道 Boost.Graph 是否已经有这个操作（也许有一些花哨的名字？）。如果不是 - 为什么这种原始操作/算法不在图形库中。也许我遗漏了一些东西，并且该操作不是原始的或很少使用。

我不需要半生不熟的快速概念验证

4

3 回答 3

10

半生不熟的快速概念验证

您可以使用add_edge()和remove_vertex()adjacency_list 

#include <iostream>
#include <iterator>
#include <boost/graph/adjacency_list.hpp>

using V = unsigned;
using E = std::pair<V, V>;
using G = boost::adjacency_list<boost::vecS, boost::vecS>;

void print_graph(G const& g)
{
    auto vs = boost::vertices(g);
    for (auto vit = vs.first; vit != vs.second; ++vit) {
        auto neighbors = boost::adjacent_vertices(*vit, g);
        for (auto nit = neighbors.first; nit != neighbors.second; ++nit)
            std::cout << "{" << *vit << "," << *nit << "}" << ", ";
    }
    std::cout << "\n";
}

void contract_vertices(V b, V a, G& g)
{
    auto be = boost::adjacent_vertices(b, g);
    for (auto beit = be.first; beit != be.second; ++beit)
        add_edge(a, *beit, g);
    remove_vertex(b, g);
}

int main()
{
    // named vertices
    auto const A = V { 1 };
    auto const B = V { 2 };

    // construct the graph
    auto e = std::vector<E> { { A, 3 }, { B, 4 } };
    auto g = G { std::begin(e), std::end(e), 4 };

    print_graph(g);
    contract_vertices(B, A, g);    
    print_graph(g);
}

打印的实时示例

{1,3}、{2,4}、
{1,2}、{1,3}、

输出并不完全符合您的预期，因为顶点的标记也更新以反映 的删除B，这导致节点 3 和 4 现在被标记为 2 和 3。

库质量代码的要求

用于顶点收缩的通用库质量算法，u通常v应至少考虑以下极端情况

  • 移除 (u,v) 和 (v,u) 边；
  • 将所有 u 和 v 出边与公共目标合并；
  • 将所有 u 和 v 入边与公共源合并；
  • 将其余的 u 外边缘移到 v；
  • 将剩余的 u 个入边移到 v；

Boost.Graph 为此类操作提供了所有必需的原语：in_edges(), out_edges(), add_edge(), clear_vertex(), remove_vertex()。对于无向图，其中几个项目可以在一个步骤中完成，而对于有向图，通常需要两个步骤。

除了这些算法步骤之外，还应该定义合并或移动边缘的语义。例如，它们的属性应该如何处理？这类似于合并两家公司：合资公司应该以哪个名称经营？

为什么 Boost.Graph 没有（还）提供contract_vertices()

TL; 博士我不知道。但我可以推测。主要是，应该指定一个假定的接口contract_vertices()。除了要收缩的两个顶点以及它们所属的图类型之外，还应该定义边缘属性的合并和移动操作。理论上，应该可以使用适合通用算法的模板参数来做到这一点。

于 2013-07-22T14:06:35.507 回答
-1

手动操作，您应该手动删除每条b边，而不是顶点：

void collapse_vertices(V b, V a, G& g)
{
    auto be = boost::adjacent_vertices(b, g);
    for (auto beit = be.first; beit != be.second; ++beit)
    {
        add_edge(a, *beit, g);
        remove_edge(b, *beit, g);
    }
}

发出你想要的{1,3}, {1,4},。

我不知道为什么它不包含在 BGL 中（据我所知），但这个函数就是它的作用。

于 2013-07-23T21:49:33.473 回答
-1

库中没有通用函数，因为通用函数不可能知道在“极端情况”中需要做什么。如果顶点 X 对顶点 A 和 B 都有边怎么办？该函数应该简单地删除 XA，还是应该删除 XB 并将 XA 移动到 X--B？如果从 X 到 A 的边（被删除的顶点）具有必须保留或修改的属性怎么办？只有应用程序代码知道在删除或移动边时如何处理属性

正如 qble 所暗示的那样，“委托”这些决定是没有意义的。如果关于如何处理已删除边的属性的决定“委托”给应用程序代码，那么应用程序代码将不得不查找并遍历必须删除的边。所以它必须重复通用函数所做的相同工作。一旦完成了每个已删除边的属性，它也可以自己进行边删除，而不必费心调用通用函数。

于 2013-07-23T22:16:29.200 回答