Packages

c

scalation.graph_db

MinSpanningTree

class MinSpanningTree extends Error

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.

See also

www.cse.ust.hk/~dekai/271/notes/L07/L07.pdf

Linear Supertypes
Error, Throwable, Serializable, AnyRef, Any
Ordering
  1. Alphabetic
  2. By Inheritance
Inherited
  1. MinSpanningTree
  2. Error
  3. Throwable
  4. Serializable
  5. AnyRef
  6. Any
  1. Hide All
  2. Show All
Visibility
  1. Public
  2. All

Instance Constructors

  1. new MinSpanningTree(g: MGraph[Double], min: Boolean = true, undirected: Boolean = true)

    g

    the multi-digraph to build the spanning tree from

    min

    whether to to create a minimum (true) or maximum (false) spanning tree

    undirected

    whether the graph is already undirected

Type Members

  1. case class Elem(idx: Int, key: Double) extends Product with Serializable

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

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

    idx

    the index of a node

    key

    the ordering key (based on cost) for a node

Value Members

  1. final def addSuppressed(arg0: Throwable): Unit
    Definition Classes
    Throwable
  2. def fillInStackTrace(): Throwable
    Definition Classes
    Throwable
  3. def getCause(): Throwable
    Definition Classes
    Throwable
  4. def getLocalizedMessage(): String
    Definition Classes
    Throwable
  5. def getMessage(): String
    Definition Classes
    Throwable
  6. def getStackTrace(): Array[StackTraceElement]
    Definition Classes
    Throwable
  7. final def getSuppressed(): Array[Throwable]
    Definition Classes
    Throwable
  8. def initCause(arg0: Throwable): Throwable
    Definition Classes
    Throwable
  9. def makeITree(): Array[Int]

    Make an inverted tree by recording the predecessor/parent array.

    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

    See also

    www.cse.ust.hk/~dekai/271/notes/L07/L07.pdf

  10. def printSTree(): Unit

    Print the spanning tree.

  11. def printStackTrace(arg0: PrintWriter): Unit
    Definition Classes
    Throwable
  12. def printStackTrace(arg0: PrintStream): Unit
    Definition Classes
    Throwable
  13. def printStackTrace(): Unit
    Definition Classes
    Throwable
  14. def setStackTrace(arg0: Array[StackTraceElement]): Unit
    Definition Classes
    Throwable
  15. def span(): Tree[Double]

    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.

  16. def toString(): String
    Definition Classes
    Throwable → AnyRef → Any
  17. object NodeOrder extends Ordering[Elem]

    The NodeOrder object defines the order of node indices based on their 'key' value.

    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)

  18. object NodeOrder2 extends Ordering[Elem]

    The NodeOrder object defines the order of node indices based on their 'key' value.

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