File StaticGraph.h

↰ Parent directory (ADS/graph)

A static GRAPH for the engineered algorithms, beyond the book [see File Graph.h]: the compressed sparse rows of ArrayGraph [see File ArrayGraph.h] (the format CSR of the sparse matrices), with each arc of a weighted graph stored next to its weight, so that a scan of the arcs of u reads one contiguous run of ( head , weight ) pairs, and the arcs of each node sorted by head, which makes the reads of the visits that follow them go forward in memory.

Definition (ADS/graph/StaticGraph.h)

Detailed Description

With :math:` a = m ` arcs if oriented and :math:` a = 2 m ` if not, the arcs of u are the places :math:`[

mathit{off}( u ) leq k < mathit{off}( u + 1 ) , qquad mathit{off}( 0 ) = 0 , quad mathit{off}( n ) = a ,

` so that the graph takes :math:` 4 ( n + 1 ) + ( 4 + s ) a ` bytes, s the size of a weight (0 if unweighted). The graph is built from a list of edges in :math:` Theta( n + a ) ` time by two passes of counting sort, by head and then, stably, by tail, and an unoriented edge [ u , v ] gives the two arcs ( u , v ) and ( v , u ). There may be parallel arcs.

transpose() gives the graph with the arcs reversed, which the visits from the bottom up and the strongly connected components of a reversed graph need, and relabel() gives the same graph with the nodes renamed, e.g., by bfsOrder(), the order of a visit in breadth from a node and then from each node not reached (the ordering of Cuthill and McKee without its sort by degree), which puts close together the nodes that the algorithms visit close in time; both take :math:` Theta( n + a ) `. StaticGraph models the concept Graph, so that the algorithms of the book also apply to it.

The contracts [see File Contract.h]: the graph has n >= 0 nodes and fewer than :math:` 2^{31} ` arcs, its edges join two distinct nodes; the operations on a node need a node, relabel() a permutation of the nodes; the invariant is that the offsets do not decrease and end at a, and that the heads are nodes, in increasing order for each tail. The operations are defined in StaticGraph.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 9.4, https://algoritmicamente.it/materiali/libro/capitoli/cap09.pdf

  1. Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM, 2003, section 3.4, doi:10.1137/1.9780898718003

  1. Cuthill, J. McKee, Reducing the bandwidth of sparse symmetric matrices, Proceedings of the 24th ACM National Conference, 157-172, 1969, doi:10.1145/800195.805928

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

  • ADS/Contract.h (File Contract.h)

  • ADS/graph/Graph.h (File Graph.h)

  • ADS/graph/impl/StaticGraph.tpp

  • cstddef

  • ranges

  • span

  • tuple

  • type_traits

  • utility

  • variant

  • vector

Included By

Namespaces

Classes

Functions

Defines