Packages

class GraphDFS extends AnyRef

The GraphDFS performs Depth First Search (DFS) or Breadth First Search (BFS) on a Directed Graph. The class currently supports three predicates: (1) to find a matching label, and (2) to see if a destination vertex is reachable.

Linear Supertypes
AnyRef, Any
Ordering
  1. Alphabetic
  2. By Inheritance
Inherited
  1. GraphDFS
  2. AnyRef
  3. Any
  1. Hide All
  2. Show All
Visibility
  1. Public
  2. All

Instance Constructors

  1. new GraphDFS(g: Graph, bfs: Boolean = false)

    g

    the directed graph to search

    bfs

    switch from DFS to BFS, if bfs flag is true (defaults to false)

Type Members

  1. type QUEUE = Queue[Int]
  2. type STACK = ArrayStack[Int]

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 asInstanceOf[T0]: T0
    Definition Classes
    Any
  5. def clone(): AnyRef
    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  6. final def eq(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  7. def equals(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  8. def finalize(): Unit
    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( classOf[java.lang.Throwable] )
  9. def find(_lab: TLabel): Int

    Find the label 'lab' in 'this' graph, returning the first vertex id with a matching label, or -1 if vertex is not found.

    Find the label 'lab' in 'this' graph, returning the first vertex id with a matching label, or -1 if vertex is not found.

    _lab

    the label to search for

  10. final def getClass(): Class[_]
    Definition Classes
    AnyRef → Any
  11. def hashCode(): Int
    Definition Classes
    AnyRef → Any
  12. final def isInstanceOf[T0]: Boolean
    Definition Classes
    Any
  13. final def ne(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  14. final def notify(): Unit
    Definition Classes
    AnyRef
  15. final def notifyAll(): Unit
    Definition Classes
    AnyRef
  16. def pred1(j: Int): Boolean
  17. def pred2(j: Int): Boolean
  18. def reach(src: Int, _dest: Int): Boolean

    Determine whether vertex '_dest' is reachable from 'src', i.e., there is a directed path from vertex 'src' to '_dest'.

    Determine whether vertex '_dest' is reachable from 'src', i.e., there is a directed path from vertex 'src' to '_dest'.

    src

    the source/starting vertex

    _dest

    the destination/ending vertex

  19. def strongComps: Int

    Count the number of strongly connected components in the graph.

    Count the number of strongly connected components in the graph. In a strongly connected component, 'reach (u, v)' is always true.

  20. final def synchronized[T0](arg0: ⇒ T0): T0
    Definition Classes
    AnyRef
  21. def toString(): String
    Definition Classes
    AnyRef → Any
  22. def visit(): Unit

    Visit vertices in DFS/BFS order accessing children and parents (as if it is an undirected graph).

  23. def visit(pred: (Int) ⇒ Boolean): Int

    Visit vertices in DFS/BFS order, returning the id of the first vertex satisfying the predicate 'pred', or -1 if vertex is not found.

    Visit vertices in DFS/BFS order, returning the id of the first vertex satisfying the predicate 'pred', or -1 if vertex is not found.

    pred

    the predicate to satisfy

  24. final def wait(): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  25. final def wait(arg0: Long, arg1: Int): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  26. final def wait(arg0: Long): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  27. def weakComps: Int

    Count the number of weakly connected components in the graph.

    Count the number of weakly connected components in the graph. In a weakly connected component, the vertices in the underlying undirected graph are connected.

Inherited from AnyRef

Inherited from Any

Ungrouped