graph
O(deg u) per walk of out(u).
Generated from spec/std/graph.cp by cpl doc --format json.
Next
pub trait Next<V>O(deg u) per walk of out(u).
What every graph algorithm walks: the arcs out of u. Implemented by
Graph, by any [V]S with S: Seq of arcs, and by any fn V -> Seq.
Next.Arc
type Arc: Target<V>Next.out
fn out(self, u: V) -> yields Self.ArcThe arcs out of u, lazily. Every graph algorithm reads the graph only through this.
- cost: O(1) per arc yielded
- order: the implementation's arc order (input order for
Graph, list order for[V]List) - traps: never
Examples:
domain V = 0..3; let g: [V]List<V> = [[2, 1], [], []]; g.out(0).collect() == [2, 1]
Target
pub trait Target<V>O(1). Where an arc leads. A plain vertex is its own target, and a record
with a to: V field is one (a field is a @get).
Target.to
fn to(self) -> VThe vertex an arc leads to. A plain vertex is its own target; a record's to field is
its target.
- cost: O(1)
- traps: never
Examples:
domain V = 0..3; V(2).to == 2domain V = 0..3; let a: (to: V, w: Int) = (to: 1, w: 7); a.to == 1
Weighted
pub trait Weighted<W>O(1). The weight of an arc: a record with a w field, or .weighted(f).
Weighted.w
fn w(self) -> WThe weight of an arc: its w field, or f(a) through g.weighted(f).
- cost: O(1) plus the cost of
funderweighted - traps: never
Examples:
domain V = 0..3; let a: (to: V, w: Int) = (to: 1, w: 7); a.w == 7
Edged
pub trait Edged<E>O(1). The edge an arc belongs to; both arcs of an undirected edge share it.
Edged.e
fn e(self) -> EThe edge an arc belongs to. Both arcs of an undirected edge carry the same e.
- cost: O(1)
- traps: never
Examples:
domain V = 0..2; domain E = 0..1; let es: [E](u: V, v: V) = [(u: 0, v: 1)]; let g = Graph.undirected(es); g.out(0).collect()[0].e == g.out(1).collect()[0].e
WeightedNext
pub trait WeightedNext<V, W> = Next<V> where Self.ArcA graph whose arcs carry weights: shortest paths, MST over arcs, DAG folds.
EdgedNext
pub trait EdgedNext<V, E> = Next<V> where Self.ArcA graph whose arcs carry edge ids: bridges, two-edge components, edge blocks. These skip the arc back along the same edge, not to the same vertex, so parallel edges are right.
EdgeArc
pub type EdgeArc<V, E, R> = (to: V, e: E, ..R without (u, v))The arc a build stores by default: the target, the edge id, and every
field of the edge record except u and v. Every carried field must be
plain; a heap field is a compile error that points at keep:.
Reweighted
pub struct Reweighted<G, F>O(1) per arc read: g.weighted(f), the arcs of g with .w read as
f(a) (or f(u, a)), .to and .e passed through. Nothing is stored.
Tree
pub type Tree<V> = [0..V.len - 1](u: V, v: V)O(n) to read.
The V.len - 1 edges of a tree on V, one u v pair per line, as an input
gives them. cpl stress makes and shrinks it as a tree.
SimpleGraph
pub type SimpleGraph<V, E> = [E](u: V, v: V)O(m) to read.
One edge on V for each value of E, u v per line, with no loop and no
pair twice. cpl stress makes and shrinks it so.
ConnectedGraph
pub type ConnectedGraph<V, E> = [E](u: V, v: V)O(n + m) to read (connectivity is validated).
A SimpleGraph in which every vertex reaches every other.
Dag
pub type Dag<V, E> = [E](u: V, v: V)O(m) to read.
One arc u -> v on V for each value of E, with no arc twice and no
directed cycle. cpl stress makes and shrinks it so.
Digraph
pub type Digraph<V, E> = [E](u: V, v: V)O(n + m) to read (acyclicity is validated).
One arc u -> v on V for each value of E, with no loop and no arc
twice; u v and v u are two arcs. cpl stress makes and shrinks it so.
Graph
pub struct Graph<V: Domain, A: Target<V>>O(n + m) memory and build.
A fixed graph in compressed sparse row form: n + 1 offsets and one arcs
list, the arcs of each vertex contiguous and in input order. Immutable; a
graph that grows is a [V]List of arcs, which is already a Next.
Graph.directed
fn directed<E: Domain, R: (u: V, v: V, ..), B: Target<V>>( edges: [E]R, keep: EdgeArc<V, E, R> -> B = a => a, ) -> Graph<V, B>A graph with one arc u -> v per edge of edges, in compressed sparse rows.
The arcs out of each vertex keep the order of their edges in edges (a stable counting
sort), so DFS orders and first-found answers are deterministic. Each arc is
EdgeArc<V, E, R>, the edge record with u, v replaced by to, e, unless keep
maps it to something else; keep runs once per arc at build and what it returns is
stored.
- cost: O(n + m) time and memory, plus
mcalls ofkeep - empty: no edges gives every vertex no arcs; an empty
Vgives the empty graph - traps: never
Examples:
domain V = 0..3; domain E = 0..2; let es: [E](u: V, v: V) = [(u: 0, v: 2), (u: 0, v: 1)]; Graph.directed(es).out(0).collect() == [(to: 2, e: 0), (to: 1, e: 1)]domain V = 0..3; domain E = 0..2; let es: [E](u: V, v: V) = [(u: 0, v: 2), (u: 0, v: 1)]; Graph.directed(es, keep: a => (to: a.to)).out(0).collect() == [(to: 2), (to: 1)]
Graph.undirected
fn undirected<E: Domain, R: (u: V, v: V, ..), B: Target<V>>( edges: [E]R, keep: EdgeArc<V, E, R> -> B = a => a, ) -> Graph<V, B>A graph with two arcs per edge of edges, u -> v and v -> u, both carrying the
same e. A loop u -> u gives two arcs at u, so it counts twice in deg.
The arcs out of each vertex come in the order of their edges in edges; a loop's two
arcs are adjacent. keep runs once per stored arc, so 2m times.
- cost: O(n + m) time and memory, plus
2mcalls ofkeep - empty: no edges gives every vertex no arcs
- traps: never
Examples:
domain V = 0..3; domain E = 0..2; let es: [E](u: V, v: V) = [(u: 0, v: 1), (u: 1, v: 2)]; Graph.undirected(es).out(1).collect() == [(to: 0, e: 0), (to: 2, e: 1)]domain V = 0..1; domain E = 0..1; let es: [E](u: V, v: V) = [(u: 0, v: 0)]; Graph.undirected(es).deg(0) == 2
Graph.of
fn of(arcs: Seq<(from: V, arc: A)>) -> Graph<V, A>A graph from (from, arc) pairs: arc is stored as one of from's arcs. The base form
the other builders reduce to.
- cost: O(n + m)
- empty: no pairs gives every vertex no arcs
- order: each vertex's arcs in the order the pairs come
- traps: never
Examples:
domain V = 0..2; let g = Graph.of([(from: V(1), arc: V(0)), (from: V(0), arc: V(1)), (from: V(1), arc: V(1))]); g.next(1).collect() == [0, 1]
Graph.at
fn at(self, u: V) -> lends Slice<A>g[u]: the arcs out of u as an Indexed view, without copying.
The view is a slice of the graph's arc list, so like every slice it keeps its source's
keys: start[u]..start[u + 1]. Iterate it, or use .first, .len and .to_list().
- cost: O(1)
- order: the arcs in input order
- traps: never
Examples:
domain V = 0..3; domain E = 0..2; let es: [E](u: V, v: V) = [(u: 0, v: 2), (u: 0, v: 1)]; let g = Graph.directed(es); g[0].len == 2 and g[1].len == 0
Graph.out
fn out(self, u: V) -> yields AThe arcs out of u, lazily: the Next implementation.
- cost: O(1) to make, O(1) per arc
- order: input order
- traps: never
Examples:
domain V = 0..3; domain E = 0..2; let es: [E](u: V, v: V) = [(u: 0, v: 2), (u: 0, v: 1)]; Graph.directed(es).out(0).collect() == [(to: 2, e: 0), (to: 1, e: 1)]
Graph.matrix
fn matrix<W: Ord>(self) -> [V, V]?W where A: Weighted<W>The weight matrix: d[u, v] is the least .w over the arcs u -> v, None without
one. The diagonal holds the least loop weight, or None; floyd_warshall starts it at
zero itself.
- cost: O(n^2 + m) time, O(n^2) memory
- ties: parallel arcs keep the least weight
- traps: never
Examples:
domain V = 0..2; domain E = 0..3; let es: [E](u: V, v: V, w: Int) = [(u: 0, v: 1, w: 5), (u: 0, v: 1, w: 3), (u: 1, v: 0, w: 4)]; let d = Graph.directed(es).matrix(); d[0, 1] == Some(3) and d[1, 0] == Some(4) and d[0, 0] == None
Graph.deg
fn deg(self, u: V) -> IntThe number of arcs out of u. An undirected loop counts twice.
- cost: O(1)
- traps: never
Examples:
domain V = 0..3; domain E = 0..2; let es: [E](u: V, v: V) = [(u: 0, v: 1), (u: 1, v: 2)]; Graph.undirected(es).deg(1) == 2
Graph.next
fn next(self, u: V) -> yields VWhere u's arcs lead: out(u) mapped to .to, repeats kept.
- cost: O(1) per vertex yielded
- order: input order
- traps: never
Examples:
domain V = 0..3; domain E = 0..2; let es: [E](u: V, v: V) = [(u: 0, v: 2), (u: 0, v: 1)]; Graph.directed(es).next(0).collect() == [2, 1]
Graph.only
fn only(self, keep: V -> Bool = v => true, from: V -> Bool = v => true) -> Only<V, Self>The induced view on the vertices keep accepts: arcs from or to a rejected vertex are
skipped. from also skips the arcs leaving a vertex it rejects, so that vertex can be
reached but not left. Rejected vertices stay in V with no arcs. See the free only.
- cost: O(1) to make;
keepandfromrun per arc walked - traps: never
Examples:
domain V = 0..4; domain E = 0..4; let es: [E](u: V, v: V) = [(u: 0, v: 1), (u: 0, v: 2), (u: 1, v: 3), (u: 2, v: 3)]; Graph.directed(es).only(keep: v => v != 1).deg(0) == 1domain V = 0..4; domain E = 0..4; let es: [E](u: V, v: V) = [(u: 0, v: 1), (u: 0, v: 2), (u: 1, v: 3), (u: 2, v: 3)]; let h = Graph.directed(es).only(from: v => v != 1); h.deg(0) == 2 and h.deg(1) == 0
Graph.weighted
fn weighted<W>(self, f: A -> W) -> lends Reweighted<Graph<V, A>, A -> W>The same graph with each arc's .w read as f(a); .to and .e pass through, so it
is a WeightedNext and stays Edged. On a weighted graph it reweights. Nothing is
stored.
- cost: O(1) to make;
fruns on every arc read - traps: never
Examples:
domain V = 0..3; domain E = 0..2; let es: [E](u: V, v: V) = [(u: 0, v: 1), (u: 1, v: 2)]; dijkstra(Graph.directed(es).weighted(a => 5), from: [(V(0), 0)])[2] == Some(10)
Graph.spanning_tree
fn spanning_tree(self) -> Rooted<V, _>A BFS spanning tree rooted at V.first, as a Rooted. Each vertex's parent is the
vertex whose arc first reached it, scanning vertices in BFS order and arcs in input
order. A forest is spanning_forest.
- cost: O(n + m)
- traps: when the graph is not connected from
V.first, orVis empty
Examples:
domain V = 0..3; domain E = 0..2; let es: [E](u: V, v: V) = [(u: 0, v: 1), (u: 1, v: 2)]; let t = Graph.undirected(es).spanning_tree(); t.parent(2) == Some(1) and t.parent(0) == None
Graph.has
fn has(self, u: V, v: V) -> BoolTrue when some arc u -> v exists. A scan of u's arcs, not a lookup.
- cost: O(deg u)
- traps: never
Examples:
domain V = 0..3; domain E = 0..2; let es: [E](u: V, v: V) = [(u: 0, v: 2), (u: 0, v: 1)]; let g = Graph.directed(es); g.has(0, 2) and not g.has(2, 0)
Graph.lists
fn lists(self) -> [V]List<V>The targets of every vertex as plain lists, lists()[u] == next(u).collect(): the shape
std.flow matchings take.
- cost: O(n + m)
- order: keyed by
V; each list in input order, repeats kept - traps: never
Examples:
domain V = 0..3; domain E = 0..2; let es: [E](u: V, v: V) = [(u: 0, v: 2), (u: 0, v: 1)]; Graph.directed(es).lists()[0] == [2, 1]
Graph.hops
fn hops(self) -> [V, V]IntThe fewest arcs between every ordered pair, by a BFS from each vertex; 0 on the
diagonal. A graph with unreachable pairs wants bfs.
- cost: O(n (n + m)) time, O(n^2) memory
- order: keyed by
(from, to) - traps: when some vertex cannot reach another
Examples:
domain V = 0..3; domain E = 0..2; let es: [E](u: V, v: V) = [(u: 0, v: 1), (u: 1, v: 2)]; let h = Graph.undirected(es).hops(); h[0, 2] == 2 and h[1, 1] == 0
Graph.edges
fn edges<E>(self) -> yields Edge<V, E> where A: Edged<E>Every edge once, as Edge(e, u, v) with its ends as given to the build. Needs arcs that
keep e; the graph keeps one source arc per edge.
- cost: O(1) to make, O(1) per edge
- order: increasing
e - traps: never
Examples:
domain V = 0..3; domain E = 0..2; let es: [E](u: V, v: V) = [(u: 1, v: 0), (u: 0, v: 2)]; Graph.undirected(es).edges().collect() == [Edge(0, 1, 0), Edge(1, 0, 2)]
Graph.dfs_tree
fn dfs_tree<E>(self, root: V) -> (tree: Rooted<V, V>, tree_edge: [E]Bool) where A: Edged<E>The DFS tree from root of the component holding it, as a Rooted tree and a mask of the
edges it uses. The search takes arcs in input order and descends at once (recursive order,
run without recursion). On an undirected graph every edge with tree_edge[e] == false
then joins a vertex to one of its ancestors in tree, which is what bridges, cut vertices
and back-edge DPs need. Vertices outside the component are not in tree.
- cost: O(n + m)
- order: children in the order the search reached them
- traps: never
Examples:
domain V = 0..3; domain E = 0..3; let es: [E](u: V, v: V) = [(u: 0, v: 1), (u: 1, v: 2), (u: 2, v: 0)]; let (tree, tree_edge) = Graph.undirected(es).dfs_tree(0); tree.parent(2) == Some(1) and tree.depth(2) == 2 and tree_edge == [true, true, false]
Graph.peel
fn peel( self, ready: ?(V -> Bool) = None, on_remove: ?((V, A) -> ()) = None, ) -> List<V>peel(g, ready:, on_remove:) as a method; see the free peel.
- cost: O(n + m) plus the calls of
readyandon_remove - order: removal order
- traps: never
Examples:
domain V = 0..4; domain E = 0..4; let es: [E](u: V, v: V) = [(u: 0, v: 1), (u: 0, v: 2), (u: 1, v: 3), (u: 2, v: 3)]; Graph.directed(es).peel() == [0, 1, 2, 3]
Graph.transpose
fn transpose(self) -> Graph<V, A> where A: (to: V, ..)Every arc u -> a.to reversed to a.to -> u, its other fields kept ((..a, to: u)).
- cost: O(n + m)
- order: each vertex's new arcs by original source in vertex order, then input order
- traps: never
Examples:
domain V = 0..4; domain E = 0..4; let es: [E](u: V, v: V) = [(u: 0, v: 1), (u: 0, v: 2), (u: 1, v: 3), (u: 2, v: 3)]; Graph.directed(es).transpose().out(3).collect() == [(to: 1, e: 2), (to: 2, e: 3)]
Paths
pub struct Paths<V, W, A>O(n) memory.
What a search found: p[v] is the distance to v (None if unreachable),
back[v] is (from, via), the vertex before v on one shortest path and the
arc or move that reached it (None at a source), and order the reached
vertices in settling order, so every vertex comes after its from and
distances never decrease. A search given until: t stops once t is settled:
distances in order are exact, and any other vertex holds None or an upper
bound. Cost: the witnesses take one slot per vertex and one write per improving
relaxation, paid even when only p[v] is read.
Storage is spelled like @memo(array) / @memo(map): by default dist and back
are dense tables over V, which must be a bounded type (a domain, range, enum or a
tuple of them); hashed: true on the search makes them hash maps over the states
reached, for state spaces like Int values or unbounded tuples. An unbounded V
without it is a compile error that names hashed: true.
Paths.get
fn get(self, v: V) -> ?Wp[v]: the distance to v, or None if no source reaches it (or the search stopped
at until first).
- cost: O(1) dense, O(1) expected
hashed - traps: never
Examples:
domain V = 0..4; let g: [V]List<V> = [[1, 2], [3], [3], []]; let p = bfs(g, from: [V(0)]); p[3] == Some(2) and p[0] == Some(0)
Paths.iter
fn iter(self) -> yields (v: V, d: W)The reached vertices with their distances, in settling order: for (v, d) in bfs(g, from: [s]).
- cost: O(1) to make, O(1) per item
- order: settling order (the
orderlist), so distances never decrease forbfs,bfs01,dial,dijkstraandfixed_cost_paths; forbellman_fordeach vertex comes after its parent - traps: never
Examples:
domain V = 0..3; let g: [V]List<V> = [[1], [2], []]; bfs(g, from: [V(0)]).iter().collect() == [(v: 0, d: 0), (v: 1, d: 1), (v: 2, d: 2)]
Paths.tight
fn tight<>(self, g: Next<V>) -> [V]List<A>The arcs on some shortest path: for each reached u, the arcs a of g.out(u) with
p[a.to] == p[u] + w(a), where w(a) is a.w for Weighted arcs and 1 otherwise.
Walking order over this DAG counts or lists shortest paths.
- cost: O(n + m)
- order: keyed by
V; each list in arc order; unreached vertices get[] - traps: never
Examples:
domain V = 0..4; let g: [V]List<V> = [[1, 2], [3], [3], []]; let t = bfs(g, from: [V(0)]).tight(g); t[0] == [1, 2] and t[2] == [3] and t[3] == []
Paths.reached
fn reached(self, v: V) -> BoolDoes some source reach v? p[v] != None.
- cost: O(1)
- traps: never
Examples:
domain V = 0..3; let g: [V]List<V> = [[1], [], []]; let p = bfs(g, from: [V(0)]); p.reached(1) and not p.reached(2)
Paths.path
fn path(self, t: V) -> ?List<V>The vertices of one shortest path from a source to t, both included, or None if
t is unreachable; [t] when t is a source. Built from the back pointers, each set
by the arc that first gave its vertex the final distance.
- cost: O(path length)
- ties: the path through the arc that first reached each vertex at its final distance
- order: from the source to
t - traps: never
Examples:
domain V = 0..4; let g: [V]List<V> = [[1, 2], [3], [3], []]; bfs(g, from: [V(0)]).path(3) == Some([0, 1, 3])domain V = 0..2; let g: [V]List<V> = [[], []]; let p = bfs(g, from: [V(0)]); p.path(0) == Some([0]) and p.path(1) == None
Paths.arcs
fn arcs(self, t: V) -> ?List<A>The arcs of path(t), in walking order: [] when t is a source, None if it is
unreachable.
- cost: O(path length)
- ties: as
path - order: from the source to
t - traps: never
Examples:
domain V = 0..4; let g: [V]List<V> = [[1, 2], [3], [3], []]; bfs(g, from: [V(0)]).arcs(3) == Some([1, 3])
Walk
pub struct Walk<V, E>O(m) memory.
A walk: where it starts, then each arc taken (to is where the arc leads, e the
edge it uses), the same arcs a Graph yields.
Walk.vertices
fn vertices(self) -> yields VThe vertices visited, start first, then each arc's to: arcs.len + 1 of them.
- cost: O(1) to make, O(1) per vertex
- order: walking order
- traps: never
Examples:
domain V = 0..3; domain E = 0..2; let es: [E](u: V, v: V) = [(u: 0, v: 1), (u: 1, v: 2)]; euler_walk(es, directed: false)!.vertices.collect() == [0, 1, 2]
Lit
pub struct Lit<X>(x: X, value: Bool)O(1).
A variable or its negation: Lit(x, true) is "x holds".
Lit.flip
fn flip(self) -> Lit<X>The opposite literal: Lit(x, v).flip == Lit(x, not v).
- cost: O(1)
- traps: never
Examples:
domain X = 0..2; Lit(X(1), true).flip == Lit(X(1), false)
TwoSat
pub struct TwoSat<X>A conjunction of two-literal clauses over the variables X. Every clause is O(1)
to add; solve is O(|X| + clauses).
TwoSat.imp
imp: List<List<Int>>Implications between literal nodes: node 2 * i is "variable i is false",
2 * i + 1 "is true"; variables past X.K are helpers of at_most_one.
TwoSat.new
fn new() -> TwoSat<X>An instance with no clauses over the variables of X; every assignment satisfies it.
- cost: O(|X|)
- traps: never
Examples:
domain X = 0..2; TwoSat<X>().solve() != None
TwoSat.add_or
fn add_or(mut self, a: Lit<X>, b: Lit<X>)Adds the clause "at least one of a, b holds".
- cost: O(1) amortized
- traps: never
Examples:
domain X = 0..2; var s = TwoSat<X>(); s.add_or(Lit(X(0), true), Lit(X(1), true)); s.must(Lit(X(0), false)); s.solve() == Some([false, true])
TwoSat.must
fn must(mut self, a: Lit<X>)Adds the clause "a holds" (add_or(a, a)).
- cost: O(1) amortized
- traps: never
Examples:
domain X = 0..1; var s = TwoSat<X>(); s.must(Lit(X(0), true)); s.must(Lit(X(0), false)); s.solve() == None
TwoSat.implies
fn implies(mut self, a: Lit<X>, b: Lit<X>)Adds "if a holds then b holds" (add_or(a.flip, b)).
- cost: O(1) amortized
- traps: never
Examples:
domain X = 0..2; var s = TwoSat<X>(); s.implies(Lit(X(0), true), Lit(X(1), true)); s.must(Lit(X(0), true)); s.solve() == Some([true, true])
TwoSat.at_most_one
fn at_most_one(mut self, lits: List<Lit<X>>)Adds "at most one of lits holds". One helper variable per literal ("some literal so
far holds") keeps it at O(k) clauses instead of O(k^2); helpers never appear in
solve's result.
- cost: O(k) amortized
- empty:
[]adds nothing - traps: never
Examples:
domain X = 0..2; var s = TwoSat<X>(); s.at_most_one([Lit(X(0), true), Lit(X(1), true)]); s.must(Lit(X(0), true)); s.solve() == Some([true, false])
TwoSat.add_xor
fn add_xor(mut self, a: Lit<X>, b: Lit<X>)Adds "exactly one of a, b holds" (two clauses).
- cost: O(1) amortized
- traps: never
Examples:
domain X = 0..2; var s = TwoSat<X>(); s.add_xor(Lit(X(0), true), Lit(X(1), true)); s.must(Lit(X(0), true)); s.solve() == Some([true, false])
TwoSat.add_eq
fn add_eq(mut self, a: Lit<X>, b: Lit<X>)Adds "a and b hold together or not at all" (two clauses).
- cost: O(1) amortized
- traps: never
Examples:
domain X = 0..2; var s = TwoSat<X>(); s.add_eq(Lit(X(0), true), Lit(X(1), true)); s.must(Lit(X(1), false)); s.solve() == Some([false, false])
TwoSat.solve
fn solve(self) -> ?[X]BoolAn assignment satisfying every clause, or None if there is None.
Runs scc on the implication graph (node 2i is "variable i is false", 2i + 1 "is
true"; clause a or b adds not a -> b then not b -> a, in the order added). A
variable is true exactly when its true node's component comes after its false node's in
scc's topological order, so the assignment is a function of the clauses and their order.
- cost: O(|X| + clauses)
- order: keyed by
X - traps: never
Examples:
domain X = 0..1; var s = TwoSat<X>(); s.implies(Lit(X(0), true), Lit(X(0), false)); s.solve() == Some([false])
TwoSat.clause
fn clause(mut self, a: Int, b: Int)Visit
pub enum Visit<V, A>: Enter(v: V, via: ?A), Exit(v: V, via: ?A), Again(from: V, viaO(1): one event of dfs, the same shape as Rooted.tour yields: via is the arc that
discovered v (None for a source); Again(from, via) is an arc into a discovered vertex.
Visit.Enter
Enter(v: V, via: ?A)Visit.Exit
Exit(v: V, via: ?A)Visit.Again
Again(from: V, via: A)Complement
pub struct Complement<V, G>(missing: G)The complement of missing over a domain V: an arc u -> v for every v != u that
missing.out(u) does not reach. Its own out(u) is O(|V|), but bfs, dfs,
reachable and components over a Complement run in O(|V| + m) by keeping the set of
unvisited vertices and scanning only it, so "BFS in the complement graph" and its
components are the ordinary searches: components(complement(g)).
Complement.out
fn out(self, u: V) -> yields VEvery v != u that missing.out(u) does not reach.
- cost: O(|V| + deg u)
- order: ascending
- traps: never
Examples:
domain V = 0..4; let g: [V]List<V> = [[1], [0], [], []]; complement(g).out(0).collect() == [2, 3]
Functional
pub struct Functional<V>O(n) build: the functional graph v -> next[v] (every vertex one out-arc).
Functional<V>
impl<V> Functional<V>Functional<V>.new
fn new(next: [V]V) -> Functional<V>The functional graph v -> next[v] (every vertex has one out-arc), with its cycles,
tails and binary-lifting tables built.
- cost: O(n log n)
- empty: an empty
Vgives an empty graph - traps: never
Examples:
domain V = 0..5; let nx: [V]V = [1, 2, 0, 0, 3]; Functional(nx).cycle_len(4) == 3
Functional<V>.on_cycle
fn on_cycle(self, v: V) -> BoolDoes v lie on a cycle?
- cost: O(1)
- traps: never
Examples:
domain V = 0..5; let nx: [V]V = [1, 2, 0, 0, 3]; let f = Functional(nx); f.on_cycle(1) and not f.on_cycle(3)
Functional<V>.root_of
fn root_of(self, v: V) -> VThe first cycle vertex reached from v (v itself on a cycle): the root of the
in-tree hanging off the cycle that holds v.
- cost: O(1)
- traps: never
Examples:
domain V = 0..5; let nx: [V]V = [1, 2, 0, 0, 3]; let f = Functional(nx); f.root_of(4) == 0 and f.root_of(1) == 1
Functional<V>.depth
fn depth(self, v: V) -> IntThe steps from v to root_of(v); 0 on a cycle.
- cost: O(1)
- traps: never
Examples:
domain V = 0..5; let nx: [V]V = [1, 2, 0, 0, 3]; let f = Functional(nx); f.depth(4) == 2 and f.depth(0) == 0
Functional<V>.cycle_len
fn cycle_len(self, v: V) -> IntThe length of the cycle v eventually reaches.
- cost: O(1)
- traps: never
Examples:
domain V = 0..5; let nx: [V]V = [1, 2, 0, 0, 3]; Functional(nx).cycle_len(4) == 3
Functional<V>.after
fn after(self, v: V, k: Int) -> VThe vertex k steps after v, by binary lifting: after(v, 0) == v. Never None,
unlike Rooted.ancestor, since every vertex has an out-arc.
- cost: O(log k)
- traps: when
k < 0
Examples:
domain V = 0..5; let nx: [V]V = [1, 2, 0, 0, 3]; let f = Functional(nx); f.after(4, 5) == 0 and f.after(4, 0) == 4
Functional<V>.jump_while
fn jump_while(self, v: V, pred: V -> Bool) -> ?VThe first vertex u on the walk from v, v included, with pred(u), or None if
None appears. pred must be monotone along every walk (once true, true onward).
- cost: O(log n)
- traps: never
Examples:
domain V = 0..5; let nx: [V]V = [1, 2, 0, 0, 3]; let f = Functional(nx); f.jump_while(4, u => f.on_cycle(u)) == Some(0)domain V = 0..5; let nx: [V]V = [1, 2, 0, 0, 3]; let f = Functional(nx); f.jump_while(0, u => u == 4) == None
Functional<V>.dist
fn dist(self, a: V, b: V) -> ?IntThe fewest steps from a to b, or None if the walk from a never reaches b;
dist(a, a) == Some(0).
- cost: O(log n)
- traps: never
Examples:
domain V = 0..5; let nx: [V]V = [1, 2, 0, 0, 3]; let f = Functional(nx); f.dist(4, 1) == Some(3) and f.dist(2, 0) == Some(1) and f.dist(1, 4) == None
Functional<V>.lift
fn lift(self, x: Int, k: Int) -> IntFunctional<V>.cycles
fn cycles(self) -> List<List<V>>Every cycle once, each in walk order from its smallest vertex.
- cost: O(n)
- order: cycles by smallest vertex
- traps: never
Examples:
domain V = 0..5; let nx: [V]V = [1, 2, 0, 0, 3]; Functional(nx).cycles() == [[0, 1, 2]]domain V = 0..3; let nx: [V]V = [0, 2, 1]; Functional(nx).cycles() == [[0], [1, 2]]
IncrementalBridges
pub struct IncrementalBridges<V>O(log n) amortized per edge: 2-edge-connectivity under edge insertions.
IncrementalBridges<V>
impl<V> IncrementalBridges<V>IncrementalBridges<V>.new
fn new() -> IncrementalBridges<V>No edges yet: every vertex alone.
- cost: O(n)
- traps: never
Examples:
domain V = 0..2; var b = IncrementalBridges<V>(); not b.same(V(0), V(1))
IncrementalBridges<V>.add
fn add(mut self, u: V, v: V)Adds the undirected edge u - v. A loop changes nothing; a parallel edge makes its
ends two-edge-connected.
- cost: O(log n) amortized
- traps: never
Examples:
domain V = 0..2; var b = IncrementalBridges<V>(); b.add(V(0), V(1)); b.add(V(0), V(1)); b.two_edge_same(V(0), V(1))
IncrementalBridges<V>.two_edge_same
fn two_edge_same(mut self, u: V, v: V) -> BoolAre u and v joined by two edge-disjoint paths? True for u == v.
- cost: O(alpha)
- traps: never
Examples:
domain V = 0..3; var b = IncrementalBridges<V>(); b.add(V(0), V(1)); b.add(V(1), V(2)); let before = b.two_edge_same(V(0), V(2)); b.add(V(2), V(0)); not before and b.two_edge_same(V(0), V(2))
IncrementalBridges<V>.same
fn same(mut self, u: V, v: V) -> BoolAre u and v connected?
- cost: O(alpha)
- traps: never
Examples:
domain V = 0..3; var b = IncrementalBridges<V>(); b.add(V(0), V(1)); b.add(V(1), V(2)); b.same(V(0), V(2))
Edge
pub struct Edge<V, E>(e: E, u: V, vO(1): one edge of a Graph: its id and its ends as given.
Only
pub struct Only<V, G>(g: G, keep: V -> Bool, from: V -> Bool)g.only(keep); see only. Implements every arc capability G has.
Only.out
fn out(self, u: V) -> yields G.ArcThe arcs out of u the view keeps: None when u is dropped, else those whose to is
kept.
- cost: O(1) to make, O(1) per arc of
gwalked - order: arc order of
g - traps: never
Examples:
domain V = 0..3; let g: [V]List<V> = [[1, 2], [2], []]; g.only(keep: v => v != 1).out(0).collect() == [2]
Only.deg
fn deg(self, u: V) -> IntThe number of arcs out of u the view keeps.
- cost: O(deg u in
g) - traps: never
Examples:
domain V = 0..3; let g: [V]List<V> = [[1, 2], [2], []]; g.only(keep: v => v != 1).deg(0) == 1
Only.transpose
fn transpose(self) -> Graph<V, G.Arc>The kept arcs reversed, built as a Graph (record arcs as (..a, to: u), a plain
vertex arc as u).
- cost: O(n + m)
- traps: never
Examples:
domain V = 0..3; let g: [V]List<V> = [[1, 2], [2], []]; g.only(keep: v => v != 1).transpose().next(2).collect() == [0]