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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
|
// SPDX-License-Identifier: Apache-2.0
package firrtlTests.graph
import firrtl.graph._
import firrtl.testutils._
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)
}
"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)
}
"reachableFrom" should "omit the queried node if no self-path exists" in {
degenerateGraph.reachableFrom("a") shouldBe empty
acyclicGraph.reachableFrom("b") should contain theSameElementsAs Vector("d", "e")
}
"reachableFrom" should "include the queried node if it is included in a cycle" in {
cyclicGraph.reachableFrom("b") should contain theSameElementsAs Vector("a", "b", "c", "d")
}
}
|
