Module flow 

Network flow algorithms for graph processing

This module contains algorithms for finding maximum flows, minimum cuts, min-cost max flows, multi-commodity flows, and bipartite matching.

Algorithms

• Edmonds-Karp: Max flow via Ford-Fulkerson with BFS (O(VE^2))
• Dinic’s: Max flow via blocking flows and level graphs (O(V^2 E))
• Push-Relabel: Max flow via preflow and relabeling (O(V^2 sqrt(E)))
• Min-Cut: Minimum s-t cut derived from max flow
• Min-Cost Max Flow: Successive shortest paths algorithm
• Multi-Commodity Flow: LP relaxation approximation
• Hopcroft-Karp: Maximum bipartite matching (O(E sqrt(V)))

Structs

CostEdge

Edge with both capacity and cost

HopcroftKarpResult

Result of Hopcroft-Karp bipartite matching

MaxFlowResult

Result of a max-flow computation

MinCostFlowResult

Result of a min-cost max-flow computation

MultiCommodityFlowResult

Result of a multi-commodity flow computation

Functions

capacity_scaling_max_flow

Capacity scaling algorithm for maximum flow. Uses Edmonds-Karp with capacity scaling for better performance on high-capacity graphs.

dinic_max_flow

Dinic’s algorithm for maximum flow.

dinic_max_flow_full

Dinic’s algorithm returning full flow result.

edmonds_karp_max_flow

Edmonds-Karp algorithm for maximum flow (Ford-Fulkerson with BFS).

ford_fulkerson_max_flow

Ford-Fulkerson max flow using BFS (Edmonds-Karp variant).

hopcroft_karp

Hopcroft-Karp algorithm for maximum bipartite matching.

isap_max_flow

ISAP (Improved Shortest Augmenting Path) algorithm for maximum flow. Delegates to Dinic’s which has similar complexity.

min_cost_max_flow

Min-cost max flow using successive shortest paths (Bellman-Ford).

min_cost_max_flow_graph

Min-cost max flow on a DiGraph with separate cost function.

minimum_cut

Find minimum s-t cut using max flow.

minimum_st_cut

Find minimum s-t cut from max flow result.

multi_commodity_flow

Multi-commodity flow using LP relaxation via iterative proportional scaling.

multi_source_multi_sink_max_flow

Multi-source multi-sink maximum flow.

parallel_max_flow

Parallel maximum flow algorithm. Currently delegates to Dinic’s; parallelism is a future optimization.

push_relabel_max_flow

Push-relabel algorithm for maximum flow.

push_relabel_max_flow_full

Push-relabel algorithm returning full flow result.