MutableDiGraph
Attributes
- Deprecated
-
[Since version Chisel 7.0.0]All APIs in package firrtl are deprecated. - Source
- DiGraph.scala
- Graph
-
- Supertypes
Members list
Value members
Concrete methods
Add edge (u,v) to the graph.
Add edge (u,v) to the graph.
Attributes
- Throws
-
java.lang.IllegalArgumentException
if u and/or v is not in the graph
- Source
- DiGraph.scala
Add edge (u,v) to the graph if and only if both u and v are in the graph prior to calling addEdgeIfValid.
Add edge (u,v) to the graph if and only if both u and v are in the graph prior to calling addEdgeIfValid.
Attributes
- Source
- DiGraph.scala
Add edge (u,v) to the graph, adding u and/or v if they are not already in the graph.
Add edge (u,v) to the graph, adding u and/or v if they are not already in the graph.
Attributes
- Source
- DiGraph.scala
Add vertex v to the graph
Inherited 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
- Inherited from:
- DiGraph
- 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
- Inherited from:
- DiGraph
- 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
- Inherited from:
- DiGraph
- 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
- Inherited from:
- DiGraph
- 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
- Inherited from:
- DiGraph
- Source
- DiGraph.scala
Find all sinks in the graph
Find all sinks in the graph
Attributes
- Returns
-
a Set[T] of sink nodes
- Inherited from:
- DiGraph
- Source
- DiGraph.scala
Find all sources in the graph
Find all sources in the graph
Attributes
- Returns
-
a Set[T] of source nodes
- Inherited from:
- DiGraph
- Source
- DiGraph.scala
Attributes
- Inherited from:
- DiGraph
- 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
- Inherited from:
- DiGraph
- 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
- Inherited from:
- DiGraph
- 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
- Inherited from:
- DiGraph
- 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
- Inherited from:
- DiGraph
- 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
- Inherited from:
- DiGraph
- 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
- Inherited from:
- DiGraph
- 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
- Inherited from:
- DiGraph
- 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 - Inherited from:
- DiGraph
- 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 - Inherited from:
- DiGraph
- 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
- Inherited from:
- DiGraph
- 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
- Inherited from:
- DiGraph
- 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]
- Inherited from:
- DiGraph
- Source
- DiGraph.scala