structures/

Umbrella for discrete structures and the algorithms that run on them.

Fundamental graph algorithms: connectivity, Dijkstra, Kruskal MST, BFS, and DFS <structures/algorithms/traversal.hpp>

structures::bfs – structures::connected_components – structures::dfs – structures::dijkstra – structures::is_connected – structures::minimum_spanning_tree

Contracts for discrete structures, stated as the algebra they maintain <structures/concepts.hpp>

concepts::addressable_priority_queue – concepts::equivalence_relation – concepts::incidence_structure – concepts::weighted_incidence

O(1) amortized bucket priority queue for minimum degree elimination in graph algorithms <structures/containers/degree_queue.hpp>

structures::basic_degree_queue – structures::degree_queue – structures::degree_queue_32

High-performance Disjoint-Set (Union-Find) with path compression and union by rank <structures/containers/disjoint_set.hpp>

basic_disjoint_set – disjoint_set – disjoint_set_32

Indexed binary heap supporting O(log N) push, pop, decrease_key, and element lookup <structures/containers/indexed_priority_queue.hpp>

indexed_priority_queue – max_indexed_pq – min_indexed_pq

Runtime verification of the laws discrete structures maintain <structures/debug.hpp>

structures::debug::check_connected – structures::debug::check_contains – structures::debug::check_index_bounds – structures::debug::check_not_contains – structures::debug::check_positive_weight – structures::debug::check_vertex_bounds – structures::debug::verify_degree_consistency – structures::debug::verify_equivalence_relation – structures::debug::verify_handshake_lemma – structures::debug::verify_heap_order – structures::debug::verify_laplacian_structure

Exact and randomized clique reduction (star-mesh transformation) on multigraphs <structures/graph/clique.hpp>

structures::add_exact_clique – structures::collect_neighbors – structures::sample_biclique_tree – structures::sample_clique – structures::sample_clique_tree

Canonical random and structured graph generators <structures/graph/generators.hpp>

structures::complete_graph – structures::cycle_graph – structures::erdos_renyi – structures::grid_2d – structures::path_graph – structures::random_spanning_tree – structures::star_graph

Weighted graph data structure with adjacency list and matrix/Laplacian conversions <structures/graph/graph.hpp>

graph

Weighted multigraph data structure with multi-edge multiplicities for RandNLA and Laplacian solvers <structures/graph/multigraph.hpp>

structures::multi_edge – structures::multigraph – structures::to_multigraph

Implicit weighted graph for a uniform Cartesian grid <structures/graph/structured_grid.hpp>

structured_grid_graph