org.jgrapht.alg.interfaces

Interface MaximumFlowAlgorithm<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Known Implementing Classes:

DinicMFImpl, EdmondsKarpMFImpl, GusfieldEquivalentFlowTree, GusfieldGomoryHuCutTree, MaximumFlowAlgorithmBase, PushRelabelMFImpl

public interface MaximumFlowAlgorithm<V,E>

Allows to derive maximum-flow from the supplied flow network

Author:

Alexey Kudinkin, Joris Kinable

Nested Class Summary

Nested Classes

Modifier and Type	Interface and Description
static interface	MaximumFlowAlgorithm.MaximumFlow<E> A maximum flow
static class	MaximumFlowAlgorithm.MaximumFlowImpl<E> Default implementation of the maximum flow

Method Summary

Modifier and Type	Method and Description
default double	calculateMaximumFlow(V source, V sink) Sets current source to source, current sink to sink, then calculates maximum flow from source to sink.
default V	getFlowDirection(E e) Returns the direction of the flow on an edge $(u,v)$.
default Map<E,Double>	getFlowMap() Returns maximum flow, that was calculated during last calculateMaximumFlow call, or null, if there was no calculateMaximumFlow calls.
MaximumFlowAlgorithm.MaximumFlow<E>	getMaximumFlow(V source, V sink) Sets current source to source, current sink to sink, then calculates maximum flow from source to sink.
default double	getMaximumFlowValue() Returns maximum flow value, that was calculated during last calculateMaximumFlow call.

Method Detail

getMaximumFlow

MaximumFlowAlgorithm.MaximumFlow<E> getMaximumFlow(V source,
                                                   V 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.

Parameters:

source - source of the flow inside the network

sink - sink of the flow inside the network

Returns:

maximum flow

calculateMaximumFlow

default double calculateMaximumFlow(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.

Parameters:

source - source vertex

sink - sink vertex

Returns:

the value of the maximum flow

getMaximumFlowValue

default double getMaximumFlowValue()

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.

Returns:

maximum flow value

getFlowMap

default Map<E,Double> getFlowMap()

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.

Returns:

read-only mapping from edges to doubles - flow values

getFlowDirection

default V getFlowDirection(E e)

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.

Parameters:

e - edge

Returns:

the vertex where the flow leaves the edge