プリフロープッシュ法
From Wikipedia, the free encyclopedia
プリフロープッシュ法（プリフロープッシュほう、プッシュ再ラベル法、英: preflow–push algorithm, push–relabel algorithm）とは、数理最適化においてフローネットワークにおける最大流を求めるアルゴリズムである。プッシュ・再ラベルの名はプッシュ操作と再ラベル操作の二つの手続きを行うことに由来する。実行を通じて、プリフロープッシュ法はプリフローを保持しながら、再ラベル操作により求まる可能ネットワークの下で近傍の頂点間にフローを流すプッシュ操作によって最大流を求める。同じ最大流問題に対するアルゴリズムのフォード・ファルカーソン法ではソースからシンクまでの路からフローを増やしていく大域的な増加路を求めるアルゴリズムである[1]。
プリフロープッシュ法は最大流問題に対して最も効率の良いアルゴリズムの一つとして知られている。汎用プリフロープッシュ法においては時間計算量が強多項式時間の O(V 2E) で動作することが知られており、計算量 O(VE 2) で動作するエドモンズ・カープ法よりも効率の良い解法とされている[2]。類似の解法の中にはより高速に動作するアルゴリズムも存在する。highest label node selection規則に従った方法では計算量が O(V 2√E) オーダーで動作することが最大流問題に対するベンチマーク問題の実験から求まっている[3][4]。動的木を使用したプリフロープッシュ法では時間計算量は O(VElog(V 2/E)) に達するが[2]、実用上の面では効率が悪くなる[要出典]。
またプリフロープッシュ法は最小費用流問題に対して拡張することができる[5]。距離ラベルの概念はより効率的に増加道を求めることができ、これとプリフロープッシュ法を組み合わせることでより高い性能を発揮するアルゴリズムを使用することができる[4][6]。
歴史
プリフローの概念は1974年にアレキサンダー・カルザノフによって Soviet Mathematical Dokladi 15 に掲載したことから始まる。プリフロー法は増加道の距離を求める際にラベリングシステムを使用せず、プッシュ操作により求めるアルゴリズムである[2][7]。
プリフロープッシュ法はアンドリュー・V・ゴールドバーグとロバート・タージャンによって提案されたアルゴリズムである。プリフロープッシュ法は1986年11月の STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computing において始めて公表され、1988年に ACM の学術論文誌に掲載された。両者の論文では計算量 O(V 2E) で終了する汎用解法、計算量 O(V 3) の段階的解法、計算量 O(VE log(V 2/E)) で動作する動的木を使用し、並列・分散実装化された解法が提案されている[2][8]。ゴールドバーグ＝タージャンはYossi Shiloach・Uzi Vishkinの並列最大流アルゴリズムにおける距離ラベルに上記の技法を適用した解法を公表した[9][10]。
実装例
#include <stdlib.h>
#include <stdio.h>
#define NODES 6
#define MIN(X,Y) ((X) < (Y) ? (X) : (Y))
#define INFINITE 10000000
void push(const int * const * C, int ** F, int *excess, int u, int v) {
int send = MIN(excess[u], C[u][v] - F[u][v]);
F[u][v] += send;
F[v][u] -= send;
excess[u] -= send;
excess[v] += send;
}
void relabel(const int * const * C, const int * const * F, int *height, int u) {
int v;
int min_height = INFINITE;
for (v = 0; v < NODES; v++) {
if (C[u][v] - F[u][v] > 0) {
min_height = MIN(min_height, height[v]);
height[u] = min_height + 1;
}
}
};
void discharge(const int * const * C, int ** F, int *excess, int *height, int *seen, int u) {
while (excess[u] > 0) {
if (seen[u] < NODES) {
int v = seen[u];
if ((C[u][v] - F[u][v] > 0) && (height[u] > height[v])) {
push(C, F, excess, u, v);
} else {
seen[u] += 1;
}
} else {
relabel(C, F, height, u);
seen[u] = 0;
}
}
}
void moveToFront(int i, int *A) {
int temp = A[i];
int n;
for (n = i; n > 0; n--) {
A[n] = A[n-1];
}
A[0] = temp;
}
int pushRelabel(const int * const * C, int ** F, int source, int sink) {
int *excess, *height, *list, *seen, i, p;
excess = (int *) calloc(NODES, sizeof(int));
height = (int *) calloc(NODES, sizeof(int));
seen = (int *) calloc(NODES, sizeof(int));
list = (int *) calloc((NODES-2), sizeof(int));
for (i = 0, p = 0; i < NODES; i++){
if ((i != source) && (i != sink)) {
list[p] = i;
p++;
}
}
height[source] = NODES;
excess[source] = INFINITE;
for (i = 0; i < NODES; i++)
push(C, F, excess, source, i);
p = 0;
while (p < NODES - 2) {
int u = list[p];
int old_height = height[u];
discharge(C, F, excess, height, seen, u);
if (height[u] > old_height) {
moveToFront(p, list);
p = 0;
} else {
p += 1;
}
}
int maxflow = 0;
for (i = 0; i < NODES; i++)
maxflow += F[source][i];
free(list);
free(seen);
free(height);
free(excess);
return maxflow;
}
void printMatrix(const int * const * M) {
int i, j;
for (i = 0; i < NODES; i++) {
for (j = 0; j < NODES; j++)
printf("%d\t",M[i][j]);
printf("\n");
}
}
int main(void) {
int **flow, **capacities, i;
flow = (int **) calloc(NODES, sizeof(int*));
capacities = (int **) calloc(NODES, sizeof(int*));
for (i = 0; i < NODES; i++) {
flow[i] = (int *) calloc(NODES, sizeof(int));
capacities[i] = (int *) calloc(NODES, sizeof(int));
}
// Sample graph
capacities[0][1] = 2;
capacities[0][2] = 9;
capacities[1][2] = 1;
capacities[1][3] = 0;
capacities[1][4] = 0;
capacities[2][4] = 7;
capacities[3][5] = 7;
capacities[4][5] = 4;
printf("Capacity:\n");
printMatrix(capacities);
printf("Max Flow:\n%d\n", pushRelabel(capacities, flow, 0, 5));
printf("Flows:\n");
printMatrix(flow);
return 0;
}
def relabel_to_front(C, source: int, sink: int) -> int:
n = len(C) # C is the capacity matrix
F = [[0] * n for _ in range(n)]
# residual capacity from u to v is C[u][v] - F[u][v]
height = [0] * n # height of node
excess = [0] * n # flow into node minus flow from node
seen = [0] * n # neighbours seen since last relabel
# node "queue"
nodelist = [i for i in range(n) if i != source and i != sink]
def push(u, v):
send = min(excess[u], C[u][v] - F[u][v])
F[u][v] += send
F[v][u] -= send
excess[u] -= send
excess[v] += send
def relabel(u):
# Find smallest new height making a push possible,
# if such a push is possible at all.
min_height = ∞
for v in range(n):
if C[u][v] - F[u][v] > 0:
min_height = min(min_height, height[v])
height[u] = min_height + 1
def discharge(u):
while excess[u] > 0:
if seen[u] < n: # check next neighbour
v = seen[u]
if C[u][v] - F[u][v] > 0 and height[u] > height[v]:
push(u, v)
else:
seen[u] += 1
else: # we have checked all neighbours. must relabel
relabel(u)
seen[u] = 0
height[source] = n # longest path from source to sink is less than n long
excess[source] = ∞ # send as much flow as possible to neighbours of source
for v in range(n):
push(source, v)
p = 0
while p < len(nodelist):
u = nodelist[p]
old_height = height[u]
discharge(u)
if height[u] > old_height:
nodelist.insert(0, nodelist.pop(p)) # move to front of list
p = 0 # start from front of list
else:
p += 1
return sum(F[source])