Boost实现DAG：删除顶点不失效vertex_descriptor且支持拓扑排序与撤销重做

我尝试使用boost::adjacency_list<>类实现有向无环图，参考相关方案做了实现，初始定义如下：

using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS>;
using Vertex = Graph::vertex_descriptor;

使用该定义时，我可以在每次调用add_edge后执行topological_sort校验图是否为合法DAG，示例代码如下：

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/topological_sort.hpp>
#include <boost/iterator/function_output_iterator.hpp>

int main()
{
    Graph g;

    // 1. 构建图结构
    auto v1 = boost::add_vertex(g);
    auto v2 = boost::add_vertex(g);
    auto v3 = boost::add_vertex(g);
    boost::add_edge(v1, v2, g);
    boost::topological_sort(g, boost::make_function_output_iterator([](int) {}));
    boost::add_edge(v2, v3, g);
    boost::topological_sort(g, boost::make_function_output_iterator([](int) {}));
}

我额外需要为图操作添加撤销/重做支持，其中包含删除指定顶点并清理其所有关联入边、出边的操作，测试代码如下：

static void Print(const Graph& g)
{
    std::cout << "Vertices: " << std::endl;
    for (auto vertices = boost::vertices(g); vertices.first != vertices.second; ++vertices.first)
    {
        std::cout << *vertices.first << std::endl;
    }

    std::cout << "Edges: " << std::endl;
    for (auto edges = boost::edges(g); edges.first != edges.second; ++edges.first)
    {
        auto edgeDescriptor = *edges.first;
        std::cout << edgeDescriptor.m_source << "->" << edgeDescriptor.m_target << std::endl;
    }

    std::cout << std::endl;
}

int main()
{
    Graph g;

    // 1. 构建图结构
    auto v1 = boost::add_vertex(g);
    auto v2 = boost::add_vertex(g);
    auto v3 = boost::add_vertex(g);
    boost::add_edge(v1, v2, g);
    boost::add_edge(v2, v3, g);
    Print(g);

    // 2. 准备删除v2
    std::vector<Vertex> outVertices;
    for(auto vertices = boost::adjacent_vertices(v2, g); vertices.first != vertices.second; ++vertices.first)
    {
        outVertices.push_back(*vertices.first);
    }
    std::vector<Vertex> inVertices;
    for (auto vertices = boost::inv_adjacent_vertices(v2, g); vertices.first != vertices.second; ++vertices.first)
    {
        inVertices.push_back(*vertices.first);
    }

    // 3. 删除v2
    boost::clear_vertex(v2, g);
    boost::remove_vertex(v2, g);
    Print(g);

    // 4 撤销删除操作
    v2 = boost::add_vertex(g);
    for(auto& outVertex : outVertices)
    {
        boost::add_edge(v2, outVertex, g);
    }

    for (auto& inVertex : inVertices)
    {
        boost::add_edge(inVertex, v2, g);
    }
    Print(g);
}

测试输出结果不符合预期：

Vertices:
0
1
2
Edges:
0->1
1->2

Vertices:
0
1
Edges:

Vertices:
0
1
2
Edges:
2->2
0->2

该问题的原因是remove_vertex调用会导致之前保存的vertex_descriptors失效。我找到的解决方案是使用listS替代vecS存储顶点，避免顶点重索引导致vertex_descriptors失效，修改后的定义如下：

using Graph = boost::adjacency_list<boost::listS, boost::listS, boost::bidirectionalS>;

修改后撤销功能运行正常，输出符合预期：

Vertices:
000001DD1902AC90
000001DD19028F70
000001DD19028D80
Edges:
000001DD1902AC90->000001DD19028F70
000001DD19028F70->000001DD19028D80

Vertices:
000001DD1902AC90
000001DD19028D80
Edges:

Vertices:
000001DD1902AC90
000001DD19028D80
000001DD19028F70
Edges:
000001DD19028F70->000001DD19028D80
000001DD1902AC90->000001DD19028F70

但现在新的Graph定义下topological_sort无法编译通过。
核心问题：如何基于Boost实现有向无环图，既可以在删除顶点时不失效vertex_descriptors，又支持topological_sort功能，以实现撤销/重做需求？

问题原因 #

boost::topological_sort 算法默认要求图的顶点具备可直接映射为连续整数的索引属性。当你使用vecS作为顶点存储容器时，顶点描述符本身就是整数下标，天然满足这个要求，所以可以直接调用。换成listS之后，顶点描述符变成了指针类型，没有默认的索引映射，因此编译报错。

可行解决方案 #

这里推荐兼容性最好、改动最小的方案：给基于listS的图手动添加顶点索引属性，调用拓扑排序时显式传入索引映射。

具体实现步骤 #

1. 修改图的定义，新增顶点索引属性

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/topological_sort.hpp>
#include <boost/iterator/function_output_iterator.hpp>
#include <iostream>

using Graph = boost::adjacency_list<
    boost::listS, 
    boost::listS, 
    boost::bidirectionalS,
    // 新增顶点索引属性
    boost::property<boost::vertex_index_t, size_t>
>;
using Vertex = Graph::vertex_descriptor;

2. 维护全局自增ID，每次新增顶点时给索引属性赋值

size_t g_vertex_id = 0;

// 新增顶点的统一逻辑
Vertex add_new_vertex(Graph& g) {
    Vertex v = boost::add_vertex(g);
    boost::put(boost::vertex_index, g, v, g_vertex_id++);
    return v;
}

3. 调用拓扑排序时显式传入顶点索引映射

// 校验DAG的代码
bool is_valid_dag(const Graph& g) {
    try {
        boost::topological_sort(
            g, 
            boost::make_function_output_iterator([](Vertex) {}),
            // 显式指定顶点索引映射
            boost::vertex_index_map(boost::get(boost::vertex_index, g))
        );
        return true;
    } catch (const boost::not_a_dag& e) {
        return false;
    }
}

这个方案完全保留了listS的特性：删除顶点不会导致其他顶点的描述符失效，你的撤销/重做逻辑不需要做任何改动，同时也能正常使用拓扑排序校验DAG合法性。

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