mapss.dif.graph
Class MinimumSpanningTreeStrategy

java.lang.Object
  mocgraph.analysis.strategy.CachedStrategy
      mapss.dif.graph.MinimumSpanningTreeStrategy

All Implemented Interfaces:

MinimumSpanningTreeAnalyzer, mocgraph.analysis.analyzer.Analyzer, mocgraph.analysis.analyzer.GraphAnalyzer

public class MinimumSpanningTreeStrategy
extends mocgraph.analysis.strategy.CachedStrategy
implements MinimumSpanningTreeAnalyzer

Computation of a minimum spanning tree in a graph. The collection returned cannot be modified.

This implementation is adapted from Prim's algorithm, as taken from Introduction to Algorithms by Cormen, Leiserson, and Rivest (second edition).

Version:

$Id: MinimumSpanningTreeStrategy.java 409 2007-05-13 19:47:16Z plishker $

Author:

Shuvra S. Bhattacharyya

See Also:

MinimumSpanningTreeAnalysis

Constructor Summary

MinimumSpanningTreeStrategy(mocgraph.Graph graph, mocgraph.mapping.ToDoubleMapping edgeWeights)
Construct a minimum spanning tree strategy for a given graph and a given set of edge weights.

Method Summary

protected java.lang.Object	_compute() Compute a minimal spanning tree of the graph in the form of a List.
protected java.lang.Object	_convertResult(java.lang.Object result) Return the result of this analysis in a form that cannot be modified.
java.util.List	edges() Compute a minimum spanning tree in the form of a a list.
java.lang.String	toString() Return a description of the minimal spanning tree.
boolean	valid() Check compatibility of the class of graph.
double	weight() Return the weight of the minimum spanning tree (i.e., the sum of the weights of the edges in the tree.

Methods inherited from class mocgraph.analysis.strategy.CachedStrategy

_result, cachingStatus, disableCaching, enableCaching, getCachedResult, graph, obsolete, reset, setCachedResult

Methods inherited from class java.lang.Object

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

Methods inherited from interface mocgraph.analysis.analyzer.GraphAnalyzer

graph

Constructor Detail

MinimumSpanningTreeStrategy

public MinimumSpanningTreeStrategy(mocgraph.Graph graph,
                                   mocgraph.mapping.ToDoubleMapping edgeWeights)

Construct a minimum spanning tree strategy for a given graph and a given set of edge weights.

Parameters:

graph - The given graph.

edgeWeights - The edge weights.

Method Detail

edges

public java.util.List edges()

Compute a minimum spanning tree in the form of a a list. Each element of the list is an Edge.

Specified by:

edges in interface MinimumSpanningTreeAnalyzer

Returns:

The edges in the minimum spanning tree. FIXME: why is this is a list?

toString

public java.lang.String toString()

Return a description of the minimal spanning tree.

Specified by:

toString in interface mocgraph.analysis.analyzer.Analyzer

Overrides:

toString in class mocgraph.analysis.strategy.CachedStrategy

Returns:

A description of the minimal spanning tree.

valid

public boolean valid()

Check compatibility of the class of graph. The given graph must be an instance of Graph.

Specified by:

valid in interface mocgraph.analysis.analyzer.Analyzer

Parameters:

graph - The given graph.

Returns:

True if the given graph is of class Graph.

weight

public double weight()

Return the weight of the minimum spanning tree (i.e., the sum of the weights of the edges in the tree.

Specified by:

weight in interface MinimumSpanningTreeAnalyzer

Returns:

The weight of the minimum spanning tree.

_compute

protected java.lang.Object _compute()

Compute a minimal spanning tree of the graph in the form of a List. Each element of the list is an Edge. If the graph contains no edges, an empty list is returned. The graph is assumed to be connected.

Overrides:

_compute in class mocgraph.analysis.strategy.CachedStrategy

Returns:

The list of edges in the minimal spanning tree.

_convertResult

protected java.lang.Object _convertResult(java.lang.Object result)

Return the result of this analysis in a form that cannot be modified.

Overrides:

_convertResult in class mocgraph.analysis.strategy.CachedStrategy

Parameters:

result - The original result.

Returns:

The analysis result in unmodifiable form.