boost graphs - topological sort with priority

Question

I'd like to do an altered topological sort. At any given level, there are a number of choices we can take.

For example, the topological order of this graph could be 1 -> 2 -> 3 or 2 -> 1 -> 3.

My vertices has data associated as such.

struct VertexData {
  int id;
  int weight;
}

I'd like the topological sort to prioritise higher weights first whenever encountering a choice. So the order will always be 2 -> 1 -> 3 in this case.

How can I do this?

Edit: I'm using Vecs for both Edge and VertexList

Answer 1

Everything rides on the choice of graph model here.

The algorithm does not provide an extension point for initial vertex ordering. It just gets the out edges using the vanilla concept:

boost::tie(ei, ei_end) = out_edges(u, g); // depth_first_search.hpp:L152

Any ordered/hashed container selector for adjacency_list's OutEdgeList parameter will compare only by the edge's target. All of this is implementation detail.

As long as you're not using an ordered/hashed container selector, you might interfere and sort those out-edges manually, like I've showed before.

In this case I might be mistaken but it looks like you can get away with sorting the vertices ahead of creating the edges:

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/topological_sort.hpp>
#include <deque>
#include <ranges>
namespace r = std::ranges;
namespace v = std::views;

template <typename G> auto topo_order(G const& g) {
    using V = G::vertex_descriptor;
    std::map<V, size_t> idx;
    for (auto v : boost::make_iterator_range(vertices(g)))
        idx.emplace(v, idx.size());

    std::deque<V> order;

    topological_sort(             //
        g, front_inserter(order), //
        vertex_index_map(boost::make_assoc_property_map(idx)));

    return order;
}

#include <fmt/ranges.h>

template <typename Cmp> void demo() {
    struct VertexData {
        int id;
        int weight;
    };
    using G = boost::adjacency_list<boost::vecS, boost::listS, boost::directedS, VertexData>;

    G g;
    auto v2 = add_vertex({2, 30}, g);
    auto v1 = add_vertex({1, 20}, g);
    auto v3 = add_vertex({3, 20}, g);

    g.m_vertices.sort([&g, cmp = Cmp{}](auto const& a, auto const& b) { //
        return cmp(g[a].weight, g[b].weight);
    });

    add_edge(v1, v3, g);
    add_edge(v2, v3, g);

    fmt::print("{} topo: {}\n", __PRETTY_FUNCTION__,
               topo_order(g) | v::transform([&g](auto v) { return g[v].id; }));
}

int main() {
    demo<r::less>();
    demo<r::greater>();
}

Printing

void demo() [with Cmp = std::ranges::less] topo: [2, 1, 3]
void demo() [with Cmp = std::ranges::greater] topo: [1, 2, 3]