scalation
API
Generated with
scalation/scalation/scalation.database/MinSpanningTree

MinSpanningTree

scalation.database.MinSpanningTree
See theMinSpanningTree companion object
class MinSpanningTree(g: Graph, undirected: Boolean)

The MinSpanningTree class is used to build minimum cost spanning trees from graphs. Edge cost/weights are given by edge labels. MinSpanningTree implements Prim's algorithm. scalation.PriorityQueue ScalaTion's extension adds increaseKey, printInOrder

Value parameters

g

the digraph to build the spanning tree from

undirected

whether the graph is already undirected

Attributes

See also
Companion
object
Graph
Supertypes
class Object
trait Matchable
class Any

Members list

Type members

Classlikes

case class Elem(idx: Int, key: Double)

The Elem class is used for ordering elements on a priority queue.

The Elem class is used for ordering elements on a priority queue.

Value parameters

idx

the index of a node

key

the ordering key (based on cost) for a node

Attributes

Supertypes
trait Serializable
trait Product
trait Equals
class Object
trait Matchable
class Any
Show all
object NodeOrder extends Ordering[Elem]

The NodeOrder object defines the order of node indices based on their 'key' value. Using -key to get "smallest first" in priority queue. This is for minimum spanning trees ('min' = true)

The NodeOrder object defines the order of node indices based on their 'key' value. Using -key to get "smallest first" in priority queue. This is for minimum spanning trees ('min' = true)

Attributes

Supertypes
trait Ordering[Elem]
trait PartialOrdering[Elem]
trait Equiv[Elem]
trait Serializable
trait Comparator[Elem]
class Object
trait Matchable
class Any
Show all
Self type
NodeOrder.type

Value members

Concrete methods

def makeITree(): VectorI

Make an inverted tree by recording the predecessor/parent array. Each node except the root will have one parent. See pseudo-code on p. 28

Make an inverted tree by recording the predecessor/parent array. Each node except the root will have one parent. See pseudo-code on p. 28

Attributes

See also
def printSTree(): Unit

Print the spanning tree.

Print the spanning tree.

Attributes

def span(): Tree

Create a minimum cost spanning tree for the given graph, returning true if a complete spanning tree connecting all of g's vertices can be created.

Create a minimum cost spanning tree for the given graph, returning true if a complete spanning tree connecting all of g's vertices can be created.

Attributes

Generated with