c++ - Boost.Graph 如何合并两个顶点/契约(Contract)边

Question

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

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

如果没有这样的功能——那为什么呢？我认为是普通的图形操作。

编辑:我确实知道可以手动执行此操作，但有一些特殊情况(如保留边缘属性)，这就是为什么它是在库中的好候选者。

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

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

Answer 1

半生不熟的快速概念验证

您可以在根据 adjacency_list 定义的图上使用 add_edge() 和 remove_vertex()

#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);
}

Live example 打印

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

输出并不完全符合您的预期，因为顶点的标签也已更新以反射(reflect) 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()。对于无向图，其中的几项可以一步完成，而对于有向图，通常需要两个步骤。

除了这些算法步骤之外，还应该定义合并或移动边意味着什么的语义。例如。他们的属性(property)应该怎么办？这类似于例如合并两家公司:合资公司应以哪个名称运营？

为什么 Boost.Graph(还)不提供 contract_vertices()

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