清除 v 所有邻居的顶点

Question

我正在使用 Boost Graph 在 C++ 中实现一个算法。

我想找到 v 附近的所有顶点（因此，它的所有邻居），然后更改它们的属性，最后清除它们的所有边。

我在 Boost 中找到函数 adjacent_vertices(v,g)（其中 v 是顶点，g 是图）来查找所有邻居。然后我想对它们全部应用函数 clear_vertex(v,g)（同样，v 是顶点，g 是图形）以删除它们的所有边。

此时，我遇到了一个问题。 adjacent_vertices 函数 returns 一对 adjacency_iterator，而对于 clear_vertex 函数，我需要 vertex_iterator（如果我正确理解这些函数的工作原理）。

所以，有一个简单的方法可以将adjacency_iterator转换成vertex_iterator？如果我保留 adjacency_iterator 并将其传递给 clear_vertex 函数，问题是它不会删除边缘（或将它们随机删除到某些顶点）。

我的错误的代码是：

Graph::adjacency_iterator v,vend;
        for(boost::tie(v,vend) = neighbours; v != vend ; ++v) {
            clear_vertex(*v,g2);
        }

Answer 1

这取决于边缘容器选择器。

最简单的方法是当容器是基于节点的时候，即只有 iterators/descriptors 到任何删除的边缘是无效的。

另一种方法是拆分“查询”和“修改”方面，例如

Compiler Explorer

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/random.hpp>
#include <random>

void clear_all_neighbours(auto v, auto& g) {
    auto neigh = adjacent_vertices(v, g);
    std::set to_clear(neigh.first, neigh.second);

    for (auto u : to_clear)
        clear_vertex(u, g);
}

int main()
{
    std::mt19937            prng(std::random_device{}());
    boost::adjacency_list<> g;
    generate_random_graph(g, 1000,2000, prng);
    std::cout << "Before: " << num_edges(g) << "\n";

    auto v = vertex(prng() % num_vertices(g), g);
    clear_all_neighbours(v, g);

    std::cout << "After: " << num_edges(g) << "\n";
}

可能的输出：

Before: 2000
After: 1983

清除 v 所有邻居的顶点

Clear vertex of all neighbors of v

c++

boost

graph