Skip to content

algorithms.md

Latest commit

 

History

History
439 lines (319 loc) · 18.5 KB

algorithms.md

File metadata and controls

439 lines (319 loc) · 18.5 KB
graph-v3 logo

Algorithms

← Back to Documentation Index

Table of Contents

Overview

All graph-v3 algorithms require a graph satisfying the adjacency_list<G> concept. This supports two families of vertex storage:

  • Index-based (index_adjacency_list<G>) — contiguous, integer-indexed random-access containers (dynamic_graph with vector/deque vertices, compressed_graph, undirected_adjacency_list, or any range-of-ranges)
  • Map-based (mapped_adjacency_list<G>) — sparse vertex ID containers (dynamic_graph with map/unordered_map vertices) where vertex IDs need not be contiguous

For map-based graphs, algorithm output parameters (distances, predecessors, component labels, etc.) should be vertex property maps created via make_vertex_property_map<G, T>(g, init_value) instead of pre-sized vectors.

Algorithms follow a consistent pattern:

  • Input: graph g, source vertex (or vertices), and optional parameters
  • Output: filled via caller-provided output ranges (distances, predecessors, component labels) — not returned by value
  • Weight functions: passed as callable WF(g, uv) returning edge weight
  • Visitors: optional structs with callback methods for fine-grained event hooks, or assemble one from reusable pieces with the composable visitor toolkit
  • Initialization: use init_shortest_paths() to properly set up distance and predecessor vectors before calling shortest-path algorithms

Bidirectional graphs: Algorithms that benefit from incoming-edge access (e.g., Kosaraju SCC, transpose graph) can use bidirectional dynamic_graph containers. Search views (BFS, DFS, topological sort) also accept an in_edge_accessor for reverse traversal — see Bidirectional Access.

#include <graph/algorithm/dijkstra_shortest_paths.hpp>

// Index-based graph: use pre-sized vectors
std::vector<int>    distance(num_vertices(g));
std::vector<size_t> predecessor(num_vertices(g));

init_shortest_paths(distance, predecessor);

dijkstra_shortest_paths(g, 0, distance, predecessor,
    [](const auto& g, const auto& uv) { return edge_value(g, uv); });
#include <graph/algorithm/dijkstra_shortest_paths.hpp>
#include <graph/adj_list/vertex_property_map.hpp>

// Map-based graph: use vertex property maps
using G = /* some mapped_adjacency_list graph */;
auto distances    = make_vertex_property_map<G, int>(g, infinite_distance<int>());
auto predecessors = make_vertex_property_map<G, vertex_id_t<G>>(g, vertex_id_t<G>{});
for (auto&& [uid, u] : views::vertexlist(g))
    predecessors[uid] = uid;

dijkstra_shortest_paths(g, source_id, distances, predecessors,
    [](const auto& g, const auto& uv) { return edge_value(g, uv); });

Algorithm Catalog

All headers are under include/graph/algorithm/.

By Category

Shortest Paths

Algorithm Header Brief description Time Space
Bellman-Ford bellman_ford_shortest_paths.hpp Shortest paths with negative weights; cycle detection O(V·E) O(1)
Dijkstra dijkstra_shortest_paths.hpp Single/multi-source shortest paths (non-negative weights) O((V+E) log V) O(V)

Traversal

Algorithm Header Brief description Time Space
BFS breadth_first_search.hpp Level-order traversal from source(s) O(V+E) O(V)
DFS depth_first_search.hpp Depth-first traversal with edge classification O(V+E) O(V)
Topological Sort topological_sort.hpp Linear ordering of DAG vertices O(V+E) O(V)

Components

Algorithm Header Brief description Time Space
Articulation Points articulation_points.hpp Cut vertices whose removal disconnects the graph O(V+E) O(V)
Biconnected Components biconnected_components.hpp Maximal 2-connected subgraphs (Hopcroft-Tarjan) O(V+E) O(V+E)
Connected Components connected_components.hpp Undirected CC, directed SCC (Kosaraju), union-find (afforest) O(V+E) O(V)
Tarjan SCC tarjan_scc.hpp Single-pass directed SCC via low-link values O(V+E) O(V)

