Boost.Graph如何合并两个顶点/收缩边。

Question

Boost.Graph如何合并两个顶点/收缩边。

c++boostgraphboost-graph

6

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

我需要将边从顶点A移到顶点B，并删除顶点A - 是否有任何内置函数？或者也许有一些特殊的针对邻接表的东西吗？

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

编辑：我知道可以手动完成，但有一些角落案例（如保留边属性），这就是为什么它是在库中好的候选项。

我最想知道的是Boost.Graph是否已经具有该操作（可能有一些花哨的名称？）。如果没有-为什么这样原始的操作/算法不在Graph Library中。也许我遗漏了什么，这种操作不是原始的或很少使用。

我不需要半成品的快速概念证明。

- qble

投票者，这个问题有什么问题吗？ - qble

1

大声喊叫“我不需要半成品的快速概念验证”可能是问题所在。(我知道，你并没有恶意，甚至还奖励了悬赏，只是说出来而已)。 - sehe

3个回答

-1

如果手动操作，您应该手动删除每个b边缘，而不是顶点：

void collapse_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_edge(b, *beit, g);
    }
}

输出你想要的{1,3}, {1,4},。

我不知道为什么它没有包含在BGL中（据我所知），但这个函数就是做这件事的。

- Enoah Netzach

1

如果您要添加的边已经存在怎么办？如果您要删除的边具有属性怎么办？ - ravenspoint

@ravenspoint 它的行为符合预期，以最自然的方式进行：如果您添加一个已经存在的边缘，则会被添加，并且您始终可以检查和删除重复项；这是手动完成的，因此您需要负责传递属性。 - Enoah Netzach

-1

由于通用函数无法知道在“边角情况”下需要执行什么操作，因此库中没有通用函数。如果顶点X同时与顶点A和B具有边缘呢？该函数应该简单地删除X-A，还是应该删除X-B并将X-A移至X--B？如果从X到A的边（要删除的顶点）具有必须保留或修改的属性怎么办？只有应用程序代码知道在删除或移动边缘时如何处理属性。

像qble建议的那样“委托”这些决策是没有意义的。如果将删除边缘的属性的决定“委托”给应用程序代码，那么应用程序代码将不得不查找并循环遍历必须删除的边缘。因此，它必须重复通用函数所执行的相同工作。一旦完成了每个删除边缘的属性，并且不需要调用通用函数，最好让应用程序自己执行边缘删除。

- ravenspoint

确实存在一些必须在通用函数中处理的特殊情况。但这并不意味着无法解决。当在特殊情况下有选择时，决策应该通过参数委托给用户。Boost.Graph已经将许多决策委托给了用户（例如使用adjacency_list自定义容器），这就是它通用的原因。 - qble

那么应用程序代码将不得不查找并循环遍历必须删除的边缘 - 不，它不必这样做。如果有疑问 - 通用版本可以只使用作为参数传递的用户函数。 - qble

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- TemplateRex · Accepted Answer

投机取巧的概念验证

你可以在基于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);
}

现场示例，输出如下：

{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()`

快速阅读： 我不知道。但我可以推测。主要是应该指定一个虚设 contract_vertices() 的接口。除了待收缩的两个顶点和它们所属的图形类型之外，还应定义边缘属性上的合并和移动操作。理论上，应该可以通过适当的模板参数来实现这一点。

Boost.Graph如何合并两个顶点/收缩边。

投机取巧的概念验证

库质量代码的要求

为什么 Boost.Graph （尚）没有提供 contract_vertices()

为什么 Boost.Graph （尚）没有提供 `contract_vertices()`