Packagecom.yworks.yfiles.algo
Classpublic class SpanningTrees
InheritanceSpanningTrees Inheritance YObject Inheritance 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.


Public Methods
 MethodDefined By
  
SpanningTrees(init:Boolean = true)
SpanningTrees
  
cost(treeEdges:EdgeList, edgeCost:DataProvider):Number
[static] Returns the overall cost of a previously calculated minimum spanning tree.
SpanningTrees
 Inherited
equals(o:Object):Boolean
YObject
  
getClass():Class
[override]
SpanningTrees
 Inherited
hashCode():int
YObject
  
kruskal(graph:Graph, cost:DataProvider):EdgeList
[static] Calculates a minimum spanning tree for the given graph.
SpanningTrees
  
minimum(graph:Graph, cost:DataProvider):EdgeList
[static] Calculates a minimum spanning tree for the given graph using our favorite algorithm for that problem.
SpanningTrees
  
newSpanningTrees():SpanningTrees
[static]
SpanningTrees
  
prim(graph:Graph, cost:DataProvider):EdgeList
[static] Calculates a minimum spanning tree for the given graph.
SpanningTrees
  
uniform(graph:Graph):EdgeList
[static] Calculates a spanning tree for the given graph.
SpanningTrees
Protected Methods
 MethodDefined By
  
initSpanningTrees():void
SpanningTrees
Constructor Detail
SpanningTrees()Constructor
public function SpanningTrees(init:Boolean = true)



Parameters
init:Boolean (default = true)
Method Detail
cost()method
public static function cost(treeEdges:EdgeList, edgeCost:DataProvider):Number

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

Parameters

treeEdges:EdgeList — edges that make up a minimum spanning tree.
 
edgeCost:DataProvider — a data provider that returns the double valued cost of each of the tree edges.

Returns
Number — the overall cost of the tree edges.
getClass()method 
override public function getClass():Class

Returns
Class
initSpanningTrees()method 
protected final function initSpanningTrees():void

kruskal()method 
public static function kruskal(graph:Graph, cost:DataProvider):EdgeList

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.

Precondition GraphComponents.isConnected(graph)

Precondition cost.length == graph.E();

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

Parameters

graph:Graph — the input graph
 
cost:DataProvider — a data provider that must return a double value for each edge in the graph.

Returns
EdgeList — a list that contains the edges that make up the minimum spanning tree.
minimum()method 
public static function minimum(graph:Graph, cost:DataProvider):EdgeList

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

Precondition GraphComponents.isConnected(graph)

Precondition cost.length == graph.E();

Parameters

graph:Graph — the input graph
 
cost:DataProvider — a data provider that must return a double value for each edge in the graph.

Returns
EdgeList — a list that contains the edges that make up the minimum spanning tree.
newSpanningTrees()method 
public static function newSpanningTrees():SpanningTrees

Returns
SpanningTrees
prim()method 
public static function prim(graph:Graph, cost:DataProvider):EdgeList

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.

Precondition GraphComponents.isConnected(graph)

Precondition cost.length == graph.E();

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

Parameters

graph:Graph — the input graph
 
cost:DataProvider — a data provider that must return a double value for each edge in the graph.

Returns
EdgeList — a list that contains the edges that make up the minimum spanning tree.
uniform()method 
public static function uniform(graph:Graph):EdgeList

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

Precondition GraphComponents.isConnected(graph)

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

Parameters

graph:Graph — the input graph

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




Wed Oct 7 2015, 04:43 PM +02:00