mascoptLib.algos.digraph
Class MinCut

java.lang.Object
  |
  +--mascoptLib.algos.digraph.MinCut

public class MinCut

extends Object

Provides an algorithm to compute the maximum st-flow and so minimum st-cut of a simple directed graph The algorithm used to compute the s-t flow max is Edmonds-Karp algorithm. The name of the capacities is "capacity" but can be change (CAPACITY="name_given") It is necessary to define the value of the variable INFINITY (which equals 999999) if some capacity is greater than the default value. The void "run" compute the max flow and must always be done to obtain the results. Entries : a digraph, two vertices s and t. Results : vertexSetCutMin() returns the set of vertices which give the minimal cut arcSetCutMin() returns the set of arcs which belong to the minimal cut minCutValue() returns the value of the minimal cut

Field Summary

String	CAPACITY The constant to read the capacity on edges.
double	INFINITY The constant for infinity.

Constructor Summary

MinCut(mascoptLib.graphs.DiGraph g, mascoptLib.graphs.Vertex s, mascoptLib.graphs.Vertex t)
Constructor for the min cut.

Method Summary

mascoptLib.graphs.ArcSet	arcSetCutMin() Returns the set of arcs of the min cut.
HashMap	maxFlow() Returns the hashmap of the max flow.
double	minCutValue() Returns the value of the min cut.
void	run() Run the algorithm.
mascoptLib.graphs.VertexSet	vertexSetCutMin() Returns the set of vertices of the min cut.

Methods inherited from class java.lang.Object

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

Field Detail

INFINITY

public double INFINITY

The constant for infinity.

CAPACITY

public String CAPACITY

The constant to read the capacity on edges.

Constructor Detail

MinCut

public MinCut(mascoptLib.graphs.DiGraph g,
              mascoptLib.graphs.Vertex s,
              mascoptLib.graphs.Vertex t)

Constructor for the min cut.

Parameters:

g - the graph to consider

s - the first vertex

t - the second vertex

Method Detail

run

public void run()

Run the algorithm.

vertexSetCutMin

public mascoptLib.graphs.VertexSet vertexSetCutMin()

Returns the set of vertices of the min cut.

Returns:

a vertex set.

arcSetCutMin

public mascoptLib.graphs.ArcSet arcSetCutMin()

Returns the set of arcs of the min cut.

Returns:

an arc set.

minCutValue

public double minCutValue()

Returns the value of the min cut.

Returns:

a double

maxFlow

public HashMap maxFlow()

Returns the hashmap of the max flow.

Returns:

an hashmap.