MELON stands for Modern and Efficient Library for Optimization in Networks. The goal of this project is to provide a graph library using modern C ++ functionalities in order to be more user-friendly than the Boost.Graph library while being as performant as the LEMON Graph library which is unfortunately not maintained and does not compile with C++ 20 and above. Implemented data structures and algorithms are often benchmarked in the repository https://github.com/fhamonic/melon_benchmark and shown to outperform both Boost.Graph and LEMON!

Work in progress.

How to link

MELON targets C++23; GCC 15 / C++26 is recommended. Every configuration below is tested by CI on every commit; MSVC is not supported (MinGW-w64 is the supported toolchain on Windows).

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

As a local Conan package (latest commit)

git clone 
cd melon
conan create . -u -b=missing -pr=<your_conan_profile>

Then add the dependency to melon in your project conanfile.txt or conanfile.py.

As a Conan center package (latest release, still depending on range-v3)

Just add melon/1.0.0-alpha.1 to your project conanfile.txt or conanfile.py.

Using CMAKE subdirectory

Either clone or add this git as submodule:

cd <your_project> && mkdir dependencies && cd dependencies
git clone https://github.com/fhamonic/melon

or

cd <your_project> && mkdir dependencies
git submodule add https://github.com/fhamonic/melon dependencies/melon

Import the library and link it to your CMake targets with

add_subdirectory(dependencies/melon)
...
target_link_libraries(<your_target> INTERFACE melon)

API stability

Starting with 1.0.0, melon follows semantic versioning: every header is frozen API for the whole 1.x series, with two explicit exceptions that carry no stability guarantee and may change or disappear in any release:

• melon/detail/ — implementation details, as well as any symbol in a detail/__detail namespace or prefixed with __;
• melon/experimental/ — work-in-progress data structures. These live in namespace melon::experimental, so nothing reaches the stable melon namespace by accident.

Documentation

📖 fhamonic.github.io/melon — sources under docs/.

The extensive use of concepts allows to provide genericity to the graph algorithms in the sense that they would work on any graph implementation fulfilling their requirements. Thus, this library aims to allow users to bring their own graph structures, best suited to their needs. However, we provide classical implementations of graphs such as static_digraph and mutable_digraph.

• Why melon and A first graph
• Graph concepts and Bringing your own graph
• Graph containers and Graph views
• Algorithms

To preview the documentation locally: pip install zensical && zensical serve.

Some code examples

Iterate on reachable vertices in the order of their distances from a source vertex:

#include "melon/algorithm/dijkstra.hpp"
#include "melon/container/static_digraph.hpp"
....
static_digraph graph = ...;
arc_map_t<static_digraph, double> length_map = ...;
vertex_t<static_digraph> s = ...; 

for(auto && [u, dist] : dijkstra(graph, length_map, s)) {
    ...;
}

Iterate over the vertices of each strongly connected component:

#include "melon/algorithm/strongly_connected_components.hpp"
#include "melon/container/static_digraph.hpp"
....
static_digraph graph = ...;
for(auto && component : strongly_connected_components(graph)) {
    for(auto && v : component) {
        ...;
    }
}

Roadmap

Concepts and containers:

• tree graphs
• planar graph
• bipartite graph

Algorithms:

• Network simplex
• Laplacian combinatorial solver
• planar map intersection

Utility:

• JSON serialization
• SVG / Graphviz printer