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;
}

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, bidirectional Dijkstra, bi-objective Dijkstra, competing Dijkstras, 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, Graphviz printer, Erdős–Rényi generator, alias-method sampler, semirings, rationals

Requirements

Header-only and dependency-free. C++23 is the baseline; GCC 15 / C++26 is recommended.

Compiler Minimum version CI configuration
GCC 14 GCC 14 / C++23, GCC 15 / C++26
Clang 18 Clang 18 / C++23 (libstdc++ 14)
MinGW-w64 GCC 15 MinGW GCC 15 / C++26 (Windows)
MSVC — not supported

Status

melon is under active development towards its first stable release; the API is not frozen until 1.0.0 ships. See the changelog for what has landed, and API stability for what the 1.x guarantee will and will not cover.

Documentation, license