Documentation
¶
Overview ¶
Package flow implements network-flow algorithms over directed capacitated graphs. v1 carries Dinic's max-flow + Stoer-Wagner global min-cut; future work will add min-cost max-flow.
Index ¶
- Variables
- func EdmondsKarp(g *Network, src, sink int) int
- func EdmondsKarpCtx(ctx context.Context, g *Network, src, sink int) (int, error)
- func MaxFlow(g *Network, src, sink int) int
- func MaxFlowCtx(ctx context.Context, g *Network, src, sink int) (int, error)
- func MinCostMaxFlow(g *CostNetwork, src, sink int) (flow, cost int)
- func MinCostMaxFlowCtx(ctx context.Context, g *CostNetwork, src, sink int) (totalFlow, totalCost int, err error)
- func PushRelabelMaxFlow(g *Network, src, sink int) int
- func PushRelabelMaxFlowCtx(ctx context.Context, g *Network, src, sink int) (int, error)
- type CostNetwork
- type MinCutResult
- type Network
Examples ¶
Constants ¶
This section is empty.
Variables ¶
var ErrCapacityOverflow = errors.New("flow: edge capacities or costs overflow int64")
ErrCapacityOverflow is returned by the context-aware flow entry points (MaxFlowCtx, EdmondsKarpCtx, PushRelabelMaxFlowCtx, MinCostMaxFlowCtx) when the input network's capacities (or, for the min-cost variant, the capacity-times-cost product) cannot be summed without overflowing int64.
The residual updates and cost accumulation in the augmenting loops use unchecked native int arithmetic for speed; this boundary check is the single point at which an overflow-prone network is rejected, so the hot loop can trust its inputs. Under the module's "fail-stop, never fail-silent" contract a network that would silently produce a wrapped (negative) max-flow or min-cost must be refused here rather than returning a corrupt result.
The non-context entry points (MaxFlow, EdmondsKarp, PushRelabelMaxFlow, MinCostMaxFlow) cannot surface an error in their signature; on a violation they return the zero result (0, or (0, 0) for min-cost), mirroring how MinCostMaxFlow already swallows ErrNegativeCycle.
var ErrNegativeCycle = errors.New("flow: MinCostMaxFlow detected a negative cycle in the residual graph")
ErrNegativeCycle is returned by MinCostMaxFlowCtx when the Bellman-Ford bootstrap on a network containing negative-cost arcs detects a negative-cost cycle reachable from the source. SSP cannot converge in that case and the caller must restructure the network.
Functions ¶
func EdmondsKarp ¶
EdmondsKarp computes the max-flow from src to sink in g using the Edmonds-Karp algorithm (Ford-Fulkerson with BFS-discovered augmenting paths). Complexity is O(V * E^2), which is worse than MaxFlow's Dinic-based bound for general networks but simpler in structure — useful as a reference implementation and a baseline for property testing.
If the network's capacities could overflow the int64 flow accumulation (see ErrCapacityOverflow), EdmondsKarp returns 0 rather than a wrapped value; use EdmondsKarpCtx to receive the typed error.
func EdmondsKarpCtx ¶
EdmondsKarpCtx is the context-aware variant of EdmondsKarp. ctx.Err() is checked at every BFS rebuild (the outer augmenting- path boundary); on cancellation returns (totalSoFar, wrapped ctx.Err()).
Before any work it validates that the capacities cannot overflow the int64 flow accumulation, returning (0, ErrCapacityOverflow) when they could.
func MaxFlow ¶
MaxFlow runs Dinic's algorithm from src to sink and returns the total flow. Complexity O(V^2 * E) general; O(E * sqrt(V)) on unit-capacity networks.
If the network's capacities could overflow the int64 flow accumulation (see ErrCapacityOverflow), MaxFlow returns 0 rather than a wrapped value; use MaxFlowCtx to receive the typed error.
Example ¶
ExampleMaxFlow computes the maximum s-t flow on the classic CLRS network (Cormen et al., Fig. 26.1). Nodes are plain int indices in [0, N); the maximum flow from source 0 to sink 5 is 23.
package main
import (
"fmt"
"github.com/FlavioCFOliveira/GoGraph/search/flow"
)
func main() {
g := flow.NewNetwork(6)
g.AddEdge(0, 1, 16)
g.AddEdge(0, 2, 13)
g.AddEdge(1, 2, 10)
g.AddEdge(2, 1, 4)
g.AddEdge(1, 3, 12)
g.AddEdge(2, 4, 14)
g.AddEdge(3, 2, 9)
g.AddEdge(3, 5, 20)
g.AddEdge(4, 3, 7)
g.AddEdge(4, 5, 4)
fmt.Println("max flow:", flow.MaxFlow(g, 0, 5))
}
Output: max flow: 23
func MaxFlowCtx ¶
MaxFlowCtx is the context-aware variant of MaxFlow. ctx.Err() is checked at every BFS-level rebuild (the outer Dinic phase boundary) AND inside the inner DFS augment at a 1<<12-step granularity, so cancellation latency stays bounded even on a dense network whose phases dominate the wall time. On cancellation returns (totalSoFar, wrapped ctx.Err()).
Before any work it validates that the capacities cannot overflow the int64 flow accumulation, returning (0, ErrCapacityOverflow) when they could; see ErrCapacityOverflow for the exact bound.
func MinCostMaxFlow ¶
func MinCostMaxFlow(g *CostNetwork, src, sink int) (flow, cost int)
MinCostMaxFlow runs Successive Shortest Paths on g, pushing flow along the cheapest augmenting path discovered by Dijkstra over reduced edge costs. Returns (totalFlow, totalCost).
Negative arc costs are supported: when any arc has cost<0 the algorithm runs a Bellman-Ford bootstrap on the residual graph to initialise the node potentials so that reduced costs are non-negative from the first Dijkstra round onward. A negative-cost cycle reachable from src is reported by MinCostMaxFlowCtx via ErrNegativeCycle; this non-context entry point silently returns (0, 0) in that case.
SSP runs at most O(V * E) Dijkstras for unit-capacity networks and O(F * E log V) for general networks where F is the resulting flow magnitude — adequate for assignment-style problems with modest source/sink counts.
If the network's capacities or capacity-times-cost products could overflow the int64 flow/cost accumulation (see ErrCapacityOverflow), MinCostMaxFlow returns (0, 0) rather than wrapped values; use MinCostMaxFlowCtx to receive the typed error.
func MinCostMaxFlowCtx ¶
func MinCostMaxFlowCtx(ctx context.Context, g *CostNetwork, src, sink int) (totalFlow, totalCost int, err error)
MinCostMaxFlowCtx is the context-aware variant of MinCostMaxFlow. ctx.Err() is checked at every SSP iteration; on cancellation returns (partialFlow, partialCost, wrapped ctx.Err()).
Negative arc costs are supported via a Bellman-Ford bootstrap; if a negative cycle is reachable from src, returns (0, 0, ErrNegativeCycle) without performing any augmentation.
Before any work it validates that the capacities cannot overflow the int64 flow accumulation and that the worst-case total cost (source-cut capacity times the largest absolute per-unit cost) fits int64, returning (0, 0, ErrCapacityOverflow) otherwise.
func PushRelabelMaxFlow ¶
PushRelabelMaxFlow computes the max-flow from src to sink in g using the FIFO push-relabel algorithm (Goldberg-Tarjan 1988) with the gap heuristic. Empirically the fastest practical max-flow on dense networks (worst-case O(V^2 * sqrt(E)) with the gap pruning).
The network's edges are mutated in place (the residual capacities are decremented and the reverse edges incremented); callers needing to re-run the algorithm should rebuild the network.
If the network's capacities could overflow the int64 excess accumulation (see ErrCapacityOverflow), PushRelabelMaxFlow returns 0 rather than a wrapped value; use PushRelabelMaxFlowCtx to receive the typed error.
func PushRelabelMaxFlowCtx ¶
PushRelabelMaxFlowCtx is the context-aware variant of PushRelabelMaxFlow. ctx.Err() is checked every 4096 discharges; on cancellation returns (totalSoFar, wrapped ctx.Err()). totalSoFar is the excess accumulated at sink — a valid lower bound on the true max-flow.
Before any work it validates that the capacities cannot overflow the int64 excess accumulation, returning (0, ErrCapacityOverflow) when they could.
Types ¶
type CostNetwork ¶
type CostNetwork struct {
*Network
// contains filtered or unexported fields
}
CostNetwork extends Network with a per-edge cost. AddEdge takes a (capacity, cost) pair; reverse edges receive cost = -cost so the residual cost of cancelling forward flow is correctly reflected.
Concurrency contract identical to Network: not safe for concurrent mutation; one CostNetwork per goroutine.
func NewCostNetwork ¶
func NewCostNetwork(n int) *CostNetwork
NewCostNetwork returns an empty cost-network with n nodes.
func (*CostNetwork) AddCostEdge ¶
func (g *CostNetwork) AddCostEdge(src, dst, capacity, cost int)
AddCostEdge inserts a directed edge from src to dst with the given capacity and per-unit cost. The reverse edge is created with zero capacity and -cost.
type MinCutResult ¶
MinCutResult is the output of StoerWagner.
func StoerWagner ¶
func StoerWagner(weights []int, n int) MinCutResult
StoerWagner computes the global minimum cut on an undirected weighted graph represented as a dense n*n weight matrix in row- major order. Weights must be non-negative; symmetry w[i*n+j] == w[j*n+i] is assumed.
Complexity O(V^3) with the simple maximum-adjacency form.
Example ¶
ExampleStoerWagner finds the global minimum cut of an undirected weighted graph supplied as a dense, symmetric n*n weight matrix in row-major order. Two pairs {0,1} and {2,3} are tightly bound (weight 3) and joined by a single bridge of weight 1, so the global minimum cut severs that bridge for a total weight of 1.
package main
import (
"fmt"
"github.com/FlavioCFOliveira/GoGraph/search/flow"
)
func main() {
const n = 4
w := make([]int, n*n)
set := func(i, j, v int) { w[i*n+j], w[j*n+i] = v, v }
set(0, 1, 3) // dense pair {0,1}
set(2, 3, 3) // dense pair {2,3}
set(1, 2, 1) // the bridge between them
res := flow.StoerWagner(w, n)
fmt.Println("min-cut weight:", res.Weight)
fmt.Println("all nodes partitioned:", len(res.A)+len(res.B) == n)
}
Output: min-cut weight: 1 all nodes partitioned: true
func StoerWagnerCtx ¶
StoerWagnerCtx is the context-aware variant of StoerWagner. ctx.Err() is checked at every phase boundary; on cancellation returns (zero MinCutResult, wrapped ctx.Err()).
type Network ¶
type Network struct {
// contains filtered or unexported fields
}
Network is a directed capacitated graph. It is stored as a sum of forward and reverse-edge adjacency lists (one slice per node) so residual updates run in O(1) per edge.
Concurrency: Network is not safe for concurrent mutation; AddEdge and MaxFlow share the residual-capacity arrays without synchronisation. Use a separate Network per goroutine, or serialise externally.
v1 limitation. Network's capacity type is int (not generic over the Weight constraint). Genericising over W requires a representable "infinity push" sentinel; Go's generics cannot produce that cleanly for arbitrary named numeric types. Callers needing other weight types should map their capacities to int.
Source Files