Skip to content

A first graph

This page walks through the program on the home page, then extends it: reading distances and paths, attaching your own data, running the search on a view, and switching to a mutable graph.

Building a graph

static_digraph is melon's workhorse: an immutable compressed-adjacency structure whose vertices and arcs are consecutive integers from 0. It has no add_arc — arcs are collected first, then the structure is built in one pass, which is what makes its lookups cheap.

#include "melon/container/static_digraph.hpp"
#include "melon/utility/static_digraph_builder.hpp"

using namespace melon;

// six vertices, 0 to 5; one double of data per arc
static_digraph_builder<static_digraph, double> builder(6);

builder.add_arc(0, 1, 7.0)
    .add_arc(0, 2, 9.0)
    .add_arc(0, 5, 14.0)
    .add_arc(1, 3, 15.0)
    .add_arc(2, 3, 12.0)
    .add_arc(2, 5, 2.0)
    .add_arc(3, 4, 6.0)
    .add_arc(5, 4, 9.0);

auto [graph, length_map] = builder.build();

The builder is variadic in its arc properties: static_digraph_builder<static_digraph, double, std::string> would take an extra argument per add_arc and return an extra map from build(). With no property at all, build() still returns a tuple, so the idiom is auto [graph] = builder.build();.

build() renumbers the arcs

Arcs are sorted by source, then by target, before the graph is built. An arc's identifier is therefore its rank in that order, not its insertion index. The property maps are permuted along with it, so length_map[a] is always the right length for arc a — but do not record the value add_arc was called with as an arc id.

What you got back

graph is a static_digraph. length_map is a plain std::vector<double>, which is all melon needs: it is indexed by arc, and std::vector already models input_mapping.

The two type aliases you will use everywhere are vertex_t<G> and arc_t<G> — for static_digraph both are unsigned int, which is why the sources below are written 0u:

static_assert(std::same_as<vertex_t<static_digraph>, unsigned int>);
static_assert(std::same_as<arc_t<static_digraph>, unsigned int>);

Looking around

Every accessor is a free function in namespace melon, called unqualified thanks to the using namespace melon above:

std::println("{} vertices, {} arcs", num_vertices(graph), num_arcs(graph));

for(auto && v : vertices(graph)) {
    std::println("vertex {} has out-degree {}", v, out_degree(graph, v));

    for(auto && a : out_arcs(graph, v))
        std::println("  arc {} to {} of length {}", a,
                     arc_target(graph, a), length_map[a]);

    // same traversal, arcs elided
    for(auto && w : out_neighbors(graph, v)) std::println("  -> {}", w);
}

// every arc with both its endpoints, in one range
for(auto && [a, st] : arcs_entries(graph)) {
    auto && [s, t] = st;
    std::println("arc {}: {} -> {}", a, s, t);
}

static_digraph stores in-arcs too, so in_arcs, in_neighbors and in_degree work as well. A structure that only stores out-arcs would still answer out_neighbors, arcs and arcs_entries — melon synthesizes them — but calling in_arcs on it would be a compile error, which is exactly the point.

Running an algorithm

dijkstra deduces its template arguments from its constructor, so you name the class and pass the graph, the length map, and a source:

#include "melon/algorithm/dijkstra.hpp"

for(auto && [v, dist] : dijkstra(graph, length_map, 0u)) {
    std::println("vertex {} at distance {}", v, dist);
}

The loop drives the search: each iteration settles one vertex and yields it with its final distance, in nondecreasing order. Nothing runs before the loop starts, and break stops the search where it stands — no visitor and no callback needed. That is worth using:

// stop as soon as the target is settled
for(auto && [v, dist] : dijkstra(graph, length_map, 0u)) {
    if(v == 4u) { std::println("d(0, 4) = {}", dist); break; }
}

The object can also be held and stepped by hand, which is what you want when two searches must advance together — see Algorithms are ranges.

Distances and paths

The default Dijkstra keeps no history: it holds one status map and one heap, and forgets a vertex once it has yielded it. Asking for dist(v) or path_to(v) after the fact requires telling it to remember, through a traits type:

struct my_traits : dijkstra_default_traits<static_digraph, double> {
    static constexpr bool store_distances = true;
    static constexpr bool store_paths = true;
};

dijkstra alg(my_traits{}, graph, length_map, 0u);
alg.run();

std::println("d(0, 4) = {}", alg.dist(4u));
for(auto && a : alg.path_to(4u))  // arcs, from the target back to the source
    std::println("  via arc {}", a);

dist() and path_to() are constrained on those flags, so the default configuration does not merely assert at runtime — the members are not there to call.

Attaching your own data

Ask the graph for the map; it picks the storage:

auto visits = create_vertex_map<int>(graph, 0);   // one int per vertex, zeroed
auto in_tree = create_arc_map<bool>(graph, false);

visits[3u] += 1;
in_tree[0u] = true;

static_assert(std::same_as<decltype(visits), vertex_map_t<static_digraph, int>>);

For static_digraph those are static_maps — a single allocation, indexed in constant time. A graph with std::string vertices could return a hash map instead, and the code above would not change. That indirection is what lets an algorithm require has_vertex_map<G, int> and work on both.

Running on a view

views::reverse(g) is a graph whose arcs point the other way. It holds a reference and rewrites nothing, so running Dijkstra on it computes distances to the source instead of from it:

#include "melon/views/reverse.hpp"

for(auto && [v, dist] : dijkstra(views::reverse(graph), length_map, 4u)) {
    std::println("vertex {} is at distance {} from 4", v, dist);
}

Views are graphs, so they nest: views::reverse(views::subgraph(g, keep_vertex)) is a perfectly ordinary graph to melon. See Graph views.

The length map does not have to be a container either — a callable works directly, and no storage is materialized at all:

// unit lengths, computed on the fly
for(auto && [v, hops] : dijkstra(graph, [](auto &&) { return 1; }, 0u))
    std::println("vertex {} at {} hops", v, hops);

The lambda is wrapped into a mapping for you: every algorithm routes its map arguments through views::mapping_all, which subscripts a callable by calling it. The same holds for a std::map, whose operator[] is not const-callable.

When the graph must change

static_digraph cannot grow. mutable_digraph can: it supports vertex and arc creation and removal, and re-pointing an arc's endpoints.

#include "melon/container/mutable_digraph.hpp"
#include "melon/graph.hpp"   // container headers do not pull in the free functions

mutable_digraph g;
auto a = create_vertex(g);
auto b = create_vertex(g);
auto c = create_vertex(g);

auto ab = create_arc(g, a, b);
create_arc(g, a, c);
create_arc(g, c, b);

remove_arc(g, ab);
remove_vertex(g, c);

Removals do not renumber what remains, so identifiers stay valid — but they leave holes, and vertices(g) is then a filtered range rather than an iota. Graph containers compares the two structures and their costs.

Next steps