- Introduction
- Create a graph
- Run the algorithm
- Description of the algorithm
- Exercise 1
- Exercise 2
- More

Network \(N = (G, c, s, t)\) with maximum flow
${f}^{*}$ \( = 6\)

A typical application of graphs is using them to represent networks of transportation infrastructure e.g. for distributing water, electricity or data. In order capture the limitations of the network it is useful to annotate the edges in the graph with capacities that model how much resource can be carried by that connection.

An interesting property of networks like this is how much of the resource can simulateneously be transported from one point to another - the maximum flow problem.

- To create a node, double-click in the drawing area.
- To create an edge, first click on the output node and then click on the destination node.
- The edge weight can be changed by double clicking on the edge. Negative weights are not allowed
- Right-clicking deletes edges and nodes.

__Annotation:__ Double edges are not allowed. Look up the description of the algorithm for the explanation!

A
occured when reading from file:
the contents:

Node | |

S/T node | |

Edge with capacity 10 and flow 7. | |

Edge in the residual graph. | |

Edge on augmenting path. |

Click on a node to select it as the source \(s\).

Intuitively is this source the start node from which the flow is sent.

Click on a node to select it as the target or sink \(t\).

Intuitively is this target the goal node to which the flow is sent.

Let now \(G = (V,E)\) be the created graph with the respective non-negative capacities \(c(e)\) for all edges \(e \in E\). Furthermore, let \(s \in V\) be the selected source and \(t \in V\) the selected target.

Together, they build a network \(N = (G,c,s,t)\).

The goal is then to find flow values \(f(e)\) for all edges \(e \in \E\) respecting the given capacities \(c\), so that the total flow ${f}^{*}$ its maximum value reaches.

Here, ${f}^{*}$ is referred to the flow, going from the source \(s\) to the target \(t\). This means: the sum over all flow values from all edges leaving the node \(s\), which is equals the sum over all flow values from all edges arriving at the node \(t\).

Click on **next** to start the algorithm

Select the so called zero-flow as the starting flow. This means setiing \(f(e) = 0\) for all edges \(e \in E\) in the graph \(G\).

The starting flow will be increased during the algorithm until the maximum flow has been found.

__Annotation:__Every valid flow can be chosen as the starting flow. It does not have to be the zero-flow.
It is only important that the capacity values remain respected. Nevertheless, the zero-flow is a good choice for the starting flow,
because it always respects the given non-negative capacities.

The main loop is runned repeatedly, until no path from the source \(s\) to the target \(t\) can be found
on the __residual network__ \(N_f\).

Such a path on \(N_f\) is called __augmenting path__.
The total flow is increased along this path.

The __residual network__, which will be constructed in the next step, gives for all edges the information
by how much the flow may be increased or reduced.
This make the new edges for the residual and backward capacities possible.

Click now on **next step** in order to find our more about \(N_f\).

Build the residual network \(N_f\) given the actual network \(N\) as follows:

Replace every edge e from N by a forward and a backward edge (e' and e'') on N_f with the following capacities c': c'(e') = c(e) - f(e) -- residual capacity c'(e'') = f(e) -- actual flow on N

