I created the simplest directed graph possible using boost::graph, and added 2 vertices that are mutually connected via 2 edges.

After removing the first vertex, the second vertex still has an out-edge that points to the previously removed vertex.

boost::adjacency_list<
    boost::vecS,
    boost::vecS,
    boost::directedS,
    boost::no_property,
    boost::no_property
>  graph;

// add 2 vertices and connect them
auto v0 = boost::add_vertex(graph);
auto v1 = boost::add_vertex(graph);

boost::add_edge(v0, v1, graph);
boost::add_edge(v1, v0, graph);

// remove the first edge
boost::remove_vertex(v0, graph); 

// iterate over vertices and print their out_degree. 
auto [begin, end] = boost::vertices(graph);

for (auto vertex_itr = begin; vertex_itr != end;   vertex_itr)
{
    auto vertex_descriptor = *vertex_itr;

    auto out_degree = boost::out_degree(vertex_descriptor, graph);

    std::cout << out_degree << '\n'; // this prints 1
}

To my understanding, my graph is in a sort of "invalid state" where an edge points to a non exiting vertex. From further examining, it seems as if the "dangling edge" has become an edge with source == target. This makes me even more confused as to why boost::graph decided to leave this edge and even go to the trouble of making it cyclic.

Questions:

• How do I fix this?
• How do I remove the in edges of a vertex?
• Does it make more sense to use a bidirectional graph in this situation?

Also, I couldn't find anything on the docs regarding this behavior, so I would appreciate if someone could point me to the right place.

CodePudding user response：

The implementation isn't "going through the trouble" - it's just doing anything, because you didn't satisfy the pre-conditions:

void remove_vertex(vertex_descriptor u, adjacency_list& g)

Remove vertex u from the vertex set of the graph. It is assumed that there are no edges to or from vertex u when it is removed. One way to make sure of this is to invoke clear_vertex() beforehand.

I repro-ed your issue slightly more briefly: Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <iostream>

int main() {
    boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS> g(2);

    add_edge(0, 1, g);
    add_edge(1, 0, g);

    print_graph(g, std::cout << "--- Before: ");
        
    remove_vertex(0, g); // remove the first edge

    print_graph(g, std::cout << "--- After: ");

    // iterate over vertices and print their out_degree. 
    for (auto [it, end] = boost::vertices(g); it != end;   it)
        std::cout << out_degree(*it, g) << "\n"; // this prints 1
}

Prints

--- Before: 0 --> 1 
1 --> 0 
--- After: 0 --> 0 
1

Fixing It

Let's simply do as the docs say:

clear_vertex(0, g);  // clear edges
remove_vertex(0, g); // remove the first edge

Now it works: Live On Coliru, printing:

--- Before: 0 --> 1 
1 --> 0 
--- After: 0 --> 
0

BONUS

For more elegance:

// iterate over vertices and print their out_degree. 
for (auto v : boost::make_iterator_range(vertices(g)))
    std::cout << v << " out_degree: " << out_degree(v, g) << "\n";