Flows

This option finds maximum flow through graph of directed links with specified maximum capacity

Input

format

The first line specifies the calculation required.

Column	Description
1	'format'
2	calculation name

Available calculations

• 'flows' maximum flow from one source
• 'multiflows' maximum flow from several sources
• 'equiflows' maximum flow from one source with equal flows on every outlink in a node https://stackoverflow.com/questions/67908818

graph mode

Column	Description
1	g for graph

This must be the second line. It specifies that the links are directed.

Links

Column	Description
1	l for link
2	src node name
3	dst node name
4	maximum capacity

source

Column	Description
1	s
2	source node name

For flows calculation, only the last source node will be used. mutiflows will add together flows from all sources specified.

end

Column	Description
1	e
2	node name

Example 1

format flows
g
l src a 210
l a b 200
l a c 200
l b d 500
l c d 500
s src
e d


total flow 500

Example 2

format multiflows
g
l src a 210
l src2 b 50
l a b 200
l a c 200
l b d 500
l c d 500
s src
s src2
e d

a -- b capacity 200 used 10
a -- c capacity 200 used 200
src -- a capacity 210 used 210
b -- d capacity 500 used 60
src2 -- b capacity 50 used 50
c -- d capacity 500 used 200
total flow 260.000000

Example 3

format equiflows
g
g
l 1 2 4
l 1 3 5
l 2 3 2
l 2 4 3
l 3 4 6
s 1
e 4

total flow 8.000000
2 -> 3 capacity 2 used 2
2 -> 4 capacity 3 used 2
1 -> 2 capacity 4 used 4
1 -> 3 capacity 5 used 4
3 -> 4 capacity 6 used 6

Algorithm

Edmonds–Karp

1. Find a shortest path from a source to a destination, using the Breadth First Search
2. Find minimum capacity of any link on the path
3. Reduce capacity of all links on path by minimum capacity
4. Remove any link that now has zero capacity
5. Repeat above steps until no more paths can be found.