Skip to Content
ReferenceLibrary

flow

A handle to one arc of a FlowGraph.

Generated from spec/std/flow.cp by cpl doc --format json.

Arc

pub struct Arc(id: 0..2_147_483_648)

A handle to one arc of a FlowGraph. Handles from add stay valid as arcs are added.

Source

Arc.rev

fn rev(self) -> Arc

The paired arc in the opposite direction, what e ^ 1 means in C++. Every add makes an arc and its reverse together, so a.rev.rev == a.

  • cost: O(1)
  • traps: never

Examples:

  • var g = FlowGraph<0..2>(); let a = g.add(0, 1, Some(5)); g.source(a.rev) == 1 and a.rev.rev == a

Source

FlowGraph

pub struct FlowGraph<V>

A flow network over the vertices V, solved with Dinic's algorithm (max_flow) or push-relabel (push_relabel). add is O(1). max_flow is O(V^2 E) in general, O(E sqrt(V)) on unit networks (bipartite matching). Memory is two arcs per add.

Source

FlowGraph.new

fn new() -> FlowGraph<V>

An empty flow network over the vertices V.

  • cost: O(n) for n = V.count
  • traps: never

Examples:

  • let g = FlowGraph<0..3>(); g.arcs.collect() == []

Source

FlowGraph.add

fn add(mut self, u: V, v: V, cap: ?Int) -> Arc

Adds an arc u -> v with capacity cap, and its reverse v -> u with capacity 0, and returns the forward arc. A cap of None is an arc no cut can afford: capacity 2^60. Self-loops are allowed and never carry flow.

  • cost: O(1) amortized; two arcs of memory
  • traps: when cap is negative

Examples:

  • var g = FlowGraph<0..2>(); let a = g.add(0, 1, Some(5)); g.cap(a) == 5 and g.cap(a.rev) == 0
  • var g = FlowGraph<0..2>(); let a = g.add(0, 1, None); g.cap(a) == 1 << 60

Source

FlowGraph.add_both

fn add_both(mut self, u: V, v: V, cap: Int) -> Arc

Adds an undirected edge between u and v: an arc u -> v whose reverse also has capacity cap. Returns the u -> v arc.

  • cost: O(1) amortized; two arcs of memory
  • traps: when cap is negative

Examples:

  • var g = FlowGraph<0..2>(); let a = g.add_both(0, 1, 3); g.cap(a.rev) == 3 and g.max_flow(1, 0) == 3

Source

FlowGraph.flow

fn flow(self, a: Arc) -> Int

The flow currently sent along a: negative on the reverse arc of a used arc, so flow(a.rev) == -flow(a).

  • cost: O(1)
  • traps: never

Examples:

  • var g = FlowGraph<0..2>(); let a = g.add(0, 1, Some(5)); g.max_flow(0, 1); g.flow(a) == 5 and g.flow(a.rev) == -5

Source

FlowGraph.cap

fn cap(self, a: Arc) -> Int

The capacity a has now: what add or the last set_cap gave it, 0 for the reverse arc of an add, cap for either arc of an add_both.

  • cost: O(1)
  • traps: never

Examples:

  • var g = FlowGraph<0..2>(); let a = g.add(0, 1, Some(4)); g.cap(a) == 4

Source

FlowGraph.source

fn source(self, a: Arc) -> V

The vertex a leaves.

  • cost: O(1)
  • traps: never

Examples:

  • var g = FlowGraph<0..3>(); let a = g.add(2, 0, Some(1)); g.source(a) == 2 and g.source(a.rev) == 0

Source

FlowGraph.target

fn target(self, a: Arc) -> V

The vertex a points to.

  • cost: O(1)
  • traps: never

Examples:

  • var g = FlowGraph<0..3>(); let a = g.add(2, 0, Some(1)); g.target(a) == 0 and g.target(a.rev) == 2

Source

FlowGraph.max_flow

