com.yworks.yfiles.algorithms

Class SpanningTrees

java.lang.Object

com.yworks.yfiles.algorithms.SpanningTrees

public final class SpanningTrees
extends 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

Modifier and Type	Method and Description
static double	cost(EdgeList treeEdges, IDataProvider edgeCost) Returns the overall cost of a previously calculated minimum spanning tree.
static EdgeList	kruskal(Graph graph, IDataProvider cost) Calculates a minimum spanning tree for the given graph.
static EdgeList	minimum(Graph graph, IDataProvider cost) Calculates a minimum spanning tree for the given graph.
static EdgeList	prim(Graph graph, IDataProvider 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

cost

public static final double cost(EdgeList treeEdges,
                                IDataProvider 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 IDataProvider that returns a double value (cost) for each tree edge

Returns:

the overall cost of the tree edges

kruskal

public static final EdgeList kruskal(Graph graph,
                                     IDataProvider 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 IDataProvider that returns a double value (cost) for each edge

Returns:

a list containing the edges that form the minimum spanning tree

minimum

public static final EdgeList minimum(Graph graph,
                                     IDataProvider cost)

Calculates a minimum spanning tree for the given graph.

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

Preconditions:

The graph must be connected.

cost.length == graph.E()

Complexity:

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

Parameters:

graph - the input graph

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

Returns:

a list containing the edges that form the minimum spanning tree

prim

public static final EdgeList prim(Graph graph,
                                  IDataProvider 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 IDataProvider that returns a double value (cost) for each edge

Returns:

a list containing the edges that form the minimum spanning tree

uniform

public static final 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