Algorithms are ranges¶

Most graph libraries express "do something at each step of a traversal" with a visitor class, a callback, or a set of named parameters. melon inverts the control flow: an algorithm is an object you step, and the loop body is the visitor.

The generator protocol¶

template <typename A>
concept algorithmic_generator = requires(A & alg) {
    { alg.finished() } -> std::convertible_to<bool>;
    alg.current();
    alg.advance();
};

Three members: is there anything left, what is the current result, move on. algorithm_view_interface turns that into a std::ranges input range by wrapping the object in an algorithm_iterator whose operator* is current(), operator++ is advance(), and whose sentinel comparison is finished().

The consequences are the point:

// 1. consume it as a range
for(auto && [v, dist] : dijkstra(graph, length_map, s)) { ... }

// 2. stop where you like — no exception, no visitor return code
for(auto && [v, dist] : dijkstra(graph, length_map, s)) {
    if(dist > radius) break;
}

// 3. compose with std::views
auto far = dijkstra(graph, length_map, s)
         | std::views::drop_while([](auto && e) { return e.second < 10; })
         | std::views::take(5);

// 4. drive two searches in lockstep
dijkstra forward(graph, length_map, s);
dijkstra backward(graph | views::reverse, length_map, t);
while(!forward.finished() && !backward.finished()) {
    forward.advance();
    backward.advance();
}

The fourth is not hypothetical: it is exactly how bidirectional_dijkstra and competing_dijkstras are built.

Which algorithms are ranges¶

An algorithm is a range exactly when it derives from algorithm_view_interface, which is what supplies begin() / end(). The thirteen below do; the rest do not, and a range-for over one of them is a compile error, not a silent single-pass.

The rest produce a single answer rather than a sequence, so they expose run() and dedicated accessors instead: bidirectional_dijkstra, bellman_ford, bellman_ford_moore, edmonds_karp, dinitz, knapsack_bnb and unbounded_knapsack_bnb.

Even the range-shaped ones offer run() — while(!finished()) advance(); — for when you want the side effects and the accessors but not the values. It returns the algorithm, like reset(), so a run and a query chain: alg.run().dist(t). The run()-only algorithms above share that shape — run() returns the algorithm, and the answer is read through the accessors afterwards — without being generators at all: they have no finished() / advance() to drain.

finished() and current() are const on every generator, so a const reference to an algorithm is enough to inspect where it stands; advance(), run() and reset() are the mutating half. Algorithms are move-only: std::copyable is false for every one of them, over every graph, because an algorithm carries the whole search state and copying it is never the cheap operation the syntax suggests. Moving is always available and always sound, mid-traversal included — the algorithms that cache incidence ranges rebase those cursors as part of the move. See Ownership. Where current() hands back a window onto the algorithm's own buffer — the component of strongly_connected_components or connected_components, the tree of traversal_forest — that window is read-only, since the next advance() rewrites it. Where it hands back a single handle it hands back a value, never a reference into that buffer.

base() and reached_map()¶

Every algorithm that stores a graph exposes base(), and every algorithm that answers reached(v) also answers reached_map().

base() follows the std::ranges shape of whatever the type is. An algorithm owns its graph view, so its base() is the std::ranges::owning_view shape — four ref-qualified overloads returning references:

auto alg = breadth_first_search(graph, 0u);
const auto & g = alg.base();          // the graph view it runs over
auto owned = std::move(alg).base();   // move it out of a finished algorithm

That is how traversal_forest reaches its sources without storing a second copy of the graph, and it is why base() here does not return a copy the way a view's does — see Ownership.

reached_map() hands back a mapping over the same information reached(v) answers one vertex at a time, for passing to anything that takes a map. Some algorithms store that map (breadth_first_search, depth_first_search, topological_sort, connected_components) and some compute it from a status map (dijkstra, network_voronoi, strongly_connected_components, biobjective_dijkstra, traversal_forest). Like every result-map accessor it is a ref-qualified pair: from an lvalue algorithm the result is a view into the algorithm, valid while it lives and stays put; from an expiring one — std::move(alg).reached_map() — the backing map moves into the returned object, which then outlives the algorithm. Extraction is terminal, like std::move(alg).base(); see Ownership.

Construction and deduction¶

Every algorithm deduces its template parameters from its constructor arguments. You name the class, not its parameters:

dijkstra alg(graph, length_map, source);
edmonds_karp flow(graph, capacity_map, source, target);
kruskal tree(ugraph, cost_map);

The graph and the mappings go through views::graph_all and maps::mapping_all, so an lvalue is referenced and an rvalue is owned. That is why the deduction guides are written in terms of views::graph_all_t<Graph> and why passing a temporary graph is safe.

Sources are usually optional constructor arguments, and can always be added afterwards:

dijkstra alg(graph, length_map);
alg.add_source(s1);
alg.add_source(s2, 10.0);   // start s2 at a nonzero distance
alg.run();

add_source has a strict precondition: the vertex must be untouched — not reached, not already in the heap — and it is asserted in debug builds. Re-adding a settled vertex would re-process it and silently corrupt stored paths and distances.

