Skip to Content
ReferenceLibrary

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.

Source

Next.Arc

type Arc: Target<V>

Source

Next.out

fn out(self, u: V) -> yields Self.Arc

The 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]

Source

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).

Source

Target.to

fn to(self) -> V

The 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 == 2
  • domain V = 0..3; let a: (to: V, w: Int) = (to: 1, w: 7); a.to == 1

Source

Weighted

pub trait Weighted<W>

O(1). The weight of an arc: a record with a w field, or .weighted(f).

Source

Weighted.w

fn w(self) -> W

The weight of an arc: its w field, or f(a) through g.weighted(f).

  • cost: O(1) plus the cost of f under weighted
  • traps: never

Examples:

  • domain V = 0..3; let a: (to: V, w: Int) = (to: 1, w: 7); a.w == 7

Source

Edged

pub trait Edged<E>

O(1). The edge an arc belongs to; both arcs of an undirected edge share it.

Source

Edged.e

fn e(self) -> E

The 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

Source

WeightedNext

pub trait WeightedNext<V, W> = Next<V> where Self.Arc

A graph whose arcs carry weights: shortest paths, MST over arcs, DAG folds.

Source

EdgedNext

pub trait EdgedNext<V, E> = Next<V> where Self.Arc

A 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.

Source

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:.

Source

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.

Source

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.

Source

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.

Source

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.

Source

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.

Source

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.

Source

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.

Source

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 m calls of keep
  • empty: no edges gives every vertex no arcs; an empty V gives 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)]

Source

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 2m calls of keep
  • 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

Source

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]

Source

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

Source

Graph.out

fn out(self, u: V) -> yields A

The 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)]

Source

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

Source

Graph.deg

fn deg(self, u: V) -> Int

The 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

Source

Graph.next

fn next(self, u: V) -> yields V

Where 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]

Source

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; keep and from run 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) == 1
  • 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)]; let h = Graph.directed(es).only(from: v => v != 1); h.deg(0) == 2 and h.deg(1) == 0

Source

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; f runs 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)

Source

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, or V is 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

Source

Graph.has

fn has(self, u: V, v: V) -> Bool

True 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)

Source

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]

Source

Graph.hops

fn hops(self) -> [V, V]Int

The 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

Source

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)]

Source

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]

Source

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 ready and on_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]

Source

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)]

Source

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.

Source

Paths.get

fn get(self, v: V) -> ?W

p[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)

Source

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 order list), so distances never decrease for bfs, bfs01, dial, dijkstra and fixed_cost_paths; for bellman_ford each 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)]

Source

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] == []

Source

Paths.reached

fn reached(self, v: V) -> Bool

Does 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)

Source

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

Source

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])

Source

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.

Source

Walk.vertices

fn vertices(self) -> yields V

The 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]

Source

Lit

pub struct Lit<X>(x: X, value: Bool)

O(1). A variable or its negation: Lit(x, true) is "x holds".

Source

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)

Source

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).

Source

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.

Source

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

Source

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])

Source

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

Source

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])

Source

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])

Source

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])

Source

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])

Source

TwoSat.solve

fn solve(self) -> ?[X]Bool

An 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])

Source

TwoSat.clause

fn clause(mut self, a: Int, b: Int)

Source

Visit

pub enum Visit<V, A>: Enter(v: V, via: ?A), Exit(v: V, via: ?A), Again(from: V, via

O(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.

Source

Visit.Enter

Enter(v: V, via: ?A)

Source

Visit.Exit

Exit(v: V, via: ?A)

Source

Visit.Again

Again(from: V, via: A)

Source

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)).

Source

Complement.out

fn out(self, u: V) -> yields V

Every 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]

Source

Functional

pub struct Functional<V>

O(n) build: the functional graph v -> next[v] (every vertex one out-arc).

Source

Functional<V>

impl<V> Functional<V>

Source

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 V gives 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

Source

Functional<V>.on_cycle

fn on_cycle(self, v: V) -> Bool

Does 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)

Source

Functional<V>.root_of

fn root_of(self, v: V) -> V

The 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

Source

Functional<V>.depth

fn depth(self, v: V) -> Int

The 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

Source

Functional<V>.cycle_len

fn cycle_len(self, v: V) -> Int

The 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

Source

Functional<V>.after

fn after(self, v: V, k: Int) -> V

The 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

Source

Functional<V>.jump_while

fn jump_while(self, v: V, pred: V -> Bool) -> ?V

The 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

Source

Functional<V>.dist

fn dist(self, a: V, b: V) -> ?Int

The 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

Source

Functional<V>.lift

fn lift(self, x: Int, k: Int) -> Int

Source

Functional<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]]

Source

IncrementalBridges

pub struct IncrementalBridges<V>

O(log n) amortized per edge: 2-edge-connectivity under edge insertions.

Source

IncrementalBridges<V>

impl<V> IncrementalBridges<V>

Source

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))

Source

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))

Source

IncrementalBridges<V>.two_edge_same

fn two_edge_same(mut self, u: V, v: V) -> Bool

Are 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))

Source

IncrementalBridges<V>.same

fn same(mut self, u: V, v: V) -> Bool

Are 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))

Source

Edge

pub struct Edge<V, E>(e: E, u: V, v

O(1): one edge of a Graph: its id and its ends as given.

Source

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.

Source

Only.out

fn out(self, u: V) -> yields G.Arc

The 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 g walked
  • 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]

Source

Only.deg

fn deg(self, u: V) -> Int

The 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

Source

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]

Source

On this page