y.algo
Class SpanningTrees

java.lang.Object
  y.algo.SpanningTrees

public class SpanningTrees
extends Object

Provides (minimum) spanning tree algorithms for graphs. A spanning tree of an undirected connected graph is a subset of its edges that form a tree connecting all edges of the graph. If the edges of a graph have a cost or a weight associated with them then it is possible to calculate a minimum spanning tree of that graph, i.e. a spanning tree whose edges have minimum overall cost of all spanning trees of that graph.

Constructor Summary

SpanningTrees()

Method Summary

static double	cost(EdgeList treeEdges, DataProvider edgeCost) Returns the overall cost of a previously calculated minimum spanning tree.
static EdgeList	kruskal(Graph graph, DataProvider cost) Calculates a minimum spanning tree for the given graph.
static EdgeList	minimum(Graph graph, DataProvider cost) Calculates a minimum spanning tree for the given graph using our favorite algorithm for that problem.
static EdgeList	prim(Graph graph, DataProvider cost) Calculates a minimum spanning tree for the given graph.
static EdgeList	uniform(Graph graph) Calculates a spanning tree for the given graph.

Methods inherited from class java.lang.Object

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

Constructor Detail

SpanningTrees

public SpanningTrees()

Method Detail

minimum

public static EdgeList minimum(Graph graph,
                               DataProvider cost)

Calculates a minimum spanning tree for the given graph using our favorite algorithm for that problem.

Parameters:

graph - the input graph

cost - a data provider that must return a double value for each edge in the graph.

Returns:

a list that contains the edges that make up the minimum spanning tree.

Preconditions:

GraphComponents.isConnected(graph)

cost.length == graph.E();

kruskal

public static EdgeList kruskal(Graph graph,
                               DataProvider cost)

Calculates a minimum spanning tree for the given graph. The implementation is based on an algorithm originally published in

J.B. Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, pages 48-50, 1956.

Parameters:

graph - the input graph

cost - a data provider that must return a double value for each edge in the graph.

Returns:

a list that contains the edges that make up the minimum spanning tree.

Complexity:

graph.E()+graph.N()*log(graph.N())

Preconditions:

GraphComponents.isConnected(graph)

cost.length == graph.E();

prim

public static EdgeList prim(Graph graph,
                            DataProvider cost)

Calculates a minimum spanning tree for the given graph. The implementation is based on an algorithm originally published in

R.C. Prim. Shortest connection networks and some generalizations. Bell System Technical Journal, 36:1389-1401, 1957.

Parameters:

graph - the input graph

cost - a data provider that must return a double value for each edge in the graph.

Returns:

a list that contains the edges that make up the minimum spanning tree.

Complexity:

graph.E()*log(graph.N())

Preconditions:

GraphComponents.isConnected(graph)

cost.length == graph.E();

uniform

public static EdgeList uniform(Graph graph)

Calculates a spanning tree for the given graph. Each edge has assumed uniform cost of 1.0.

Parameters:

graph - the input graph

Returns:

a list that contains the edges that make up the minimum spanning tree.

Complexity:

O(graph.E()+graph.N())

Precondition:

GraphComponents.isConnected(graph)

cost

public static double cost(EdgeList treeEdges,
                          DataProvider edgeCost)

Returns the overall cost of a previously calculated minimum spanning tree.

Parameters:

treeEdges - edges that make up a minimum spanning tree.

edgeCost - a data provider that returns the double valued cost of each of the tree edges.

Returns:

the overall cost of the tree edges.