Furthermore, We only keep the edges \(e'\) and \(e''\) on \(N_f\), if it is fulfilled: \(c'(e')>0\) or \(c'(e'')>0\) respectively.

Look for a path from \(s\) to \(t\) on \(N_f\).

Choose the augmenting value \(a\) as the smallest capacity value of the edges along the chosen path.

Increase the total flow ${f}^{*}$ by the augmenting value \(a\).

Increase the flow along the augmenting path as follows:

Apply \(f(e) = f(e) + a\), if the forward edge \(e'\) of \(e\) is on the path and

\(f(e) = f(e) - a\), if the backward edge \(e''\) of \(e\) is on the path.

No other (\(s,t\))-path found on the residual network.

The algorithm terminated with a maximum flow value ${f}^{*}$ of:

__Annotation:__ The algorithm always gives a maximum flow as output if it terminates. Furthermore, it always terminates after a finite number of iterations
if the given capacities are non-negative integer numbers.

s ← select(v)

t ← select(v)

BEGIN

INPUT: network N = (G,c,s,t)

with G = (V,E), s,t ∈ V

OUTPUT: flow values f(e) for all e ∈ E,

maximum flow f*

(* Initialize the flow *)

FOR { e ∈ E } DO

f(e) ← 0

(* Main Loop *)

WHILE (s,t)-path on res.network found DO

N_f ← BUILD_RES_NETWORK(N, f)

path ← FIND_PATH(N_f, s, t)

augmentation ← min(e ∈ path)

f* ← f* + augmentation

FOR {e ∈ path}

flow(e) ← flow(e) + augmentation

RETURN f, f*

END

path | augmentation |
---|---|

{} | 0 |

You can open the app in another browser window,f you want to keep reading in parallel.

Node | |

S/T Node | |

Edge with capacity 10 and flow 7. | |

Edge on residual network. | |

Edge on residual network. |

-You have the chance to answer these and more questions by running the algorithm!

Click on a node to select it as the source \(s\).

Click on a node to select it as the target or sink \(t\).

Let now \(G = (V,E)\) be the created graph with the respective non-negative capacities \(c(e)\) for all edges \(e \in E\). Furthermore, let \(s \in V\) be the selected source and \(t \in V\) the selected target.

Together, they build a network \(N = (G,c,s,t)\).

The goal is then to find flow values \(f(e)\) for all edges \(e \in E\) respecting the given capacities \(c\), so that the total flow ${f}^{*}$ its maximum value reaches.

Answer the multiple choice questions during the algorithm!

Click on **next** to start!

Select the so called zero-flow as the starting flow. This means setiing \(f(e) = 0\) for all edges \(e \in E\) in the graph \(G\).

The starting flow will be increased during the algorithm until the maximum flow has been found.

The main loop is runned repeatedly, until no path from the source \(s\) to the target \(t\) can be found
on the __residual network__ \(N_f\).

Build the residual network \(N_f\) given the actual network \(N\)

Look for a path from \(s\) to \(t\) on \(N_f\) and then choose the augmenting value \(a\).

Increase the total flow ${f}^{*}$ by the augmenting value \(a\).

Increase the flow along the augmenting path.

No other (\(s,t\))-path found on the residual network.

The algorithm terminated with a maximum flow value ${f}^{*}$ of:

s ← choose(v)

t ← choose(v)

BEGIN

INPUT: Network N = (G,c,s,t)

OUTPUT:Flow f(e) for all e ∈ E,

maximum flow value f*

(* Initialize the flow *)

FOR { e ∈ E } DO

f(e) ← 0

(* Main loop *)

WHILE ex. (s,t)-path on res.network DO

N_f ← BUILD_RES_NET(N, f)

path ← FIND_PATH(N_f, s, t)

Aug ← min(c(e) ∈ path)

f* ← f* + Aug

FOR {e ∈ path}

f(e) ← f(e) + Aug

RETURN f, f*

END

The algorithm runs once again and stops at some points so that questions can be asked.

Tip: Read the description of the algorithm.

Good luck!

You can open the app in another browser window,f you want to keep reading in parallel.

Node | |

S/T Node | |

Edge with capacity 10 and flow 7. | |

Edge on residual network. | |

Edge on augmenting path. |

You will receive different networks \(N\) with capacities \(c(e)\) and flow values \(f(e)\) for all edges \(e \in E\), based on a current flow \(f\).

Your task is to complete the residual capacities \(c(e')\) and \(c(e'')\) of the residual edges \(e'\) and \(e''\) on the residual network ${N}_{f}$.

Complete the missing residual capacities on the residual network!

**WARNING:**You are only allowed to fill a capacity value once!

**Tip:** Read the description of residual networks.

**Good luck!**

You can open the app in another browser window,f you want to keep reading in parallel.