Traversals and components¶

All of these are ranges: the loop drives them, and break stops them. The graph, when it appears in a constructor, follows the ownership rule.

breadth_first_search¶

#include "melon/algorithm/breadth_first_search.hpp"

for(auto && v : breadth_first_search(graph, 0u)) std::print(" {}", v);
//  0 1 2 5 3 4

Requires outward_adjacency_graph and has_vertex_map — arcs are never inspected, so a graph that only lists neighbors is enough.

On a digraph \(G = (V, A)\) with \(n = |V|\) and \(m = |A|\), the search from \(s\) settles vertices in nondecreasing hop distance

one layer at a time, in \(O(n + m)\).

Traits.

struct bfs_traits {
    static constexpr bool store_pred_vertices = false;
    static constexpr bool store_pred_arcs = true;
    static constexpr bool store_distances = true;
    static constexpr bool store_traversal_range = false;
};

breadth_first_search bfs(bfs_traits{}, graph, 0u);
bfs.run();
for(auto && v : vertices(graph))
    if(bfs.reached(v)) std::println("{} at {} hops", v, bfs.dist(v));

Other members: reset(), add_source(v), reached(v), reached_map(), base().

depth_first_search¶

#include "melon/algorithm/depth_first_search.hpp"

for(auto && v : depth_first_search(graph, 0u)) std::print(" {}", v);
//  0 1 3 4 2 5

Same requirements as BFS. The traversal is iterative — an explicit stack of partially consumed incidence ranges — so depth costs heap memory, not call frames, and a path of a million vertices does not overflow the stack.

Vertices come out in preorder of the search tree \(T_s\) — each before any vertex first reached through it — in \(O(n + m)\). The predecessor chain is the tree path, so

with equality only when the out-arc order happens to favour it.

Traits.

topological_sort¶

#include "melon/algorithm/topological_sort.hpp"

for(auto && v : topological_sort(graph)) std::print(" {}", v);
//  0 1 2 3 5 4

Yields the vertices of a DAG in an order where every arc goes forward. Requires outward_incidence_graph, has_vertex_map and has_num_vertices — the constructor reserves num_vertices and keeps an iterator into that buffer, so the count must be known; unlike the searches, it takes no source — it starts from every vertex with no incoming arc and discovers the rest by decrementing in-degrees.

Kahn's algorithm: a numbering \(\pi : V \to \{1, \dots, n\}\) with \(\pi(u) < \pi(v)\) for every arc \(u \to v\) exists exactly when \(G\) is acyclic, and is produced by repeatedly emitting a vertex of in-degree zero and deleting its out-arcs, in \(O(n + m)\).

Traits are store_ranks and store_critical_paths. store_ranks enables rank(v): the number of arcs on the longest path from a source down to v, \(\mathrm{rank}(v) = \max_{u \to v} \mathrm{rank}(u) + 1\) with \(0\) at the sources, so that rank(u) < rank(v) for every arc u -> v. It is a level, not a position in the emitted sequence — vertices that no path orders relative to each other share a rank. store_critical_paths enables pred_vertex(v), pred_arc(v) and critical_path_to(t).

auto alg = topological_sort(graph);
for(auto && v : alg) { /* ... */ }
if(!alg.is_acyclic()) { /* the graph had a cycle */ }

strongly_connected_components¶

#include "melon/algorithm/strongly_connected_components.hpp"

for(auto && component : strongly_connected_components(graph)) {
    for(auto && v : component) std::print(" {}", v);
    std::println("");
}

Tarjan's algorithm, iterative for the same reason as DFS. Each current() is a range of the vertices of one component, and components come out in reverse topological order of the condensation — the sinks first.

Two vertices are strongly connected when each reaches the other, \(u \sim v \iff u \leadsto v \wedge v \leadsto u\); the classes of \(\sim\) are the components, and contracting each to a vertex gives the condensation, always a DAG. One DFS finds them all in \(O(n + m)\), popping a component each time the search leaves its root.

With the store_component_ids traits flag, the algorithm records a component id per vertex as each component is popped — dense, in emission order — and component_id(u) answers from those ids once u's component has been yielded, so directly after a run(). Comparing ids is the same-component query, and component_ids_map() views the whole map, for passing to anything that takes a vertex map:

struct scc_traits {
    static constexpr bool store_component_ids = true;
};

strongly_connected_components alg(scc_traits{}, graph);
alg.run();
if(alg.component_id(u) == alg.component_id(v)) { ... }  // mutually reachable
auto ids = alg.component_ids_map();  // ids[v] == 0 for the first component, ...

Without the flag none of these exist and no id map is stored. num_components() is available either way: the number of components yielded so far, current() included, so the component count of the graph after a run().

Requires outward_adjacency_graph and has_vertex_map.

Connected components¶

connected_components works on an undirected graph:

#include "melon/algorithm/connected_components.hpp"

auto ugraph = views::undirect(graph);
for(auto && component : connected_components(ugraph)) { ... }

The classes of \(u \sim v \iff\) some path joins \(u\) and \(v\), direction ignored: one breadth-first search per component, \(O(n + m)\) in all.

For a digraph, weakly_connected_components(g) is the wrapper that undirects it first:

for(auto && component : weakly_connected_components(graph)) {
    for(auto && v : component) std::print(" {}", v);
    std::println("");
}

It requires the digraph to be both outward_incidence_graph and inward_incidence_graph, plus has_vertex_map, since the underlying views::undirect must walk both ways.

traversal_forest¶

#include "melon/algorithm/traversal_forest.hpp"

for(auto && tree : traversal_forest(graph)) {
    for(auto && v : tree) std::print(" {}", v);
    std::println("");
}

Repeats a breadth-first search from each not-yet-reached source until every vertex has been visited, yielding one range of vertices per tree. With no source range it uses vertices(g); pass one to control the order and the roots:

std::vector<vertex_t<static_digraph>> roots = {3u, 0u};
for(auto && tree : traversal_forest(graph, roots)) { ... }

This is the reachability-partition counterpart of weakly_connected_components: the trees partition the vertices, but by forward reachability from the chosen roots, so a vertex is placed in the first tree that reaches it.

With roots \(r_1, r_2, \dots\) in the given order and \(R(r)\) the set of vertices reachable from \(r\), the \(i\)-th tree spans

an already-reached root is skipped, and the whole forest costs \(O(n + m)\).

Choosing¶