fn max_flow(mut self, s: V, t: V, limit: ?Int = None) -> Int

Pushes as much flow as possible from s to t, on top of the flow already there but no more than limit in this call, and returns the amount added.

Dinic's algorithm: BFS levels, then blocking flows by DFS scanning each vertex's arcs in add order. Calling it again with no change adds 0; after it runs to completion (returns less than limit, or limit is None), min_cut(s) and cut_arcs(s) are valid.

  • cost: O(V² E); O(E sqrt V) when every capacity is 1
  • ties: among maximum flows, the one Dinic finds scanning arcs in add order
  • traps: when s == t or limit is negative

Examples:

  • var g = FlowGraph<0..4>(); g.add(0, 1, Some(3)); g.add(0, 2, Some(2)); g.add(1, 2, Some(1)); g.add(1, 3, Some(2)); g.add(2, 3, Some(3)); g.max_flow(0, 3) == 5
  • var g = FlowGraph<0..4>(); g.add(0, 1, Some(3)); g.add(0, 2, Some(2)); g.add(1, 2, Some(1)); g.add(1, 3, Some(2)); g.add(2, 3, Some(3)); g.max_flow(0, 3, limit: Some(4)) == 4 and g.max_flow(0, 3) == 1

Source

FlowGraph.min_cut

fn min_cut(self, s: V) -> [V]Bool

The source side of a minimum s-t cut: the vertices s still reaches in the residual network, after max_flow(s, t) (or push_relabel(s, t)) ran to completion.

  • cost: O(V + E)
  • ties: the smallest source side among minimum cuts (exactly what s reaches)
  • order: keyed by V
  • traps: when no completed max_flow or push_relabel from s came since the last add, set_cap or reset

Examples:

  • var g = FlowGraph<0..3>(); g.add(0, 1, Some(5)); g.add(1, 2, Some(1)); g.max_flow(0, 2); g.min_cut(0) == [true, true, false]

Source

FlowGraph.reset

fn reset(mut self)

Clears all flow, so every arc is back at its current capacity with nothing sent.

  • cost: O(E)
  • traps: never

Examples:

  • var g = FlowGraph<0..2>(); let a = g.add(0, 1, Some(5)); g.max_flow(0, 1); g.reset(); g.flow(a) == 0 and g.max_flow(0, 1) == 5

Source

FlowGraph.set_cap

fn set_cap(mut self, a: Arc, cap: ?Int)

Changes arc a's capacity to cap (None: 2^60), keeping its flow; a later max_flow continues from the current flow. The reverse arc keeps its own capacity.

  • cost: O(1)
  • traps: when the flow on a exceeds the new capacity (lower it with reset first), or cap is negative

Examples:

  • var g = FlowGraph<0..2>(); let a = g.add(0, 1, Some(2)); g.max_flow(0, 1); g.set_cap(a, Some(5)); g.max_flow(0, 1) == 3

Source

FlowGraph.residual

fn residual(self, a: Arc) -> Int

The capacity left on a in the residual network: cap(a) - flow(a).

  • cost: O(1)
  • traps: never

Examples:

  • var g = FlowGraph<0..2>(); let a = g.add(0, 1, Some(5)); g.max_flow(0, 1, limit: Some(2)); g.residual(a) == 3 and g.residual(a.rev) == 2

Source

FlowGraph.arcs

fn arcs(self) -> yields Arc

Every arc add or add_both returned, lazily; never a reverse arc. O(1) to make.

  • cost: O(E) for the whole walk
  • empty: yields nothing before the first add
  • order: the order add returned them
  • traps: never

Examples:

  • var g = FlowGraph<0..3>(); let a = g.add(0, 1, Some(1)); let b = g.add(1, 2, Some(1)); g.arcs.collect() == [a, b]

Source

FlowGraph.out

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

The arcs add or add_both returned whose source is u, lazily; never a reverse arc.

  • cost: O(deg u) for the whole walk
  • empty: yields nothing when no added arc leaves u
  • order: the order add returned them
  • traps: never

