Have a DAG graph in boost without vertex descriptor invalidation

Question

I am trying to implement a direct acyclic graph with the boost::adjacency_list<> class. For that I re-implemented the idea from this question: boost graph that doesn't allow circular references

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

With that I was able to call the topological_sort after each add_edge to confirm I have a 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) {}));
}

An additional requirement I have is to enable some undo/redo support on actions I do on my graph. One of the operation could be to remove a vertex and deleting all incoming and outgoing edges from the specified vertex. A sample code could look like this:

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

Output:

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

Vertices:
0
1
Edges:

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

This doesn't work of course because the remove_vertex call invalidates my earlier saved vertex_descriptors. A solution I found for this problem was how to call "boost::remove_vertex" without re-indexing the vertices?

Here it proposed to use a list instead of a vector for saving the vertices and therefore the vertex_descriptors do not get invalidated.

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

This does work as expected and gives the desired output where the undo works:

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

Vertices:
000001DD1902AC90
000001DD19028D80
Edges:

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

The problem I have now is that the topological_sort does not compile anymore with my new Graph definition. For full error message: https://godbolt.org/z/WKjeK3ddP

The question I have (or the problem I am trying to solve is) how can I implement a direct acyclic graph in boost without invalidating the vertex_descriptors while removing vertices and having the topological_sort possibility?

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

Answer 1

Excellent question.

The topological sort

It fails because there's no longer an implicit vertex index. Topological sort requires it to get a default color map, so things that work:

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

Or, just provide a color map directly, which is probably a better idea:

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?

Big Picture

The thing I like most about your question is that after a very high level of detailed analysis, you still go back and wonder whether there's something else. This is you, trying to avoid tunnel vision or X/Y problem.

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

To be completely honest, I think you're shoe-horning a very specific datastructure into something BGL should have. And that's just improbable. I'd reverse the design priorities.

BGL is expressly designed to be almost completely generic. This means you can use the algorithms on your own data structures given the right instrumentation/adaptation.

Your requirements feel more like a versioned tree/forest. A Sean-Parent-style tree with shared_ptr<const T> nodes seems more applicable.

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

A more advanced strategy could be e.g. splay trees, but I'd have to freshen up on theory myself before recommening/implementing anything like that.

Now, all of this doesn't really touch on any requirements for graph algorithms. The linked answer above incidentally shows topological sort on a custom graph model, so you can have a look and see whether that looks viable. At some point you might decide it's better to "just implement" BFS for your own datastructure.