fr.inria.opengve.bridge.algorithms.undirected.minCut
Class NagamochiMinCut<V,E extends Edge<V>,G extends Graph<V,E>>

java.lang.Object
  java.util.Observable
      fr.inria.opengve.bridge.algorithms.StepAlgo<V,E>
          fr.inria.opengve.bridge.algorithms.undirected.minCut.NagamochiMinCut<V,E,G>

Type Parameters:

V - The type of vertices

E - The type of links

All Implemented Interfaces:

java.lang.Runnable

public abstract class NagamochiMinCut<V,E extends Edge<V>,G extends Graph<V,E>>
extends StepAlgo<V,E>

Compute the minimum cut of a graph. The algorithm used to computed the minimum cut is based on the algorithm given by H. Nagamochi and T. Ibaraki ("Computing edge connectivity in mulyigraphs and capacited graphs") SIAM Journal on Discrete Mathematics 5 (1992). The computation of minimum cut (run()) must be preceded by initialisation (setEdgesValueMap(Map), setEdgesValueName(String), ...). The result of the computation can be given as a set of edges or a cuple of vertex set (getEdgeMinCut() and getVertexMinCut()).

Author:

fabrice.peix@sophia.inria.fr

Nested Class Summary

Nested classes/interfaces inherited from class fr.inria.opengve.bridge.algorithms.StepAlgo

StepAlgo.StepAlgoMessage, StepAlgo.StepAlgoMessageType

Constructor Summary

NagamochiMinCut(G g)
Initialize the algorithm.

NagamochiMinCut(G g, boolean stepMode)
Initialize the algorithm with step mode set to a given value

Method Summary

protected abstract CopyGraph<V,E,G>	createCopier() Create a graph copier
protected abstract E	createEdge(V v1, V v2) Create a new edge
protected abstract G	createEmptyGraph() Create a new empty graph
protected abstract HierarchicalSet<E>	createEmptySet() Create a new empty edge set (based on an empty vertex set)
protected abstract HierarchicalSet<V>	createEmptyVertexSet() Create a new empty vertex set
HierarchicalSet<E>	getEdgeMinCut() Give the minimum cut of the graph as a edge set.
HierarchicalSet<V>[]	getVertexMinCut() Give the minimum cut of the graph as a cuple of vertex set.
void	run() Compute the minimum cut of the graph.
void	setEdgesValueContext(java.lang.Object context) Set the context used to load edges values in the map.
void	setEdgesValueMap(Map m) Set the map used to load edges values.
void	setEdgesValueName(java.lang.String name) Set the name used to load edges values in the map.

Methods inherited from class fr.inria.opengve.bridge.algorithms.StepAlgo

ends, getDemoMode, getStepMode, isEnded, nextStep, notifyGraphDisplayRequest, notifyGraphDisplayRequest, notifyLabelEdgesRequest, notifyLabelVerticesRequest, pause, setPauseMode, setTime, start

Methods inherited from class java.util.Observable

addObserver, clearChanged, countObservers, deleteObserver, deleteObservers, hasChanged, notifyObservers, notifyObservers, setChanged

Methods inherited from class java.lang.Object

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

Constructor Detail

NagamochiMinCut

public NagamochiMinCut(G g,
                       boolean stepMode)

Initialize the algorithm with step mode set to a given value

Parameters:

g - The graph

stepMode - The step mode

NagamochiMinCut

public NagamochiMinCut(G g)

Initialize the algorithm.

Parameters:

g - The graph.

Method Detail

createEmptyVertexSet

protected abstract HierarchicalSet<V> createEmptyVertexSet()

Create a new empty vertex set

createEmptySet

protected abstract HierarchicalSet<E> createEmptySet()

Create a new empty edge set (based on an empty vertex set)

createEmptyGraph

protected abstract G createEmptyGraph()

Create a new empty graph

createCopier

protected abstract CopyGraph<V,E,G> createCopier()

Create a graph copier

createEdge

protected abstract E createEdge(V v1,
                                V v2)

Create a new edge

setEdgesValueMap

public void setEdgesValueMap(Map m)

Set the map used to load edges values.

Parameters:

m - The map used to load edges values.

setEdgesValueName

public void setEdgesValueName(java.lang.String name)

Set the name used to load edges values in the map.

Parameters:

name - The name used to edges values in the map.

setEdgesValueContext

public void setEdgesValueContext(java.lang.Object context)

Set the context used to load edges values in the map.

Parameters:

context - The context used to edges values in the map.

run

public void run()

Compute the minimum cut of the graph.

Specified by:

run in interface java.lang.Runnable

Specified by:

run in class StepAlgo<V,E extends Edge<V>>

getEdgeMinCut

public HierarchicalSet<E> getEdgeMinCut()

Give the minimum cut of the graph as a edge set.

Returns:

The edge set representing the minimum cut of the graph.

getVertexMinCut

public HierarchicalSet<V>[] getVertexMinCut()

Give the minimum cut of the graph as a cuple of vertex set.

Returns:

The two vertex set representing the minimum cut of the graph.