fr.inria.opengve.bridge.algorithms.undirected
Class Kruskal<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.Kruskal<V,E,G>

All Implemented Interfaces:

java.lang.Runnable

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

This class implement the Kruskal algorithms to compute minimum spanning tree, it work only on non directed graph. The complexity of this implementation is O(|V||E|) where V and E are respectivly the set of vertices and edges of the graph. When this class run in StepMode the map given by user is modified to store "color" of edge (Demo mode) and the graph is also modified (some edges are deleted.).

Author:

Fabrice Peix (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

Kruskal(G g, Map map)
Constructor.

Kruskal(G g, Map map, boolean demoMode)
Constructor.

Method Summary

protected abstract G	createGraph(G g) Create a new empty subgraph of a given graph.
G	getMST() Return a minimum spanning tree.
void	run() Compute the minimum spanning tree of graph.
void	setLengthContext(java.lang.Object context) Set the context used to load edge length in the map.
void	setLengthName(java.lang.String name) Set the name used to load value of edge length 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

Kruskal

public Kruskal(G g,
               Map map)

Constructor.

Parameters:

g - The graph on which Kruskal algorithm msut be apply.

map - The map containing length of edges.

Kruskal

public Kruskal(G g,
               Map map,
               boolean demoMode)

Constructor.

Parameters:

g - The graph on which Kruskal algorithm msut be apply.

map - The map containing length of edges.

demoMode - Set the demoMode of the algorithms.

Method Detail

createGraph

protected abstract G createGraph(G g)

Create a new empty subgraph of a given graph.

Parameters:

g - The given graph.

Returns:

A new empty subgraph of g.

setLengthName

public void setLengthName(java.lang.String name)

Set the name used to load value of edge length in the map. By default the name is "Length".

Parameters:

name - The new name used to load edge length in the map.

setLengthContext

public void setLengthContext(java.lang.Object context)

Set the context used to load edge length in the map. By default the context is the graph on which is computed the minimum spanning tree. If null is given default context is used.

Parameters:

context - The new context used to load edge length in the map.

run

public void run()

Compute the minimum spanning tree of graph.

Specified by:

run in interface java.lang.Runnable

Specified by:

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

getMST

public G getMST()

Return a minimum spanning tree.

Returns:

A minimum spanning of the given graph.