Examples:

  • var g = FlowGraph<0..3>(); let a = g.add(0, 1, Some(1)); g.add(1, 2, Some(1)); let c = g.add(0, 2, Some(1)); g.out(0).collect() == [a, c]

Source

FlowGraph.cut_arcs

fn cut_arcs(self, s: V) -> List<Arc>

The added arcs crossing the minimum cut min_cut(s) from the source side to the other, after max_flow(s, t) ran to completion. Every one is saturated and their capacities sum to the flow value.

  • cost: O(V + E)
  • order: the order add returned them
  • traps: like min_cut, when the flow from s is missing or stale

Examples:

  • var g = FlowGraph<0..3>(); g.add(0, 1, Some(5)); let b = g.add(1, 2, Some(1)); g.max_flow(0, 2); g.cut_arcs(0) == [b]

Source

FlowGraph.paths

fn paths(self, s: V, t: V) -> yields (arcs: List<Arc>, amount: Int)

The current s-t flow split into paths, each with the amount it carries; the amounts sum to the net flow out of s. Cycles of flow are skipped. Does not change the flow.

Each path walks from s along the first arc, in add order, that still carries unclaimed flow, until it reaches t; its amount is the least unclaimed flow on the way.

  • cost: O(P (V + E)) for P paths
  • empty: yields nothing when no flow goes from s to t
  • order: discovery order, as above
  • traps: when s == t

Examples:

  • var g = FlowGraph<0..4>(); let a = g.add(0, 1, Some(1)); let b = g.add(1, 3, Some(1)); let c = g.add(0, 2, Some(1)); let d = g.add(2, 3, Some(1)); g.max_flow(0, 3); g.paths(0, 3).collect() == [(arcs: [a, b], amount: 1), (arcs: [c, d], amount: 1)]

Source

FlowGraph.push_relabel

fn push_relabel(mut self, s: V, t: V) -> Int

The same maximum flow amount as max_flow(s, t) by push-relabel (highest label, gap heuristic), often several times faster than Dinic on dense or unit-capacity grids. Adds to the flow already there and returns the amount added; min_cut(s) works after it.

  • cost: O(V² sqrt E)
  • traps: when s == t

Examples:

  • var g = FlowGraph<0..4>(); g.add(0, 1, Some(3)); g.add(0, 2, Some(2)); g.add(1, 2, Some(1)); g.add(1, 3, Some(2)); g.add(2, 3, Some(3)); g.push_relabel(0, 3) == 5

Source

FlowGraph.push

fn push( mut self, a: Arc, f: Int, mut excess: [V]Int, mut active: List<List<V>>, height: [V]Int, )

Source

FlowGraph.close

fn close(mut self, a: Arc)

Source

FlowGraph.levels

fn levels(self, s: V) -> [V]?Int

Source

FlowGraph.augment

fn augment(mut self, s: V, t: V, level: [V]?Int, mut next: [V]Int, most: Int) -> Int

One augmenting path in the level graph, found without recursion.

Source

CostFlow

pub struct CostFlow<V>

A flow network with a cost per unit on every arc, solved by successive shortest paths with Johnson potentials. Arc handles and accessors are those of FlowGraph. add is O(1); memory is two arcs per add.

Source

CostFlow.new

fn new() -> CostFlow<V>

An empty min-cost flow network over the vertices V.

  • cost: O(n) for n = V.count
  • traps: never

Examples:

  • let g = CostFlow<0..3>(); g.arcs.collect() == []

Source

CostFlow.add

fn add(mut self, u: V, v: V, cap: ?Int, cost: Int) -> Arc

Adds an arc u -> v with capacity cap and cost cost per unit; its reverse has capacity 0 and cost -cost. cap: None is 2^60. Costs may be negative; min_cost_flow needs no residual cycle of negative total cost (run cancel_cycles first when there may be one).

  • cost: O(1) amortized; two arcs of memory
  • traps: when cap is negative

