c

# DiGraph 

### Companion object DiGraph

#### class DiGraph[T] extends AnyRef

Represents common behavior of all directed graphs

Source
DiGraph.scala
Linear Supertypes
Known Subclasses
Ordering
1. Alphabetic
2. By Inheritance
Inherited
1. DiGraph
2. AnyRef
3. Any
1. Hide All
2. Show All
Visibility
1. Public
2. All

### Value Members

1. final def !=(arg0: Any)
Definition Classes
AnyRef → Any
2. final def ##(): Int
Definition Classes
AnyRef → Any
3. def +(that: DiGraph[T]): DiGraph[T]

Graph sum of `this` and `that`

Graph sum of `this` and `that`

that

a second DiGraph[T]

returns

a DiGraph[T] containing all vertices and edges of each graph

4. final def ==(arg0: Any)
Definition Classes
AnyRef → Any
5. def BFS(root: T, blacklist: Set[T]): Map[T, T]

Performs breadth-first search on the directed graph, with a blacklist of nodes

Performs breadth-first search on the directed graph, with a blacklist of nodes

root

the start node

blacklist

list of nodes to avoid visiting, if encountered

returns

a Map[T,T] from each visited node to its predecessor in the traversal

6. def BFS(root: T): Map[T, T]

Performs breadth-first search on the directed graph

Performs breadth-first search on the directed graph

root

the start node

returns

a Map[T,T] from each visited node to its predecessor in the traversal

7. final def asInstanceOf[T0]: T0
Definition Classes
Any
8. def clone()
Attributes
protected[lang]
Definition Classes
AnyRef
Annotations
@throws( ... ) @native()
9. def contains(v: T)

Check whether the graph contains vertex v

10. final def eq(arg0: AnyRef)
Definition Classes
AnyRef
11. def equals(arg0: Any)
Definition Classes
AnyRef → Any
12. def finalize(): Unit
Attributes
protected[lang]
Definition Classes
AnyRef
Annotations
@throws( classOf[java.lang.Throwable] )
13. def findLoopAtNode(node: T): Seq[T]

Finds a Seq of Nodes that form a loop

Finds a Seq of Nodes that form a loop

node

Node to start loop path search from.

returns

The found Seq, the Seq is empty if there is no loop

14. def findSCCs: Seq[Seq[T]]

Finds the strongly connected components in the graph

Finds the strongly connected components in the graph

returns

a Seq of Seq[T], each containing nodes of an SCC in traversable order

15. def findSinks: Set[T]

Find all sinks in the graph

Find all sinks in the graph

returns

a Set[T] of sink nodes

16. def findSources: Set[T]

Find all sources in the graph

Find all sources in the graph

returns

a Set[T] of source nodes

17. final def getClass(): Class[_]
Definition Classes
AnyRef → Any
Annotations
@native()
18. def getEdgeMap: Map[T, Set[T]]
19. def getEdges(v: T): Set[T]

Get all edges of a node

Get all edges of a node

v

the specified node

returns

a Set[T] of all vertices that v has edges to

20. def getVertices: Set[T]

Get all vertices in the graph

Get all vertices in the graph

returns

a Set[T] of all vertices in the graph

21. def hashCode(): Int
Definition Classes
AnyRef → Any
Annotations
@native()
22. final def isInstanceOf[T0]
Definition Classes
Any
23. def linearize: Seq[T]

Linearizes (topologically sorts) a DAG

Linearizes (topologically sorts) a DAG

returns

a Seq[T] describing the topological order of the DAG traversal

Exceptions thrown

`CyclicException` if the graph is cyclic

24. final def ne(arg0: AnyRef)
Definition Classes
AnyRef
25. final def notify(): Unit
Definition Classes
AnyRef
Annotations
@native()
26. final def notifyAll(): Unit
Definition Classes
AnyRef
Annotations
@native()
27. def path(start: T, end: T, blacklist: Set[T]): Seq[T]

