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. Protected

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

  20. final def ne(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  21. final def notify(): Unit
    Definition Classes
    AnyRef
    Annotations
    @native() @HotSpotIntrinsicCandidate()
  22. final def notifyAll(): Unit
    Definition Classes
    AnyRef
    Annotations
    @native() @HotSpotIntrinsicCandidate()
  23. def printSTree(): Unit

    Print the spanning tree.

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

  29. final def synchronized[T0](arg0: => T0): T0
    Definition Classes
    AnyRef
  30. def toString(): String
    Definition Classes
    Throwable → AnyRef → Any
  31. final def wait(arg0: Long, arg1: Int): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.InterruptedException])
  32. final def wait(arg0: Long): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.InterruptedException]) @native()
  33. final def wait(): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.InterruptedException])
  34. 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)

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

Deprecated Value Members

  1. def finalize(): Unit
    Attributes
    protected[lang]
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.Throwable]) @Deprecated
    Deprecated

Inherited from Error

Inherited from Throwable

Inherited from Serializable

Inherited from AnyRef

Inherited from Any

Ungrouped