MELON

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. 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

Compiler	Minimum version
GCC	12
Clang	17
MSVC	19

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.

Soon, as a Conan center package (latest release)

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)

Then ensure that your CMake can find Range-v3 and fmt with find_package calls.

Documentation

The extensive use of C++20 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.

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
• bipartite graph
• planar graph
• geometry coordinates (trilinear)

Algorithms:

• Bentley-Ottman (line segment intersections)
• planar map intersection
• Network simplex
• Traveling salesman

Utility:

• JSON serialization
• SVG / Graphviz printer