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.
Arc.rev
fn rev(self) -> ArcThe 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
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.
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() == []
FlowGraph.add
fn add(mut self, u: V, v: V, cap: ?Int) -> ArcAdds 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
capis negative
Examples:
var g = FlowGraph<0..2>(); let a = g.add(0, 1, Some(5)); g.cap(a) == 5 and g.cap(a.rev) == 0var g = FlowGraph<0..2>(); let a = g.add(0, 1, None); g.cap(a) == 1 << 60
FlowGraph.add_both
fn add_both(mut self, u: V, v: V, cap: Int) -> ArcAdds 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
capis 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
FlowGraph.flow
fn flow(self, a: Arc) -> IntThe 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
FlowGraph.cap
fn cap(self, a: Arc) -> IntThe 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
FlowGraph.source
fn source(self, a: Arc) -> VThe 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
FlowGraph.target
fn target(self, a: Arc) -> VThe 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
FlowGraph.max_flow
fn max_flow(mut self, s: V, t: V, limit: ?Int = None) -> IntPushes 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
addorder - traps: when
s == torlimitis 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) == 5var 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
FlowGraph.min_cut
fn min_cut(self, s: V) -> [V]BoolThe 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
sreaches) - order: keyed by
V - traps: when no completed
max_floworpush_relabelfromscame since the lastadd,set_caporreset
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]
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
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
aexceeds the new capacity (lower it withresetfirst), orcapis 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
FlowGraph.residual
fn residual(self, a: Arc) -> IntThe 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
FlowGraph.arcs
fn arcs(self) -> yields ArcEvery 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
addreturned 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]
FlowGraph.out
fn out(self, u: V) -> yields ArcThe 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
addreturned 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]
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
addreturned them - traps: like
min_cut, when the flow fromsis 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]
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
stot - 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)]
FlowGraph.push_relabel
fn push_relabel(mut self, s: V, t: V) -> IntThe 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
FlowGraph.push
fn push( mut self, a: Arc, f: Int, mut excess: [V]Int, mut active: List<List<V>>, height: [V]Int, )FlowGraph.close
fn close(mut self, a: Arc)FlowGraph.levels
fn levels(self, s: V) -> [V]?IntFlowGraph.augment
fn augment(mut self, s: V, t: V, level: [V]?Int, mut next: [V]Int, most: Int) -> IntOne augmenting path in the level graph, found without recursion.
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.
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() == []
CostFlow.add
fn add(mut self, u: V, v: V, cap: ?Int, cost: Int) -> ArcAdds 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
capis 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
CostFlow.flow
fn flow(self, a: Arc) -> IntThe 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
CostFlow.cap
fn cap(self, a: Arc) -> IntThe 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
CostFlow.cost
fn cost(self, a: Arc) -> IntThe 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
CostFlow.source
fn source(self, a: Arc) -> VThe 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
CostFlow.target
fn target(self, a: Arc) -> VThe 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
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
aexceeds the new capacity, orcapis 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)
CostFlow.arcs
fn arcs(self) -> yields ArcEvery 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
addreturned 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]
CostFlow.cancel_cycles
fn cancel_cycles(mut self) -> IntSaturates 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() == -1var g = CostFlow<0..2>(); g.add(0, 1, Some(1), 2); g.cancel_cycles() == 0
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,limitis 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)
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)]
CostFlow.potentials
fn potentials(self) -> [V]IntPotentials 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.
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.
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
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)
Matching.augment
fn augment(mut self, from: L) -> BoolLooks 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)
Matching.augment_all
fn augment_all(mut self) -> IntGrows 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
Matching.remove
fn remove(mut self, l: L) -> IntUnmatches 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)
Matching.mate
fn mate(self, l: L) -> ?Rl'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
Matching.back
fn back(self, r: R) -> ?Lr'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
Matching.len
fn len(self) -> IntThe 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
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:
leftkeyed byL,rightkeyed byR - 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])
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.
Matroid.rebuild
fn rebuild(mut self, take: [E]Bool)Matroid.can_add
fn can_add(self, e: E) -> BoolMatroid.can_swap
fn can_swap(self, out: E, e: E) -> BoolGraphicMatroid
pub struct GraphicMatroid<V, E>O(E α) per rebuild. Independent sets are forests of the edges' endpoints.
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
rebuildis 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)
ColorMatroid
pub struct ColorMatroid<E, C>O(E) per rebuild. Independent sets take at most limit[c] elements of each colour.
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
rebuildis 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)