From e2ad4650c73a33fa84f1b8d4aa84438feaefb153 Mon Sep 17 00:00:00 2001 From: Schuyler Eldridge Date: Tue, 12 Sep 2017 18:07:31 -0400 Subject: Make pathsInDAG walk all possible paths (#655) * Make pathsInDAG walk all possible paths Signed-off-by: Schuyler Eldridge * Use linearization order when finding all paths in DAG --- src/main/scala/firrtl/graph/DiGraph.scala | 10 +++------- 1 file changed, 3 insertions(+), 7 deletions(-) (limited to 'src') diff --git a/src/main/scala/firrtl/graph/DiGraph.scala b/src/main/scala/firrtl/graph/DiGraph.scala index ee00789e..39016732 100644 --- a/src/main/scala/firrtl/graph/DiGraph.scala +++ b/src/main/scala/firrtl/graph/DiGraph.scala @@ -273,17 +273,13 @@ class DiGraph[T] (val edges: Map[T, Set[T]]) extends DiGraphLike[T] { // paths(v) holds the set of paths from start to v val paths = new mutable.HashMap[T,mutable.Set[Seq[T]]] with mutable.MultiMap[T,Seq[T]] val queue = new mutable.Queue[T] - val visited = new mutable.HashSet[T] + val reachable = reachableFrom(start) paths.addBinding(start,Seq(start)) - queue.enqueue(start) - visited += start + queue += start + queue ++= linearize.filter(reachable.contains(_)) while (!queue.isEmpty) { val current = queue.dequeue for (v <- getEdges(current)) { - if (!visited.contains(v)) { - queue.enqueue(v) - visited += v - } for (p <- paths(current)) { paths.addBinding(v, p :+ v) } -- cgit v1.2.3