reset() returns the object to its initial state, keeping the graph and the maps, so a loop over many sources allocates once:

dijkstra alg(graph, length_map);
for(auto && s : terminals) {
    alg.reset().add_source(s);
    for(auto && [v, d] : alg) { ... }
}

The lifecycle contract¶

These reset() / run() / add_source semantics are not a per-class convention: they are the named concepts melon::traversal_algorithm and rooted_traversal_algorithm (melon/utility/algorithmic_generator.hpp), statically asserted for every generator-shaped algorithm in the library — the run()-only ones are pinned to the vocabulary they share, reset() and run() returning the algorithm, by the same consistency test — and frozen for the whole 1.x series. In full:

• reset() restores exactly the state the constructor leaves behind — blank for an algorithm whose sources are added afterwards, re-seeded and immediately runnable for one whose constructor seeds (topological_sort, traversal_forest). alg.reset() is always equivalent to constructing a fresh object from the same arguments, minus the allocations.
• run() drains and returns *this. It is idempotent: finished() holds afterwards and a second call is a no-op, with the results still readable through the accessors — which is why bidirectional_dijkstra's answer is read as alg.run().dist().
• current() and advance() require !finished() — asserted in debug builds, undefined in release builds, like every precondition (below).
• There is no post-construction, pre-iteration step. A constructed (and, for rooted algorithms, sourced) object is ready to iterate. LEMON-style init() has no melon counterpart.

Traits¶

Most algorithms take a traits template parameter — usually the last one, and defaulted; bentley_ottmann is the exception, taking it first — that selects the data structures and what gets recorded. It is passed as a first constructor argument, which is what makes the deduction work:

struct my_traits : dijkstra_default_traits<static_digraph, double> {
    static constexpr bool store_distances = true;
    static constexpr bool store_paths = true;
};

dijkstra alg(my_traits{}, graph, length_map, source);

Two things follow from the design.

Unused storage costs nothing. The optional maps are declared with [[no_unique_address]] and become empty types when their flag is false, so the default Dijkstra carries exactly one status map and one heap.

Unavailable accessors do not exist. dist() and path_to() carry a requires(Traits::store_distances) / requires(Traits::store_paths) clause. Calling them on a default-configured algorithm is a compile error naming the flag, not an assertion at runtime.

The flags available per algorithm are listed on each algorithm's page. The data-structure slots — the heap type, the semiring, the index map — are described under Shortest paths.

Map roles¶

Every map an algorithm creates is requested under a role, the defaulted second template parameter of the map factories: create_vertex_map<T, Role>(g), vertex_map_t<Graph, T, Role>. The roles of each algorithm are gathered in a struct named after it — dijkstra_roles::vertex_status, dijkstra_roles::heap_index, dijkstra_roles::pred_arc, dijkstra_roles::distance, dinitz_roles::flow, network_simplex_roles::potential, … — and the default traits spell the heap through the role-aware alias, vertex_map_t<Graph, std::size_t, dijkstra_roles::heap_index>.

Roles exist for providers that hand out storage which already exists: two maps of the same value type are two roles — bidirectional_dijkstra_roles::forward_heap_index and reverse_heap_index — so no slot is ever handed to both. A graph whose factories take a single template parameter, every container included, answers every role with its standard map and is unaffected.

Roles are extension points with a weaker stability guarantee than the rest of the API: an algorithm may retire a map, and with it a role, or add one, in a minor release. Such changes are recorded in the changelog. One structural limit to know: bidirectional_dijkstra's traits name a single heap type for both directions, so a provider must answer its two heap-index roles with the same map type (a projection choosing its field at run time, not a type per field); answering only one of them is a static_assert, never a silent copy.

A note on noexcept¶

melon marks a function noexcept only when it can keep the promise. An algorithm's constructor, reset(), add_source(), advance() and run() are not noexcept: they allocate (the heap, the queue, the vertex maps) and they run your code — your length map, your semiring, your comparator, your graph's out_arcs(). A noexcept there would not prevent the throw, it would turn it into std::terminate with no diagnostic.

The observers are noexcept when their body allows it. Where a view forwards to the wrapped graph — graph_ref_view::vertices(), reverse::arc_targets_map(), every create_*_map() — the specification is conditional, noexcept(noexcept(melon::vertices(*_graph))), so wrapping a graph in a view neither invents a guarantee the graph does not give nor throws one away that it does.

A note on assert¶

melon does not throw on contract violations. Every stated precondition — current() on a finished generator, dist(v) on an unvisited vertex, add_source on a touched vertex, promote in the wrong direction — is an assert in debug builds and undefined behaviour in release builds, where NDEBUG strips the checks. Run your test suite without NDEBUG (and, ideally, with -DMELON_SANITIZE=address,undefined) at least once before shipping — the test suite of melon itself starts every file with #undef NDEBUG for exactly that reason.

The exceptions that are thrown are the STL-shaped ones: at() on the map containers throws std::out_of_range, and allocation failures propagate std::bad_alloc.