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

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

Type Parameters:

V - the type of vertices.

E - the type of edges.

All Implemented Interfaces:

java.lang.Runnable

public abstract class PrimST<V,E extends Edge<V>>
extends StepAlgo<V,E>

This class computes the Minimum Spanning Tree of a graph G with the Prim's algorithm. This implementation use Fibonacci heap as priority queue. This class is generic There is three kind of methods :

• Initialization methods
• setLengthName(String)
Set the name used to load value of length in the map.
• setLengthContext(Object)
Set the context used to load value of length in the map.
• Computation
• run()
Compute the Minimum Spanning Tree of the graph.
• Getting results
• getMST()
Return the Minimum Spanning Tree of the graph.
• getMSTWeight()
Return the weight of the Minimum Spanning Tree.

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

Field Summary

static java.lang.String

VERTEX_WEIGHT_NAME This is the name used to store weight of vertex in demoMode only.

Constructor Summary

PrimST(Graph<V,E> g, Map map)

PrimST(Graph<V,E> g, Map m, boolean demoMode)

Method Summary

protected abstract Graph<V,E>	createGraph(Graph<V,E> g) Create a new empty graph sub graph of a given garph.
Graph<V,E>	getMST() Return the computed minimum spanning tree.
AbstractScalar	getMSTWeight() Return the weight of the computed MST.
void	run() Compute the MST.
void	setInfiniteValue(AbstractScalar infinity) Set the value used as infinity.
void	setInitialVertex(V initialVertex) This method can be used to set the root of the resulting MST.
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 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

Field Detail

VERTEX_WEIGHT_NAME

public static final java.lang.String VERTEX_WEIGHT_NAME

This is the name used to store weight of vertex in demoMode only.

See Also:

Constant Field Values

Constructor Detail

PrimST

public PrimST(Graph<V,E> g,
              Map map)

PrimST

public PrimST(Graph<V,E> g,
              Map m,
              boolean demoMode)

Method Detail

createGraph

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

Create a new empty graph sub graph of a given garph.

Parameters:

g - The super graph.

Returns:

The new graph sub graph of the given graph.

setInitialVertex

public void setInitialVertex(V initialVertex)

This method can be used to set the root of the resulting MST. If this method is not call before computation the root of MST is undetermined.

Parameters:

initialVertex - The root of the resulting MST.

Throws:

java.lang.IllegalArgumentException - If the given vertex doesn't belong to the graph.

setLengthName

public void setLengthName(java.lang.String name)

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

Parameters:

name - The new name used to load length.

setLengthContext

public void setLengthContext(java.lang.Object context)

Set the context used to load edge length in the map. By default no context is used.

Parameters:

context - The new context used to load edge length in the map or null to specify that no context must be used.

setInfiniteValue

public void setInfiniteValue(AbstractScalar infinity)

Set the value used as infinity. By default this value is set to Double.MAX_VALUE.

Parameters:

infinity - The value used as infinity.

run

public void run()

Compute the MST.

Specified by:

run in interface java.lang.Runnable

Specified by:

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

getMST

public Graph<V,E> getMST()

Return the computed minimum spanning tree.

Returns:

The minimum spanning tree.

getMSTWeight

public AbstractScalar getMSTWeight()

Return the weight of the computed MST.

Returns:

The weigth of the MST.