在没有顶点描述符失效的情况下在 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;

这样我就可以在每次 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. 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) {}));
}

我的另一个要求是为我在图表上执行的操作启用一些 undo/redo 支持。其中一项操作可能是删除顶点并删除指定顶点的所有传入和传出边。示例代码可能如下所示：

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 无效。我为这个问题找到的解决方案是

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

我的问题（或者我正在尝试解决的问题是）如何在不使 vertex_descriptors 无效的情况下在 boost 中实现直接无环图，同时删除顶点并具有 topological_sort 的可能性？

或者可能不是那么具体：如何在我可以 enable/implement undo/redo 可能性的地方实现带有提升的 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:

大图

我最喜欢你的问题是，在非常高水平的详细分析之后，你仍然回头想知道是否还有其他问题。这是你，试图避免狭隘的视野或 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 明确地 设计为几乎完全通用。这意味着您可以在您自己的数据结构上使用这些算法，只要有正确的 instrumentation/adaptation.

您的要求感觉更像是版本化 tree/forest。具有 shared_ptr<const T> 个节点的 Sean-Parent 风格的树似乎更适用。

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

更高级的策略可能是，例如splay trees，但在 recommening/implementing 类似的事情之前，我必须自己重新梳理理论。

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

在没有顶点描述符失效的情况下在 boost 中有一个 DAG 图

Have a DAG graph in boost without vertex descriptor invalidation

c++

boost

boost-graph

拓扑排序

大图