Module dinics 

Functions

adjusted_residual_flow 🔒

Returns the adjusted residual flow for given edge and flow increase.

build_level_graph 🔒

Makes a BFS that labels network vertices with levels representing their distance to the source vertex, considering only edges with positive residual capacity.

dinics

Compute the maximum flow from source to destination in a directed graph. Implements Dinic’s (or Dinitz’s) algorithm, which builds successive level graphs using breadth-first search and finds blocking flows within them through depth-first searches.

find_augmenting_path 🔒

Makes a DFS to find an augmenting path from source to destination vertex using previously computed edge_levels from level graph.

find_blocking_flow 🔒

Find blocking flow for current level graph by repeatingly finding augmenting paths in it.

min 🔒

Returns the minimum value between given a and b. Will panic if it tries to compare two elements that aren’t comparable (i.e., given two elements a and b, neither a >= b nor a < b).

other_endpoint 🔒

Gets the other endpoint of graph edge, if any, otherwise panics.

residual_capacity 🔒

Returns the residual capacity of given edge.