Documentation — FlowNet

Introduction to Network Flow

Network flow theory is a branch of combinatorial optimization studying flows through networks. A flow network is a directed graph where each edge has a capacity, and the goal is to determine the maximum amount of "flow" that can be sent from a designated source node to a sink node without exceeding any edge's capacity.

FlowNet provides an interactive environment to build flow networks, run algorithms, and observe how flow moves through the graph step by step — making it ideal for students, educators, and researchers.

Quick Start

To create and analyze your first flow network:

1. Add Nodes — In "Add Node" mode, click anywhere on the canvas. The first node becomes the source (S), the last becomes the sink (T). Right-click any node to toggle its type.

2. Add Edges — Switch to "Add Edge" mode, click the source node, then the target. Enter the edge capacity in the prompt.

3. Run Max-Flow — Select an algorithm from the dropdown and click "Run Max Flow." The result is displayed immediately. Use "Step Forward" to walk through each augmenting path one at a time.

You can also load a preset graph using the "Presets" panel on the left.

Interface Guide

Toolbar Modes

Mode	Action	Shortcut
Add Node	Click canvas to place node	N
Add Edge	Click two nodes to connect	E
Move	Drag nodes to reposition	M
Delete	Click node/edge to remove	Del

Right-Click Context

Right-clicking any node cycles its type: Normal → Source → Sink. Source nodes are highlighted in cyan, sinks in orange.

Flow Networks

Formally, a flow network G = (V, E) is a directed graph with a capacity function c: E → ℝ≥0, a source s ∈ V, and a sink t ∈ V. A flow f is a function f: E → ℝ that satisfies:

Capacity constraint:   0 ≤ f(u,v) ≤ c(u,v)  ∀(u,v) ∈ E
Flow conservation:     Σ f(u,v) = Σ f(v,w)    ∀v ≠ s,t
                       (inflow = outflow at every intermediate node)

The value of a flow |f| is the total flow leaving the source: |f| = Σ f(s,v) for all v adjacent to s.

The Max-Flow Problem

The maximum flow problem asks: given a flow network, what is the maximum value of flow that can be routed from source s to sink t? This is one of the most fundamental combinatorial optimization problems with applications ranging from transportation logistics to computer networks and bipartite matching.

Problem Statement

Maximize:   |f| = Σ f(s,v)
Subject to: Capacity constraints for all edges
            Flow conservation at all intermediate nodes

Max-Flow Min-Cut Theorem

One of the most elegant results in graph theory: the maximum value of any flow equals the minimum capacity of any cut separating s from t.

A cut (S, T) partitions V into S (containing s) and T (containing t). The capacity of cut (S, T) is the sum of capacities of edges going from S to T. The max-flow min-cut theorem states that these two quantities are always equal.

max |f| = min { Σ c(u,v) : u ∈ S, v ∈ T, (u,v) ∈ E }

Residual Graphs

The residual graph G_f of a flow network G with respect to flow f contains:

For each edge (u,v) ∈ E with capacity c and flow f:
  Forward edge  (u→v): residual capacity = c - f
  Backward edge (v→u): residual capacity = f (cancellation)

An augmenting path is any path from s to t in the residual graph. The bottleneck of the path is the minimum residual capacity on the path. Pushing flow along this path increases total flow by the bottleneck amount.

Ford-Fulkerson Algorithm

The foundational max-flow algorithm, introduced by Ford and Fulkerson in 1956.

function ford_fulkerson(G, s, t):
  initialize f(u,v) = 0 for all edges
  while exists augmenting path P in residual graph G_f:
    bottleneck = min { c_f(u,v) : (u,v) on P }
    for each edge (u,v) on P:
      f(u,v) += bottleneck
      f(v,u) -= bottleneck
  return total flow |f|

The DFS variant may not terminate with irrational capacities. The BFS variant (Edmonds-Karp) always finds the shortest augmenting path and runs in O(VE²).

Dinic's Algorithm

Dinic's algorithm achieves O(V²E) time by using layered (level) graphs and blocking flows. It is the fastest general-purpose max-flow algorithm for dense graphs.

function dinic(G, s, t):
  while BFS(G_f, s, t) finds level graph L:
    while exists blocking flow in L:
      find and push blocking flow via DFS
  return total flow |f|

function blocking_flow(L, s, t):
  use DFS with advance/retreat on level graph
  saturate at least one edge per path found

For unit-capacity networks (all capacities = 1), Dinic's runs in O(E√V), making it extremely efficient for bipartite matching.

Push-Relabel Algorithm

Instead of augmenting along paths, push-relabel works locally by maintaining a preflow (allows excess at nodes) and a height labeling.

function push_relabel(G, s, t):
  initialize height h[s]=|V|, h[others]=0
  saturate all edges out of s (create excess)
  while exists active node (excess > 0, not s or t):
    if admissible edge (u,v): push(u, v)
    else: relabel(u)  // increase height
  return excess at t

The HLPPS (Highest Label Pre-flow Push) variant processes the highest active node first, achieving O(V²√E) in practice.

Bipartite Matching via Max-Flow

Maximum bipartite matching can be reduced to max-flow. Given bipartite graph G=(L∪R, E):

Add super-source s connected to all L nodes (cap=1)
Add super-sink t connected from all R nodes (cap=1)
Each original edge (l,r) has capacity 1
Run max-flow; the value equals max matching size
Matched pairs are edges with flow = 1

This runs in O(E√V) with Dinic's algorithm. Load the "Bipartite Match" preset in the Visualizer to see this in action.

Real-World Applications

Domain	Application	Model
Transportation	Road/rail capacity planning	Edge = road segment, capacity = vehicles/hour
Networking	Internet bandwidth allocation	Edge = link capacity in Mbps
Scheduling	Job-machine assignment	Bipartite matching reduction
Image Segmentation	Foreground/background separation	Grid graph, min-cut = segmentation boundary
Supply Chain	Distribution optimization	Min-cost max-flow on supply network
Baseball Elimination	Team elimination checking	Flow constraint feasibility test