c++ - boost 中有一个 DAG 图，没有顶点描述符失效

Question

我正在尝试使用 boost::adjacency_list<> 实现直接无环图类(class)。为此，我重新实现了这个问题的想法:boost graph that doesn't allow circular references

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

这样我就可以调用 topological_sort每次之后 add_edge确认我有 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. build a graph structure
    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. build a graph structure
    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. prepare for deletion of 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. delete v2
    boost::clear_vertex(v2, g);
    boost::remove_vertex(v2, g);
    Print(g);

    // 4 undo the operation
    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 失效。我发现这个问题的解决方案是 how to call "boost::remove_vertex" without re-indexing the vertices?

这里建议使用列表而不是 vector 来保存顶点，因此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

我现在遇到的问题是 topological_sort不再用我的新 Graph 进行编译定义。有关完整错误消息:https://godbolt.org/z/WKjeK3ddP

我的问题(或者我试图解决的问题是)如何在 boost 中实现直接无环图而不使 vertex_descriptors 无效同时删除顶点并具有 topological_sort可能性？

或者也许不是那么具体:如何在我可以启用/实现撤消/重做可能性的地方 boost DAG？

Answer 1

很好的问题。

拓扑排序

它失败了，因为不再有隐式顶点索引。拓扑排序要求它获取默认的颜色图，因此有效的方法是:

std::map<Vertex, int> index;
for (auto v : boost::make_iterator_range(vertices(g)))
    index.emplace(v, index.size());

boost::topological_sort(
    g, boost::make_function_output_iterator([](Vertex) {}),
    boost::vertex_index_map(boost::make_assoc_property_map(index)));

或者，直接提供颜色图，这可能是一个更好的主意:

std::map<Vertex, boost::default_color_type> colors;

boost::topological_sort(
    g, boost::make_function_output_iterator([](Vertex) {}),
    boost::color_map(boost::make_assoc_property_map(colors)));

There's some more thinking behind this problem here: What is required for a custom BGL graph to work with topological sort?

大局

关于你的问题，我最喜欢的一点是，经过非常高水平的详 segmentation 析后，你仍然会回过头来想知道是否还有其他问题。这就是你，试图避免视野狭隘或 X/Y 问题。

Or maybe not that specific: How to impelement a DAG with boost on where I can enable/implement undo/redo possibilities?

说实话，我认为您正在将一个非常具体的数据结构硬塞到 BGL 应该具有的东西中。那是不可能的。我会颠倒设计优先级。

BGL明确被设计为几乎完全通用。这意味着您可以在适当的检测/调整的情况下在自己的数据结构上使用算法。

您的需求感觉更像是版本化的树/森林。 Sean-Parent 风格的树 shared_ptr<const T>节点似乎更适用。

A quick demonstration of the concept, focusing on Copy-On-Write deep modification of sub-trees: Transforming trees in C++

更高级的策略可能是例如伸展树(Splay Tree)，但在推荐/实现类似的东西之前，我必须自己更新理论。

现在，所有这些并没有真正触及图算法的任何要求。上面的链接答案顺便显示了自定义图形模型上的拓扑排序，因此您可以查看一下这是否可行。在某些时候，您可能会决定为您自己的数据结构“仅实现”BFS 更好。