Maximum Flow

Overview

The Maximum Flow algorithm finds the maximum amount of flow that can be sent from a source node to a sink node through a network, respecting edge capacities. Unlike Minimum Cost Flow which also minimizes cost, this algorithm only maximizes flow.

Applications:

• Network bandwidth: Finding the maximum data throughput between two servers.
• Transportation: Maximum number of vehicles that can travel from origin to destination.
• Bipartite matching: Maximum matching can be reduced to a max-flow problem.

Concepts

Maximum Flow

In a flow network, each edge has a capacity (the maximum flow it can carry). The maximum flow is the largest total flow that can be routed from source to sink without exceeding any edge's capacity.

This implementation uses the Push-Relabel algorithm:

1. Flood: Push the maximum possible flow from the source to all its neighbors, filling each edge to capacity. Like Minimum Cost Flow, whenever flow is sent through an edge, the forward edge's remaining capacity decreases (remove edge if remaining capacity is 0) and a reverse edge is created with capacity equal to the flow sent. For example, sending 5 units through an edge with capacity 5 leaves the forward edge at 0 (edge removed) and creates a reverse edge with capacity 5.
2. Push: Each node with excess flow tries to push it toward the sink through available edges (including reverse edges).
3. Drain back: Flow that can't reach the sink gets pushed back to the source through reverse edges.

Using this network with capacity and cost on each edge:

Step 1 (Flood): Push maximum flow from S to neighbors: 10 units to A, 8 units to B. Now A has 10 excess, B has 8 excess.

Step 2 (Push toward sink): Each node pushes excess greedily to its outgoing edges in no particular order — the algorithm doesn't know the optimal split in advance. For example,

• A now has 10 excess, it might split as 5 to B and 5 to C, or 3 to B and 7 to C. Suppose A pushes 5 to B and 5 to C.
• B now has 13 excess (8 from S + 5 from A). Pushes 6 to T. B's excess = 7.
• C has 5 excess. Pushes 5 to T. T receives 11 total.

Step 3 (Redistribute): Using reverse edges, B pushes 2 units back to A. A redirects these 2 units to C (A→C still has 2 remaining capacity). C pushes 2 more to T. The remaining 5 excess at B drains back to S.

Result: Maximum flow = 13. Final flow per edge:

NOTE

The actual flow distribution per edge may vary depending on the order nodes push their excess, but the maximum flow value is always the same.

Considerations

• The algorithm follows outgoing edges only.
• If capacityProperty is not specified, all edges have unit capacity (1.0).

Example Graph

GQL
INSERT (S:default {_id: "S"}), (A:default {_id: "A"}),
       (B:default {_id: "B"}), (C:default {_id: "C"}),
       (D:default {_id: "D"}), (T:default {_id: "T"}),
       (S)-[:default {cap: 8}]->(A),
       (S)-[:default {cap: 6}]->(B),
       (A)-[:default {cap: 4}]->(C),
       (A)-[:default {cap: 5}]->(D),
       (B)-[:default {cap: 3}]->(C),
       (B)-[:default {cap: 5}]->(D),
       (C)-[:default {cap: 7}]->(T),
       (D)-[:default {cap: 6}]->(T)

Parameters

Run Mode

Returns:

GQL
CALL algo.maxflow({
  sourceNode: "S",
  sinkNode: "T",
  capacityProperty: "cap"
}) YIELD maxFlow, sourceId, targetId, flow, capacity

Result:

Stream Mode

Returns the same columns as run mode, streamed for memory efficiency.

GQL
CALL algo.maxflow.stream({
  sourceNode: "S",
  sinkNode: "T",
  capacityProperty: "cap"
}) YIELD sourceId, targetId, flow
FILTER sourceId = "S" AND targetId = "T"
RETURN sourceId, targetId, flow

Result:

Stats Mode

Returns:

GQL
CALL algo.maxflow.stats({
  sourceNode: "S",
  sinkNode: "T",
  capacityProperty: "cap"
}) YIELD maxFlow, edgeCount

Result: