1

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.

1
  • It would help if you shared some actual code that you have trouble with. Or at least the expected output datastructure/example data. Meanwhile all I can say is that you need not modify boost's code to override the visitor events.
    – sehe
    Commented Nov 23, 2023 at 19:08

1 Answer 1

2

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]
2
  • Perhaps using this example you can illustrate the expected outcome. If you do I'm happy to show how I'd implement the extra functionality
    – sehe
    Commented Nov 23, 2023 at 19:32
  • (I'm assuming you've seen stackoverflow.com/a/29200511/85371, but in case you didn't, it may help you)
    – sehe
    Commented Nov 23, 2023 at 19:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.