Represents common behavior of all directed graphs
Attributes
- Companion
- object
- Deprecated
-
[Since version Chisel 7.0.0]All APIs in package firrtl are deprecated. - Source
- DiGraph.scala
- Graph
-
- Supertypes
-
class Objecttrait Matchableclass Any
- Known subtypes
-
class MutableDiGraph[T]
Members list
Value members
Concrete methods
Graph sum of this and that
Graph sum of this and that
Value parameters
- that
-
a second DiGraph[T]
Attributes
- Returns
-
a DiGraph[T] containing all vertices and edges of each graph
- Source
- DiGraph.scala
Performs breadth-first search on the directed graph
Performs breadth-first search on the directed graph
Value parameters
- root
-
the start node
Attributes
- Returns
-
a Map[T,T] from each visited node to its predecessor in the traversal
- Source
- DiGraph.scala
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
Value parameters
- blacklist
-
list of nodes to avoid visiting, if encountered
- root
-
the start node
Attributes
- Returns
-
a Map[T,T] from each visited node to its predecessor in the traversal
- Source
- DiGraph.scala
Check whether the graph contains vertex v
Finds a Seq of Nodes that form a loop
Finds a Seq of Nodes that form a loop
Value parameters
- node
-
Node to start loop path search from.
Attributes
- Returns
-
The found Seq, the Seq is empty if there is no loop
- Source
- DiGraph.scala
Finds the strongly connected components in the graph
Finds the strongly connected components in the graph
Attributes
- Returns
-
a Seq of Seq[T], each containing nodes of an SCC in traversable order
- Source
- DiGraph.scala
Find all sinks in the graph
Find all sources in the graph
Attributes
- Source
- DiGraph.scala
Get all edges of a node
Get all edges of a node
Value parameters
- v
-
the specified node
Attributes
- Returns
-
a Set[T] of all vertices that v has edges to
- Source
- DiGraph.scala
Get all vertices in the graph
Get all vertices in the graph
Attributes
- Returns
-
a Set[T] of all vertices in the graph
- Source
- DiGraph.scala
Linearizes (topologically sorts) a DAG
Linearizes (topologically sorts) a DAG
Attributes
- Returns
-
a Seq[T] describing the topological order of the DAG traversal
- Throws
-
CyclicException
if the graph is cyclic
- Source
- DiGraph.scala
Finds a path (if one exists) from one node to another
Finds a path (if one exists) from one node to another
Value parameters
- end
-
the destination node
- start
-
the start node
Attributes
- Returns
-
a Seq[T] of nodes defining an arbitrary valid path
- Source
- DiGraph.scala
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
Value parameters
- blacklist
-
list of nodes which break path, if encountered
- end
-
the destination node
- start
-
the start node
Attributes
- Returns
-
a Seq[T] of nodes defining an arbitrary valid path
- Source
- DiGraph.scala
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.
Value parameters
- start
-
the node to start at
Attributes
- Returns
-
a Map[T,Seq[Seq[T]]] where the value associated with v is the Seq of all paths from start to v
- Source
- DiGraph.scala
Serializes a DiGraph[String] as a pretty tree
Serializes a DiGraph[String] as a pretty tree
Multiple roots are supported, but cycles are not.
Attributes
- Source
- DiGraph.scala
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.
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.
Value parameters
- root
-
the start node
Attributes
- Returns
-
a Set[T] of nodes reachable from
root - Source
- DiGraph.scala
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.
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.
Value parameters
- blacklist
-
list of nodes to stop searching, if encountered
- root
-
the start node
Attributes
- Returns
-
a Set[T] of nodes reachable from
root - Source
- DiGraph.scala
Returns a graph with all edges reversed
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).
Value parameters
- vprime
-
the Set[T] of desired vertices
Attributes
- Returns
-
the simplified graph
- Throws
-
java.lang.IllegalArgumentException
if vprime is not a subset of V
- Source
- DiGraph.scala
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
Value parameters
- vprime
-
the Set[T] of desired vertices
Attributes
- Returns
-
the subgraph
- Throws
-
java.lang.IllegalArgumentException
if vprime is not a subset of V
- Source
- DiGraph.scala
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.
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.
Value parameters
- f
-
A function {(T) => Q} that transforms each node
Attributes
- Returns
-
a transformed DiGraph[Q]
- Source
- DiGraph.scala