} 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