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.

⚠️ Since commit e494eb8d7db1629af280354dc4d76d3c36ed8701 the use of Range-v3 has been replaced by C++26 ranges functionnalities which are currently only implemented in GCC 15.

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.

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

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)

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. We describe the fundamental concepts of the library and their motivation in the wiki page Concepts. 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'. The graph structures provided are described in the wiki page Containers#Graph-structures. Algorithms and code examples are available on the wiki page Algorithms.

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) {
        ...;
    }
}

Concepts and containers:

• tree graphs
• bipartite graph
• planar graph

Algorithms:

• planar map intersection
• Network simplex

Utility:

• JSON serialization
• SVG / Graphviz printer