Clear vertex of all neighbors of v

Question

I'm implementing an algorithm in C++ with Boost Graph.

I want to find all the vertex in the neighborhood of v (so, all its neighbors), then change a property of their and finally clear all of their edges.

I found in Boost the function adjacent_vertices(v,g) (where v is the vertex and g is the graph) to find all the neighbors. Then I want to apply on all of them the function clear_vertex(v,g) (again, v is the vertex and g is the graph) to remove all of their edges.

At this point, I have a problem. The adjacent_vertices function returns a pair of adjacency_iterator, while for the clear_vertex function I need vertex_iterator (if I understand correctly how these functions work).

So, there is an easy way to transform the adjacency_iterator in vertex_iterator? If I keep the adjacency_iterator and pass it to the clear_vertex function, the problem is that it doesn't remove the edges (or remove them randomly to some vertices).

My wrong code is:

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

Answer 1

It depends on the edge container selectors.

The easiest way is when the containers are node-based, i.e. only the iterators/descriptors to any removed edges are invalidated.

Another way is when you split the "query" and "modification" aspects, e.g.

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

Possible output:

Before: 2000
After: 1983