diff options
| -rw-r--r-- | src/main/scala/firrtl/graph/DiGraph.scala | 24 | ||||
| -rw-r--r-- | src/main/scala/firrtl/graph/RenderDiGraph.scala | 235 | ||||
| -rw-r--r-- | src/test/scala/firrtlTests/graph/DiGraphTests.scala | 48 |
3 files changed, 303 insertions, 4 deletions
diff --git a/src/main/scala/firrtl/graph/DiGraph.scala b/src/main/scala/firrtl/graph/DiGraph.scala index 9cfcad52..1cac34b5 100644 --- a/src/main/scala/firrtl/graph/DiGraph.scala +++ b/src/main/scala/firrtl/graph/DiGraph.scala @@ -109,6 +109,30 @@ 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 + } + /** Performs breadth-first search on the directed graph * * @param root the start node diff --git a/src/main/scala/firrtl/graph/RenderDiGraph.scala b/src/main/scala/firrtl/graph/RenderDiGraph.scala new file mode 100644 index 00000000..812a86ef --- /dev/null +++ b/src/main/scala/firrtl/graph/RenderDiGraph.scala @@ -0,0 +1,235 @@ +// See LICENSE for license details. + +package firrtl.graph + +import scala.collection.mutable + +/** + * Implement a really simple graphviz dot renderer for a digraph + * There are three main renderers currently + * - + * + * @param diGraph The DiGraph to be rendered + * @param graphName Name of the graph, when shown in viewer + * @param rankDir Graph orientation, default is LR (left to right), most common alternative is TB (top to bottom) + * @tparam T The type of the Node. + */ +class RenderDiGraph[T <: Any](diGraph: DiGraph[T], graphName: String = "", rankDir: String = "LR") { + + + /** + * override this to change the default way a node is displayed. Default is toString surrounded by double quotes + * {{{ + * val rend = new RenderDiGraph(graph, "alice") { + * override def renderNode(node: Symbol): String = s"\"${symbol.name}\"" + * } + * }}} + */ + def renderNode(node: T): String = { + s""""${node.toString}"""" + } + + /** + * This finds a loop in a DiGraph if one exists and returns nodes + * @note there is no way to currently to specify a particular loop + * @return + */ + def findOneLoop: Set[T] = { + var path = Seq.empty[T] + + try { + diGraph.linearize + } + catch { + case cyclicException: CyclicException => + val node = cyclicException.node.asInstanceOf[T] + path = diGraph.findLoopAtNode(node) + + case t: Throwable => + throw t + + } + path.toSet + } + + /** + * Searches a DiGraph for a cycle. The first one found will be rendered as a graph that contains + * only the nodes in the cycle plus the neighbors of those nodes. + * @return a string that can be used as input to the dot command, string is empty if no loop + */ + def showOnlyTheLoopAsDot: String = { + // finds the loop + + val loop = findOneLoop + + if(loop.nonEmpty) { + + // Find all the children of the nodes in the loop + val childrenFound = diGraph.getEdgeMap.flatMap { + case (node, children) if loop.contains(node) => children + case _ => Seq.empty + }.toSet + + // Create a new DiGraph containing only loop and direct children or parents + val edgeData = diGraph.getEdgeMap + val newEdgeData = edgeData.flatMap { case (node, children) => + if(loop.contains(node)) { + Some(node -> children) + } + else if(childrenFound.contains(node)) { + Some(node -> children.intersect(loop)) + } + else { + val newChildren = children.intersect(loop) + if(newChildren.nonEmpty) { + Some(node -> newChildren) + } + else { + None + } + } + } + + val justLoop = DiGraph(newEdgeData) + val newRenderer = new RenderDiGraph(justLoop, graphName, rankDir) { + override def renderNode(node: T): String = { + super.renderNode(node) + } + } + newRenderer.toDotWithLoops(loop, getRankedNodes) + } + else { + "" + } + } + + /** + * Convert this graph into input for the graphviz dot program + * @return A string representation of the digraph in dot notation + */ + def toDot: String = { + val s = new mutable.StringBuilder() + + s.append(s"digraph $graphName {\n") + s.append(s""" rankdir="$rankDir";""" + "\n") + + val edges = diGraph.getEdgeMap + + edges.foreach { case (parent, children) => + children.foreach { child => + s.append(s""" ${renderNode(parent)} -> ${renderNode(child)};""" + "\n") + } + } + s.append("}\n") + s.toString + } + + /** + * Convert this graph into input for the graphviz dot program, but with a + * loop,if present, highlighted in red. + * @return string that is a graphviz digraph, but with loops highlighted + */ + def toDotWithLoops(loopedNodes: Set[T], rankedNodes: mutable.ArrayBuffer[Seq[T]]): String = { + val s = new mutable.StringBuilder() + val allNodes = new mutable.HashSet[T] + + s.append(s"digraph $graphName {\n") + s.append(s""" rankdir="$rankDir";""" + "\n") + + val edges = diGraph.getEdgeMap + + edges.foreach { case (parent, children) => + allNodes += parent + allNodes ++= children + + children.foreach { child => + val highlight = if(loopedNodes.contains(parent) && loopedNodes.contains(child)) { + "[color=red,penwidth=3.0]" + } + else { + "" + } + s.append(s""" ${renderNode(parent)} -> ${renderNode(child)}$highlight;""" + "\n") + } + } + + val paredRankedNodes = rankedNodes.flatMap { nodes => + val newNodes = nodes.filter(allNodes.contains) + if(newNodes.nonEmpty) { Some(newNodes) } else { None } + } + + paredRankedNodes.foreach { nodesAtRank => + s.append(s""" { rank=same; ${nodesAtRank.map(renderNode).mkString(" ")} };""" + "\n") + } + + s.append("}\n") + s.toString + } + + /** + * Creates a series of Seq of nodes for each minimum depth that those + * are from the sources of this graph. + * @return + */ + private def getRankedNodes: mutable.ArrayBuffer[Seq[T]] = { + val alreadyVisited = new mutable.HashSet[T]() + val rankNodes = new mutable.ArrayBuffer[Seq[T]]() + + def walkByRank(nodes: Seq[T], rankNumber: Int = 0): Unit = { + rankNodes.append(nodes) + + alreadyVisited ++= nodes + + val nextNodes = nodes.flatMap { node => + diGraph.getEdges(node) + }.filterNot(alreadyVisited.contains).distinct + + if(nextNodes.nonEmpty) { + walkByRank(nextNodes, rankNumber + 1) + } + } + + walkByRank(diGraph.findSources.toSeq) + rankNodes + } + /** + * Convert this graph into input for the graphviz dot program. + * It tries to align nodes in columns based + * on their minimum distance to a source. + * Can also be faster and better behaved on large graphs + * @return string that is a graphviz digraph + */ + def toDotRanked: String = { + val s = new mutable.StringBuilder() + val alreadyVisited = new mutable.HashSet[T]() + val rankNodes = new mutable.ArrayBuffer[Seq[T]]() + + def walkByRank(nodes: Seq[T], rankNumber: Int = 0): Unit = { + rankNodes.append(nodes) + + alreadyVisited ++= nodes + + val nextNodes = nodes.flatMap { node => + val children = diGraph.getEdges(node) + + s.append(s""" ${renderNode(node)} -> { ${children.map(renderNode).mkString(" ")} };""" + "\n") + + children + }.filterNot(alreadyVisited.contains).distinct + + if(nextNodes.nonEmpty) { + walkByRank(nextNodes, rankNumber + 1) + } + } + + s.append(s"digraph {\n") + s.append(s""" rankdir="$rankDir";""" + "\n") + + walkByRank(diGraph.findSources.toSeq) + rankNodes.foreach { nodesAtRank => + s.append(s""" { rank=same; ${nodesAtRank.map(renderNode).mkString(" ")} };""" + "\n") + } + s.append("}\n") + s.toString + } +} diff --git a/src/test/scala/firrtlTests/graph/DiGraphTests.scala b/src/test/scala/firrtlTests/graph/DiGraphTests.scala index 52ded253..d3553a23 100644 --- a/src/test/scala/firrtlTests/graph/DiGraphTests.scala +++ b/src/test/scala/firrtlTests/graph/DiGraphTests.scala @@ -2,13 +2,10 @@ package firrtlTests.graph -import java.io._ -import org.scalatest._ -import org.scalatest.prop._ -import org.scalatest.Matchers._ import firrtl.graph._ import firrtlTests._ +//scalastyle:off magic.number class DiGraphTests extends FirrtlFlatSpec { val acyclicGraph = DiGraph(Map( @@ -110,4 +107,47 @@ class DiGraphTests extends FirrtlFlatSpec { val graph = DiGraph(Map("a" -> Set[String](), "b" -> Set[String]())) graph.linearize.toSet should be (graph.getVertices) } + + "acyclic graph" should "be rendered" in { + val acyclicGraph2 = DiGraph(Map( + "a" -> Set("b","c"), + "b" -> Set("d", "x", "z"), + "c" -> Set("d", "x"), + "d" -> Set("e", "k", "l"), + "x" -> Set("e"), + "z" -> Set("e", "j"), + "j" -> Set("k", "l", "c"), + "k" -> Set("l"), + "l" -> Set("e"), + "e" -> Set.empty[String] + )) + val render = new RenderDiGraph(acyclicGraph2) + val dotLines = render.toDotRanked.split("\n") + + dotLines.count(s => s.contains("rank=same")) should be (4) + dotLines.exists(s => s.contains(""""b" -> { "d" "x" "z" };""")) should be (true) + dotLines.exists(s => s.contains("""rankdir="LR";""")) should be (true) + } + + "subgraphs containing cycles" should "be rendered with loop edges in red, can override orientation" in { + val cyclicGraph2 = DiGraph(Map( + "a" -> Set("b","c"), + "b" -> Set("d", "x", "z"), + "c" -> Set("d", "x"), + "d" -> Set("e", "k", "l"), + "x" -> Set("e"), + "z" -> Set("e", "j"), + "j" -> Set("k", "l", "c"), + "k" -> Set("l"), + "l" -> Set("e"), + "e" -> Set("c") + )) + val render = new RenderDiGraph(cyclicGraph2, rankDir = "TB") + val dotLines = render.showOnlyTheLoopAsDot.split("\n") + + dotLines.count(s => s.contains("rank=same")) should be (4) + dotLines.count(s => s.contains("""[color=red,penwidth=3.0];""")) should be (3) + dotLines.exists(s => s.contains(""""d" -> "k";""")) should be (true) + dotLines.exists(s => s.contains("""rankdir="TB";""")) should be (true) + } } |