boost::graph: 如何删除先前删除的顶点的入边？

Question

我使用 boost::graph 创建了最简单的有向图，并添加了 2 个通过 2 条边相互连接的顶点。

删除第一个顶点后，第二个顶点仍然有一个指向先前删除的顶点的出边。

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 vertex
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
}

据我了解，我的图处于一种“无效状态”，其中一条边指向一个不存在的顶点。进一步观察，似乎“悬垂边”变成了source == target的边。这让我更加困惑为什么 boost::graph 决定离开这个边缘，甚至不厌其烦地让它循环。

问题：

我该如何解决这个问题？
如何删除顶点的内边？
在这种情况下使用双向图是否更有意义？

另外，我在文档中找不到任何关于此行为的信息，所以如果有人能指出我正确的地方，我将不胜感激。

Answer 1

实施不是“解决问题”——它只是在做任何事情，因为 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.

我repro-ed你的问题稍微简单一点：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 vertex

    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
}

版画

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

修复它

让我们简单地按照文档说的去做：

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

现在有效：Live On Coliru，打印：

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

奖金

对于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";

boost::graph: 如何删除先前删除的顶点的入边？

boost::graph: How to remove in-edges of a previously removed vertex?

c++

boost

boost-graph

修复它

奖金