Module org.jgrapht.core

Package org.jgrapht.generate.netgen

Class MaximumFlowProblem.MaximumFlowProblemImpl<V,E>

java.lang.Object

org.jgrapht.generate.netgen.MaximumFlowProblem.MaximumFlowProblemImpl<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

MaximumFlowProblem<V,E>

Enclosing interface:

MaximumFlowProblem<V,E>

public static class MaximumFlowProblem.MaximumFlowProblemImpl<V,E>
extends java.lang.Object
implements MaximumFlowProblem<V,E>

Default implementation of a Maximum Flow Problem.

Nested Class Summary

Nested classes/interfaces inherited from interface org.jgrapht.generate.netgen.MaximumFlowProblem

MaximumFlowProblem.MaximumFlowProblemImpl<V,E>

Field Summary

Fields

Modifier and Type	Field	Description
private java.util.function.Function<E,java.lang.Double>	capacities
private Graph<V,E>	graph
private java.util.Set<V>	sinks
private java.util.Set<V>	sources

Fields inherited from interface org.jgrapht.generate.netgen.MaximumFlowProblem

CAPACITY_INF

Constructor Summary

Constructors

Constructor	Description
MaximumFlowProblemImpl(Graph<V,E> graph, java.util.Set<V> sources, java.util.Set<V> sinks, java.util.function.Function<E,java.lang.Double> capacities)	Constructs a new maximum flow problem.

Method Summary

Modifier and Type	Method	Description
private java.util.Set<V>	convert(java.util.Set<V> vertices, java.util.Set<E> newEdges, boolean sources)	Adds a new super vertex and connects it to all vertices in vertices.
java.util.function.Function<E,java.lang.Double>	getCapacities()	Returns the capacity function of this problem.
Graph<V,E>	getGraph()	Returns the network the problem is defined on.
java.util.Set<V>	getSinks()	Returns the sink set of this problem.
java.util.Set<V>	getSources()	Returns the source set of this problem.
MaximumFlowProblem<V,E>	toSingleSourceSingleSinkProblem()	Converts this problem to the canonical form.

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.jgrapht.generate.netgen.MaximumFlowProblem

dumpCapacities, getSink, getSource, isSingleSourceSingleSinkProblem

Field Detail

graph

private final Graph<V,E> graph

sources

private final java.util.Set<V> sources

sinks

private final java.util.Set<V> sinks

capacities

private final java.util.function.Function<E,java.lang.Double> capacities

Constructor Detail

MaximumFlowProblemImpl

public MaximumFlowProblemImpl(Graph<V,E> graph,
                              java.util.Set<V> sources,
                              java.util.Set<V> sinks,
                              java.util.function.Function<E,java.lang.Double> capacities)

Constructs a new maximum flow problem.

Parameters:

graph - flow network

sources - set of network sources

sinks - set of network sinks

capacities - network capacity function

Method Detail

getGraph

public Graph<V,E> getGraph()

Returns the network the problem is defined on.

Specified by:

getGraph in interface MaximumFlowProblem<V,E>

Returns:

the network the problem is defined on.

getSources

public java.util.Set<V> getSources()

Returns the source set of this problem.

Specified by:

getSources in interface MaximumFlowProblem<V,E>

Returns:

the source set of this problem.

getSinks

public java.util.Set<V> getSinks()

Returns the sink set of this problem.

Specified by:

getSinks in interface MaximumFlowProblem<V,E>

Returns:

the sink set of this problem.

getCapacities

public java.util.function.Function<E,java.lang.Double> getCapacities()

Returns the capacity function of this problem. This function is defined for all edges of the underlying network.

Specified by:

getCapacities in interface MaximumFlowProblem<V,E>

Returns:

the capacity function of this problem.

toSingleSourceSingleSinkProblem

public MaximumFlowProblem<V,E> toSingleSourceSingleSinkProblem()

Converts this problem to the canonical form. Resulting problem is equivalent to the previous one.

Specified by:

toSingleSourceSingleSinkProblem in interface MaximumFlowProblem<V,E>

Returns:

a problem in the canonical form.

convert

private java.util.Set<V> convert(java.util.Set<V> vertices,
                                 java.util.Set<E> newEdges,
                                 boolean sources)

Adds a new super vertex and connects it to all vertices in vertices. Depending on the value of sources, the edges are directed from super vertex or to super vertex. New edges are added to newEdges.

Parameters:

vertices - set of vertices to connect super vertex to

newEdges - container to add new edges to

sources - true if super vertex is super source, false if it's super sink

Returns:

1 element set containing the super vertex