Packages

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 !=(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  2. final def ##(): Int
    Definition Classes
    AnyRef → Any
  3. final def ==(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  4. final def addSuppressed(arg0: Throwable): Unit
    Definition Classes
    Throwable
  5. def aniSTree(): Unit

    Animate the display of the spanning tree.

  6. final def asInstanceOf[T0]: T0
    Definition Classes
    Any
  7. def clone(): AnyRef
    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  8. final def eq(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  9. def equals(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  10. def fillInStackTrace(): Throwable
    Definition Classes
    Throwable
  11. def finalize(): Unit
    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( classOf[java.lang.Throwable] )
  12. def getCause(): Throwable
    Definition Classes
    Throwable
  13. final def getClass(): Class[_]
    Definition Classes
    AnyRef → Any
  14. def getLocalizedMessage(): String
    Definition Classes
    Throwable
  15. def getMessage(): String
    Definition Classes
    Throwable
  16. def getStackTrace(): Array[StackTraceElement]
    Definition Classes
    Throwable
  17. final def getSuppressed(): Array[Throwable]
    Definition Classes
    Throwable
  18. def hashCode(): Int
    Definition Classes
    AnyRef → Any
  19. def initCause(arg0: Throwable): Throwable
    Definition Classes
    Throwable
  20. final def isInstanceOf[T0]: Boolean
    Definition Classes
    Any
  21. 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 note 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

  22. final def ne(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  23. final def notify(): Unit
    Definition Classes
    AnyRef
  24. final def notifyAll(): Unit
    Definition Classes
    AnyRef
  25. def printSTree(): Unit

    Print the spanning tree.

  26. def printStackTrace(arg0: PrintWriter): Unit
    Definition Classes
    Throwable
  27. def printStackTrace(arg0: PrintStream): Unit
    Definition Classes
    Throwable
  28. def printStackTrace(): Unit
    Definition Classes
    Throwable
  29. def setStackTrace(arg0: Array[StackTraceElement]): Unit
    Definition Classes
    Throwable
  30. 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.

  31. final def synchronized[T0](arg0: ⇒ T0): T0
    Definition Classes
    AnyRef
  32. def toString(): String
    Definition Classes
    Throwable → AnyRef → Any
  33. final def wait(): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  34. final def wait(arg0: Long, arg1: Int): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  35. final def wait(arg0: Long): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  36. 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)

  37. 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)

Inherited from Error

Inherited from Throwable

Inherited from Serializable

Inherited from AnyRef

Inherited from Any

Ungrouped