Алгоритм форда фалкерсона java

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

Ford-Fulkerson Algorithm (FFA) integrated with Breadth-First Search (BFS) implementation along with input file passer

nuvinga/ford-fulkerson-algorithm

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

Ford-Fulkerson Algorithm Implementation

This application was built as partial completion of my second year reading for the B.Eng. (Hons) Software Engineering degree, from the University of Westminster.

The Ford–Fulkerson method or Ford–Fulkerson algorithm (FFA) is a greedy algorithm that computes the maximum flow in a flow network. It is sometimes called a «method» instead of an «algorithm» as the approach to finding augmenting paths in a residual graph is not fully specified or it is specified in several implementations with different running times. It was published in 1956 by L. R. Ford Jr. and D. R. Fulkerson. The name «Ford–Fulkerson» is often also used for the Edmonds–Karp algorithm, which is a fully defined implementation of the Ford–Fulkerson method.

This implementation uses the Breadth-first search (BFS) along with the FFA for node visiting.

As long as there is a path from the source (start node) to the sink (end node), with available capacity on all edges in the path, we send flow along one of the paths. Then we find another path, and so on. A path with available capacity is called an augmenting path.

Indexed in Turn-It In Global Referencing Scheme

This project should not be used for any coursework related activity and all codes have been submitted to Turn-It In global referencing platform , where usage of this code may be caught for Plagiarism.

About

Ford-Fulkerson Algorithm (FFA) integrated with Breadth-First Search (BFS) implementation along with input file passer

Источник

Ford-Fulkerson Algorithm for Maximum Flow Problem

The Ford-Fulkerson algorithm is a widely used algorithm to solve the maximum flow problem in a flow network. The maximum flow problem involves determining the maximum amount of flow that can be sent from a source vertex to a sink vertex in a directed weighted graph, subject to capacity constraints on the edges.

The algorithm works by iteratively finding an augmenting path, which is a path from the source to the sink in the residual graph, i.e., the graph obtained by subtracting the current flow from the capacity of each edge. The algorithm then increases the flow along this path by the maximum possible amount, which is the minimum capacity of the edges along the path.

Given a graph which represents a flow network where every edge has a capacity. Also, given two vertices source ‘s’ and sink ‘t’ in the graph, find the maximum possible flow from s to t with the following constraints:

• Flow on an edge doesn’t exceed the given capacity of the edge.
• Incoming flow is equal to outgoing flow for every vertex except s and t.

For example, consider the following graph from the CLRS book.

The maximum possible flow in the above graph is 23.

1. Start with initial flow as 0.
2. While there exists an augmenting path from the source to the sink:
   • Find an augmenting path using any path-finding algorithm, such as breadth-first search or depth-first search.
   • Determine the amount of flow that can be sent along the augmenting path, which is the minimum residual capacity along the edges of the path.
   • Increase the flow along the augmenting path by the determined amount.
3. Return the maximum flow.

Time Complexity: Time complexity of the above algorithm is O(max_flow * E). We run a loop while there is an augmenting path. In worst case, we may add 1 unit flow in every iteration. Therefore the time complexity becomes O(max_flow * E).

How to implement the above simple algorithm?
Let us first define the concept of Residual Graph which is needed for understanding the implementation.

Residual Graph of a flow network is a graph which indicates additional possible flow. If there is a path from source to sink in residual graph, then it is possible to add flow. Every edge of a residual graph has a value called residual capacity which is equal to original capacity of the edge minus current flow. Residual capacity is basically the current capacity of the edge.

Let us now talk about implementation details. Residual capacity is 0 if there is no edge between two vertices of residual graph. We can initialize the residual graph as original graph as there is no initial flow and initially residual capacity is equal to original capacity. To find an augmenting path, we can either do a BFS or DFS of the residual graph. We have used BFS in below implementation. Using BFS, we can find out if there is a path from source to sink. BFS also builds parent[] array. Using the parent[] array, we traverse through the found path and find possible flow through this path by finding minimum residual capacity along the path. We later add the found path flow to overall flow.

The important thing is, we need to update residual capacities in the residual graph. We subtract path flow from all edges along the path and we add path flow along the reverse edges We need to add path flow along reverse edges because may later need to send flow in reverse direction (See following link for example).
https://www.geeksforgeeks.org/max-flow-problem-introduction/

Below is the implementation of Ford-Fulkerson algorithm. To keep things simple, graph is represented as a 2D matrix.

Источник

Ford-Fulkerson Algorithm

