class DiGraph[T] extends AnyRef
Represents common behavior of all directed graphs
- Annotations
- @deprecated
- Deprecated
(Since version Chisel 7.0.0) All APIs in package firrtl are deprecated.
- Source
- DiGraph.scala
- Alphabetic
- By Inheritance
- DiGraph
- AnyRef
- Any
- by any2stringadd
- by StringFormat
- by Ensuring
- by ArrowAssoc
- Hide All
- Show All
- Public
- Protected
Instance Constructors
- new DiGraph(edges: LinkedHashMap[T, LinkedHashSet[T]])
Value Members
- final def !=(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
- final def ##: Int
- Definition Classes
- AnyRef → Any
- def +(that: DiGraph[T]): DiGraph[T]
Graph sum of
this
andthat
Graph sum of
this
andthat
- that
a second DiGraph[T]
- returns
a DiGraph[T] containing all vertices and edges of each graph
- def ->[B](y: B): (DiGraph[T], B)
- final def ==(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
- 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
- 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
- final def asInstanceOf[T0]: T0
- Definition Classes
- Any
- def clone(): AnyRef
- Attributes
- protected[lang]
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.CloneNotSupportedException]) @native()
- def contains(v: T): Boolean
Check whether the graph contains vertex v
- def ensuring(cond: (DiGraph[T]) => Boolean, msg: => Any): DiGraph[T]
- def ensuring(cond: (DiGraph[T]) => Boolean): DiGraph[T]
- def ensuring(cond: Boolean, msg: => Any): DiGraph[T]
- def ensuring(cond: Boolean): DiGraph[T]
- final def eq(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
- def equals(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef → Any
- def finalize(): Unit
- Attributes
- protected[lang]
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.Throwable])
- 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
- 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
- def findSinks: Set[T]
Find all sinks in the graph
Find all sinks in the graph
- returns
a Set[T] of sink nodes
- def findSources: Set[T]
Find all sources in the graph
Find all sources in the graph
- returns
a Set[T] of source nodes
- final def getClass(): Class[_ <: AnyRef]
- Definition Classes
- AnyRef → Any
- Annotations
- @native()
- def getEdgeMap: Map[T, Set[T]]
- 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
- 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
- def hashCode(): Int
- Definition Classes
- AnyRef → Any
- Annotations
- @native()
- final def isInstanceOf[T0]: Boolean
- Definition Classes
- Any
- 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
- final def ne(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
- final def notify(): Unit
- Definition Classes
- AnyRef
- Annotations
- @native()
- final def notifyAll(): Unit
- Definition Classes
- AnyRef
- Annotations
- @native()
- 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
- 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
- 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
- def prettyTree(charSet: CharSet = PrettyCharSet)(implicit ev: =:=[T, String]): String
Serializes a
DiGraph[String]
as a pretty treeSerializes a
DiGraph[String]
as a pretty treeMultiple roots are supported, but cycles are not.
- 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 reachroot
along a non-trivial path beginning atroot
; i.e., if the graph has a cycle that containsroot
.- root
the start node
- blacklist
list of nodes to stop searching, if encountered
- returns
a Set[T] of nodes reachable from
root
- def reachableFrom(root: T): LinkedHashSet[T]
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 reachroot
along a non-trivial path beginning atroot
; i.e., if the graph has a cycle that containsroot
.- root
the start node
- returns
a Set[T] of nodes reachable from
root
- def reverse: DiGraph[T]
Returns a graph with all edges reversed
- 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
- 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
- final def synchronized[T0](arg0: => T0): T0
- Definition Classes
- AnyRef
- def toString(): String
- Definition Classes
- AnyRef → Any
- 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]
- final def wait(): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.InterruptedException])
- final def wait(arg0: Long, arg1: Int): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.InterruptedException])
- final def wait(arg0: Long): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.InterruptedException]) @native()
Shadowed Implicit Value Members
- def +(other: String): String
- Implicit
- This member is added by an implicit conversion from DiGraph[T] toany2stringadd[DiGraph[T]] performed by method any2stringadd in scala.Predef.
- Shadowing
- This implicitly inherited member is shadowed by one or more members in this class.
To access this member you can use a type ascription:(diGraph: any2stringadd[DiGraph[T]]).+(other)
- Definition Classes
- any2stringadd
Deprecated Value Members
- def formatted(fmtstr: String): String
- Implicit
- This member is added by an implicit conversion from DiGraph[T] toStringFormat[DiGraph[T]] performed by method StringFormat in scala.Predef.
- Definition Classes
- StringFormat
- Annotations
- @deprecated @inline()
- Deprecated
(Since version 2.12.16) Use
formatString.format(value)
instead ofvalue.formatted(formatString)
, or use thef""
string interpolator. In Java 15 and later,formatted
resolves to the new method in String which has reversed parameters.
- def →[B](y: B): (DiGraph[T], B)
- Implicit
- This member is added by an implicit conversion from DiGraph[T] toArrowAssoc[DiGraph[T]] performed by method ArrowAssoc in scala.Predef.
- Definition Classes
- ArrowAssoc
- Annotations
- @deprecated
- Deprecated
(Since version 2.13.0) Use
->
instead. If you still wish to display it as one character, consider using a font with programming ligatures such as Fira Code.
This is the documentation for Chisel.
Package structure
The chisel3 package presents the public API of Chisel. It contains the concrete core types
UInt
,SInt
,Bool
,Clock
, andReg
, the abstract typesBits
,Aggregate
, andData
, and the aggregate typesBundle
andVec
.The Chisel package is a compatibility layer that attempts to provide chisel2 compatibility in chisel3.
Utility objects and methods are found in the
util
package.The
testers
package defines the basic interface for chisel testers.