
Search this API  
PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object y.algo.SpanningTrees
public class SpanningTrees
This class provides (minimum) spanning tree algorithms for graphs.
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 

public static EdgeList minimum(Graph graph, DataProvider cost)
Currently, the result is obtained by calling prim(Graph, DataProvider)
.
connected
.cost.length == graph.E()
graph.E() * log(graph.N())
graph
 the input graphcost
 the DataProvider
that returns a double value (cost) for each edge
list
containing the edges that form the minimum spanning treepublic static EdgeList kruskal(Graph graph, DataProvider cost)
The implementation is based on an algorithm originally published in:
connected
.cost.length == graph.E()
graph.E() + graph.N() * log(graph.N())
graph
 the input graphcost
 the DataProvider
that returns a double value (cost) for each edge
list
containing the edges that form the minimum spanning treepublic static EdgeList prim(Graph graph, DataProvider cost)
The implementation is based on an algorithm originally published in:
connected
.cost.length == graph.E()
graph.E() * log(graph.N())
graph
 the input graphcost
 the DataProvider
that returns a double value (cost) for each edge
list
containing the edges that form the minimum spanning treepublic static EdgeList uniform(Graph graph)
1.0
.
connected
.O(graph.E() + graph.N())
graph
 the input graph
list
containing the edges that form the minimum spanning treepublic static double cost(EdgeList treeEdges, DataProvider edgeCost)
treeEdges
 the given list
of edges that form a minimum spanning treeedgeCost
 the DataProvider
that returns a double value (cost) for each tree edge

© Copyright 20002022, yWorks GmbH. All rights reserved. 

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 