Minimum Spanning Trees

Algorithm Header Brief description Time Space
Kruskal MST mst.hpp Edge-list-based MST via union-find O(E log E) O(E+V)
Prim MST mst.hpp Adjacency-list-based MST via priority queue O(E log V) O(V)

Analytics

Algorithm Header Brief description Time Space
Jaccard Coefficient jaccard.hpp Pairwise neighbor-set similarity per edge O(V + E·d) O(V+E)
Label Propagation label_propagation.hpp Community detection via majority-vote labels O(E) per iter O(V)
Maximal Independent Set mis.hpp Greedy MIS (non-adjacent vertex set) O(V+E) O(V)
Triangle Count tc.hpp Count 3-cliques via sorted-list intersection O(m^{3/2}) O(1)

Alphabetical

Algorithm Category Header Time Space
Articulation Points Components articulation_points.hpp O(V+E) O(V)
Bellman-Ford Shortest Paths bellman_ford_shortest_paths.hpp O(V·E) O(1)
BFS Traversal breadth_first_search.hpp O(V+E) O(V)
Biconnected Components Components biconnected_components.hpp O(V+E) O(V+E)
Connected Components Components connected_components.hpp O(V+E) O(V)
Kosaraju SCC Components connected_components.hpp O(V+E) O(V)
DFS Traversal depth_first_search.hpp O(V+E) O(V)
Dijkstra Shortest Paths dijkstra_shortest_paths.hpp O((V+E) log V) O(V)
Jaccard Coefficient Analytics jaccard.hpp O(V + E·d) O(V+E)
Kruskal MST MST mst.hpp O(E log E) O(E+V)
Label Propagation Analytics label_propagation.hpp O(E) per iter O(V)
Maximal Independent Set Analytics mis.hpp O(V+E) O(V)
Prim MST MST mst.hpp O(E log V) O(V)
Topological Sort Traversal topological_sort.hpp O(V+E) O(V)
Tarjan SCC Components tarjan_scc.hpp O(V+E) O(V)
Triangle Count Analytics tc.hpp O(m^{3/2}) O(1)

Shortest Paths

Dijkstra's Shortest Paths

Finds single-source or multi-source shortest paths in a graph with non-negative edge weights using a binary-heap priority queue. Provides both dijkstra_shortest_paths (distances + predecessors) and dijkstra_shortest_distances (distances only) variants.

Time: O((V+E) log V) — Space: O(V) — Header: dijkstra_shortest_paths.hpp

Bellman-Ford Shortest Paths

Finds shortest paths supporting negative edge weights and detects negative-weight cycles. Returns std::optional<vertex_id_t<G>> — empty if no negative cycle, or a vertex on the cycle. Use find_negative_cycle to extract the full cycle path.

Time: O(V·E) — Space: O(1) — Header: bellman_ford_shortest_paths.hpp

Traversal

Breadth-First Search

Explores vertices in level-order (FIFO) from one or more sources. Entirely visitor-driven — you provide callback methods for vertex/edge events. Supports single-source and multi-source variants.

Time: O(V+E) — Space: O(V) — Header: breadth_first_search.hpp

Depth-First Search

Performs iterative DFS with three-color marking (White/Gray/Black), enabling precise edge classification into tree, back, and forward/cross edges. Foundation for cycle detection, topological sorting, and SCC discovery.

Time: O(V+E) — Space: O(V) — Header: depth_first_search.hpp

Topological Sort

Produces a linear ordering of vertices in a DAG such that for every edge (u,v), u appears before v. Returns bool — false if a cycle is detected. Supports full-graph, single-source, and multi-source variants.

Time: O(V+E) — Space: O(V) — Header: topological_sort.hpp

Components

Connected Components

Three algorithms in one header: connected_components (DFS-based, undirected), kosaraju (two-pass DFS for directed SCC, uses in_edge_accessor for the reverse pass on bidirectional graphs), and afforest (union-find with neighbor sampling, parallel-friendly).

