Computes the maximum flow from source to sink using Dinic's algorithm. @param capacity square capacity matrix (n x n); entries must be >= 0 @param source source vertex index in [0, n) @param sink sink vertex index in [0, n) @return the maximum flow value @throws IllegalArgumentException if the inpu
(int[][] capacity, int source, int sink)
| 35 | * indices invalid |
| 36 | */ |
| 37 | public static int maxFlow(int[][] capacity, int source, int sink) { |
| 38 | if (capacity == null || capacity.length == 0) { |
| 39 | throw new IllegalArgumentException("Capacity matrix must not be null or empty"); |
| 40 | } |
| 41 | final int n = capacity.length; |
| 42 | for (int i = 0; i < n; i++) { |
| 43 | if (capacity[i] == null || capacity[i].length != n) { |
| 44 | throw new IllegalArgumentException("Capacity matrix must be square"); |
| 45 | } |
| 46 | for (int j = 0; j < n; j++) { |
| 47 | if (capacity[i][j] < 0) { |
| 48 | throw new IllegalArgumentException("Capacities must be non-negative"); |
| 49 | } |
| 50 | } |
| 51 | } |
| 52 | if (source < 0 || sink < 0 || source >= n || sink >= n) { |
| 53 | throw new IllegalArgumentException("Source and sink must be valid vertex indices"); |
| 54 | } |
| 55 | if (source == sink) { |
| 56 | return 0; |
| 57 | } |
| 58 | |
| 59 | // residual capacities |
| 60 | int[][] residual = new int[n][n]; |
| 61 | for (int i = 0; i < n; i++) { |
| 62 | residual[i] = Arrays.copyOf(capacity[i], n); |
| 63 | } |
| 64 | |
| 65 | int[] level = new int[n]; |
| 66 | int flow = 0; |
| 67 | while (bfsBuildLevelGraph(residual, source, sink, level)) { |
| 68 | int[] next = new int[n]; // current-edge optimization |
| 69 | int pushed; |
| 70 | do { |
| 71 | pushed = dfsBlocking(residual, level, next, source, sink, Integer.MAX_VALUE); |
| 72 | flow += pushed; |
| 73 | } while (pushed > 0); |
| 74 | } |
| 75 | return flow; |
| 76 | } |
| 77 | |
| 78 | private static boolean bfsBuildLevelGraph(int[][] residual, int source, int sink, int[] level) { |
| 79 | Arrays.fill(level, -1); |