최대 유량 (Maximum Flow)

참고:
- https://koosaga.com/18 전반적인 요약

알고리즘

다양한 알고리즘들이 존재하고, 실제로 사용되는 알고리즘들도 다양한 편이다.
목록과 요약은 위키를 참고
잘 알려져 있는 알고리즘들에 대해서만 간단히 언급해보자

Ford–Fulkerson 알고리즘

가장 처음 배우고 기본이 되는 알고리즘.
Augmenting path를 찾아서 그 패스에 플로우를 흘리는 것을 반복.
유량이 모두 정수이고, 전체의 최대 유량이 f일때, 시간복잡도는 $O(fE)$.
- 가장 큰 엣지 용량이 U라면 f=O(VU)이므로 시간복잡도를 $O(VEU)$로 쓸수도 있다
유량이 실수이면 복잡도도 늘어난다. 무리수인 경우에는 알고리즘이 종료하지 않고 계속 반복할 수도 있다.
Augmenting path를 찾는 방법에 대해서는 정해져있지 않다. 실제 구현은 거의 Edmonds–Karp로 하게 된다

Edmonds–Karp 알고리즘

Ford–Fulkerson에서 augmenting path를 찾을때 BFS를 이용해서 shortest path를 찾도록 한것.
탐색을 BFS로 구현하는 것은 구현 난이도상으로는 DFS와 거의 차이가 없지만, 이것만으로 알고리즘의 종료가 보장되고 $O(VE^2)$의 다항시간 시간복잡도를 얻을 수 있다.
Ford–Fulkerson 알고리즘 자체에서는 augmenting path를 찾는 방식을 따로 언급하지 않았기 때문에, 새로운 알고리즘이라기 보다는 Ford–Fulkerson 알고리즘의 구현방식중 한가지라고 생각할 수도 있고, 그래서 Edmonds–Karp를 그냥 Ford–Fulkerson이라고 부르기도 한다고 한다 (주변에서는 그렇게 부르는 경우를 본적은 없다)
Edmonds–Karp 알고리즘이라고 불리지만, 역사적으로는 Dinic이 Edmonds와 Karp보다 더 빨리 만들었고, Dinic은 이보다 더욱 효율적인 알고리즘도 만들었다.
일반적으로 PS에서 가장 흔히 쓰이는 알고리즘이다. 학교 수업시간에서도 여기까지만 배웠다

Dinic 알고리즘

자세한 설명은 아래 링크들을 참고
기본적으로는 Ford–Fulkerson계열의 알고리즘이다. augmenting path를 찾아서 그 패스에 플로우를 흘리는 것을 반복한다
- Dinic은 Ford–Fulkerson 알고리즘도 모르는 상태에서, 알고리즘 수업 과제를 하다가 이 알고리즘을 만들었다고 한다. Ford–Fulkerson 알고리즘이 나오고서 10년동안 그 알고리즘을 다항시간에 종료시키는 방법을 못찾고 있었는데, 디닉이 이것을 처음 증명했다고 한다. ㄷㄷ
BFS를 이용해서 level graph라는 것을 만들고, level graph 에서 augmenting path를 찾아서 플로우를 흘리는 방식. 보통 후자는 DFS로 구현되므로, 결국 BFS와 DFS를 모두 구현해야 하므로 구현량은 좀더 많다. 하지만 생각보다 그렇게 복잡하거나 길지는 않다.
시간복잡도는 $O(V^2E)$. Edmonds-Karp에 비해서는 확실히 빠르다.
예전까지는 PS에서는 Edmonds-Karp만 사용해도 문제를 푸는데 어려움이 없었지만, 언제부턴가 슬슬 Dinic을 써야만 풀리는 문제도 나오고 있다고 한다.
링크컷 트리를 이용하면 시간복잡도를 $O(VElogV)$까지 줄일 수 있지만, PS쪽에서는 상수값이 커져서 실제 수행시간에는 이득이 없다고 하는것 같다
유닛 캐퍼시티 네트워크 (모든 엣지의 용량이 일정한 경우) 에서는 시간복잡도 $O(min(V^{2/3}E, E\sqrt{E}))$가 성립한다
- 이때에는 Edmonds-Karp를 써도 O(fE)에서 f=O(E)인 경우로 볼수 있으므로, O(E^2)가 된다
유닛 네트워크 (s,t를 제외한 모든 노드가 incoming 또는 outcoming 엣지를 한개만 갖고 용량이 일정한 경우) 에서는 $O(E\sqrt{V})$의 시간복잡도가 성립한다.
- 이분매칭 문제를 유량문제로 변환해서 풀때 만들어지는 네트워크가 이 형태이다. 이렇게 이분매칭에 Dinic을 적용해서 $O(E\sqrt{V})$에 푸는 알고리즘이 Hopcroft-Karp 알고리즘이다.
Dinic with scaling 라고 불리우는 기법이 있다. $O(VElogU)$ 의 시간복잡도를 가진다고 한다. U는 엣지의 캐퍼시티중 최대값이다.
- scaling에 대해서는 https://koosaga.com/287을 참고. 링크에서는 push relabel의 휴리스틱으로 scaling을 설명했는데, 이 아이디어는 dinic에 적용해도 성립한다.
- Edmonds-Karp 에 scaling을 적용하면 $O(E^2logU)$ 에 동작한다
- Pyrival의 구현체가 Dinic with scaling을 사용해서 구현되어있다.
- 이 방식을 사용할경우 당연히 용량을 정수값으로만 주어야 한다. infinite를 넣으면 안된다!