Finds a path (if one exists) from one node to another, with a blacklist

Finds a path (if one exists) from one node to another, with a blacklist

start

the start node

end

the destination node

blacklist

list of nodes which break path, if encountered

returns

a Seq[T] of nodes defining an arbitrary valid path

Exceptions thrown
28. def path(start: T, end: T): Seq[T]

Finds a path (if one exists) from one node to another

Finds a path (if one exists) from one node to another

start

the start node

end

the destination node

returns

a Seq[T] of nodes defining an arbitrary valid path

Exceptions thrown
29. def pathsInDAG(start: T): LinkedHashMap[T, Seq[Seq[T]]]

Finds all paths starting at a particular node in a DAG

Finds all paths starting at a particular node in a DAG

WARNING: This is an exponential time algorithm (as any algorithm must be for this problem), but is useful for flattening circuit graph hierarchies. Each path is represented by a Seq[T] of nodes in a traversable order.

start

the node to start at

returns

a Map[T,Seq[Seq[T]]] where the value associated with v is the Seq of all paths from start to v

30. def prettyTree(charSet: CharSet = PrettyCharSet)(implicit ev: =:=[T, String]): String

Serializes a `DiGraph[String]` as a pretty tree

Serializes a `DiGraph[String]` as a pretty tree

Multiple roots are supported, but cycles are not.

31. def reachableFrom(root: T, blacklist: Set[T]): LinkedHashSet[T]

Finds the set of nodes reachable from a particular node, with a blacklist.

Finds the set of nodes reachable from a particular node, with a blacklist. The semantics of adding a node to the blacklist is that any of its inedges will be ignored in the traversal. The `root` node is *not* included in the returned set unless it is possible to reach `root` along a non-trivial path beginning at `root`; i.e., if the graph has a cycle that contains `root`.

root

the start node

blacklist

list of nodes to stop searching, if encountered

returns

a Set[T] of nodes reachable from `root`

Finds the set of nodes reachable from a particular node.

Finds the set of nodes reachable from a particular node. The `root` node is *not* included in the returned set unless it is possible to reach `root` along a non-trivial path beginning at `root`; i.e., if the graph has a cycle that contains `root`.

root

the start node

returns

a Set[T] of nodes reachable from `root`

33. def reverse: DiGraph[T]

Returns a graph with all edges reversed

34. def simplify(vprime: Set[T]): DiGraph[T]

Return a simplified connectivity graph with only a subset of the nodes

Return a simplified connectivity graph with only a subset of the nodes

Any path between two non-deleted nodes (u,v) in the original graph will be transformed into an edge (u,v).

vprime

the Set[T] of desired vertices

returns

the simplified graph

Exceptions thrown

`java.lang.IllegalArgumentException` if vprime is not a subset of V

35. def subgraph(vprime: Set[T]): DiGraph[T]

Return a graph with only a subset of the nodes

Return a graph with only a subset of the nodes

Any edge including a deleted node will be deleted

vprime

the Set[T] of desired vertices

returns

the subgraph

Exceptions thrown

`java.lang.IllegalArgumentException` if vprime is not a subset of V

36. final def synchronized[T0](arg0: ⇒ T0): T0
Definition Classes
AnyRef
37. def toString()
Definition Classes
AnyRef → Any
38. def transformNodes[Q](f: (T) ⇒ Q): DiGraph[Q]

Return a graph with all the nodes of the current graph transformed by a function.

Return a graph with all the nodes of the current graph transformed by a function. Edge connectivity will be the same as the current graph.

f

A function {(T) => Q} that transforms each node

returns

a transformed DiGraph[Q]

39. final def wait(): Unit
Definition Classes
AnyRef
Annotations
@throws( ... )
40. final def wait(arg0: Long, arg1: Int): Unit
Definition Classes
AnyRef
Annotations
@throws( ... )
41. final def wait(arg0: Long): Unit
Definition Classes
AnyRef
Annotations
@throws( ... ) @native()