This section describes how to implement a flow network.
A flow network is a directed graph that has the following properties:
Let us define the MaxFlow
class that keeps track of the amount of flows in every edge used to find the maximum flow:
L2
: consists of (edge, flow) as the key-value pair.
L3
: stores the total amount of flows to the target vertices.
L13-14
: initializes all flows to 0
.
Let us define getter methods:
L5
: returns the remaining residual that can be used to push more flows.
L6
: the edge weight represents the total capacity.
Finally, let us define setter methods:
L1
: takes the path from a source and a target.
L2
: updates the flow of every edge in the path with the specific flow.
L3
: updates the overall flow.
L6
: adds the specific flow to the specific edge.
This chapter discusses the optimization problem called Network Flows that finds the maximum flow given a flow network.
This section describes the implementation of Ford-Fulkerson Algorithm
Let us define the Subgraph
class that consists of a subset of vertices and edges from the original graph:
Let us define helper methods:
Ford-Fulkerson algorithm finds the maximum flow from a flow network as follows:
Let us create the FordFulkerson
class:
L2
: indicates one source and one target vertices.
L6
: iterates as long as it can find an augmenting path
L7
: finds the edge with the minimum capacity in the augmenting path.
L8
: updates the edges in the path with the flow.
Let us define the getMin()
method:
Finally, let us define the getAugmentingPath()
method:
L2
: once the source reaches the target, it found an augmenting path.
L6
: adding the source vertex would cause a cycle.
L7
: cannot push the flow when there is no residual left.
L10
: recursively finds the augmenting path by switching the target.
Let us consider the following graph:
As shown, our implementation of Ford-Fulkerson Algorithm does not always guarantee to find the maximum flow correctly. To fix this issue, we need to implement backward pushing:
The backward pushing can be performed after the applying the flow to all edges as in the implementation above (see the code in the "With Backward Pushing" tab).
Finally, the updateBackward() method can be implemented as follows:
This section provides exercises for better understanding in network flow
An augmenting path is a directed path between the source and target vertices; no need to worry about residuals for this quiz.
Update the getAugmentingPaths()
method that returns all augmenting paths between the specific source and target vertices using depth-first traverse.
Create the NetworkFlowQuizExtra
class and update the getAugmentingPaths()
method such that it uses breadth-first traverse instead of depth-first traverse.
Write quiz8
that includes:
The worst-case complexity of your getAugmentingPaths()
method.
An explanation of when the depth-first traverse is preferred over the breadth-first traverse and vice versa to find augmenting paths.
An objective function and is constraints to find max-flow.
An objective function and is constraints to find min-cut.
Create the class under the package.
Given the following graph where there are two source vertices, and , and two target vertices, and , define the objective functions and their constraints to find the (1) max-flow and (2) min-cut using the simplex algorithm:
Let - cut be a set of edges whose removal disconnects any path between and :