如何使用 Boost.Graph 从有向图中提取子图？

Question

我有一个非常大的图点文件，想要从给定的顶点提取子图。该子图应包含给定的顶点及其下方的所有顶点。

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

#include <iostream>

struct Vertex {
    std::string node;
};

int main() {
    std::istringstream input(
        "digraph{"
        "0;1;2;3;4;5;6;7;8;9;"
        "0->1;1->2;2->3;2->6;3->4;4->5;5->8;6->7;6->5;7->8;8->9;"
        "}");

    boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, Vertex> g(0);

    boost::dynamic_properties dp(boost::ignore_other_properties);
    dp.property("node_id", get(&Vertex::node, g));

    boost::read_graphviz(input, g, dp);

    // delete everything that is not below Node 6

    boost::write_graphviz(std::cout, g);
}

在这个最小的示例中，给定的顶点的节点 ID 为 6。下图显示了我想要提取的内容：

如何删除不低于节点6的节点和边？

我尝试使用

depth_first_search

以某种方式解决这个问题，不幸的是没有成功。 ChatGPT 和文档也没有引导我实现目标。

点文件转SVG图形：

dot -Tsvg out.dot -o out.svg

Answer 1

boost graph有一种将点文件读入boost graph的方法。

从您指定的节点开始并执行 DFS 或 BFS。当您访问节点时标记它们。 当搜索结束时，删除未标记的节点及其所有链接。