Ford-Fulkerson algorithm is a greedy approach for calculating the maximum possible flow in a network or a graph.

A term, flow network, is used to describe a network of vertices and edges with a source (S) and a sink (T). Each vertex, except S and T, can receive and send an equal amount of stuff through it. S can only send and T can only receive stuff.

We can visualize the understanding of the algorithm using a flow of liquid inside a network of pipes of different capacities. Each pipe has a certain capacity of liquid it can transfer at an instance. For this algorithm, we are going to find how much liquid can be flowed from the source to the sink at an instance using the network.

Terminologies Used

Augmenting Path

It is the path available in a flow network.

Residual Graph

It represents the flow network that has additional possible flow.

Residual Capacity

It is the capacity of the edge after subtracting the flow from the maximum capacity.

How Ford-Fulkerson Algorithm works?

1. Initialize the flow in all the edges to 0.
2. While there is an augmenting path between the source and the sink, add this path to the flow.
3. Update the residual graph.

We can also consider reverse-path if required because if we do not consider them, we may never find a maximum flow.

The above concepts can be understood with the example below.

Ford-Fulkerson Example

The flow of all the edges is 0 at the beginning.

1. Select any arbitrary path from S to T. In this step, we have selected path S-A-B-T .
   The minimum capacity among the three edges is 2 ( B-T ). Based on this, update the flow/capacity for each path.
2. Select another path S-D-C-T . The minimum capacity among these edges is 3 ( S-D ).
   Update the capacities according to this.
3. Now, let us consider the reverse-path B-D as well. Selecting path S-A-B-D-C-T . The minimum residual capacity among the edges is 1 ( D-C ).
   Updating the capacities.
   The capacity for forward and reverse paths are considered separately.
4. Adding all the flows = 2 + 3 + 1 = 6, which is the maximum possible flow on the flow network.

Note that if the capacity for any edge is full, then that path cannot be used.

Python, Java and C/C++ Examples

# Ford-Fulkerson algorith in Python from collections import defaultdict class Graph: def __init__(self, graph): self.graph = graph self. ROW = len(graph) # Using BFS as a searching algorithm def searching_algo_BFS(self, s, t, parent): visited = [False] * (self.ROW) queue = [] queue.append(s) visited[s] = True while queue: u = queue.pop(0) for ind, val in enumerate(self.graph[u]): if visited[ind] == False and val > 0: queue.append(ind) visited[ind] = True parent[ind] = u return True if visited[t] else False # Applying fordfulkerson algorithm def ford_fulkerson(self, source, sink): parent = [-1] * (self.ROW) max_flow = 0 while self.searching_algo_BFS(source, sink, parent): path_flow = float("Inf") s = sink while(s != source): path_flow = min(path_flow, self.graph[parent[s]][s]) s = parent[s] # Adding the path flows max_flow += path_flow # Updating the residual values of edges v = sink while(v != source): u = parent[v] self.graph[u][v] -= path_flow self.graph[v][u] += path_flow v = parent[v] return max_flow graph = [[0, 8, 0, 0, 3, 0], [0, 0, 9, 0, 0, 0], [0, 0, 0, 0, 7, 2], [0, 0, 0, 0, 0, 5], [0, 0, 7, 4, 0, 0], [0, 0, 0, 0, 0, 0]] g = Graph(graph) source = 0 sink = 5 print("Max Flow: %d " % g.ford_fulkerson(source, sink))

// Ford-Fulkerson algorith in Java import java.util.LinkedList; class FordFulkerson < static final int V = 6; // Using BFS as a searching algorithm boolean bfs(int Graph[][], int s, int t, int p[]) < boolean visited[] = new boolean[V]; for (int i = 0; i < V; ++i) visited[i] = false; LinkedListqueue = new LinkedList(); queue.add(s); visited[s] = true; p[s] = -1; while (queue.size() != 0) < int u = queue.poll(); for (int v = 0; v < V; v++) < if (visited[v] == false && Graph[u][v] >0) < queue.add(v); p[v] = u; visited[v] = true; >> > return (visited[t] == true); > // Applying fordfulkerson algorithm int fordFulkerson(int graph[][], int s, int t) < int u, v; int Graph[][] = new int[V][V]; for (u = 0; u < V; u++) for (v = 0; v < V; v++) Graph[u][v] = graph[u][v]; int p[] = new int[V]; int max_flow = 0; # Updating the residual calues of edges while (bfs(Graph, s, t, p)) < int path_flow = Integer.MAX_VALUE; for (v = t; v != s; v = p[v]) < u = p[v]; path_flow = Math.min(path_flow, Graph[u][v]); >for (v = t; v != s; v = p[v]) < u = p[v]; Graph[u][v] -= path_flow; Graph[v][u] += path_flow; >// Adding the path flows max_flow += path_flow; > return max_flow; > public static void main(String[] args) throws java.lang.Exception < int graph[][] = new int[][] < < 0, 8, 0, 0, 3, 0 >, < 0, 0, 9, 0, 0, 0 >, < 0, 0, 0, 0, 7, 2 >, < 0, 0, 0, 0, 0, 5 >, < 0, 0, 7, 4, 0, 0 >, < 0, 0, 0, 0, 0, 0 >>; FordFulkerson m = new FordFulkerson(); System.out.println("Max Flow: " + m.fordFulkerson(graph, 0, 5)); > >

