/*
* (C) Copyright 2015-2017, by Alexey Kudinkin and Contributors.
*
* JGraphT : a free Java graph-theory library
*
* This program and the accompanying materials are dual-licensed under
* either
*
* (a) the terms of the GNU Lesser General Public License version 2.1
* as published by the Free Software Foundation, or (at your option) any
* later version.
*
* or (per the licensee's choosing)
*
* (b) the terms of the Eclipse Public License v1.0 as published by
* the Eclipse Foundation.
*/
package org.jgrapht.alg.flow;
import java.util.*;
import org.jgrapht.*;
import org.jgrapht.alg.util.*;
import org.jgrapht.alg.util.extension.*;
/**
*
* Push-relabel
* maximum flow algorithm designed by Andrew V. Goldberg and Robert Tarjan. Current
* implementation complexity upper-bound is O(V^3). For more details see: "A new approach to the
* maximum flow problem" by Andrew V. Goldberg and Robert Tarjan STOC '86: Proceedings of the
* eighteenth annual ACM symposium on Theory of computing
*
*
*
* This class can also computes minimum s-t cuts. Effectively, to compute a minimum s-t cut, the
* implementation first computes a minimum s-t flow, after which a BFS is run on the residual graph.
*
*
* Note: even though the algorithm accepts any kind of graph, currently only Simple directed and
* undirected graphs are supported (and tested!).
*
* @param the graph vertex type
* @param the graph edge type
*
* @author Alexey Kudinkin
*/
public class PushRelabelMFImpl
extends MaximumFlowAlgorithmBase
{
// Diagnostic
private static final boolean DIAGNOSTIC_ENABLED = false;
private final ExtensionFactory vertexExtensionsFactory;
private final ExtensionFactory edgeExtensionsFactory;
// Label pruning helpers
private Map labeling;
boolean flowBack;
private PushRelabelDiagnostic diagnostic;
/**
* Construct a new push-relabel algorithm.
*
* @param network the network
*/
public PushRelabelMFImpl(Graph network)
{
this(network, DEFAULT_EPSILON);
}
/**
* Construct a new push-relabel algorithm.
*
* @param network the network
* @param epsilon tolerance used when comparing floating-point values
*/
public PushRelabelMFImpl(Graph network, double epsilon)
{
super(network, epsilon);
this.vertexExtensionsFactory = () -> new VertexExtension();
this.edgeExtensionsFactory = () -> new AnnotatedFlowEdge();
if (DIAGNOSTIC_ENABLED) {
this.diagnostic = new PushRelabelDiagnostic();
}
}
/**
* Prepares all data structures to start a new invocation of the Maximum Flow or Minimum Cut
* algorithms
*
* @param source source
* @param sink sink
*/
void init(V source, V sink)
{
super.init(source, sink, vertexExtensionsFactory, edgeExtensionsFactory);
this.labeling = new HashMap<>();
this.flowBack = false;
}
/**
* Initialization
*
* @param source the source
* @param sink the sink
* @param active resulting queue with all active vertices
*/
public void initialize(
VertexExtension source, VertexExtension sink, Queue active)
{
source.label = network.vertexSet().size();
source.excess = Double.POSITIVE_INFINITY;
label(source, sink);
for (AnnotatedFlowEdge ex : source.getOutgoing()) {
pushFlowThrough(ex, ex.capacity);
if (ex.getTarget().prototype != sink.prototype) {
active.offer(ex. getTarget());
}
}
}
private void label(VertexExtension source, VertexExtension sink)
{
Set seen = new HashSet<>();
Queue q = new ArrayDeque<>();
q.offer(sink);
sink.label = 0;
seen.add(sink);
seen.add(source);
while (!q.isEmpty()) {
VertexExtension ux = q.poll();
for (AnnotatedFlowEdge ex : ux.getOutgoing()) {
VertexExtension vx = ex.getTarget();
if (!seen.contains(vx)) {
seen.add(vx);
vx.label = ux.label + 1;
q.add(vx);
}
}
}
// NOTA BENE:
// count label frequencies
//
// This is part of label-pruning mechanic which
// targets to diminish all 'useless' relabels during
// "flow-back" phase of the algorithm pushing excess
// flow back to the source
for (V v : network.vertexSet()) {
VertexExtension vx = getVertexExtension(v);
if (!labeling.containsKey(vx.label)) {
labeling.put(vx.label, 1);
} else {
labeling.put(vx.label, labeling.get(vx.label) + 1);
}
}
if (DIAGNOSTIC_ENABLED) {
System.out.println("INIT LABELING " + labeling);
}
}
@Override
public MaximumFlow getMaximumFlow(V source, V sink)
{
this.calculateMaximumFlow(source, sink);
maxFlow = composeFlow();
return new MaximumFlowImpl<>(maxFlowValue, maxFlow);
}
/**
* Sets current source to source, current sink to sink, then calculates
* maximum flow from source to sink. Note, that source and
* sink must be vertices of the
* network passed to the constructor, and they must be different.
*
* @param source source vertex
* @param sink sink vertex
* @return the value of the maximum flow
*/
public double calculateMaximumFlow(V source, V sink)
{
init(source, sink);
Queue active = new ArrayDeque<>();
initialize(getVertexExtension(source), getVertexExtension(sink), active);
while (!active.isEmpty()) {
VertexExtension ux = active.poll();
for (;;) {
for (AnnotatedFlowEdge ex : ux.getOutgoing()) {
if (isAdmissible(ex)) {
if ((ex.getTarget().prototype != sink)
&& (ex.getTarget().prototype != source))
{
active.offer(ex.getTarget());
}
// Check whether we're rip off the excess
if (discharge(ex)) {
break;
}
}
}
if (ux.hasExcess()) {
relabel(ux);
} else {
break;
}
// Check whether we still have any vertices with the label '1'
if (!flowBack && !labeling.containsKey(0) && !labeling.containsKey(1)) {
// This supposed to drastically improve performance cutting
// off the necessity to drive labels of all vertices up to
// value 'N' one-by-one not entailing eny effective
// discharge -- at this point there is no vertex with the
// label <= 1 in the network & therefore no
// 'discharging-path' to the _sink_ also signalling that
// we're in the flow-back stage of the algorithm
getVertexExtension(source).label = Collections.max(labeling.keySet()) + 1;
flowBack = true;
}
}
}
// Calculate the max flow that reaches the sink. There may be more efficient ways to do
// this.
for (E e : network.edgesOf(sink)) {
AnnotatedFlowEdge edge = edgeExtensionManager.getExtension(e);
maxFlowValue += (directed_graph ? edge.flow : edge.flow + edge.getInverse().flow);
}
if (DIAGNOSTIC_ENABLED) {
diagnostic.dump();
}
return maxFlowValue;
}
private void relabel(VertexExtension vx)
{
assert (vx.hasExcess());
int min = Integer.MAX_VALUE;
for (AnnotatedFlowEdge ex : vx.getOutgoing()) {
if (ex.hasCapacity()) {
VertexExtension ux = ex.getTarget();
if (min > ux.label) {
min = ux.label;
}
}
}
if (DIAGNOSTIC_ENABLED) {
diagnostic.incrementRelabels(vx.label, min + 1);
}
assert (labeling.get(vx.label) > 0);
updateLabeling(vx, min + 1);
// Sanity
if (min != Integer.MAX_VALUE) {
vx.label = min + 1;
}
}
private void updateLabeling(VertexExtension vx, int l)
{
if (labeling.get(vx.label) == 1) {
labeling.remove(vx.label);
} else {
labeling.put(vx.label, labeling.get(vx.label) - 1);
}
if (!labeling.containsKey(l)) {
labeling.put(l, 1);
} else {
labeling.put(l, labeling.get(l) + 1);
}
}
private boolean discharge(AnnotatedFlowEdge ex)
{
VertexExtension ux = ex.getSource();
if (DIAGNOSTIC_ENABLED) {
diagnostic.incrementDischarges(ex);
}
pushFlowThrough(ex, Math.min(ux.excess, ex.capacity - ex.flow));
return !ux.hasExcess();
}
/**
* Push flow through an edge.
*
* @param ex the edge
* @param f the amount of flow to push through
*/
protected void pushFlowThrough(AnnotatedFlowEdge ex, double f)
{
ex.getSource().excess -= f;
ex.getTarget().excess += f;
assert ((ex.getSource().excess >= 0.0) && (ex.getTarget().excess >= 0));
super.pushFlowThrough(ex, f);
}
private boolean isAdmissible(AnnotatedFlowEdge e)
{
return e.hasCapacity() && (e
. getSource().label == (e. getTarget().label + 1));
}
private VertexExtension getVertexExtension(V v)
{
return (VertexExtension) vertexExtensionManager.getExtension(v);
}
private class PushRelabelDiagnostic
{
// Discharges
Map, Integer> discharges = new HashMap<>();
long dischargesCounter = 0;
// Relabels
Map, Integer> relabels = new HashMap<>();
long relabelsCounter = 0;
private void incrementDischarges(AnnotatedFlowEdge ex)
{
Pair p = Pair.of(ex.getSource().prototype, ex.getTarget().prototype);
if (!discharges.containsKey(p)) {
discharges.put(p, 0);
}
discharges.put(p, discharges.get(p) + 1);
dischargesCounter++;
}
private void incrementRelabels(int from, int to)
{
Pair p = Pair.of(from, to);
if (!relabels.containsKey(p)) {
relabels.put(p, 0);
}
relabels.put(p, relabels.get(p) + 1);
relabelsCounter++;
}
void dump()
{
Map labels = new HashMap<>();
for (V v : network.vertexSet()) {
VertexExtension vx = getVertexExtension(v);
if (!labels.containsKey(vx.label)) {
labels.put(vx.label, 0);
}
labels.put(vx.label, labels.get(vx.label) + 1);
}
System.out.println("LABELS ");
System.out.println("------ ");
System.out.println(labels);
List, Integer>> relabelsSorted =
new ArrayList<>(relabels.entrySet());
Collections.sort(relabelsSorted, (o1, o2) -> -(o1.getValue() - o2.getValue()));
System.out.println("RELABELS ");
System.out.println("-------- ");
System.out.println(" Count: " + relabelsCounter);
System.out.println(" " + relabelsSorted);
List, Integer>> dischargesSorted =
new ArrayList<>(discharges.entrySet());
Collections
.sort(dischargesSorted, (one, other) -> -(one.getValue() - other.getValue()));
System.out.println("DISCHARGES ");
System.out.println("---------- ");
System.out.println(" Count: " + dischargesCounter);
System.out.println(" " + dischargesSorted);
}
}
/**
* Vertex extension for the push-relabel algorithm, which contains an additional label.
*/
public class VertexExtension
extends VertexExtensionBase
{
private int label;
private boolean hasExcess()
{
return excess > 0;
}
@Override
public String toString()
{
return prototype.toString() + String.format(" { LBL: %d } ", label);
}
}
}
// End PushRelabelMFImpl.java
Ads help maintain this website.