Search this API

y.algo
Class SpanningTrees

java.lang.Object
  extended by y.algo.SpanningTrees

public class SpanningTrees
extends java.lang.Object

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

Definitions

 

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:

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:

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

© Copyright 2000-2022,
yWorks GmbH.
All rights reserved.