mascoptLib.algos.graph
Class STMinCut

java.lang.Object
  |
  +--mascoptLib.algos.graph.STMinCut

public class STMinCut

extends Object

Provides an algorithm to compute a s-t cut min in a graph. We consider the digraph associated to the graph given and we apply the algorithm of Edmonds Karps (which is implemented in the class MinCut). 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. Entries : A graph g and the two vertices to consider (s,t). Results : vertexSetCutMin() returns the set of vertices which give the minimal cut edgeSetCutMin() returns the set of edges which belong to the minimal cut minCutValue() returns the value of the minimal cut

Field Summary

String	CAPACITY The string used to search the capacity on edges.
double	INFINITY A constant for the "infinity" number.

Constructor Summary

STMinCut(mascoptLib.graphs.Graph g, mascoptLib.graphs.Vertex s, mascoptLib.graphs.Vertex t)
Build the algorithm on a graph.

Method Summary

mascoptLib.graphs.EdgeSet	edgeSetCutMin() Returns the edges of the min cut
double	minCutValue() Computes the value of the min cut.
mascoptLib.graphs.VertexSet	vertexSetCutMin() Returns the set for the min cut.

Methods inherited from class java.lang.Object

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

Field Detail

CAPACITY

public String CAPACITY

The string used to search the capacity on edges.

INFINITY

public double INFINITY

A constant for the "infinity" number.

Constructor Detail

STMinCut

public STMinCut(mascoptLib.graphs.Graph g,
                mascoptLib.graphs.Vertex s,
                mascoptLib.graphs.Vertex t)

Build the algorithm on a graph. s and t are the two vertices to consider for the cut.

Parameters:

g - the graph

s - the first vertex

t - the second vertex

Method Detail

vertexSetCutMin

public mascoptLib.graphs.VertexSet vertexSetCutMin()

Returns the set for the min cut.

Returns:

a vertex set

edgeSetCutMin

public mascoptLib.graphs.EdgeSet edgeSetCutMin()

Returns the edges of the min cut

Returns:

an edge set.

minCutValue

public double minCutValue()

Computes the value of the min cut.

Returns:

a double