Max Flow - FalkorDB Docs

Overview

The Max Flow algorithm computes the maximum amount of flow that can be routed through a directed, weighted graph from one or more source nodes to one or more sink (target) nodes. Edge weights represent capacities — the upper bound on how much flow an edge can carry. Max Flow is commonly applied in scenarios such as:

Network throughput optimization (bandwidth, pipelines, logistics)
Traffic routing and congestion analysis
Supply chain and distribution planning
Bipartite matching and scheduling problems

Algorithm Details

The procedure implements a capacity-scaling max-flow algorithm over the subgraph induced by the specified node labels and relationship types. It builds a residual graph from the selected edges (using the configured capacity property), then repeatedly finds augmenting paths from the source super-node to the sink super-node and pushes flow along them until no augmenting path exists. Multiple source or sink nodes are supported by introducing a virtual super-source connected to every source node, and a virtual super-sink connected from every sink node, each with infinite capacity. The algorithm returns the set of nodes and edges that carry positive flow, together with the per-edge flow values and the total maximum flow.

Performance

The algorithm operates with a time complexity of O(V · E²), where:

|V| represents the total number of nodes in the subgraph
|E| represents the total number of edges in the subgraph

For sparse graphs this is typically much faster in practice.

Syntax

CALL algo.maxFlow(config)
YIELD nodes, edges, edgeFlows, maxFlow

Parameters

The procedure accepts a required configuration Map with the following parameters:

Name	Type	Default	Description
`sourceNodes`	Array	(required)	One or more node objects that act as flow sources
`targetNodes`	Array	(required)	One or more node objects that act as flow sinks
`relationshipTypes`	Array	(required)	Relationship types that define the edges of the flow network
`capacityProperty`	String	`'capacity'`	Name of the numeric edge property used as the edge capacity
`nodeLabels`	Array	All labels	Array of node labels used to restrict which nodes are included

Return Values

The procedure yields a single record with the following fields:

Name	Type	Description
`nodes`	Array	All node entities that participate in the max-flow solution (carry positive flow)
`edges`	Array	All edge entities that carry positive flow
`edgeFlows`	Array	Numeric flow value for each edge in `edges`, in the same order
`maxFlow`	Integer	The total maximum flow from all source nodes to all sink nodes

Examples

Consider this pipeline network:

(A) --[cap:10]--> (B) --[cap:8]--> (C)
 \                                  ^
  \----------[cap:5]---------------/

Node A is the source, node C is the sink. There are two routes from A to C:

A → C directly, with capacity 5
A → B → C, with a bottleneck of 8 (min of 10 and 8)

The maximum flow is therefore 13.

Create the Graph

CREATE
  (a:Node {name: 'A'}),
  (b:Node {name: 'B'}),
  (c:Node {name: 'C'}),

  (a)-[:PIPE {cap: 10}]->(b),
  (a)-[:PIPE {cap: 5}]->(c),
  (b)-[:PIPE {cap: 8}]->(c)

Example: Compute the maximum flow between two nodes

MATCH (s:Node {name: 'A'}), (t:Node {name: 'C'})
CALL algo.maxFlow({
    sourceNodes:       [s],
    targetNodes:       [t],
    capacityProperty:  'cap',
    relationshipTypes: ['PIPE']
})
YIELD nodes, edges, edgeFlows, maxFlow
RETURN maxFlow

Expected Results

maxFlow
`13`

Example: Inspect per-edge flow on the solution

MATCH (s:Node {name: 'A'}), (t:Node {name: 'C'})
CALL algo.maxFlow({
    sourceNodes:       [s],
    targetNodes:       [t],
    capacityProperty:  'cap',
    relationshipTypes: ['PIPE']
})
YIELD edges, edgeFlows
UNWIND range(0, size(edges) - 1) AS i
RETURN
    startNode(edges[i]).name AS from,
    endNode(edges[i]).name   AS to,
    edgeFlows[i]             AS flow

Expected Results

from	to	flow
`A`	`B`	`8`
`A`	`C`	`5`
`B`	`C`	`8`

Example: Restrict the subgraph by node label

When the graph contains multiple node labels, use nodeLabels to limit the algorithm to a specific subset of nodes:

MATCH (s:Intersection {name: 'Source'}), (t:Intersection {name: 'Sink'})
CALL algo.maxFlow({
    sourceNodes:       [s],
    targetNodes:       [t],
    capacityProperty:  'bandwidth',
    nodeLabels:        ['Intersection'],
    relationshipTypes: ['CONNECTS']
})
YIELD nodes, maxFlow
RETURN size(nodes) AS participatingNodes, maxFlow

Example: Multiple sources and multiple sinks

sourceNodes and targetNodes each accept arrays, allowing multi-commodity-style problems to be modelled with virtual super-nodes:

MATCH
    (s1:Node {name: 'SourceA'}),
    (s2:Node {name: 'SourceB'}),
    (t:Node  {name: 'Sink'})
CALL algo.maxFlow({
    sourceNodes:       [s1, s2],
    targetNodes:       [t],
    capacityProperty:  'cap',
    relationshipTypes: ['PIPE']
})
YIELD maxFlow
RETURN maxFlow

​Overview

​Algorithm Details

​Performance

​Syntax

​Parameters

​Return Values

​Examples

​Create the Graph

​Example: Compute the maximum flow between two nodes

​Expected Results

​Example: Inspect per-edge flow on the solution

​Expected Results

​Example: Restrict the subgraph by node label

​Example: Multiple sources and multiple sinks

Overview

Algorithm Details

Performance

Syntax

Parameters

Return Values

Examples

Create the Graph

Example: Compute the maximum flow between two nodes

Expected Results

Example: Inspect per-edge flow on the solution

Expected Results

Example: Restrict the subgraph by node label

Example: Multiple sources and multiple sinks