@Test public void testPushRelabel() { System.out.println("Push-Relabel"); double[][] results = { { 0, 1, 3, 0, 0, 0}, {-1, 0, 1, 0, 0, 0}, {-3, -1, 0, 0, 4, 0}, { 0, 0, 0, 0, 0, 0}, { 0, 0, -4, 0, 0, 4}, { 0, 0, 0, 0, -4, 0} }; AdjacencyMatrix graph = new AdjacencyMatrix(6, true); graph.addEdge(0, 1, 2); graph.addEdge(0, 2, 9); graph.addEdge(1, 2, 1); graph.addEdge(1, 3, 0); graph.addEdge(1, 4, 0); graph.addEdge(2, 4, 7); graph.addEdge(3, 5, 7); graph.addEdge(4, 5, 4); double[][] flow = new double[6][6]; double maxFlow = graph.pushRelabel(flow, 0, 5); assertEquals(4.0, maxFlow, 1E-1); assertTrue(MathEx.equals(flow, results)); }
public double pushRelabel(double[][] flow, int source, int sink) { int[] seen = new int[n]; int[] queue = new int[n-2]; for (int i = 0, p = 0; i < n; i++) { if ((i != source) && (i != sink)) { queue[p++] = i; } } int[] height = new int[n]; height[source] = n; double[] excess = new double[n]; excess[source] = Double.MAX_VALUE; for (int i = 0; i < n; i++) { push(flow, excess, source, i); } int p = 0; while (p < n-2) { int u = queue[p]; double oldHeight = height[u]; discharge(flow, excess, height, seen, u); if (height[u] > oldHeight) { moveToFront(p, queue); p = 0; } else { p += 1; } } double maxflow = 0.0; for (int i = 0; i < n; i++) { maxflow += flow[source][i]; } return maxflow; }
AdjacencyMatrix implements Graph { public double pushRelabel(double[][] flow, int source, int sink) { int[] seen = new int[n]; int[] queue = new int[n-2]; for (int i = 0, p = 0; i < n; i++) { if ((i != source) && (i != sink)) { queue[p++] = i; } } int[] height = new int[n]; height[source] = n; double[] excess = new double[n]; excess[source] = Double.MAX_VALUE; for (int i = 0; i < n; i++) { push(flow, excess, source, i); } int p = 0; while (p < n-2) { int u = queue[p]; double oldHeight = height[u]; discharge(flow, excess, height, seen, u); if (height[u] > oldHeight) { moveToFront(p, queue); p = 0; } else { p += 1; } } double maxflow = 0.0; for (int i = 0; i < n; i++) { maxflow += flow[source][i]; } return maxflow; } }
AdjacencyMatrix implements Graph { public double pushRelabel(double[][] flow, int source, int sink) { int[] seen = new int[n]; int[] queue = new int[n-2]; for (int i = 0, p = 0; i < n; i++) { if ((i != source) && (i != sink)) { queue[p++] = i; } } int[] height = new int[n]; height[source] = n; double[] excess = new double[n]; excess[source] = Double.MAX_VALUE; for (int i = 0; i < n; i++) { push(flow, excess, source, i); } int p = 0; while (p < n-2) { int u = queue[p]; double oldHeight = height[u]; discharge(flow, excess, height, seen, u); if (height[u] > oldHeight) { moveToFront(p, queue); p = 0; } else { p += 1; } } double maxflow = 0.0; for (int i = 0; i < n; i++) { maxflow += flow[source][i]; } return maxflow; } AdjacencyMatrix(int n);  AdjacencyMatrix(int n, boolean digraph); }
AdjacencyMatrix implements Graph { public double pushRelabel(double[][] flow, int source, int sink) { int[] seen = new int[n]; int[] queue = new int[n-2]; for (int i = 0, p = 0; i < n; i++) { if ((i != source) && (i != sink)) { queue[p++] = i; } } int[] height = new int[n]; height[source] = n; double[] excess = new double[n]; excess[source] = Double.MAX_VALUE; for (int i = 0; i < n; i++) { push(flow, excess, source, i); } int p = 0; while (p < n-2) { int u = queue[p]; double oldHeight = height[u]; discharge(flow, excess, height, seen, u); if (height[u] > oldHeight) { moveToFront(p, queue); p = 0; } else { p += 1; } } double maxflow = 0.0; for (int i = 0; i < n; i++) { maxflow += flow[source][i]; } return maxflow; } AdjacencyMatrix(int n);  AdjacencyMatrix(int n, boolean digraph); @Override int getNumVertices(); @Override boolean hasEdge(int source, int target); @Override double getWeight(int source, int target); @Override AdjacencyMatrix setWeight(int source, int target, double weight); @Override Collection<Edge> getEdges(); @Override Collection<Edge> getEdges(int vertex); @Override Collection<Edge> getEdges(int source, int target); @Override Edge getEdge(int source, int target); @Override void addEdge(int source, int target); @Override void addEdge(int source, int target, double weight); @Override void removeEdges(Collection<Edge> edges); @Override void removeEdge(int source, int target); @Override void removeEdge(Edge edge); @Override int getDegree(int vertex); @Override int getIndegree(int vertex); @Override int getOutdegree(int vertex); @Override int[] sortdfs(); @Override int[][] dfs(); @Override void dfs(Visitor visitor); @Override int[] sortbfs(); @Override int[][] bfs(); @Override void bfs(Visitor visitor); @Override double[] dijkstra(int s); double[] dijkstra(int s, boolean weighted); @Override AdjacencyMatrix subgraph(int[] vertices); double[][] toArray(); double pushRelabel(double[][] flow, int source, int sink); @Override Matrix toMatrix(); }
AdjacencyMatrix implements Graph { public double pushRelabel(double[][] flow, int source, int sink) { int[] seen = new int[n]; int[] queue = new int[n-2]; for (int i = 0, p = 0; i < n; i++) { if ((i != source) && (i != sink)) { queue[p++] = i; } } int[] height = new int[n]; height[source] = n; double[] excess = new double[n]; excess[source] = Double.MAX_VALUE; for (int i = 0; i < n; i++) { push(flow, excess, source, i); } int p = 0; while (p < n-2) { int u = queue[p]; double oldHeight = height[u]; discharge(flow, excess, height, seen, u); if (height[u] > oldHeight) { moveToFront(p, queue); p = 0; } else { p += 1; } } double maxflow = 0.0; for (int i = 0; i < n; i++) { maxflow += flow[source][i]; } return maxflow; } AdjacencyMatrix(int n);  AdjacencyMatrix(int n, boolean digraph); @Override int getNumVertices(); @Override boolean hasEdge(int source, int target); @Override double getWeight(int source, int target); @Override AdjacencyMatrix setWeight(int source, int target, double weight); @Override Collection<Edge> getEdges(); @Override Collection<Edge> getEdges(int vertex); @Override Collection<Edge> getEdges(int source, int target); @Override Edge getEdge(int source, int target); @Override void addEdge(int source, int target); @Override void addEdge(int source, int target, double weight); @Override void removeEdges(Collection<Edge> edges); @Override void removeEdge(int source, int target); @Override void removeEdge(Edge edge); @Override int getDegree(int vertex); @Override int getIndegree(int vertex); @Override int getOutdegree(int vertex); @Override int[] sortdfs(); @Override int[][] dfs(); @Override void dfs(Visitor visitor); @Override int[] sortbfs(); @Override int[][] bfs(); @Override void bfs(Visitor visitor); @Override double[] dijkstra(int s); double[] dijkstra(int s, boolean weighted); @Override AdjacencyMatrix subgraph(int[] vertices); double[][] toArray(); double pushRelabel(double[][] flow, int source, int sink); @Override Matrix toMatrix();  }