Algorithms

Traversal algorithms

Breadth First Search

#include "melon/algorithm/breadth_first_search.hpp"
....
for(auto && vertex : breadth_first_search(graph)) {
    ...;
}

Depth First Search

#include "melon/algorithm/depth_first_search.hpp"
....
for(auto && vertex : depth_first_search(graph)) {
    ...;
}

Topological Sort

#include "melon/algorithm/topological_sort.hpp"
....
for(auto && vertex : topological_sort(graph)) {
    ...;
}

Strongly Connected Components

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

Shortest path algorithms

Dijkstra

#include "melon/algorithm/dijkstra.hpp"
....
for(auto && [vertex, distance] : dijkstra(graph, length_map, source)) {
    ...;
}

Bidirectional Dijkstra

#include "melon/algorithm/bidirectional_dijkstra.hpp"
....
bidirectional_dijkstra algorithm(graph, length_map, source, target);
auto distance = algorithm.run();
if(algorithm.path_found()) {
    for(auto && arc : algorithm.path()) {
        ...:
    }
}

Maximum flow algorithms

Edmonds Karp

#include "melon/algorithm/edmonds_karp.hpp"
....
edmonds_karp algorithm(graph, capacity_map, source, target);
algorithm.run();
auto max_flow = algorithm.flow_value();
for(auto && arc : algorithm.minimum_cut()) {
    ...:
}

Dinitz

#include "melon/algorithm/dinitz.hpp"
....
dinitz algorithm(graph, capacity_map, source, target);
algorithm.run();
auto max_flow = algorithm.flow_value();
for(auto && arc : algorithm.minimum_cut()) {
    ...:
}

Geometry algorithms

Bentley-Ottmann

#include "melon/algorithm/bentley_ottmann.hpp"
....
for(auto && [p, intersecting_segments_ids] :
    bentley_ottmann(segments_ids, segments_map)) {
    ...
}