Examples:

  • var g = CostFlow<0..2>(); let a = g.add(0, 1, Some(2), 7); g.cost(a) == 7 and g.cost(a.rev) == -7

Source

CostFlow.flow

fn flow(self, a: Arc) -> Int

The flow currently sent along a; flow(a.rev) == -flow(a).

  • cost: O(1)
  • traps: never

Examples:

  • var g = CostFlow<0..2>(); let a = g.add(0, 1, Some(2), 1); g.min_cost_flow(0, 1); g.flow(a) == 2

Source

CostFlow.cap

fn cap(self, a: Arc) -> Int

The capacity a has now: what add or the last set_cap gave it, 0 for a reverse arc.

  • cost: O(1)
  • traps: never

Examples:

  • var g = CostFlow<0..2>(); let a = g.add(0, 1, Some(2), 1); g.cap(a) == 2 and g.cap(a.rev) == 0

Source

CostFlow.cost

fn cost(self, a: Arc) -> Int

The cost per unit of flow along a; cost(a.rev) == -cost(a).

  • cost: O(1)
  • traps: never

Examples:

  • var g = CostFlow<0..2>(); let a = g.add(0, 1, Some(2), -3); g.cost(a) == -3

Source

CostFlow.source

fn source(self, a: Arc) -> V

The vertex a leaves.

  • cost: O(1)
  • traps: never

Examples:

  • var g = CostFlow<0..3>(); let a = g.add(2, 0, Some(1), 0); g.source(a) == 2

Source

CostFlow.target

fn target(self, a: Arc) -> V

The vertex a points to.

  • cost: O(1)
  • traps: never

Examples:

  • var g = CostFlow<0..3>(); let a = g.add(2, 0, Some(1), 0); g.target(a) == 0

Source

CostFlow.set_cap

fn set_cap(mut self, a: Arc, cap: ?Int)

Changes arc a's capacity, keeping its flow, as FlowGraph.set_cap.

  • cost: O(1)
  • traps: when the flow on a exceeds the new capacity, or cap is negative

Examples:

  • var g = CostFlow<0..2>(); let a = g.add(0, 1, Some(1), 2); g.min_cost_flow(0, 1); g.set_cap(a, Some(3)); g.min_cost_flow(0, 1) == (flow: 2, cost: 4)

Source

CostFlow.arcs

fn arcs(self) -> yields Arc

Every arc add returned, lazily; never a reverse arc. O(1) to make.

  • cost: O(E) for the whole walk
  • empty: yields nothing before the first add
  • order: the order add returned them
  • traps: never

Examples:

  • var g = CostFlow<0..2>(); let a = g.add(0, 1, Some(1), 0); let b = g.add(1, 0, Some(1), 0); g.arcs.collect() == [a, b]

Source

CostFlow.cancel_cycles

fn cancel_cycles(mut self) -> Int

Saturates every negative-cost cycle of the residual network, so the stored flow becomes a min-cost circulation plus the s-t flows already sent, and returns the cost added (zero or negative). Negative cycles are allowed here; afterwards min_cost_flow is safe.

  • cost: O(V E log V) worst case, by cost scaling
  • traps: never

Examples:

  • var g = CostFlow<0..2>(); g.add(0, 1, Some(1), -2); g.add(1, 0, Some(1), 1); g.cancel_cycles() == -1
  • var g = CostFlow<0..2>(); g.add(0, 1, Some(1), 2); g.cancel_cycles() == 0

Source

CostFlow.min_cost_flow

fn min_cost_flow(mut self, s: V, t: V, limit: ?Int = None) -> (flow: Int, cost: Int)

Sends the most flow from s to t, up to limit in this call, at the least cost among flows of that amount, on top of the flow already there. Returns the amount and cost added.

