Maximum Flow

This is the 20th day of my participation in the August More Text Challenge

Basic properties of Flow Networks

In graph theory, a network flow is defined as a directed graph containing a starting point Source and an ending point Target, as well as edges connecting each vertex. Each edge has its own Capacity, which is the maximum flow that an edge can allow

The FFF of network traffic must meet the following conditions

• The flow from node XXX to node YYy cannot be larger than the capacity of edge(x,y)edge(x,y)edge(x, Y)edge(x, Y)f(x,y)≤ C (x,y) F (x,y)≤ C (x,y) F (x,y)≤ C (x,y)
• If f(x,y)= 5F (x,y)= 5F (x,y)=5, then f(y,x)=− 5F (y,x)= -5F (y,x)=−5 is defined as the traffic from node XXX to node YYy
• For nodes in the diagram except Source and Target, the sum of all input traffic must equal the sum of all output traffic
  • That is, the flow does not increase or decrease without cause, which can be regarded as a conservation of energy
  • In the following figure, for example, the flow into node A is 6, and the flow out is also 6, as is the flow into node C and D

Maximum Flow: The maximum amount of traffic that the network allows from Source to destination Target

The following describes the Ford-Fulkerson Algorithm (also known as Edmonds-Karp Algorithm if BFS is used) to solve this problem

Ford-Fulkerson Algorithm

Ford-fulkerson Algorithm requires two auxiliary tools

1. Residual Networks
2. One of the most important Paths

Residual Networks

Residual network represents the graph composed of the remaining allowable traffic on each edge of the graph, as shown in the following figure

If the Path: All the sides of S-A-C-D-T have 6 units of flow, so these sides, Edge (S, A) edge (S, A) edge (S, A), edge (A, C) edge (A, C) edge (A, C), edge (C, D) edge (C, D) edge (C, D), Edge (D,T) Edge (D,T) The remaining capacity of edge(D,T) should be reduced by 6. For example, edge(S,A)edge(S,A) Edge (S,A) can hold only 3 units of traffic, and edge(C,D)edge(C,D) Edge (C,D) can hold only 1 unit of traffic

If the edge (x, y) edge (x, y) on the edge (x, y) f (x, y) f (x, y) f (x, y) unit of traffic flow, the edge (x, y) edge (x, y) edge (x, y) on the residual capacity is defined as:

• 
  $c_f(x,y)=c(x,y)-f(x,y)$
  • C (x,y)c(x,y)c(x,y) is the capacity of the original edge(x,y)
  • F (x,y)f(x,y)f(x,y) indicates how much traffic edge(x,y) has
  • Cf (x,y) c_F (x,y) CF (x,y) indicates how much more traffic edge(x,y) can hold

Residual Networks is also a directed graph, where:

• The vertex set is identical to the original digraph
• Edge capacity is replaced by residual capacity, as shown in the following figure

Edge (A,C)edge(A,C)edge(A,C) edge(A,C) f(A,C)= 6F (A,C)= 6F (A,C)=6 on Residual Networks Edge (C,A)edge(C,A)edge(C,A) edge(C,A)edge(C,A)edge(C,A) is residual capacity cf(C,A)= 6C_F (C,A)= 6CF (C,A)=6

What’s the point? This can be understood as if you want to reconfigure the direction of traffic

For example, suppose that we are now back to the initial state (no traffic flows) and that 2 units of traffic now pass through Path: S-c-a-b-t, but since there is no edge(C,A)edge(C,A)edge(C,A) edge(C,A)edge(C,A) from vertex C to vertex A, so C (C,A)=0c(C,A)=0c(C,A)=0. Assuming 6 units of traffic flow from vertex A to vertex C (as shown in the figure above), then 2 units of traffic can now be recovered from edge(A,C)edge(A,C)edge(A,C) edge(A,C) and distributed to edge(A,B)edge(A,B)edge(A,B), On edge(A,C) Edge (A,C)edge(A,C) there is only 4 units of flow left. The last result is shown on the left and the Residual Networks are shown on the right

Here is another example found on the Internet

Augmenting Paths

In the Residual Networks, all the hardly Paths that can be traveled from Source to final Target are called Augmenting Paths.

One of the most important Paths has many possibilities, e.g

• Path: S-A-B-T, 1 to 3 units of traffic
  • Because the minimum capacity of all edges in this path is C (S,A)= C (A,B)= 3C (S,A)= C (A,B)=3c(S,A)= C (A,B)=3, the allowable flow size can be 1~3
• Path: s-C-B-D-T, 1 to 2 units of traffic
  • In this path, the minimum capacity of all edges is C (B,D)= C (D,T)=2c(B,D)= C (D,T)=2c(B,D)=c(D,T)=2, so the allowable flow size is 1~2

To sum up

• If you want to seeTotal current traffic to Target, should be marked on the left edge of the picture belowflow/capacityFind on the drawing
  • The flow into the destination Target on the left in the figure below is 8 units
• If you want to findHow much more traffic can we addThat is, to findAugmenting PathsThat need to be inResidual NetworksLook up, as shown on the right of the picture below
  • If the flow of Path: S-A-B-T, Path: S-A-C-D-T, or Path: S-C-B-T does not exceed the minimum residual capacity on the Path, these are Augmenting Paths

After talking about the above two concepts, the following explains the Ford-Fulkerson Algorithm Algorithm

• inResidual NetworksOn looking forAugmenting Paths
  • In order toBFS()1. Look for carefully crafted Paths with the least edge
  • Find the least residual capacity on the hardly Paths and add it to the total flow
  • Then update the residual capacity of edge on the residual network with the minimum residual capacity
