diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/main/scala/firrtl/graph/DiGraph.scala | 65 |
1 files changed, 28 insertions, 37 deletions
diff --git a/src/main/scala/firrtl/graph/DiGraph.scala b/src/main/scala/firrtl/graph/DiGraph.scala index ac2dd62f..d3015b5a 100644 --- a/src/main/scala/firrtl/graph/DiGraph.scala +++ b/src/main/scala/firrtl/graph/DiGraph.scala @@ -64,14 +64,37 @@ class DiGraph[T] private[graph] (private[graph] val edges: LinkedHashMap[T, Link */ def findSinks: Set[T] = reverse.findSources - /** Linearizes (topologically sorts) a DAG using a DFS. This can be seeded with an order to use for the DFS if the user - * wants to tease out a special ordering of the DAG. - * @param seed an optional sequence of vertices to use. This will default to the vertices ordering provided by getVertices. + /** + * Finds a Seq of Nodes that form a loop + * @param node Node to start loop path search from. + * @return The found Seq, the Seq is empty if there is no loop + */ + def findLoopAtNode(node: T): Seq[T] = { + var foundPath = Seq.empty[T] + getEdges(node).exists { vertex => + try { + foundPath = path(vertex, node, blacklist = Set.empty) + true + } + catch { + case _: PathNotFoundException => + foundPath = Seq.empty[T] + false + case t: Throwable => + throw t + + } + } + foundPath + } + + /** Linearizes (topologically sorts) a DAG + * * @throws CyclicException if the graph is cyclic * @return a Map[T,T] from each visited node to its predecessor in the * traversal */ - def seededLinearize(seed: Option[Seq[T]] = None): Seq[T] = { + def linearize: Seq[T] = { // permanently marked nodes are implicitly held in order val order = new mutable.ArrayBuffer[T] // invariant: no intersection between unmarked and tempMarked @@ -81,7 +104,7 @@ class DiGraph[T] private[graph] (private[graph] val edges: LinkedHashMap[T, Link case class LinearizeFrame[A](v: A, expanded: Boolean) val callStack = mutable.Stack[LinearizeFrame[T]]() - unmarked ++= seed.getOrElse(getVertices) + unmarked ++= getVertices while (unmarked.nonEmpty) { callStack.push(LinearizeFrame(unmarked.head, false)) while (callStack.nonEmpty) { @@ -110,38 +133,6 @@ class DiGraph[T] private[graph] (private[graph] val edges: LinkedHashMap[T, Link order.reverse.toSeq } - /** - * Finds a Seq of Nodes that form a loop - * @param node Node to start loop path search from. - * @return The found Seq, the Seq is empty if there is no loop - */ - def findLoopAtNode(node: T): Seq[T] = { - var foundPath = Seq.empty[T] - getEdges(node).exists { vertex => - try { - foundPath = path(vertex, node, blacklist = Set.empty) - true - } - catch { - case _: PathNotFoundException => - foundPath = Seq.empty[T] - false - case t: Throwable => - throw t - - } - } - foundPath - } - - /** Linearizes (topologically sorts) a DAG - * - * @throws CyclicException if the graph is cyclic - * @return a Map[T,T] from each visited node to its predecessor in the - * traversal - */ - def linearize: Seq[T] = seededLinearize(None) - /** Performs breadth-first search on the directed graph * * @param root the start node |