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

Question

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

我需要将边缘从顶点A移动到顶点B,并删除顶点A - 是否有任何内置函数？或者也许adjacency_list有一些特别的东西？

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

编辑:我知道可以手动完成,但有一些极端情况(如保留边缘属性),这就是为什么它是在库中的好候选人.

我最感兴趣的是知道Boost.Graph是否已经有了这个操作(可能有一些奇特的名字？).如果不是 - 为什么这样的原始操作/算法不在图形库中.也许我错过了一些东西,而且这种操作不是原始的或很少使用.

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

Answer 1

半生不熟的快速概念验证

您可以使用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 in-edge与公共源合并;
• 把剩下的你的边缘移到v;
• 把你的其余边缘移到v;

Boost.Graph提供所有这样的操作所需要的原语:in_edges(),out_edges(),add_edge(),clear_vertex(),remove_vertex().对于无向图,这些项中的一些可以在一个步骤中完成,而对于有向图,通常需要两个步骤.

除了这些算法步骤之外,还应该定义合并或移动边缘的语义.例如,他们的财产会发生什么？这类似于合并两家公司:联合公司应该以何种名义运营？

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

TL; DR我不知道.但我可以推测.主要是,应该指定假定的界面contract_vertices().除了要缩小的两个顶点以及它们所属的图形类型之外,还应该在边缘属性上定义合并和移动操作.理论上,应该可以使用适合通用算法的模板参数来完成此操作.