• Repeat these steps until there are no more Augmenting Paths

In the above picture, the steps to find Maximum Flow are as follows

• At the beginning of the useflow = 0Initialize residual Networks

• In the picture, withbfs()Find fromStoTThe Path with the least edge: S-A-B-T
  • bfs()It is possible to find three shortest paths, for example, S-A-B-T

• Edge (A,B)edge(A,B)edge(A,B) has minimum residual capacity CF (A,B)= 3C_F (A,B)= 3CF (A,B)=3, so update: Total flow is increased by 3
• Update edge residual Capacity
  • 
    $c_f(S,A)=c(S,A)-f(S,A)=9-3=6$
  • 
    $c_f(A,S)=c(A,S)-f(A,S)=0+3=3$
  • 
    $c_f(A,B)=c(A,B)-f(A,B)=3-3=0$
  • 
    $c_f(B,A)=c(B,A)-f(B,A)=0+3=3$
  • 
    $c_f(B,T)=c(B,T)-f(B,T)=9-3=6$
  • 
    $c_f(T,B)=c(T,B)-f(T,B)=0+3=3$

• On the way tobfs()Find fromS* toTThe Path with the least edge: S-C-D-T

• Edge (C,D)edge(C,D)edge(C,D) has minimum residual capacity CF (C,D)=7c_f(C,D)= 7CF (C,D)=7 update: The total flow is increased by 7

• Update edge residual Capacity

  • 
    $c_f(S,C)=c(S,C)-f(S,C)=9-7=2$
  • 
    $c_f(C,S)=c(C,S)-f(C,S)=0+7=7$
  • 
    $c_f(C,D)=c(C,D)-f(C,D)=7-7=0$
  • 
    $c_f(D,C)=c(D,C)-f(D,C)=0+7=7$
  • 
    $c_f(D,T)=c(D,T)-f(D,T)=8-7=1$
  • 
    $c_f(T,D)=c(D,T)-f(T,D)=0+7=7$

Then repeat the above steps: update Residual Networks and find Augmenting Paths

• Find Path: S-C-B-T

• Update the Residual Networks

• Find Path: S-A-C-B-T

• Update the Residual Networks

• Find Path: S-A-C-b-D-T

• Update the Residual Networks

• Find the Maximum Flow = 17

The complete code is as follows

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Graph {
private:
    int num_vertex; / / the vertices
    vector<vector<int>> map; // Adjacency matrix
public:
    Graph() :num_vertex(0) {};Graph(int n);
    void AddEdge(int from, int to, int capacity);
    void FordFulkerson(int s, int t);
    bool BfsFindExistingPath(vector<vector<int>> graph, int* predecessor, int s, int t);
    int MinCapacity(vector<vector<int>> graph, int* predecessor, int t);
};

Graph::Graph(int n):num_vertex(n) {
    map.resize(num_vertex);
    for (int i = 0; i < num_vertex; i++)
        map[i].resize(num_vertex);
}

bool Graph::BfsFindExistingPath(vector<vector<int>> graph, int* predecessor, int s, int t) {
    int visited[num_vertex];
    for (int i = 0; i < num_vertex; i++) {
        visited[i] = 0; // 0 indicates no access
        predecessor[i] = - 1;
    }

    queue<int> queue;
    queue.push(s);
    visited[s] = 1; // 1 indicates yes
    while(! queue.empty()) {
        int vertex = queue.front(a); queue.pop(a);for (int j = 0; j < num_vertex; j++) {
            if(graph[vertex][j] ! =0 && visited[j] == 0) {
                queue.push(j);
                visited[j] = 1; predecessor[j] = vertex; }}}return (visited[t] == 1); // If t is accessed, there is a path from s to t
}

int Graph::MinCapacity(vector<vector<int>> graph, int* predecessor, int t) {
    int min = 0x3f3f3f; // Make sure min is updated, assuming capacity on graph is less than 0x3f3f3f
    
    The predecessor[IDx] and IDX represent an edge
    // Find the minimum value of capacity in the path from s to t and store it in min
    for (intidx = t; predecessor[idx] ! =- 1; idx = predecessor[idx])
        if(graph[predecessor[idx]][idx] ! =0 && graph[predecessor[idx]][idx] < min)
            min = graph[predecessor[idx]][idx];
    return min;
}

void Graph::FordFulkerson(int s, int t) {
    vector<vector<int>> graphResidual(map);
    int maxflow = 0;
    int predecessor[num_vertex];

    // bfs find augmeting path
    while (BfsFindExistingPath(graphResidual, predecessor, s, t)) {
        int min_capacity = MinCapacity(graphResidual, predecessor, t);
        maxflow = maxflow + min_capacity;
        for (inty = t; y ! = s; y= predecessor[y]) {// update residual graph
            int x = predecessor[y];
            graphResidual[x][y] -= min_capacity;
            graphResidual[y][x] += min_capacity;
        }
    }
    cout << "Maximum Flow: " << maxflow << endl;
}

void Graph::AddEdge(int from, int to, int capacity) {
    map[from][to] = capacity;
}

int main(a) {
    Graph g(6);
    g.AddEdge(0.1.9); g.AddEdge(0.3.9);
    g.AddEdge(1.2.3); g.AddEdge(1.3.8);
    g.AddEdge(2.4.2); g.AddEdge(2.5.9);
    g.AddEdge(3.2.7); g.AddEdge(3.4.7);
    g.AddEdge(4.2.4); g.AddEdge(4.5.8);

    g.FordFulkerson(0.5); // Set source to 0 and target to 5
    return 0;
}
Copy the code