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

本文介绍了Boost.Graph如何合并两个顶点/边缘合同的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

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

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

我需要从顶点A边缘移动到顶点B，并删除顶点A - 有没有内置的功能？或者，也许有一些特殊的的adjacency_list？

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.

修改：我不知道这是可以做手工，但也有一些其他的情况（像preserving边的属性），那为什么它是很好的候选人是在库

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.

我最感兴趣的要知道，如果Boost.Graph已经该操作（也许有一些奇特的名字吗？）。如果没有 - 为什么这样原始的操作/算法在图库。也许我失去了一些东西，而且操作不本原或很少使用的。

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.

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

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 << "\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);
}

<一个href=\"http://coliru.stacked-crooked.com/view?id=dbbea297b178c65ae69b732806cd2e4b-ce6b7b81d29c30e32c78aebe6e642254\"相对=nofollow>活生生的例子 的打印

Live example that prints

{1,3}，{2,4}，结果
{1,2}，{1,3}，

输出是不太您所期望的，因为顶点的标签也被更新，以反映去除 B ，导致节点3和4的被标记为2和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.

顶点收缩 U A库的一般品质的算法和 v 通常应考虑到至少下面的角落情况下

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

删除（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 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?

TL; DR 我不知道。但是，我可以推测。主要是，一要指定一个假定的 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.

这篇关于Boost.Graph如何合并两个顶点/边缘合同的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！

to