Kosaraju’s algorithm works with any graph that supports both outgoing and incoming edge iteration (i.e., bidirectional_adjacency_list concept). A transpose_graph view is also available for algorithms that need a transposed adjacency structure:

#include <graph/algorithm/connected_components.hpp>
#include <graph/algorithm/transpose_graph.hpp>

Time: O(V+E) — Space: O(V) — Header: connected_components.hpp

Biconnected Components

Finds all maximal 2-connected subgraphs using the iterative Hopcroft-Tarjan algorithm. Articulation points appear in multiple components; bridges form their own 2-vertex components.

Time: O(V+E) — Space: O(V+E) — Header: biconnected_components.hpp

Articulation Points

Finds cut vertices whose removal disconnects the graph, using the iterative Hopcroft-Tarjan algorithm with discovery times and low-link values. Each articulation point is emitted exactly once.

Time: O(V+E) — Space: O(V) — Header: articulation_points.hpp

Minimum Spanning Trees

Kruskal's Algorithm

Edge-list-based MST using sort + union-find. Returns {total_weight, num_components}. Includes inplace_kruskal variant that sorts input in-place. Pass std::greater<>{} for maximum spanning tree.

Time: O(E log E) — Space: O(E+V) — Header: mst.hpp

Prim's Algorithm

Adjacency-list-based MST using a priority queue. Grows the MST from a seed vertex, filling predecessor and weight arrays. Returns total MST weight.

Time: O(E log V) — Space: O(V) — Header: mst.hpp

Graph Analytics

Triangle Count

Counts 3-cliques via merge-based sorted-list intersection. Requires adjacency lists sorted by target ID (ordered_vertex_edges concept). Works with sorted-edge containers (vos, dos) and undirected_adjacency_list.

Time: O(m^{3/2}) — Space: O(1) — Header: tc.hpp

Maximal Independent Set

Greedy MIS — finds a maximal set of non-adjacent vertices starting from a seed. Result is seed-dependent (different seeds may yield different-sized sets). Self-loops exclude a vertex from the MIS.

Time: O(V+E) — Space: O(V) — Header: mis.hpp

Jaccard Coefficient

Computes pairwise neighbor-set similarity $J(u,v) = |N(u) \cap N(v)| / |N(u) \cup N(v)|$ for every directed edge. Callback-driven — invokes a user-provided callable for each edge with its coefficient in [0.0, 1.0].

Time: O(V + E·d) — Space: O(V+E) — Header: jaccard.hpp

Label Propagation

Community detection via iterative majority-vote label propagation. Each vertex adopts the most frequent label among its neighbors until convergence. Supports partial labeling via an empty-label sentinel. Tie-breaking is random.

Time: O(E) per iteration — Space: O(V) — Header: label_propagation.hpp

Common Infrastructure

All shortest-path algorithms share utilities from traversal_common.hpp:

Utility Purpose
init_shortest_paths(distances) Set all distances to infinity
init_shortest_paths(distances, predecessors) Set distances to infinity, predecessors to self
infinite_distance<T>() Returns the "infinity" sentinel for type T
zero_distance<T>() Returns the additive identity for type T

Visitors

Algorithms accept an optional visitor struct with callback methods. Only the callbacks you define are called — unimplemented callbacks are silently skipped.

Shortest-path visitor events:

Event Called when
on_initialize_vertex(g, u) Before traversal starts, for each vertex
on_discover_vertex(g, u) Vertex first reached
on_examine_vertex(g, u) Vertex popped from queue
on_examine_edge(g, uv) Edge examined
on_edge_relaxed(g, uv) Edge improved a shorter path
on_edge_not_relaxed(g, uv) Edge did not improve path
on_edge_minimized(g, uv) Edge achieved final minimum (Bellman-Ford)
on_edge_not_minimized(g, uv) Edge not at final minimum (Bellman-Ford)

DFS-specific visitor events:

