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?
