네트워크 유량 ( network flow) / 포드 - 풀커슨 알고리즘 JAVA

network flow는 실세계에서 적용이 가능한 유명한 알고리즘이다.

 

network flow를 이해하기 위해서는 먼저 몇가지 용어 정리가 필요하다.

 

A -> B 로가는 네트워크에 대해서 최대 x라는 트래픽으로 보낼 수 있다면 capactiy(a,b) = x 가된다.

 

즉 a->b로 보낼 수 있는 최대 용량은 x라는 뜻이다.

 

만약 a->b에서 실제 y라는 트래픽이 발생한다면 flow(a,b) = y 가된다. 즉 a->b로가는 유량은 y라고 한다.

 

여기서 몇가지 속성을 알아보자

1. 용량 제한 속성 flow(u,v) <= capcity(u,v)를 만족한다.
당연히 현재 흐르는 유량은 최대값이 용량을 넘을 수 없다.

2.유량의 대칭성 flow(u,v) = - flow(v,u)이다. u에 입장에서는 v로 x만큼 보낸다한다면 v에 입장에서는 u로 -x만큼 보낸다라고 할 수 있다. ( 이 개념이 상당히 중요하다.)

3.유량의 보존 특정한 u에서 나가는 유량의 합은 들어오는 유량의 합과같다. 이정당성은 2의 대칭성에서 알수 있다. 

마지막으로 network flow는 두개의 특수한 정점을 가진다. 바로 source 와 sink이다

 

source는 유량이 시작하는 지점 sink는 유량이 도착하는 지점. 이정점은 유량의 보전은 적용 되지않는다.

 

 

포드- 풀커슨 알고리즘(Ford-Fulkerson Algorithm) 을 알아보자.

 

포드 - 풀커슨은 유량을 보낼수 있는 경로를 찾아서 유량을 보내고 보낼 수 없을때 까지 반복하는 알고리즘이다.

1.모든 간선의 유량을 0으로 초기화한다. ( 시작할 때는 어떠한 유량도 없기 때문에)

2. c(u,v) - f(u,v) >0 을 만족하는 u v 간선을 경로라고 생각하고 BFS 너비우선 탐색으로 경로를 탐색한다.

3. 만약 경로가 없으면 알고리즘은 종료한다.

4. 만약 경로가 존재한다면 경로에서 가장작은 flow 증가경로를 찾는다 그값을 amount에 저장한다.

5. amount 값으로 실제 flow를 계산한다. 그리고 2번으로 돌아가서 알고리즘이 종료할때 까지 반복한다.

 

 

 

 

위의 5가지를 실행하는것이 포드 -풀커슨 알고리즘이다. 그림으로 한번 살펴보자.

실제 다음과 같은 Network가 잇다고 가정하고 간선들은 현재 용량을 나타낸다. 

실제로 bfs 너비 우선 탐색을 이용해요 증가 경로(플로우 네트워크를 갈수있는 경로) 가 존재하는 찾는다.

 

만약 이러한 경로를 찾았다면 가장 작은 amount를 계산하면 1이라는 것을 알수 있다.

그렇다면 실제로 계산한다면 networkFlow    유량 / 용량 이라고한다면 다음과 같이된다.

 

우린 여기서 중간의 원형 도형에서 위에서 아래로 flow가 1만큼 간다는 것을 확인 할수 있다.

그렇다는 의미는 유량의 대칭성으로 인해서 밑에서 위로 흐르는 flow는 -1이라는 것을 확인할 수있고

용량(밑,위) - flow(밑,위) = 0 - (-1) = 1 > 0 보다 크다는 것을 확인 할수 있고 실제는 없는 선이지만 있다고 생각한다면 그다음 경로를 결정할수 있다.

 

 

이런식으로 결정되고 최소의 amount를 결정하면 1이라는 것을 알수 있다.

 

이처럼  유량 / 용량 에서 용량 값이 0이지만 실제로 1만큼을 흘려보낼수 있다. 그렇게 되면 가운데 원의

유량은 서로 주고 받으므로 다음과 같이 바뀌게된다.

 

이로서 이 netwrokFlow의 최대 유량은 2라는것을 알수가 있다.

소스코드

 

package 개인공부;
 
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
 
public class 포드_풀커슨 {
    
    static final int INF = 987654321;
    static int V;
    // capacity[u][v] : u 에서 v 로 보낼 수 있는 용량
    // flow[u][v]  u에서 v로 흘러가는 유량 ( 반대방향일 경우 음수)
    
    int capacity[][] = new int[V][V], flow[][] = new int[V][V];
    // flow[][] 를 계싼하고 총 유량을 반환하다.
    
    // source 는 시작점 sink는 도착하는곳 이 두정점을 제외하고는 유량보존의 법칙이 적용된다.
    int networkFlow(int source, int sink) {
        
        //flow를 0으로 초기화 한다.
        for(int i=0;i<V;i++)
            Arrays.fill(flow[i], 0);
        
        //answer 값
        int totalFlow = 0;
        
        while(true) {
            // 너비 우선탐색으로 증가 경로를 찾는다.
            int[] parent = new int[V];
            Arrays.fill(parent, -1);
            Queue<Integer> q = new LinkedList<Integer>();
            
            //경로탐색의 끝지점 즉 시작지점.. source -> a -> b- > c -> ... -> sink 까지 간다면 
            // parent[sink] = ? , parent [c] = b , parent[b] = a , parent[a] = source  parent[source] = source 를 해서
            // 자기 자신이 나오는 경로까지 찾아간다면 source -> sink의 경로를 알 수 있다.
            parent[source] = source;
            q.add(source);
            
            // 이 while문 자체는 어떻게서든지 하나의 경로를 찾는 while 문이다.
            while(!q.isEmpty() && parent[sink] == -1) {
                int here = q.poll();
                for(int there = 0;there<V;++there) {
                    // 잔여 용량이 남아 있는 간선을 따라 탐색한다.
                    // 방문안한 곳에만 방문한다.
                    if(capacity[here][there] - flow[here][there] > 0
                            && parent[there] == -1) {
                        q.add(there);
                        parent[there] = here;
                    }
                        
                }
            }
            
            
            // 증가 경로가 없으면 종료한다.
            // q를 돌리면서 너비우선탐색을 돌렷는데 sink가 가리키는게 -1이라는것은 연결된 간선 자체가 존재하지 않는다는 것.
            if( parent[sink] == -1) break;
            
            
            // 증가 경로를 통해 유량을 얼마나 보낼지 결정한다.
            // 출발지점에서 시작하여 가장 작은 유량을 결정하는 구분.
            // 이렇게 돌고나면 amount에는 처음 구했던 하나의 증가경로에서 가장작은 유량을 결정함.
            
            int amount = INF;
            for(int p= sink;p != source; p= parent[p]) {
                // 유량을 보낼수 있는 경우에만 간선을 이었으니 가능함.
                amount = Math.min(capacity[parent[p]][p] - flow[parent[p]][p], amount);
            }
            
            // 증가 경로를 통해 유량을 보낸다
            for(int p = sink; p!= source; p= parent[p]) {
                flow[parent[p]][p] += amount;
                flow[p][parent[p]] -= amount;
            }
            
            totalFlow += amount;
        }
        return totalFlow;
    }
    
}