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

The beauty of Conan 2.0 allows this library to be linked either as a Conan package Git/CMake submodule. In both cases you need a recent compiler (at least GCC 12).

As a Conan package (preferred)

Clone this repository and run:

make package

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

melon/0.5

As git and cmake submodules

Either clone or add this git as submodule in a folder named, for example, "dependencies"

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

or

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(<some_target> INTERFACE melon)

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

How to Compile and Run Tests

Having a compiler (GCC 12+ required), CMake and Conan, compile and run tests with

make

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