Event Called when
on_start_vertex(g, u) DFS root vertex
on_tree_edge(g, uv) Edge to unvisited vertex (White → Gray)
on_back_edge(g, uv) Edge to ancestor (Gray vertex)
on_forward_or_cross_edge(g, uv) Edge to already-finished vertex (Black)
on_finish_edge(g, uv) All descendants of edge target explored
on_finish_vertex(g, u) All adjacent edges explored

Each callback also has an _id variant that receives vertex/edge IDs instead of descriptors.

Composable visitors

Instead of hand-writing a visitor struct, you can assemble one from reusable pieces with the toolkit in <graph/algorithm/visitor_factory.hpp> (also pulled in by the algorithms.hpp umbrella header). It is the graph-v3 analogue of Boost.Graph's make_bfs_visitor / event-tag combinators. There are three layers:

1. Single-event adaptors — wrap any (g, x) callable so it fires for exactly one event. One adaptor exists per event name (on_discover_vertex, on_tree_edge, on_edge_relaxed, …):

#include <graph/algorithms.hpp>
using namespace graph;

std::vector<vertex_id_t<G>> order;
breadth_first_search(g, s,
    on_discover_vertex([&](auto& g, auto u) { order.push_back(vertex_id(g, u)); }));

2. make_visitor(...) — fan a single traversal out to several sub-visitors. A composite only exposes an on_X method when at least one child handles event X, so unused events still compile away to nothing. Descriptor-form and id-form children can be mixed freely:

auto pred = make_vertex_property_map<G, vertex_id_t<G>>(g);
auto dist = make_vertex_property_map<G, int>(g);
std::vector<vertex_id_t<G>> order;

breadth_first_search(g, s,
    make_visitor(
        on_tree_edge(predecessor_recorder(pred)),
        on_tree_edge(distance_recorder(dist)),   // hop-count layering
        on_discover_vertex([&](auto& g, auto u) { order.push_back(vertex_id(g, u)); })));

3. Prebuilt recorders — ready-made (g, x) -> void callables for the most common bookkeeping; you choose the event to bind them to:

Recorder Records Typical event
predecessor_recorder(pred) pred[target] = source on_tree_edge (BFS/DFS), on_edge_relaxed (Dijkstra/Bellman-Ford)
distance_recorder(dist, weight_fn) dist[target] = dist[source] + weight(g, uv) on_edge_relaxed (weighted)
distance_recorder(dist) dist[target] = dist[source] + 1 on_tree_edge (hop-count layering)
time_stamper(time_map, clock) time[u] = clock++ on_discover_vertex / on_finish_vertex

Because the recorders are event-agnostic, the same pieces work for Dijkstra by binding them to the relaxation event:

auto pred = make_vertex_property_map<G, vertex_id_t<G>>(g);
dijkstra_shortest_paths(g, s, dist, weight,
    make_visitor(
        on_edge_relaxed(predecessor_recorder(pred)),
        on_edge_relaxed(distance_recorder(dist, weight))));

A time_stamper advances its clock by reference, so two stampers sharing one counter produce interleaved discover/finish timestamps:

auto discover = make_vertex_property_map<G, int>(g);
auto finish   = make_vertex_property_map<G, int>(g);
int  clock    = 0;
depth_first_search(g, s,
    make_visitor(
        on_discover_vertex(time_stamper(discover, clock)),
        on_finish_vertex(time_stamper(finish, clock))));

Misspelled event names are caught at compile time: BFS, DFS, Dijkstra, and Bellman-Ford static_assert on valid_visitor, so a visitor with no recognized on_* method produces a clear diagnostic instead of silently doing nothing.

Roadmap

The following algorithms are planned but not yet implemented:

  • A* search
  • Bidirectional Dijkstra
  • Johnson's all-pairs shortest paths
  • Floyd-Warshall all-pairs shortest paths
  • Maximum flow (push-relabel, Dinic's)
  • Minimum cut
  • Graph coloring
  • Betweenness centrality
  • PageRank

See Also