/*
 * (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.interfaces;

import java.util.*;

/**
 * Allows to derive maximum-flow
 * from the supplied flow network
 *
 * @author Alexey Kudinkin
 * @author Joris Kinable
 *
 * @param  the graph vertex type
 * @param  the graph edge type
 *
 */
public interface MaximumFlowAlgorithm
{
    /**
     * Sets current source to source, current sink to sink, then calculates
     * maximum flow from source to sink. Returns an object containing detailed
     * information about the flow.
     *
     * @param source source of the flow inside the network
     * @param sink sink of the flow inside the network
     *
     * @return maximum flow
     * @deprecated use {@link #getMaximumFlow(Object, Object)} instead
     */
    @Deprecated
    default MaximumFlow buildMaximumFlow(V source, V sink)
    {
        return getMaximumFlow(source, sink);
    };

    /**
     * Sets current source to source, current sink to sink, then calculates
     * maximum flow from source to sink. Returns an object containing detailed
     * information about the flow.
     *
     * @param source source of the flow inside the network
     * @param sink sink of the flow inside the network
     *
     * @return maximum flow
     */
    MaximumFlow getMaximumFlow(V source, V sink);

    /**
     * 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
     */
    default double calculateMaximumFlow(V source, V sink)
    {
        return getMaximumFlow(source, sink).getValue();
    }

    /**
     * Returns maximum flow value, that was calculated during last 
     * calculateMaximumFlow call.
     *
     * NOTE: this function currently has a default implementation to guarantee backwards
     * compatibility. This function should be enforced in the next version.
     *
     * @return maximum flow value
     */
    default double getMaximumFlowValue()
    {
        throw new UnsupportedOperationException("Function not implemented");
    }

    /**
     * Returns maximum flow, that was calculated during last 
     * calculateMaximumFlow call, or null, if there was no 
     * calculateMaximumFlow calls.
     *
     * NOTE: this function currently has a default implementation to guarantee backwards
     * compatibility. This function should be enforced in the next version.
     *
     * @return read-only mapping from edges to doubles - flow values
     */
    default Map getFlowMap()
    {
        throw new UnsupportedOperationException("Function not implemented");
    }

    /**
     * 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.
     *
     * NOTE: this function currently has a default implementation to guarantee backwards
     * compatibility. This function should be enforced in the next version.
     *
     * @param e edge
     * @return the vertex where the flow leaves the edge
     */
    default V getFlowDirection(E e)
    {
        throw new UnsupportedOperationException("Function not implemented");
    }

    /**
     * A maximum flow
     *
     * @param  the graph edge type
     */
    interface MaximumFlow
    {
        /**
         * Returns value of the maximum-flow for the given network
         *
         * @return value of the maximum-flow
         */
        Double getValue();

        /**
         * Returns mapping from edge to flow value through this particular edge
         *
         * @return maximum flow
         */
        Map getFlow();
    }

    /**
     * Default implementation of the maximum flow
     *
     * @param  the graph edge type
     */
    class MaximumFlowImpl
        implements MaximumFlow
    {
        private Double value;
        private Map flow;

        /**
         * Create a new maximum flow
         * 
         * @param value the flow value
         * @param flow the flow map
         */
        public MaximumFlowImpl(Double value, Map flow)
        {
            this.value = value;
            this.flow = Collections.unmodifiableMap(flow);
        }

        @Override
        public Double getValue()
        {
            return value;
        }

        @Override
        public Map getFlow()
        {
            return flow;
        }

        @Override
        public String toString()
        {
            return "Flow Value: " + value + "\nFlow map:\n" + flow;
        }
    }
}

// End MaximumFlowAlgorithm.java

 

Ads help maintain this website.