Network Flow

algo.maxFlow

Property Value

Procedure

algo.maxFlow

Category

Network Flow

Complexity

CPU+RAM

Min Args

2

Max Args

5

Syntax

CALL algo.maxFlow(sourceNode, sinkNode [, relTypes, capacityProperty, direction])
YIELD maxFlow, sourceId, sinkId

Parameters

Parameter Type Required Default Description

sourceNode

Vertex

Yes

—

Flow source vertex

sinkNode

Vertex

Yes

—

Flow sink vertex

relTypes

String

No

all types

Comma-separated relationship types

capacityProperty

String

No

uniform capacity

Edge property for flow capacity

direction

String

No

OUT

How a relationship carries flow: OUT from its source to its target, IN from its target to its source, BOTH either way (an undirected pipe)

Yield Fields

Field Type Description

maxFlow

Double

Maximum flow value from source to sink

sourceId

RID

Identity of the source vertex

sinkId

RID

Identity of the sink vertex

Description

Computes the maximum flow from a source to a sink using Dinic’s algorithm over a sparse residual network: O(V²·E) time and O(V+E) memory. Every relationship is a pipe from its source to its target (with the default direction OUT), so flow never runs against a relationship, and relationships between the same two nodes in the same direction add their capacities. A self loop, or a capacity that is not positive, carries nothing. The flow from a node to itself is 0. Returns a single row with the maximum achievable flow.

Before 26.12.1 every relationship was read as an undirected pipe, the behavior direction BOTH now selects (issue #11798).

Use Cases

  • Network throughput capacity analysis

  • Traffic flow optimization

  • Supply chain max throughput calculation

Example

MATCH (src:Node {id:'source'}), (sink:Node {id:'sink'})
CALL algo.maxFlow(src, sink, 'PIPE', 'capacity')
YIELD maxFlow, sourceId, sinkId
RETURN maxFlow, sourceId, sinkId

References