com.tensegrity.graph.algorithm
Class MinimumSpanningTree

java.lang.Object
  com.tensegrity.graph.algorithm.MinimumSpanningTree

All Implemented Interfaces:

TransformAlgorithm

public class MinimumSpanningTree

extends java.lang.Object

implements TransformAlgorithm

This algorithm computes a minimum spanning tree for a given (connected) graph. The output graph has equivalent nodes and a subset of the original edges.

Version:

$Id: MinimumSpanningTree.java,v 1.11 2005/05/24 14:13:02 KevinCVS Exp $

Author:

Stepan Rutz

Constructor Summary

MinimumSpanningTree()
Constructs a new stateless instance of the MinimumSpanningTree algorithm.

Method Summary

Graph

apply(Graph input) Outputs a new graph that is a tree.

Methods inherited from class java.lang.Object

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

Constructor Detail

MinimumSpanningTree

public MinimumSpanningTree()

Constructs a new stateless instance of the MinimumSpanningTree algorithm.

Method Detail

apply

public Graph apply(Graph input)
            throws GraphException

Outputs a new graph that is a tree. Infact it is one of the minimum cost spanning trees for the input graph. Kruskal's algorithm is used. The running time is O(|E| * log |V|).

Specified by:

apply in interface TransformAlgorithm

Parameters:

input - the input Graph to examine, may not be null.

Returns:

the transformed output graph.

Throws:

GraphException - if the construction of the output Graph failed.