I'm trying to adapt this git page on simultaneously obtaining a topologically sorted list of incoming vertices whilst topologically sorting. The reason I'm doing this is to compare this implementation of transitive reduction with boost's undocumented version.
I'm trying to edit boost's own topological sort. From what I can tell, all I need to do is to override the discover_vertex or examine_edge functions to append a value to specific vectors depending on the vertex but I'm struggling to do so.
Should I pass in a data structure to the visitor or another OutputIterator? How can I properly override these functions and update either of these two options?
If anybody could shed some light that would be lovely. Many thanks in advance.
I was slightly wrong in my comment. I remembered topological_sort as having a more general-purpose interface.
So, let me show you how I'd replicate topological-sort directly against the depth_first_search interface, which will will make it easy for you to modify the behavior to your taste.
template <typename G> auto my_algo(G const& g) {
using V = G::vertex_descriptor;
using E = G::edge_descriptor;
using Out = std::deque<V>;
struct Visitor : public boost::dfs_visitor<> {
Out& o;
Visitor(Out& o) : o(o) {}
void back_edge(E, G const&) const { throw std::runtime_error("cycle"); }
void finish_vertex(V u, G const&) const { o.push_front(u); }
};
Out order;
depth_first_search(g, boost::visitor(Visitor{order}));
return order;
}
At this point it does nothing more than just the original topological_sort. Indeed we can verify using the documentation example:
boost::adjacency_list<> g;
add_edge(0, 1, g);
add_edge(2, 4, g);
add_edge(2, 5, g);
add_edge(0, 3, g);
add_edge(1, 4, g);
add_edge(4, 3, g);
fmt::print("Order: {}\n", my_algo(g));
Which prints the expected: Live On Coliru
Order: [2, 5, 0, 1, 4, 3]