Maximum Flow Graph Algorithm

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

Frequently Asked Questions

What is the max flow algorithm used for?

Max Flow computes the greatest amount of flow that can be pushed from source nodes to sink nodes through a capacity-constrained network. It is commonly used for network throughput and bandwidth planning, traffic routing and congestion analysis, supply chain and distribution planning, and bipartite matching or scheduling problems.

How do I run max flow in FalkorDB?

Match your source and target nodes, then call algo.maxFlow with a configuration map: CALL algo.maxFlow(...) YIELD nodes, edges, edgeFlows, maxFlow. Unlike most FalkorDB algorithms, the configuration map is required — sourceNodes, targetNodes, and relationshipTypes must all be supplied.

Can algo.maxFlow handle multiple sources and sinks?

Yes. Both sourceNodes and targetNodes accept arrays. FalkorDB adds a virtual super-source connected to every source and a virtual super-sink fed by every sink, each with infinite capacity, so multi-source and multi-sink problems work without changing your graph.

Which edge property is used as the capacity?

The property named by capacityProperty, which defaults to 'capacity'. If your edges store capacity under a different name — such as cap or bandwidth — set capacityProperty to that name.

What do the nodes and edges fields returned by algo.maxFlow contain?

They contain only the entities that carry positive flow in the solution, not the whole subgraph. edgeFlows holds the numeric flow for each edge in edges, in the same order, so you can zip them together with UNWIND range(0, size(edges) - 1).

How do I limit max flow to part of my graph?

Use relationshipTypes to choose which edges form the flow network, and nodeLabels to restrict which nodes participate. Only the induced subgraph is considered, which also keeps the computation faster.

How does max flow perform on large graphs?

The algorithm is O(V · E²) in the worst case, where V and E are the nodes and edges of the selected subgraph. Sparse graphs typically run much faster in practice. Narrowing the subgraph with nodeLabels and relationshipTypes is the most effective way to speed it up.

​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

​Frequently Asked Questions

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

Frequently Asked Questions