Successive shortest paths with Johnson potentials: each augmentation takes a cheapest residual path, so the cost added is convex in the amount (see slope). Costs may be negative; the first call with a negative residual arc runs Bellman-Ford once.

  • cost: O(F E log V) for F augmenting paths, plus O(V E) once when a residual arc has a negative cost
  • ties: among cheapest flows, the one the shortest paths find (Dijkstra breaking ties by least vertex)
  • traps: when s == t, limit is negative, or the residual network has a negative-cost cycle

Examples:

  • var g = CostFlow<0..3>(); g.add(0, 1, Some(2), 1); g.add(1, 2, Some(2), 1); g.add(0, 2, Some(1), 5); g.min_cost_flow(0, 2) == (flow: 3, cost: 9)
  • var g = CostFlow<0..3>(); g.add(0, 1, Some(2), 1); g.add(1, 2, Some(2), 1); g.add(0, 2, Some(1), 5); g.min_cost_flow(0, 2, limit: Some(2)) == (flow: 2, cost: 4)

Source

CostFlow.slope

fn slope(mut self, s: V, t: V, limit: ?Int = None) -> List<(flow: Int, cost: Int)>

The breakpoints of the cheapest cost of sending each amount from s to t, up to limit: (0, 0) first, then one (flow, cost) per change of slope, ending at the largest amount. Between breakpoints the cost is linear and the slopes never decrease. Sends the flow, as min_cost_flow does; amounts and costs are relative to the flow already there.

  • cost: as min_cost_flow
  • order: increasing flow
  • traps: as min_cost_flow

Examples:

  • var g = CostFlow<0..3>(); g.add(0, 1, Some(2), 1); g.add(1, 2, Some(2), 1); g.add(0, 2, Some(1), 5); g.slope(0, 2) == [(flow: 0, cost: 0), (flow: 2, cost: 4), (flow: 3, cost: 9)]
  • var g = CostFlow<0..2>(); g.slope(0, 1) == [(flow: 0, cost: 0)]

Source

CostFlow.potentials

fn potentials(self) -> [V]Int

Potentials under which every residual arc has a nonnegative reduced cost: all zero when no residual arc is negative, else Bellman-Ford from every vertex at once.

Source

Matching

pub struct Matching<L, R>

O(E sqrt V) for the first augment_all, O(V + E) per later add + augment. A bipartite matching that grows with the graph: edges arrive online and each augment(l) tries one augmenting path from l (Kuhn), so a contest that adds vertices or edges between queries keeps a maximum matching without re-solving.

Source

Matching.new

fn new() -> Matching<L, R>

An online bipartite matching between L and R with no edges and nothing matched.

  • cost: O(L + R)
  • traps: never

Examples:

  • let m = Matching<0..2, 0..2>(); m.len == 0 and m.mate(0) == None

Source

Matching.add

fn add(mut self, l: L, r: R)

Allows l to match r. Does not augment; a repeated edge is harmless.

  • cost: O(1) amortized
  • traps: never

Examples:

  • var m = Matching<0..2, 0..2>(); m.add(0, 1); m.len == 0 and m.augment(0) and m.mate(0) == Some(1)

Source

Matching.augment

fn augment(mut self, from: L) -> Bool

