Coming from Boost.Graph or LEMON¶

If you have written graph code in C++ before, most of melon will be familiar under different names. This page is the translation table, followed by the four places where the model genuinely differs.

Vocabulary¶

Note the vocabulary choice: melon says arc for a directed edge and reserves edge for undirected graphs, following LEMON rather than Boost.Graph's edge-for-everything.

The same program, three ways¶

static_digraph_builder<static_digraph, double> builder(n);
builder.add_arc(0, 1, 7.0).add_arc(1, 2, 9.0);
auto [g, length] = builder.build();

for(auto && [v, dist] : dijkstra(g, length, 0u))
    std::println("{} {}", v, dist);

using G = adjacency_list<vecS, vecS, directedS, no_property,
                         property<edge_weight_t, double>>;
G g(n);
add_edge(0, 1, 7.0, g);
add_edge(1, 2, 9.0, g);

std::vector<double> dist(num_vertices(g));
dijkstra_shortest_paths(g, 0, distance_map(&dist[0]));
for(auto v : make_iterator_range(vertices(g)))
    std::println("{} {}", v, dist[v]);

ListDigraph g;
std::vector<ListDigraph::Node> node(n);
for(int i = 0; i < n; ++i) node[i] = g.addNode();
ListDigraph::ArcMap<double> length(g);
length[g.addArc(node[0], node[1])] = 7.0;
length[g.addArc(node[1], node[2])] = 9.0;

Dijkstra<ListDigraph, ListDigraph::ArcMap<double>> alg(g, length);
alg.run(node[0]);
for(ListDigraph::NodeIt v(g); v != INVALID; ++v)
    std::println("{} {}", g.id(v), alg.dist(v));

Four things that differ¶

1. Ranges, not iterator pairs or It classes¶

Everything that iterates returns a std::ranges range, usable directly in a for loop and composable with std::views:

// the five nearest out-neighbors, by arc length
for(auto && a : out_arcs(g, v) | std::views::filter([&](auto a) {
                    return length[a] < 10.0; }) | std::views::take(5)) { ... }

There is no tie(it, end) = vertices(g), no INVALID sentinel to compare against, and no graph_traits specialization to write.

2. Algorithms are lazy generators, not visitor-driven calls¶

Boost.Graph expresses "do something at each step" with a visitor class and named parameters; LEMON with init() / addSource() / processNextNode(). melon inverts the control flow: the algorithm is an input range, so the loop body is the visitor, and break is the early exit.

// Boost: a visitor struct, an exception thrown to stop early
// melon: this
for(auto && [v, dist] : dijkstra(g, length, s)) {
    if(dist > radius) break;
    reachable.push_back(v);
}

LEMON's stepwise interface is the closest analogue, and melon keeps it: finished(), current(), advance(), plus run() when you want the whole thing.

3. Data maps are created by the graph, not handed to it¶

Boost.Graph's property maps are read and written through get(pm, k) and put(pm, k, v), and come in interior and exterior flavours with make_iterator_property_map in between. LEMON's NodeMap is closer: it is constructed from the graph and uses operator[].

melon follows LEMON, through a free function:

auto dist = create_vertex_map<double>(g, 0.0);
dist[v] = 3.0;

The storage type is the graph's choice, and anything with operator[] qualifies as a map — std::vector, std::map, std::vector<bool>, your own type, or a lambda wrapped in views::map. See Mappings.

4. Concepts replace traits classes — and your type can be the graph¶

To make a type usable by Boost.Graph you specialize graph_traits and provide the free functions with the exact expected signatures. In melon you provide member functions or ADL free functions, and a concept checks them; there is no traits class to specialize, and what you do not provide is often synthesized from what you do.

An algorithm's requirements are visible in its signature and enforced at the call site:

template <outward_incidence_graph Graph, input_mapping<arc_t<Graph>> LengthMap,
          dijkstra_trait Traits>
    requires has_vertex_map<Graph>
class dijkstra;

Pass a graph without out-arcs and the error names outward_incidence_graph, not a missing member three instantiations deep.

What melon does not have¶

Boost.Graph's catalogue is far larger. melon has no planarity testing, no graph isomorphism, no matching, no min-cost flow, no A*, no Bellman–Ford, no graph I/O formats beyond a Graphviz printer. LEMON's LP/MIP interfaces have no counterpart either — that is a separate library by the same author. If you need one of those today, melon is a complement rather than a replacement.