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