Looks for one augmenting path from the unmatched from (Kuhn's DFS, trying edges in add order); true when it grew the matching. false also when from is already matched.

  • cost: O(V + E)
  • traps: never

Examples:

  • var m = Matching<0..2, 0..2>(); m.add(0, 0); m.add(0, 1); m.add(1, 0); m.augment(0); m.augment(1) and m.mate(0) == Some(1) and m.mate(1) == Some(0)

Source

Matching.augment_all

fn augment_all(mut self) -> Int

Grows the current matching to a maximum one by Hopcroft-Karp and returns the number of pairs added.

  • cost: O(E sqrt V)
  • traps: never

Examples:

  • var m = Matching<0..2, 0..2>(); m.add(0, 0); m.add(1, 0); m.add(1, 1); m.augment_all() == 2 and m.len == 2

Source

Matching.remove

fn remove(mut self, l: L) -> Int

Unmatches l and its mate r, then tries to rematch both: augment(l) first, then one augmenting path ending at r if it is still free. Returns the new size; the matching stays maximum when it was before. No edge is removed.

  • cost: O(V + E)
  • traps: never

Examples:

  • var m = Matching<0..2, 0..2>(); m.add(0, 0); m.add(1, 0); m.augment(0); m.remove(0) == 1 and m.mate(0) == Some(0)

Source

Matching.mate

fn mate(self, l: L) -> ?R

l's partner, None when unmatched.

  • cost: O(1)
  • traps: never

Examples:

  • var m = Matching<0..2, 0..2>(); m.add(1, 0); m.augment(1); m.mate(1) == Some(0) and m.mate(0) == None

Source

Matching.back

fn back(self, r: R) -> ?L

r's partner, None when unmatched.

  • cost: O(1)
  • traps: never

Examples:

  • var m = Matching<0..2, 0..2>(); m.add(1, 0); m.augment(1); m.back(0) == Some(1) and m.back(1) == None

Source

Matching.len

fn len(self) -> Int

The number of matched pairs.

  • cost: O(1)
  • traps: never

Examples:

  • var m = Matching<0..2, 0..2>(); m.add(1, 0); m.augment(1); m.len == 1

Source

Matching.cover

fn cover(self) -> (left: [L]Bool, right: [R]Bool)

The König vertex cover of the current matching, built as in min_vertex_cover; a minimum cover when the matching is maximum.

  • cost: O(V + E)
  • order: left keyed by L, right keyed by R
  • traps: never

Examples:

  • var m = Matching<0..2, 0..1>(); m.add(0, 0); m.add(1, 0); m.augment_all(); m.cover() == (left: [false, false], right: [true])

Source

Matroid

pub trait Matroid<E>

An independence oracle for matroid_intersection. rebuild(take) sets the current independent set; can_add(e) asks whether take + e stays independent, and can_swap(out, e) whether take - out + e does. Graphic and colour (partition) matroids ship as GraphicMatroid and ColorMatroid.

Source

Matroid.rebuild

fn rebuild(mut self, take: [E]Bool)

Source

Matroid.can_add

fn can_add(self, e: E) -> Bool

Source

Matroid.can_swap

fn can_swap(self, out: E, e: E) -> Bool

Source

GraphicMatroid

pub struct GraphicMatroid<V, E>

O(E α) per rebuild. Independent sets are forests of the edges' endpoints.

Source

GraphicMatroid.new

fn new(edges: [E](u: V, v: V)) -> GraphicMatroid<V, E>

The graphic matroid of edges: a set of edges is independent when it is a forest on V.

  • cost: O(1); each rebuild is O(E alpha(V))
  • traps: never

Examples:

  • let es: [0..3](u: 0..3, v: 0..3) = [(u: 0, v: 1), (u: 1, v: 2), (u: 0, v: 2)]; var m = GraphicMatroid(es); m.rebuild([true, true, false]); not m.can_add(2) and m.can_swap(0, 2)

Source

ColorMatroid

pub struct ColorMatroid<E, C>

O(E) per rebuild. Independent sets take at most limit[c] elements of each colour.

Source

ColorMatroid.new

fn new(color: [E]C, limit: [C]Int) -> ColorMatroid<E, C>

The partition matroid of color: a set is independent when it holds at most limit[c] elements of each colour c.

  • cost: O(1); each rebuild is O(E)
  • empty: with no elements only the empty set exists and every query is false
  • traps: when some limit[c] is negative

Examples:

  • let col: [0..3]0..2 = [0, 0, 1]; let lim: [0..2]Int = [1, 1]; var m = ColorMatroid(col, lim); m.rebuild([true, false, false]); not m.can_add(1) and m.can_add(2)

Source

On this page