mascoptLib.algos.graph
Class OddGomoryHu

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

public class OddGomoryHu

extends Object

Provides an algorithm to compute an odd minimum-cut set, using the Gomory-Hu algorithm. The label of the nodes is nammed label, but can be change (LABEL="name") The name of the capacities is "capacity" but can be change (CAPACITY="name") A node is odd if his label is 1 and even if his label is 0. The algorithm give a minimal cut which contains an odd number of odd nodes. So in the graph, there are an even number of odd nodes. IMPORTANT : you must do the initialization before asking the results (void init) Entries : A graph results : oddMinCut returns an array, the first element is the cut solution W (a vertex Set) the second element is V-T the third element is the value of the min cut

Field Summary

String	CAPACITY The string for capacity.
mascoptLib.graphs.EdgeSet	edgesMinCut The set of edges of the min cut.
String	LABEL The label on nodes.
double	min_cut_value The value of the min cut.

Constructor Summary

OddGomoryHu(mascoptLib.graphs.Graph g)
Constructor of oo gomory hu.

Method Summary

void	init() Initialize the algorithm.
mascoptLib.graphs.VertexSet[]	oddMinCut() Returns the solution in a table.

Methods inherited from class java.lang.Object

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

Field Detail

LABEL

public String LABEL

The label on nodes.

CAPACITY

public String CAPACITY

The string for capacity.

min_cut_value

public double min_cut_value

The value of the min cut.

edgesMinCut

public mascoptLib.graphs.EdgeSet edgesMinCut

The set of edges of the min cut.

Constructor Detail

OddGomoryHu

public OddGomoryHu(mascoptLib.graphs.Graph g)

Constructor of oo gomory hu.

Parameters:

g - the graph

Method Detail

init

public void init()

Initialize the algorithm. Run it befor using the class !

oddMinCut

public mascoptLib.graphs.VertexSet[] oddMinCut()

Returns the solution in a table. VertexSet[0] is the set of vertices of the solution. VertexSet[1] = All nodes / VertexSet[0]

Returns:

a table containing two vertex sets.