y.algo
Class SpanningTrees

java.lang.Object
  y.algo.SpanningTrees

public class SpanningTrees
extends java.lang.Object

This class provides (minimum) spanning tree algorithms for graphs.

Definitions

• A spanning tree of an undirected connected graph is a subset of its edges that induce a tree that connects all nodes of the graph.
• A minimum spanning tree of a weighted connected graph is a spanning tree whose edges have minimum overall cost among all spanning trees of that graph.

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.
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 in which each edge has a uniform cost of 1.0.

Methods inherited from class java.lang.Object

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

Method Detail

minimum

public static EdgeList minimum(Graph graph,
                               DataProvider cost)

Calculates a minimum spanning tree for the given graph.

Currently, the result is obtained by calling prim(Graph, DataProvider).

Preconditions:

The graph must be connected.

cost.length == graph.E()

Complexity:

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

Parameters:

graph - the input graph

cost - the DataProvider that returns a double value (cost) for each edge

Returns:

a list containing the edges that form the minimum spanning tree

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.

Preconditions:

The graph must be connected.

cost.length == graph.E()

Complexity:

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

Parameters:

graph - the input graph

cost - the DataProvider that returns a double value (cost) for each edge

Returns:

a list containing the edges that form the minimum spanning tree

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.

Preconditions:

The graph must be connected.

cost.length == graph.E()

Complexity:

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

Parameters:

graph - the input graph

cost - the DataProvider that returns a double value (cost) for each edge

Returns:

a list containing the edges that form the minimum spanning tree

uniform

public static EdgeList uniform(Graph graph)

Calculates a spanning tree for the given graph in which each edge has a uniform cost of 1.0.

Precondition:

The graph must be connected.

Complexity:

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

Parameters:

graph - the input graph

Returns:

a list containing the edges that form the minimum spanning tree

cost

public static double cost(EdgeList treeEdges,
                          DataProvider edgeCost)

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

Parameters:

treeEdges - the given list of edges that form a minimum spanning tree

edgeCost - the DataProvider that returns a double value (cost) for each tree edge

Returns:

the overall cost of the tree edges