Boost.Graph如何合并两个顶点/收缩边
如何在Boost.Graph合并两个顶点/契约边？
我需要移动边从顶点A到顶点B，并删除顶点A-有任何内置功能吗？或者也许对adjacency_list有什么特别的东西？
如果没有这样的功能，那为什么？我认为这是一种常见的图形操作。
编辑：我知道可以手动完成，但是也有一些角落情况(比如保留边缘属性)，这就是为什么在库中是很好的候选对象。
我很想知道Boost.Graph是否已经有了这个操作(可能有一些花哨的名字？)。如果不是，为什么这种原始操作/算法不在图库中。也许我错过了什么，而且那个操作不是原始的，也不是很少使用的。
我不需要半生不熟的快速概念证明
回答 3
Stack Overflow用户
发布于 2013-07-22 14:06:35
半生不熟的概念快速证明
您可以在用add_edge()定义的图形上使用adjacency_list和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()
TL；博士我不知道。但我可以推测。主要是，应该指定一个假定的contract_vertices()的接口。除了要收缩的两个顶点和它们所属的图的类型之外，还应该定义边属性上的合并和移动操作。在理论上，应该可以通过适当的模板参数来实现这一点。
Stack Overflow用户
发布于 2013-07-23 21:49:33
手动操作时，应该手动删除每个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中(在我的知识中)，但是这个函数就是这样做的。
Stack Overflow用户
发布于 2013-07-23 22:16:29
库中没有泛型函数，因为泛型函数不可能知道在“角情况”中需要做什么。如果顶点X与顶点A和B都有一条边呢？函数应该简单地删除X，还是应该删除X并将X移动到X？如果从X到A的边缘(被删除的顶点)具有必须保留或修改的属性怎么办？只有应用程序代码知道如何在删除或移动边缘时处理属性。
正如qble建议的那样，“委托”这些决定是没有意义的。如果有关如何处理已删除边的属性的决定“委托”给应用程序代码，则应用程序代码将不得不查找并遍历必须删除的边缘。所以它必须重复泛型函数所做的相同的工作。如果它已经完成了每个已删除边缘的属性，并且不需要调用泛型函数，那么它也可以执行边缘删除本身。
https://stackoverflow.com/questions/17762482
复制相似问题
腾讯云开发者
