Dinic's Maxflow¶

Min-cut is how core reasons about topology bottlenecks: the smallest total capacity whose removal separates a source from a sink. It is an analysis tool; it does not authorize a change by itself.

Network Flow Modeling¶

Cloud infrastructure maps to a directed graph: nodes \(v \in V\) are hardware (instances, gateways), edges \((u,v) \in E\) are routing flows. Each edge gets a capacity \(c(u,v) \ge 0\) determined by the hardware's network bandwidth.

Removing a target node \(t\) simulates a topology fracture. S.A.U. assigns a mathematical source node \(s\) (e.g., an Application Load Balancer egress point) and measures whether maximum flow through the subgraph drops below a critical failure threshold.

Dinic's Algorithm Implementation¶

Dinic's runs in core at pkg/graph/flow/dinic.go. It resolves max flow in \(O(V^2 E)\) — faster than Edmonds-Karp's \(O(VE^2)\) on dense infrastructure graphs.

The algorithm builds a Level Graph via BFS (isolating paths where distance strictly increases), then runs DFS blocking flow pushes along those paths.

n := flow.New(vertexCount)
n.AddEdge(from, to, capacityUSDPerGB)

value, reachable := n.MinCut(source, sink)
_, crossings := n.MinCutEdges(source, sink)

MinCut returns the cut value and the residual source side; MinCutEdges returns the original edges crossing the cut with their capacities. Capacities are float64, so cost, bandwidth, or risk weights can be used directly. ```

Disruption Validation¶

When S.A.U. simulates terminating target \(t\), the core builds a subgraph omitting \(t\) and recalculates DinicMaxFlow(). If \(Flow_{new} < Flow_{original}\) and the variance exceeds the load balancing tolerance threshold, S.A.U. raises a TopologicalFracture exception and aborts the quarantine saga to preserve application health.