/*
 * (C) Copyright 2015-2017, by Alexey Kudinkin, Joris Kinable 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 java.util.stream.*;

import org.jgrapht.*;
import org.jgrapht.alg.interfaces.*;
import org.jgrapht.alg.util.*;
import org.jgrapht.alg.util.extension.*;

/**
 * Base class backing algorithms allowing to derive
 * maximum-flow from the supplied
 * flow network
 *
 * @param  the graph vertex type
 * @param  the graph edge type
 *
 * @author Alexey Kudinkin
 * @author Joris Kinable
 */
public abstract class MaximumFlowAlgorithmBase
    implements MaximumFlowAlgorithm, MinimumSTCutAlgorithm
{
    /**
     * Default tolerance.
     */
    public static final double DEFAULT_EPSILON = 1e-9;

    /* input network */
    protected Graph network;
    /* indicates whether the input graph is directed or not */
    protected final boolean directed_graph;
    /* Used to compare floating point values */
    protected Comparator comparator;

    protected ExtensionManager vertexExtensionManager;
    protected ExtensionManager edgeExtensionManager;

    /* Source used during the last invocation of this algorithm */
    protected V source = null;
    /* Sink used during the last invocation of this algorithm */
    protected V sink = null;
    /* Max flow established after last invocation of the algorithm. */
    protected double maxFlowValue = -1;
    /* Mapping of the flow on each edge. */
    protected Map maxFlow = null;
    /* Source parition of S-T cut */
    protected Set sourcePartition;
    /* Sink parition of S-T cut */
    protected Set sinkPartition;
    /* Cut edges */
    protected Set cutEdges;

    /**
     * Construct a new maximum flow
     * 
     * @param network the network
     * @param epsilon the tolerance for the comparison of floating point values
     */
    public MaximumFlowAlgorithmBase(Graph network, double epsilon)
    {
        this.network = network;
        this.directed_graph = network instanceof DirectedGraph;
        this.comparator = new ToleranceDoubleComparator(epsilon);
    }

    /**
     * Prepares all data structures to start a new invocation of the Maximum Flow or Minimum Cut
     * algorithms
     * 
     * @param source source
     * @param sink sink
     * @param vertexExtensionFactory vertex extension factory
     * @param edgeExtensionFactory edge extension factory
     * @param  vertex extension type
     */
    protected  void init(
        V source, V sink, ExtensionFactory vertexExtensionFactory,
        ExtensionFactory edgeExtensionFactory)
    {
        vertexExtensionManager = new ExtensionManager<>(vertexExtensionFactory);
        edgeExtensionManager = new ExtensionManager<>(edgeExtensionFactory);

        buildInternal();
        this.source = source;
        this.sink = sink;
        maxFlowValue = 0;
        maxFlow = null;
        sourcePartition = null;
        sinkPartition = null;
        cutEdges = null;
    }

    /**
     * Create internal data structure
     */
    private void buildInternal()
    {
        if (directed_graph) { // Directed graph
            DirectedGraph directedGraph = (DirectedGraph) network;
            for (V v : directedGraph.vertexSet()) {
                VertexExtensionBase vx = vertexExtensionManager.getExtension(v);
                vx.prototype = v;
            }
            for (V u : directedGraph.vertexSet()) {
                VertexExtensionBase ux = vertexExtensionManager.getExtension(u);

                for (E e : directedGraph.outgoingEdgesOf(u)) {
                    V v = directedGraph.getEdgeTarget(e);
                    VertexExtensionBase vx = vertexExtensionManager.getExtension(v);

                    AnnotatedFlowEdge forwardEdge =
                        createEdge(ux, vx, e, directedGraph.getEdgeWeight(e));
                    AnnotatedFlowEdge backwardEdge = createBackwardEdge(forwardEdge);

                    ux.getOutgoing().add(forwardEdge);

                    if (backwardEdge.prototype == null) {
                        vx.getOutgoing().add(backwardEdge);
                    }
                }
            }
        } else { // Undirected graph
            for (V v : network.vertexSet()) {
                VertexExtensionBase vx = vertexExtensionManager.getExtension(v);
                vx.prototype = v;
            }
            for (E e : network.edgeSet()) {
                VertexExtensionBase ux =
                    vertexExtensionManager.getExtension(network.getEdgeSource(e));
                VertexExtensionBase vx =
                    vertexExtensionManager.getExtension(network.getEdgeTarget(e));
                AnnotatedFlowEdge forwardEdge = createEdge(ux, vx, e, network.getEdgeWeight(e));
                AnnotatedFlowEdge backwardEdge = createBackwardEdge(forwardEdge);
                ux.getOutgoing().add(forwardEdge);
                vx.getOutgoing().add(backwardEdge);
            }
        }
    }

    private AnnotatedFlowEdge createEdge(
        VertexExtensionBase source, VertexExtensionBase target, E e, double weight)
    {
        AnnotatedFlowEdge ex = edgeExtensionManager.getExtension(e);
        ex.source = source;
        ex.target = target;
        ex.capacity = weight;
        ex.prototype = e;

        return ex;
    }

    private AnnotatedFlowEdge createBackwardEdge(AnnotatedFlowEdge forwardEdge)
    {
        AnnotatedFlowEdge backwardEdge;
        E backwardPrototype =
            network.getEdge(forwardEdge.target.prototype, forwardEdge.source.prototype);

        if (directed_graph && backwardPrototype != null) { // if edge exists in directed input graph
            backwardEdge = createEdge(
                forwardEdge.target, forwardEdge.source, backwardPrototype,
                network.getEdgeWeight(backwardPrototype));
        } else {
            backwardEdge = edgeExtensionManager.createExtension();
            backwardEdge.source = forwardEdge.target;
            backwardEdge.target = forwardEdge.source;
            if (!directed_graph) { // Undirected graph: if (u,v) exists, then so much (v,u)
                backwardEdge.capacity = network.getEdgeWeight(backwardPrototype);
                backwardEdge.prototype = backwardPrototype;
            }
        }

        forwardEdge.inverse = backwardEdge;
        backwardEdge.inverse = forwardEdge;

        return backwardEdge;
    }

    /**
     * Increase flow in the direction denoted by edge (u,v). Any existing flow in the reverse
     * direction (v,u) gets reduced first. More precisely, let f2 be the existing flow in the
     * direction (v,u), and f1 be the desired increase of flow in direction (u,v). If
     * {@literal f1 >= f2}, then the flow on (v,u) becomes 0, and the flow on (u,v) becomes f1-f2.
     * Else, if {@literal f1= f2
            double flowDifference = flow - inverseEdge.flow;

            edge.flow += flowDifference;
            edge.capacity -= inverseEdge.flow; // Capacity on edge (u,v) PLUS flow on (v,u) gives
                                               // the MAXIMUM flow in the direction (u,v) i.e
                                               // edge.weight in the graph 'network'.

            inverseEdge.flow = 0;
            inverseEdge.capacity += flowDifference;
        } else { // If f1 < f2
            edge.capacity -= flow;
            inverseEdge.flow -= flow;
        }
    }

    /**
     * Create a map which specifies for each edge in the input map the amount of flow that flows
     * through it
     * 
     * @return a map which specifies for each edge in the input map the amount of flow that flows
     *         through it
     */
    protected Map composeFlow()
    {
        Map maxFlow = new HashMap<>();

        for (E e : network.edgeSet()) {
            AnnotatedFlowEdge annotatedFlowEdge = edgeExtensionManager.getExtension(e);
            maxFlow.put(
                e, directed_graph ? annotatedFlowEdge.flow
                    : Math.max(annotatedFlowEdge.flow, annotatedFlowEdge.inverse.flow));
        }

        return maxFlow;
    }

    class VertexExtensionBase
        implements Extension
    {
        private final List outgoing = new ArrayList<>();

        V prototype;

        double excess;

        public List getOutgoing()
        {
            return outgoing;
        }
    }

    class AnnotatedFlowEdge
        implements Extension
    {
        /* Edge source */
        private VertexExtensionBase source;
        /* Edge target */
        private VertexExtensionBase target;
        /* Inverse edge */
        private AnnotatedFlowEdge inverse;

        E prototype; // Edge
        double capacity; // Maximum by which the flow in the direction can be increased (on top of
                         // the flow already in this direction).
        double flow; // Flow in the direction denoted by this edge

        public  VE getSource()
        {
            return (VE) source;
        }

        public void setSource(VertexExtensionBase source)
        {
            this.source = source;
        }

        public  VE getTarget()
        {
            return (VE) target;
        }

        public void setTarget(VertexExtensionBase target)
        {
            this.target = target;
        }

        public AnnotatedFlowEdge getInverse()
        {
            return inverse;
        }

        public boolean hasCapacity()
        {
            return comparator.compare(capacity, flow) > 0;
        }

        @Override
        public String toString()
        {
            return "(" + (source == null ? null : source.prototype) + ","
                + (target == null ? null : target.prototype) + ",c:" + capacity + " f: " + flow
                + ")";
        }
    }

    /**
     * Returns current source vertex, or null if there was no 
     * calculateMaximumFlow calls.
     *
     * @return current source
     */
    public V getCurrentSource()
    {
        return source;
    }

    /**
     * Returns current sink vertex, or null if there was no 
     * calculateMaximumFlow calls.
     *
     * @return current sink
     */
    public V getCurrentSink()
    {
        return sink;
    }

    /**
     * Returns maximum flow value, that was calculated during last 
     * calculateMaximumFlow call.
     *
     * @return maximum flow value
     */
    public double getMaximumFlowValue()
    {
        return maxFlowValue;
    }

    /**
     * Returns maximum flow, that was calculated during last 
     * calculateMaximumFlow call, or null, if there was no 
     * calculateMaximumFlow calls.
     *
     * @return read-only mapping from edges to doubles - flow values
     */
    public Map getFlowMap()
    {
        if (maxFlow == null) // Lazily calculate the max flow map
            maxFlow = composeFlow();
        return maxFlow;
    }

    /**
     * Returns the direction of the flow on an edge (u,v). In case (u,v) is a directed edge (arc),
     * this function will always return the edge target v. However, if (u,v) is an edge in an
     * undirected graph, flow may go through the edge in either side. If the flow goes from u to v,
     * we return v, otherwise u. If the flow on an edge equals 0, the returned value has no meaning.
     * 
     * @param e edge
     * @return the vertex where the flow leaves the edge
     */
    public V getFlowDirection(E e)
    {
        if (!network.containsEdge(e))
            throw new IllegalArgumentException(
                "Cannot query the flow on an edge which does not exist in the input graph!");
        AnnotatedFlowEdge annotatedFlowEdge = edgeExtensionManager.getExtension(e);

        if (directed_graph)
            return annotatedFlowEdge.getTarget().prototype;

        AnnotatedFlowEdge inverseEdge = annotatedFlowEdge.getInverse();
        if (annotatedFlowEdge.flow > inverseEdge.flow)
            return annotatedFlowEdge.getTarget().prototype;
        else
            return inverseEdge.getTarget().prototype;
    }

    /*---------------- Minimum s-t cut related methods -------------------*/

    @Override
    public double calculateMinCut(V source, V sink)
    {
        return this.calculateMaximumFlow(source, sink);
    }

    @Override
    public double getCutCapacity()
    {
        return getMaximumFlowValue();
    }

    @Override
    public Set getSourcePartition()
    {
        if (sourcePartition == null)
            calculateSourcePartition();
        return sourcePartition;
    }

    @Override
    public Set getSinkPartition()
    {
        if (sinkPartition == null) {
            sinkPartition = new LinkedHashSet<>(network.vertexSet());
            sinkPartition.removeAll(this.getSourcePartition());
        }
        return sinkPartition;
    }

    @Override
    public Set getCutEdges()
    {
        if (cutEdges != null)
            return cutEdges;
        cutEdges = new LinkedHashSet<>();

        Set p1 = getSourcePartition();
        if (directed_graph) {
            DirectedGraph directedGraph = (DirectedGraph) network;
            for (V vertex : p1) {
                cutEdges.addAll(
                    directedGraph
                        .outgoingEdgesOf(vertex).stream()
                        .filter(edge -> !p1.contains(network.getEdgeTarget(edge)))
                        .collect(Collectors.toList()));
            }
        } else {
            cutEdges.addAll(
                network
                    .edgeSet().stream()
                    .filter(
                        e -> p1.contains(network.getEdgeSource(e))
                            ^ p1.contains(network.getEdgeTarget(e)))
                    .collect(Collectors.toList()));
        }
        return cutEdges;
    }

    /**
     * Calculate the set of reachable vertices from s in the residual graph.
     */
    protected void calculateSourcePartition()
    {
        // the source partition contains all vertices reachable from s in the residual graph
        this.sourcePartition = new LinkedHashSet<>();
        Queue processQueue = new LinkedList<>();
        processQueue.add(vertexExtensionManager.getExtension(getCurrentSource()));
        while (!processQueue.isEmpty()) {
            VertexExtensionBase vx = processQueue.poll();
            if (sourcePartition.contains(vx.prototype))
                continue;
            sourcePartition.add(vx.prototype);
            for (AnnotatedFlowEdge ex : vx.getOutgoing()) {
                if (ex.hasCapacity())
                    processQueue.add(ex.getTarget());
            }
        }
    }
}

// End MaximumFlowAlgorithmBase.java

 

Ads help maintain this website.