Push-relabel 알고리즘

구체적인 알고리즘 설명은 다음을 참고
PS에서 현재 사용되는 알고리즘 중에서는 가장 빠르다. HLPP 휴리스틱을 적용했을때의 시간복잡도는 $O(V^2\sqrt{E})$ 이다
기존 알고리즘들과 달리 만든사람 이름보다는 알고리즘의 특징으로 흔히 불리운다. push-relabel 알고리즘 또는 preflow 알고리즘으로 불리는데, 그래도 Goldberg-Tarjan's preflow push-relabel algorithm 처럼 만든사람 이름까지 붙여주는 경우가 없지는 않다.
Ford–Fulkerson, Edmonds–Karp, Dinic 등의 augmenting path 기반 알고리즘과는 기본 접근방식 자체가 다르다.
- augmenting path 기반의 알고리즘들은 기본적으로 augmenting path 를 찾은 뒤에 그 패스로 유량을 추가하는 것을 반복하는 형태이다. 이 방식에서는 path 위에 유량을 흘리므로, 각 노드에 들어오는 유량과 나가는 유량이 항상 동일하게 유지된다. 하지만 Push-relabel은, 먼저 들어오는 유량이 나가는 유량보다 많을수 있는 preflow를 흘린 다음에, 이 초과유량을 인접 노드들로 배분하는 것을 반복하는 방식으로 이루어진다.
- cp-algorithm에 augmenting path 방식들과 preflow 방식의 차이를 좀더 쉽게 설명한 부분이 있다. 우리가 찾으려는 max flow는 valid flow (모든 노드마다 들어오는 유량과 나가는 유량이 같다)이면서 augmenting path가 없는 상태(더이상 추가로 흘릴수 있는 유량이 없다) 의 flow이다. augmenting path 방식은 처음부터 끝까지 valid flow 상태를 유지하면서 augmenting path가 없어질때까지 반복하는 방식이다. Push-relabel은 처음부터 끝까지 augmenting path가 없는 상태를 유지하면서 valid flow가 될때까지 반복하는 방법이다.
Ford–Fulkerson 에서 augmenting path를 찾는 방법에 따라서 시간복잡도가 많이 단축되었듯이, Push-relabel에서는 초과유량을 갖는 노드들중 어느것을 먼저 선택해서 처리하는지에 따라서 복잡도가 단축된다.
- 아무렇게나 선택하면 $ O(V^2E) $
- FIFO queue를 이용해서 선택하면 $ O(V^3) $
- FIFO 에 링컷트리를 같이 써서 $ O(VElog{{V^2}/E})$
- Relabel-to-front selection rule $ O(V^3) $
- greatest height를 갖는 노드를 먼저 선택하면 (Highest label selection rule, HLPP) $O(V^2\sqrt{E})$
실질적으로는 HLPP 가 대부분 가장 빠르다고 한다 (https://codeforces.com/blog/entry/66006)
일반적으로 쓰이는 라이브러리들에서도 HLPP방식의 push-relabel을 기본으로 쓴다
- cpp의 boost에는 HLPP가 구현되어 있다
  - There is a long history of algorithms for solving the maximum flow problem, with the first algorithm due to Ford and Fulkerson. The best general purpose algorithm to date is the push-relabel algorithm of Goldberg which is based on the notion of a preflow introduced by Karzanov.
    - https://www.boost.org/doc/libs/1_81_0/libs/graph/doc/graph_theory_review.html#sec:network-flow-algorithms
- Lemon에도 HLPP가 구현되어있다
  - https://lemon.cs.elte.hu/pub/doc/1.3.1/a00311.html#details
- google OR-tools 도 마찬가지로 HLPP를 쓴다
  - https://developers.google.com/optimization/reference/graph/max_flow
기본 구현 코드 자체는 생각보다 그렇게 길지 않다. 그러나 https://koosaga.com/289에서도 언급하고 있는데, push-relabel 알고리즘은 휴리스틱 사용에 따라 성능이 많이 차이나고, 휴리스틱부분을 구현하는 것이 복잡하다. 휴리스틱들을 포기하면 dinic등의 알고리즘에 비해 별 차이가 없는 경우도 흔한듯 하다. https://blog.naver.com/jinhan814/222861435654 에서는 기본 구현만 했다가는 V=1000 문제에서 TLE가 났다는 이야기도 있고, 나도 비슷한 경험을 했다.
- 휴리스틱을 포함하는 구현에 관련해서는 아래에 설명
알고리즘의 특성으로, max flow를 구하고 나면, min cut를 거의 바로 찾을수 있다.

기타 등등

그 외 알고리즘 중에 설명을 찾을 수 있는 것은 MPM 알고리즘이다. 제대로 보지는 않았지만 디닉과 유사한 방식이고 시간복잡도는 O(V^3)이라고 한다. (위키피디아에서는 MKM 알고리즘이라고 소개되어있는 알고리즘이 있는데, 동일한 알고리즘인것 같다)
- https://cp-algorithms.com/graph/mpm.html
boost에는 Boykov-Kolmogorov 알고리즘도 구현되어있다
이론상 끝판왕은 상당히 최근에 발표된 (2020년) 알고리즘인데, 딱히 정확한 이름이 없는것 같다.. 그냥 Almost linear time algorithm 이라고 부르는 경우도 있다. 시간복잡도는 말그대로 거의 선형이다 $O(|E|^{1+o(1)})$

구현 - Push-relabel algorithm

다른 알고리즘들에 비해서는 덜 알려진 알고리즘이고 그러다보니 설명이나 소스를 찾기도 쉽지는 않다. 특히 파이썬은 더욱..
휴리스틱이 없는 가장 기본적인 구현은 cp-algorithm이 깔끔하다 (cpp이지만..)
- https://cp-algorithms.com/graph/push-relabel.html 기본
- https://cp-algorithms.com/graph/push-relabel-faster.html HLPP
파이썬으로 쓰여진 기본 구현체는 https://www.geeksforgeeks.org/push-relabel-algorithm-set-2-implementation/ 에서 찾을수 있다.
- 코드에 오류가 있다. 다행히 어디가 잘못되어있는지를 찾는지는 어렵지 않다. 커멘트에도 나와있다
하지만 휴리스틱이 포함되지 않은 기본 구현은 실질적으로는 dinic 등에 비해 별 메리트가 없다, 빠른 속도를 원한다면 필수적으로 휴리스틱을 추가적으로 구현해줘야 한다.

휴리스틱

일반적으로 사용되는 휴리스틱은 Global Labeling과 Gap relabeling, freeze operation 정도이다.
- 위키피디아
- https://qiita.com/nariaki3551/items/65baee3c6ef0a6ffa136
Global Labeling은 sink에서부터 BFS를 통해서 한번에 모든 노드의 highest label을 다시 계산해주는 작업이다. 이것을 시작시점에 수행해주고, 이후로도 주기적으로 수행해주는것이 속도 향상에 도움이 된다고 한다.
- https://codeforces.com/blog/entry/66006?#comment-501187 에 의하면 relabel을 4n번할때마다 global labeling을 해주는 것이 좋다는 논문이 있다고 한다. 물론 경험적인 결과이므로 최적 주기는 문제에 따라 다르겠지만..
gap relabel은 알고리즘 수행중에, 해당하는 노드가 하나도 없는 n미만의 height(=gap)가 생기는지를 추적하고, gap이 존재할경우 gap이상의 height를 갖는 노드들을 전부 n으로 relabel해버리는 방식이다.
- gap이 생기면, 그 이상의 노드들에서는 어차피 sink로 도착할 수 없기 때문.
freeze operation 은 height가 n이상이 되는 노드들은 active 상태가 되지 않도록 (push/relabel 이 모두 안되도록) 처리하는 휴리스틱이다. 속도 향상에 효과가 있긴 한데, 각 엣지에 흐르는 유량들을 정확히 알수 없는 단점이 있다.
- 싱크쪽까지 흘러갈수 없는 excess flow는 굳이 끝까지 배분을 하지 않고, 그냥 그대로 두는 방식이다. 알고리즘을 끝까지 진행한다면 이 excess들은 소스쪽으로 돌아가게 된다. 하지만 이 작업을 안해도 싱크에 흘러가는 유량(=최대유량) 자체만을 계산하는데에는 문제가 없다.
- gap relabel과 같이 쓰면, gap 이상의 노드들은 이후에 activate가 안되게 된다.
이 설명대로 각각의 휴리스틱을 개별적으로 구현해서 추가하면 간단할것 같지만, 여러개의 휴리스틱들이 동시에 사용될경우 휴리스틱들간에 상호관계들이 생겨서 로직이 복잡해지는 부분들이 있다. 휴리스틱이 조합되면서 도달 불가능한 컨디션들이 새로이 생겨서 필요 없는 부분들을 제거할수 있게 되고, 이런것들을 고려하면 더 효율적인 구현이 가능해지는 부분들이 있다. 이런 부분들을 어떻게 구현하는게 효율적인지에 대해서는 잘 정리된 문서를 찾기 어렵고, 쓰여진 코드를 기반으로 분석하기에도 이해하기 복잡한 부분이 많다..
- 예를 들어 gap relabel을 하면 gap 이상의 노드들의 height를 모두 n으로 relabel한다. 그런데 freeze operation을 같이 쓰게 되면, height가 n이상인 노드들은 freeze시키게 되므로, gap relabel의 대상이 되는 노드들을 그냥 곧바로 frozen 으로 마킹해버려도 무방하다.
그래도 다른 구현체를 찾아서 참고하는 것으로부터 시작하는 것이 그나마 쉽다..

참고할 구현체

Koosaga - https://koosaga.com/289 에서 언급된 구현체. 원 저자는 teapotd라고 한다
- highest node를 linked list를 이용해서 관리한다
- 4n번의 relabel마다 global labeling을 수행한다
- 각 엣지별 유량을 구할수 있다.
  - freeze operation과 gap relabel은 사용하지 않았다.
  - 엣지 구조체에 전체 용량과 남은 용량이 함께 저장되어있다. 엣지에 흐르는 유량은 {전체용량} - {남은 용량} 으로 구할수 있다.
tjkendev - 파이썬으로 된 구현체. HLPP를 사용하고 Global Labeling과 Gap relabeling, freeze operation이 포함되어있다.
- highest node는 height별로 리스트에 저장해서 처리한다
- n번의 relabel마다 global labeling을 수행한다
- 각 엣지별 유량을 구하는 것은 포기한다
  - freeze operation과 gap relabel을 모두 적용
  - 엣지 구조체에 남은 용량만 저장한다.
- 갭 리레이블을 할때, 높이가 갭이상인 노드들을 모두 추적해서 한번에 리레이블해주는 것이 아니라, 레이지하게? 처리한다. 선택한 highest active node가 갭 이상이면 리레이블하고 다음 노드를 픽하는 방식으로.
  - 액티브하지 않은 노드들의 목록은 굳이 따로 저장할 필요가 없다. 갯수만 추적한다.
- 코드 이해가 쉽지는 않다. 한글자 변수도 많고 로직들이 보조함수들로 분리되어있지도 않고..
- 코드상의 다른 부분은 그래도 한참 들여다 보면 대충 그 뒤에 있는 논리가 이해가 되었는데, 이해가 안되는 부분은 푸쉬하는 부분이다. push-relabel 알고리즘에서 push할때 admissible 한 노드를 찾는것은 대상 노드가 높이가 1만큼만 낮아야 하는게 원칙인데, 여기에서는 높이가 낮은 노드들에는 모두 다 보내는 식으로 쓰여져있다. 코드는 잘 돌아가니 틀린것은 아니고 그래도 되는 이유가 있을텐데 잘 모르겠다;
- 사실 이 코드를 내 스타일로 다시 정리해보는 것으로부터 구현을 시작해보려 했으나, 명확하게 이해 안되는 부분들 때문에 포기하고, 아래의 boost 코드에서 출발하는 것으로 작전을 바꿨다.
Boost
- HLPP + global relabel + gap relabel + freeze operation
- gap relabel을 위해서, active node와 inactive node를 모두 관리한다.
- freeze를 하지만, excess flow를 source로 돌려보내는 second phase까지 모두 구현되어있어서, 엣지별로 흐르는 실제 플로우를 찾는것까지 가능하다.
- cpp로 구현된 코드지만, 보조함수들로 잘 나눠져있고 적절한 위치에 주석도 있어서 코드 이해가 가장 쉬웠다. 내 구현도 이것을 python으로 옮기는 것으로부터 시작했다.

활용

Max-flow Min-cut Theorem

참고
- Max-flow min-cut theorem
- https://m.blog.naver.com/kks227/220808685331
간단히 요약하면, 최소 컷의 용량은 최대 유량의 값과 동일하다는 정리이다
- 컷은 그래프에서 엣지들을 한개 이상 제거해서 두 개의 디스조인트한 노드 집합 V1, V2로 나누는 것이다. 이때 V1의 노드들과 V2의 노드들 사이에는 엣지가 없어야 한다. 여기에서의 컷은 s-t컷인데, s노드는 V1안에 속하고 t노드는 V2안에 속하도록 컷을 만드는 것이다. 이렇게 컷을 만들기 위해 제거한 엣지의 용량들의 합이 컷의 용량이 되고, 이 값을 최소화 하는 s-t 컷을 찾는 것이 minimum cut problem이 된다. Max-flow Min-cut Theorem은 이 minimum cut의 용량이 s에서 t로 향하는 최대유량과 동일하다는 뜻이고, 결국 minimum cut problem을 max flow 알고리즘으로 풀수 있다는 것을 의미한다
- 증명은 max flow 과 min cut이 lp duality 관계에 있다는 것을 이용해서 보일수 있다
이를 통해서 관련된 문제들을 풀수 있는데..
- 최소 컷의 용량만 구하면 되는 문제라면, 최대 유량 알고리즘을 돌려서 얻어낸 최대 유량값을 사용하면 된다
- s-t 최소 컷에서 실제로 각 노드들이 s쪽과 t쪽 중 어디에 속하는지를 찾는 문제
  - augment path 기반의 알고리즘을 사용할 경우에는, 엣지들마다 실제로 흐르는 flow값들을 이용해서 residual edge를 구분해야 한다. s에서 시작해서 residual edge로 연결된 노드들을 BFS나 DFS를 이용해서 모두 찾으면, 이 노드들이 s쪽 집합에 속한 노드들이 되고, 나머지는 t쪽에 속한 노드들이 된다.
  - push-relabel 의 경우는 좀더 간편하다. 알고리즘 동작 과정에서 구해진 노드들의 height값을 이용해서, height가 |V| 이상인 노드들은 s쪽, |V|미만인 노드들은 t쪽으로 구분할수 있다.
- s-t 최소 컷에서 삭제된 엣지들을 찾는 문제
  - 위의 방식으로 s쪽 노드들과 t쪽 노드들을 분류한 뒤에, 그 사이에 있는 엣지들을 모두 찾으면 된다.
관련 문제
- 13161: 최소컷의 용량 + 각 노드들이 어디에 속하는지를 구하는 문제

(임시) 문제 분류들

11377 열혈강호3 # 유닛 캐퍼시티 네트워크에 가까운 그래프, 이분매칭 변형으로도 풀수 있고 사실 그쪽이 제일 빠름 N,M,K ⇐ 1000

f = N+K U = K

Dinic : min(fE, V^2E) DinicW.S : VElogU PushRelabel: V^2sqrt(E)

UnitCapNetModeling V=N+M+K E=N*M+K*N

Dinic : Esqrt(E)

1014 컨닝 ⇒ 이분매칭

2316 도시 왕복하기

목차