Add graph summation "+" to DiGraph (#744)

* Add DiGraph sum and DiGraph sum test

Signed-off-by: Schuyler Eldridge <schuyler.eldridge@ibm.com>

* Make DiGraph sum deterministic

Signed-off-by: Schuyler Eldridge <schuyler.eldridge@ibm.com>

* Remove ordered hashes/sets from DiGraphTests

Signed-off-by: Schuyler Eldridge <schuyler.eldridge@ibm.com>

2 files changed, 25 insertions, 0 deletions

diff --git a/src/main/scala/firrtl/graph/DiGraph.scala b/src/main/scala/firrtl/graph/DiGraph.scala
index 6538c880..6dad56d7 100644
--- a/src/main/scala/firrtl/graph/DiGraph.scala
+++ b/src/main/scala/firrtl/graph/DiGraph.scala
@@ -308,6 +308,17 @@ class DiGraph[T] private[graph] (private[graph] val edges: LinkedHashMap[T, Link
     edges.foreach({ case (k, v) => eprime(f(k)) ++= v.map(f(_)) })
     new DiGraph(eprime)
   }
+
+  /** Graph sum of `this` and `that`
+    *
+    * @param that a second DiGraph[T]
+    * @return a DiGraph[T] containing all vertices and edges of each graph
+    */
+  def +(that: DiGraph[T]): DiGraph[T] = {
+    val eprime = edges.clone
+    that.edges.map({ case (k, v) => eprime.getOrElseUpdate(k, new LinkedHashSet[T]) ++= v })
+    new DiGraph(eprime)
+  }
 }
 
 class MutableDiGraph[T] extends DiGraph[T](new LinkedHashMap[T, LinkedHashSet[T]]) {
diff --git a/src/test/scala/firrtlTests/graph/DiGraphTests.scala b/src/test/scala/firrtlTests/graph/DiGraphTests.scala
index b9f51699..147b22d7 100644
--- a/src/test/scala/firrtlTests/graph/DiGraphTests.scala
+++ b/src/test/scala/firrtlTests/graph/DiGraphTests.scala
@@ -58,4 +58,18 @@ class DiGraphTests extends FirrtlFlatSpec {
     tupleGraph.transformNodes(_._1).getEdgeMap should contain ("a" -> Set("b", "c"))
   }
 
+  "Graph summation" should "be order-wise equivalent to original" in {
+    val first = acyclicGraph.subgraph(Set("a", "b", "c"))
+    val second = acyclicGraph.subgraph(Set("b", "c", "d", "e"))
+
+    (first + second).getEdgeMap should equal (acyclicGraph.getEdgeMap)
+  }
+
+  it should "be idempotent" in {
+    val first = acyclicGraph.subgraph(Set("a", "b", "c"))
+    val second = acyclicGraph.subgraph(Set("b", "c", "d", "e"))
+
+    (first + second + second + second).getEdgeMap should equal (acyclicGraph.getEdgeMap)
+  }
+
 }