PushRelabel.java

packagecom.jwetherell.algorithms.graph;

importjava.util.ArrayDeque;
importjava.util.ArrayList;
importjava.util.Collection;
importjava.util.List;
importjava.util.Map;
importjava.util.Queue;
importjava.util.TreeMap;

importcom.jwetherell.algorithms.data_structures.Graph;

/**
 * In mathematical optimization, the push–relabel algorithm (alternatively, preflow–push 
 * algorithm) is an algorithm for computing maximum flows. The name "push–relabel" comes 
 * from the two basic operations used in the algorithm. Throughout its execution, the 
 * algorithm maintains a "preflow" and gradually converts it into a maximum flow by moving 
 * flow locally between neighboring nodes using push operations under the guidance of an 
 * admissible network maintained by relabel operations.
 * <p>
 * @see <a href="https://en.wikipedia.org/wiki/Push%E2%80%93relabel_maximum_flow_algorithm">Push-Relabel Algorithm (Wikipedia)</a>
 * <br>
 * @author Miron Ficak <miron.ficak@gmail.com>
 * @author Justin Wetherell <phishman3579@gmail.com>
 */
publicclassPushRelabel {

privatefinalQueue<Vertex> queue = newArrayDeque<Vertex>();
privatefinalList<Vertex> vertices = newArrayList<Vertex>();

privateintrelabelCounter;
privateintn;
privateVertexsource;
privateVertexsink;

/**
 * Computes maximum flow in flow network, using push-relabel algorithm with O(V^3) complexity.
 *
 * @param edgesToCapacities represents edges of network with capacities
 * @param source source of network
 * @param sink sink of network
 * @param <T> parameter of graph on which network is based
 * @return the maximum flow
 */
publicstatic <TextendsComparable<T>> LonggetMaximumFlow(Map<Graph.Edge<T>, Long> edgesToCapacities, Graph.Vertex<T> source, Graph.Vertex<T> sink) {
if (edgesToCapacities == null)
thrownewIllegalArgumentException("Graph is NULL.");

finalMap<Graph.Vertex<T>, Vertex> vertexMap = newTreeMap<Graph.Vertex<T>, Vertex>();
for (Graph.Edge<T> edge : edgesToCapacities.keySet()) {
vertexMap.put(edge.getFromVertex(), newVertex());
vertexMap.put(edge.getToVertex(), newVertex());
 }

finalVertexs = newVertex(); // source
vertexMap.put(source, s);

finalVertext = newVertex(); // sink
vertexMap.put(sink, t);

finalPushRelabelpushRelabel = newPushRelabel(vertexMap.values(), s, t);
for (Map.Entry<Graph.Edge<T>, Long> edgeWithCapacity : edgesToCapacities.entrySet()) {
finalGraph.Edge<T> e = edgeWithCapacity.getKey();
addEdge(
vertexMap.get(e.getFromVertex()),
vertexMap.get(e.getToVertex()),
edgeWithCapacity.getValue()
 );
 }

returnpushRelabel.maxFlow();
 }

privatePushRelabel(Collection<Vertex> vertices, Vertexsource, Vertexsink) {
this.vertices.addAll(vertices);
this.source = source;
this.sink = sink;
this.n = vertices.size();
 }

privatestaticfinalvoidaddEdge(Vertexfrom, Vertexto, longcost) {
finalintplaceOfEdge = from.edges.indexOf(newEdge(from, to));
if (placeOfEdge == -1) {
finalEdgeedge = newEdge(from, to, cost);
finalEdgerevertedEdge = newEdge(to, from, 0);
edge.revertedEdge = revertedEdge;
revertedEdge.revertedEdge = edge;
from.edges.add(edge);
to.edges.add(revertedEdge);
 } else {
from.edges.get(placeOfEdge).cost += cost;
 }
 }

privatefinalvoidrecomputeHeight() {
finalQueue<Vertex> que = newArrayDeque<Vertex>();
for (Vertexvertex : vertices) {
vertex.visited = false;
vertex.height = 2 * n;
 }

sink.height = 0;
source.height = n;
source.visited = true;
sink.visited = true;
que.add(sink);
while (!que.isEmpty()) {
finalVertexact = que.poll();
for (Edgee : act.edges) {
if (!e.to.visited && e.revertedEdge.cost > e.revertedEdge.flow) {
e.to.height = act.height + 1;
que.add(e.to);
e.to.visited = true;
 }
 }
 }
que.add(source);
while (!que.isEmpty()) {
finalVertexact = que.poll();
for (Edgee : act.edges) {
if (!e.to.visited && e.revertedEdge.cost > e.revertedEdge.flow) {
e.to.height = act.height + 1;
que.add(e.to);
e.to.visited = true;
 }
 }
 }
 }

privatefinalvoidinit() {
for (Edgee : source.edges) {
e.flow = e.cost;
e.revertedEdge.flow = -e.flow;
e.to.excess += e.flow;
if (e.to != source && e.to != sink)
queue.add(e.to);
 }
recomputeHeight();
relabelCounter = 0;
 }

privatestaticfinalvoidrelabel(Vertexv) {
intminimum = 0;
for (Edgee : v.edges) {
if (e.flow < e.cost)
minimum = Math.min(minimum, e.to.height);
 }
v.height = minimum + 1;
 }

privatefinalvoidpush(Vertexu, Edgee) {
finallongdelta = (u.excess < e.cost - e.flow) ? u.excess : e.cost - e.flow;
e.flow += delta;
e.revertedEdge.flow -= delta;
u.excess -= delta;

if (e.to.excess == 0 && e.to != source && e.to != sink)
queue.add(e.to);

e.to.excess += delta;
 }

privatefinalvoiddischarge(Vertexu) {
while (u.excess > 0) {
if (u.currentEdge == u.edges.size()) {
relabel(u);
if ((++relabelCounter) == n) {
recomputeHeight();
for (Vertexvertex : vertices)
vertex.currentEdge = 0;
relabelCounter = 0;
 }
u.currentEdge = 0;
 } else {
Edgee = u.edges.get(u.currentEdge);
if (e.flow < e.cost && u.height == e.to.height + 1)
push(u, e);
else
u.currentEdge++;
 }
 }
 }

privatefinallongmaxFlow() {
init();
while (!queue.isEmpty())
discharge(queue.poll());
returnsink.excess;
 }

privatestaticfinalclassVertex {

privatefinalList<Edge> edges = newArrayList<Edge>();

privatebooleanvisited = false;
privateintheight;
privateintcurrentEdge;
privatelongexcess;

 }

privatefinalstaticclassEdge {

privatefinalVertexfrom;
privatefinalVertexto;
privatelongcost;

privatelongflow;
privateEdgerevertedEdge;

privateEdge(Vertexfrom, Vertexto, longcost) {
this.from = from;
this.to = to;
this.cost = cost;
 }

privateEdge(Vertexfrom, Vertexto) {
this.from = from;
this.to = to;
 }

/**
 * {@inheritDoc}
 */
@Override
publicbooleanequals(Objecto) {
if (this == o)
returntrue;

if (o == null || getClass() != o.getClass())
returnfalse;

finalEdgeedge = (Edge) o;
if (!from.equals(edge.from))
returnfalse;
returnto.equals(edge.to);

 }

/**
 * {@inheritDoc}
 */
@Override
publicinthashCode() {
intresult = from.hashCode();
result = 31 * result + to.hashCode();
returnresult;
 }
 }
}