/ Ford - Fulkerson algorith in C #include #define A 0 #define B 1 #define C 2 #define MAX_NODES 1000 #define O 1000000000 int n; int e; int capacity[MAX_NODES][MAX_NODES]; int flow[MAX_NODES][MAX_NODES]; int color[MAX_NODES]; int pred[MAX_NODES]; int min(int x, int y) < return x < y ? x : y; >int head, tail; int q[MAX_NODES + 2]; void enqueue(int x) < q[tail] = x; tail++; color[x] = B; >int dequeue() < int x = q[head]; head++; color[x] = C; return x; >// Using BFS as a searching algorithm int bfs(int start, int target) < int u, v; for (u = 0; u < n; u++) < color[u] = A; >head = tail = 0; enqueue(start); pred[start] = -1; while (head != tail) < u = dequeue(); for (v = 0; v < n; v++) < if (color[v] == A && capacity[u][v] - flow[u][v] >0) < enqueue(v); pred[v] = u; >> > return color[target] == C; > // Applying fordfulkerson algorithm int fordFulkerson(int source, int sink) < int i, j, u; int max_flow = 0; for (i = 0; i < n; i++) < for (j = 0; j < n; j++) < flow[i][j] = 0; >> // Updating the residual values of edges while (bfs(source, sink)) < int increment = O; for (u = n - 1; pred[u] >= 0; u = pred[u]) < increment = min(increment, capacity[pred[u]][u] - flow[pred[u]][u]); >for (u = n - 1; pred[u] >= 0; u = pred[u]) < flow[pred[u]][u] += increment; flow[u][pred[u]] -= increment; >// Adding the path flows max_flow += increment; > return max_flow; > int main() < for (int i = 0; i < n; i++) < for (int j = 0; j < n; j++) < capacity[i][j] = 0; >> n = 6; e = 7; capacity[0][1] = 8; capacity[0][4] = 3; capacity[1][2] = 9; capacity[2][4] = 7; capacity[2][5] = 2; capacity[3][5] = 5; capacity[4][2] = 7; capacity[4][3] = 4; int s = 0, t = 5; printf("Max Flow: %d\n", fordFulkerson(s, t)); >

// Ford-Fulkerson algorith in C++ #include #include #include #include using namespace std; #define V 6 // Using BFS as a searching algorithm bool bfs(int rGraph[V][V], int s, int t, int parent[]) < bool visited[V]; memset(visited, 0, sizeof(visited)); queueq; q.push(s); visited[s] = true; parent[s] = -1; while (!q.empty()) < int u = q.front(); q.pop(); for (int v = 0; v < V; v++) < if (visited[v] == false && rGraph[u][v] >0) < q.push(v); parent[v] = u; visited[v] = true; >> > return (visited[t] == true); > // Applying fordfulkerson algorithm int fordFulkerson(int graph[V][V], int s, int t) < int u, v; int rGraph[V][V]; for (u = 0; u < V; u++) for (v = 0; v < V; v++) rGraph[u][v] = graph[u][v]; int parent[V]; int max_flow = 0; // Updating the residual values of edges while (bfs(rGraph, s, t, parent)) < int path_flow = INT_MAX; for (v = t; v != s; v = parent[v]) < u = parent[v]; path_flow = min(path_flow, rGraph[u][v]); >for (v = t; v != s; v = parent[v]) < u = parent[v]; rGraph[u][v] -= path_flow; rGraph[v][u] += path_flow; >// Adding the path flows max_flow += path_flow; > return max_flow; > int main() < int graph[V][V] = , , , , , >; cout

Ford-Fulkerson Applications

• Water distribution pipeline
• Bipartite matching problem
• Circulation with demands

Источник