Package com.jgalgo.alg.flow

Class MaximumFlowAbstract

java.lang.Object

com.jgalgo.alg.connect.MinimumEdgeCutStAbstract

com.jgalgo.alg.flow.MaximumFlowAbstract

All Implemented Interfaces:

MinimumEdgeCutSt, MaximumFlow

Direct Known Subclasses:

MaximumFlowAbstractWithoutResidualNet, MaximumFlowAbstractWithResidualNet

public abstract class MaximumFlowAbstract
extends MinimumEdgeCutStAbstract
implements MaximumFlow

Abstract class for computing a maximum flow in a graph.

This abstract class also implements the MinimumEdgeCutSt interface, and thus can be used to compute the minimum edge cut of a graph.

The class implements the interface by solving the problem on the index graph and then maps the results back to the original graph. The implementation for index graphs is abstract and left to the subclasses.

Author:

Barak Ugav

Constructor Summary

Constructors

Constructor	Description
MaximumFlowAbstract()	Default constructor.

Method Summary

Modifier and Type	Method	Description
<V,E> Flow<V,E>	computeMaximumFlow(Graph<V,E> g, WeightFunction<E> capacity, Collection<V> sources, Collection<V> sinks)	Calculate the maximum flow in a network between a set of sources and a set of sinks.
<V,E> Flow<V,E>	computeMaximumFlow(Graph<V,E> g, WeightFunction<E> capacity, V source, V sink)	Calculate the maximum flow in a network between a source and a sink.

Methods inherited from class com.jgalgo.alg.connect.MinimumEdgeCutStAbstract

computeMinimumCut, computeMinimumCut

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

MaximumFlowAbstract

public MaximumFlowAbstract()

Default constructor.

Method Detail

computeMaximumFlow

public <V,E> Flow<V,E> computeMaximumFlow(Graph<V,E> g,
                                                      WeightFunction<E> capacity,
                                                      V source,
                                                      V sink)

Description copied from interface: MaximumFlow

Calculate the maximum flow in a network between a source and a sink.

Some algorithm might run faster for integer capacities, and WeightFunctionInt can be passed as capacity.

If g is an IntGraph, its better to pass a IWeightFunction as capacity to avoid boxing/unboxing. If g is an IntGraph, the returned object is IFlow.

Specified by:

computeMaximumFlow in interface MaximumFlow

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

capacity - a capacity edge weight function

source - a source vertex

sink - a sink vertex

Returns:

the flows computed for each edge

computeMaximumFlow

public <V,E> Flow<V,E> computeMaximumFlow(Graph<V,E> g,
                                                      WeightFunction<E> capacity,
                                                      Collection<V> sources,
                                                      Collection<V> sinks)

Description copied from interface: MaximumFlow

Calculate the maximum flow in a network between a set of sources and a set of sinks.

Some algorithm might run faster for integer capacities, and WeightFunctionInt can be passed as capacity.

If g is an IntGraph, its better to pass a IWeightFunction as capacity to avoid boxing/unboxing. If g is an IntGraph, the returned object is IFlow.

Specified by:

computeMaximumFlow in interface MaximumFlow

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

capacity - a capacity edge weight function

sources - a set of source vertices

sinks - a set of sink vertices

Returns:

the flows computed for each edge