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

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

我需要将边从顶点 A 移动到顶点 B，并删除顶点 A - 有内置函数吗？或者adjacency_list可能有一些特殊的东西？

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

EDIT：我确实知道可以手动执行此操作，但存在一些极端情况（例如保留边缘属性），这就是为什么它是库中的良好候选者。

我最感兴趣的是知道 Boost.Graph 是否已经有这个操作（也许有一些奇特的名字？）。如果不是 - 为什么这样的原始操作/算法不存在Graph图书馆。也许我遗漏了一些东西，并且该操作不是原始的或很少使用的。

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

半生不熟的快速概念验证

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