Packages

class GraphDFS[TLabel] 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[TLabel], 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. 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

  2. def pred1(j: Int): Boolean
  3. def pred2(j: Int): Boolean
  4. 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

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

  6. def visit(): Unit

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

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

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