如何用Boost.Graph提取有向图指定顶点下游子图并修正遍历问题？

问题需求 #

需要从大型Graphviz dot格式文件中提取指定顶点及其所有下游顶点构成的子图，移除所有非下游的节点和边。现有基于Boost.Graph的C++代码无法正确实现该功能，removeUnreachable函数中的遍历逻辑存在问题。

代码错误分析 #

原代码存在两个关键问题：

• 遍历函数使用错误：depth_first_search会遍历图中的所有连通分量，即使指定了root_vertex，它仍会访问所有节点，导致reachable数组错误标记全部节点，无法区分下游节点。正确做法是使用depth_first_visit，该函数仅遍历从起始顶点可达的下游节点。
• 顶点移除条件写反：removeVertexIf的判断条件为return reachable[index]，这会移除所有被标记为可达的节点，与需求（移除不可达节点）完全相反，应改为return !reachable[index]。

修正后的代码 #

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

#include <iostream>
#include <sstream>

struct Vertex {
    std::string node;
};

using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, Vertex>;
using VertexDesc = Graph::vertex_descriptor;
using ColorMap = boost::property_map<Graph, boost::vertex_color_t>::type;

template <typename Fn>
requires std::is_invocable_r_v<bool, Fn, VertexDesc>
void removeVertexIf(Graph& graph, Fn const& fn) {
    VertexDesc count = num_vertices(graph);
    VertexDesc i = 0;
    while (i < count) {
        if (fn(i)) {
            clear_vertex(i, graph);
            remove_vertex(i, graph);
            --count;
        } else {
            ++i;
        }
    }
}

struct DFSVisitor : boost::default_dfs_visitor {
    DFSVisitor(std::vector<bool>& reachable) : reachable(reachable) {}

    void discover_vertex(VertexDesc index, Graph const&) {
        reachable[index] = true;
    }

    std::vector<bool>& reachable;
};

void removeUnreachable(Graph& graph, VertexDesc start_index) {
    std::vector<bool> reachable(num_vertices(graph), false);
    DFSVisitor visitor(reachable);

    // 获取颜色映射，用于depth_first_visit跟踪访问状态
    ColorMap color_map = get(boost::vertex_color, graph);
    // 初始化起始节点状态
    boost::initialize_vertex(start_index, graph);
    // 仅遍历从start_index可达的下游节点
    depth_first_visit(graph, start_index, visitor, color_map);

    // 移除所有不可达的非下游节点
    removeVertexIf(graph, [&](VertexDesc index) {
        return !reachable[index];
    });
}

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

    Graph g(0);

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

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

    // 移除所有不在顶点6下游的节点和边
    removeUnreachable(g, 6);

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

验证方法 #

1. 编译运行修正后的代码，将输出保存为dot文件：

   g++ -std=c++20 -o extract_subgraph extract_subgraph.cpp -lboost_graph
   ./extract_subgraph > out.dot
   

2. 将dot文件转换为SVG查看结果：

   dot -Tsvg out.dot -o out.svg
   

   生成的SVG应仅包含顶点6及其下游节点：6、7、5、8、9，以及对应的边：6->7、6->5、7->8、5->8、8->9。

内容的提问来源于stack exchange，提问作者Benjamin Buch