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

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

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

如果没有这样的功能――那为什么?我认为是常见的图操作.

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

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

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

解决方案

半生不熟的快速概念验证

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

#include #include <迭代器>#include 使用 V = 无符号；使用 E = std::pair ；使用 G = boost::adjacency_list;void print_graph(G const& g){auto vs = boost::vertices(g);for (auto vit = vs.first; vit != vs.second; ++vit) {自动邻居 = boost::adjacent_vertices(*vit, g);for (自动尼特=邻居.第一；尼特！=邻居.第二；++尼特)std::cout <<{"<<*维生素<<，"<<*尼特<<"}" <<", ";}std::cout <<"
";}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(){//命名顶点自动常量 A = V { 1 };自动常量 B = V { 2 };//构造图auto e = std::vector{ { A, 3 }, { B, 4 } };自动 g = G { std::begin(e), std::end(e), 4 };打印图(g)；合同顶点(B，A，g)；打印图(g)；}

Live/p><块引用>

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

How to merge two vertices/contract edge at Boost.Graph?

I need to move edges from vertex A to vertex B, and delete vertex A - is there any built-in function? Or maybe there is something special for adjacency_list?

If there is no such function - then why? I think it is common graph operation.

EDIT: I do know that it is possible to do it manually, but there are some corner cases (like preserving edges properties), that why it is good candidate to be in library.

I mostly interested to know if Boost.Graph have already that operation (maybe with some fancy name?). And if not - why such primitive operation/algorithm is not in Graph Library. Maybe I am missing something, and that operation is not-primitive or rarely used.

I do not need half-baked quick proof-of-concepts

解决方案

Half-baked quick proof-of-concept

You can use add_edge() and remove_vertex() on a graph defined in terms of 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 << "
";
}

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 that prints

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

The output is not quite what you expect because the labelling of vertices is also updated to reflect the removal of B, which cause nodes 3 and 4 to be labelled 2 and 3 now.

Requirements for library-quality code

A general library-quality algorithm for contraction of vertices u and v should typically take into account at least the following corner cases

• remove (u,v) and (v,u) edges;
• merge all u and v out-edges with common targets;
• merge all u and v in-edges with common sources;
• move the rest of u out-edges to v;
• move the rest of u in-edges to v;

Boost.Graph provides all the required primitives for such an operation: in_edges(), out_edges(), add_edge(), clear_vertex(), remove_vertex(). For undirected graphs several of these items can be done in a single step, whereas for directed graphs typically two steps are required.

In addition to these algorithmic steps, one should also define the semantics of what it means to merge or move edges. E.g. what should happen to their properties? This is similar to e.g. merging two corporations: under which name should the joint firm operate?

Why Boost.Graph does not (yet) provide a contract_vertices()

TL;DR I don't know. But I can speculate. Mainly, one should specify the interface of a putative contract_vertices(). Apart from the two vertices to be contracted, and the type of graph they are a part of, one should also define the merge and move operations on the edge properties. In theory, it should be possible to do this with suitable template parameter to the general algorithm.