This option finds maximum flow through graph of 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

If present, this must be the second line. It specifies that the links are directed. If absent the links are undirected.

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