1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
|
// See LICENSE for license details.
package firrtlTests.graph
import java.io._
import org.scalatest._
import org.scalatest.prop._
import org.scalatest.Matchers._
import firrtl.graph._
import firrtlTests._
class DiGraphTests extends FirrtlFlatSpec {
val acyclicGraph = DiGraph(Map(
"a" -> Set("b","c"),
"b" -> Set("d"),
"c" -> Set("d"),
"d" -> Set("e"),
"e" -> Set.empty[String]))
val reversedAcyclicGraph = DiGraph(Map(
"a" -> Set.empty[String],
"b" -> Set("a"),
"c" -> Set("a"),
"d" -> Set("b", "c"),
"e" -> Set("d")))
val cyclicGraph = DiGraph(Map(
"a" -> Set("b","c"),
"b" -> Set("d"),
"c" -> Set("d"),
"d" -> Set("a")))
val tupleGraph = DiGraph(Map(
("a", 0) -> Set(("b", 2)),
("a", 1) -> Set(("c", 3)),
("b", 2) -> Set.empty[(String, Int)],
("c", 3) -> Set.empty[(String, Int)]
))
val degenerateGraph = DiGraph(Map("a" -> Set.empty[String]))
"A graph without cycles" should "have NOT SCCs" in {
acyclicGraph.findSCCs.filter(_.length > 1) shouldBe empty
}
"A graph with cycles" should "have SCCs" in {
cyclicGraph.findSCCs.filter(_.length > 1) should not be empty
}
"Asking a DiGraph for a path that exists" should "work" in {
acyclicGraph.path("a","e") should not be empty
}
"Asking a DiGraph for a path from one node to another with no path" should "error" in {
an [PathNotFoundException] should be thrownBy acyclicGraph.path("e","a")
}
"The first element in a linearized graph with a single root node" should "be the root" in {
acyclicGraph.linearize.head should equal ("a")
}
"A DiGraph with a cycle" should "error when linearized" in {
a [CyclicException] should be thrownBy cyclicGraph.linearize
}
"CyclicExceptions" should "contain information about the cycle" in {
val c = the [CyclicException] thrownBy {
cyclicGraph.linearize
}
c.getMessage.contains("found at a") should be (true)
c.node.asInstanceOf[String] should be ("a")
}
"Reversing a graph" should "reverse all of the edges" in {
acyclicGraph.reverse.getEdgeMap should equal (reversedAcyclicGraph.getEdgeMap)
}
"Reversing a graph with no edges" should "equal the graph itself" in {
degenerateGraph.getEdgeMap should equal (degenerateGraph.reverse.getEdgeMap)
}
"transformNodes" should "combine vertices that collide, not drop them" in {
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)
}
"linearize" should "not cause a stack overflow on very large graphs" in {
// Graph of 0 -> 1, 1 -> 2, etc.
val N = 10000
val edges = (1 to N).zipWithIndex.map({ case (n, idx) => idx -> Set(n)}).toMap
val bigGraph = DiGraph(edges + (N -> Set.empty[Int]))
bigGraph.linearize should be (0 to N)
}
it should "work on multi-rooted graphs" in {
val graph = DiGraph(Map("a" -> Set[String](), "b" -> Set[String]()))
graph.linearize.toSet should be (graph.getVertices)
}
}
|
