Skip to content

MELON logo

   MELON

Modern and Efficient Library for Optimization in Networks.

Get started View on GitHub

MELON is a header-only C++23 graph library built on ranges and concepts. It aims to be as pleasant to use as the standard library and as fast as LEMON — which is unmaintained and no longer compiles past C++17 — without the type-erasure and property-map machinery of Boost.Graph. Algorithms are constrained by concepts rather than written against one graph class, so they run on melon's containers, on its zero-cost views, and on your graph structure if it models the right concept.

#include <print>

#include "melon/algorithm/dijkstra.hpp"
#include "melon/container/static_digraph.hpp"
#include "melon/utility/static_digraph_builder.hpp"

using namespace melon;

int main() {
    static_digraph_builder<static_digraph, double> builder(6);
    builder.add_arc({0, 1}, 7.0)
        .add_arc({0, 2}, 9.0)
        .add_arc({0, 5}, 14.0)
        .add_arc({1, 3}, 15.0)
        .add_arc({2, 3}, 12.0)
        .add_arc({2, 5}, 2.0)
        .add_arc({3, 4}, 6.0)
        .add_arc({5, 4}, 9.0);
    auto [graph, length_map] = builder.build();

    // an algorithm is a range: the loop drives it, one settled vertex per step
    for(auto && [v, dist] : dijkstra(graph, length_map, 0u)) {
        std::println("vertex {} at distance {}", v, dist);
    }
    return 0;
}

The algorithm object driven by that loop is move-only — copying it is a compile error, and reset() reuses its allocated state instead (Algorithms are ranges).

Where to start

The documentation follows the way the library is layered: the concepts first, then what implements them, then what consumes them.

1. Getting started — read in order, about half an hour.

2. The graph model — graph concepts, mappings, undirected graphs, and bringing your own graph.

3. Containers — graph containers (static_digraph, mutable_digraph, …) and the maps, heaps and disjoint sets the algorithms are built on.

4. Views — graph views (reverse, subgraph, undirect, …) and the ownership and mapping views that make lambdas usable as maps.

5. Algorithms — why they are ranges, then traversals, shortest paths, flows and spanning trees, and combinatorial and geometric ones.

What is in the box
Graph containers static_digraph, static_forward_digraph, mutable_digraph
Graph views reverse, subgraph, induced_subgraph, undirect, complete_digraph
Traversals BFS, DFS, topological sort, traversal forest, strongly and weakly connected components
Shortest paths Dijkstra, A*, bidirectional Dijkstra, bi-objective Dijkstra, competing Dijkstras, Bellman–Ford and Bellman–Ford–Moore (negative lengths), network Voronoi
Flows and trees Edmonds–Karp, Dinitz, Kruskal
Other knapsack and unbounded knapsack branch-and-bound, Bentley–Ottmann segment intersection
Data structures d_ary_heap, updatable_d_ary_heap, static_map, static_filter_map, disjoint_sets
Utilities graph builder, make_static_digraph (rebuild any graph as a renumbered static_digraph, translating its maps), Graphviz printer, Erdős–Rényi generator, alias-method sampler, semirings, rationals

Requirements

Header-only and dependency-free. C++23 is the baseline — GCC 14 and Clang 18 at minimum, GCC 15 / C++26 recommended; on macOS Apple Clang 21 (Xcode 26.4) with libc++, and on Windows both MinGW-w64 and MSVC (VS 2022 17.11 or newer) are supported. Installation has the full CI matrix, the C++23-versus-C++26 note and the MSVC note.

Status

1.0.0 is melon's first stable release. Every header outside melon/detail/ and melon/experimental/ is frozen API for the 1.x series, under semantic versioning — see API stability for the scope of the guarantee and the design decisions it rests on.

Documentation, license