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

java.lang.Object
  fr.inria.opengve.bridge.algorithms.undirected.minCut.StoerWagnerMinCut<V,E>

Type Parameters:

V - The type of vertices

E - The type of edge

public abstract class StoerWagnerMinCut<V,E extends Edge<V>>
extends java.lang.Object

This algorithm is based on: A simple min-cut algorithm Source Journal of the ACM (JACM) archive Volume 44 , Issue 4 (July 1997) table of contents Pages: 585 - 591 Year of Publication: 1997 ISSN:0004-5411 Authors Mechthild Stoer Televerkets Forskningsinstitutt, Kjeller, Norway Frank Wagner Freie Univ. Berlin, Berlin-Dahlem, Germany Publisher ACM Press New York, NY, USA it use minCutPhaseSimple that is a simplified version of minCutPhase that do not use a fibonacci heap. an improvement of this algorithm is to implement the minCutPhase with fibonacci heap as explaned in the document.

Author:

fabrice.peix@sophia.inria.fr

Constructor Summary

StoerWagnerMinCut()
Initialize the algorithm.

Method Summary

AbstractScalar	compute() Give the value of the minimal cut.
protected abstract Graph<V,E>	copyGraph(Graph<V,E> g) Get a copy of the given graph.
protected abstract AbstractScalar	createOne() Create an abstract scalar with a value one.
void	setDistanceContext(java.lang.Object context) Set the context used to read edge's distance in the map.
void	setDistanceMap(Map map) Set the map used to read edge's distance.
void	setDistanceName(java.lang.String name) Set the name used to read edge's distance in the map.
void	setGraph(Graph<V,E> graph) Set the graph on which is computed the minimal cut.

Methods inherited from class java.lang.Object

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

Constructor Detail

StoerWagnerMinCut

public StoerWagnerMinCut()

Initialize the algorithm.

Method Detail

copyGraph

protected abstract Graph<V,E> copyGraph(Graph<V,E> g)

Get a copy of the given graph.

Parameters:

g - The graph that must be copied.

Returns:

The copy of the given graph.

createOne

protected abstract AbstractScalar createOne()

Create an abstract scalar with a value one.

Returns:

An AbstractScalar with a value equal to one.

setGraph

public void setGraph(Graph<V,E> graph)

Set the graph on which is computed the minimal cut.

Parameters:

graph - The graph.

setDistanceMap

public void setDistanceMap(Map map)

Set the map used to read edge's distance. If none is given then all links have a distance value equal to one.

Parameters:

map - A map.

setDistanceName

public void setDistanceName(java.lang.String name)

Set the name used to read edge's distance in the map.

Parameters:

name - The name used to read edge's distance.

setDistanceContext

public void setDistanceContext(java.lang.Object context)

Set the context used to read edge's distance in the map.

Parameters:

context - The context used to read edge's distance.

compute

public AbstractScalar compute()

Give the value of the minimal cut.

Returns:

The value of the minimal cut.