|
147
|
1 //===- llvm/unittest/ADT/DirectedGraphTest.cpp ------------------*- C++ -*-===//
|
|
|
2 //
|
|
|
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
|
|
|
4 // See https://llvm.org/LICENSE.txt for license information.
|
|
|
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
|
|
|
6 //
|
|
|
7 //===----------------------------------------------------------------------===//
|
|
|
8 //
|
|
|
9 // This file defines concrete derivations of the directed-graph base classes
|
|
|
10 // for testing purposes.
|
|
|
11 //
|
|
|
12 //===----------------------------------------------------------------------===//
|
|
|
13
|
|
|
14 #include "llvm/ADT/DirectedGraph.h"
|
|
|
15 #include "llvm/ADT/GraphTraits.h"
|
|
|
16 #include "llvm/ADT/SCCIterator.h"
|
|
|
17 #include "llvm/ADT/SmallPtrSet.h"
|
|
|
18 #include "gtest/gtest.h"
|
|
|
19
|
|
|
20 namespace llvm {
|
|
|
21
|
|
|
22 //===--------------------------------------------------------------------===//
|
|
|
23 // Derived nodes, edges and graph types based on DirectedGraph.
|
|
|
24 //===--------------------------------------------------------------------===//
|
|
|
25
|
|
|
26 class DGTestNode;
|
|
|
27 class DGTestEdge;
|
|
|
28 using DGTestNodeBase = DGNode<DGTestNode, DGTestEdge>;
|
|
|
29 using DGTestEdgeBase = DGEdge<DGTestNode, DGTestEdge>;
|
|
|
30 using DGTestBase = DirectedGraph<DGTestNode, DGTestEdge>;
|
|
|
31
|
|
|
32 class DGTestNode : public DGTestNodeBase {
|
|
|
33 public:
|
|
|
34 DGTestNode() = default;
|
|
|
35 };
|
|
|
36
|
|
|
37 class DGTestEdge : public DGTestEdgeBase {
|
|
|
38 public:
|
|
|
39 DGTestEdge() = delete;
|
|
|
40 DGTestEdge(DGTestNode &N) : DGTestEdgeBase(N) {}
|
|
|
41 };
|
|
|
42
|
|
|
43 class DGTestGraph : public DGTestBase {
|
|
|
44 public:
|
|
|
45 DGTestGraph() = default;
|
|
|
46 ~DGTestGraph(){};
|
|
|
47 };
|
|
|
48
|
|
|
49 using EdgeListTy = SmallVector<DGTestEdge *, 2>;
|
|
|
50
|
|
|
51 //===--------------------------------------------------------------------===//
|
|
|
52 // GraphTraits specializations for the DGTest
|
|
|
53 //===--------------------------------------------------------------------===//
|
|
|
54
|
|
|
55 template <> struct GraphTraits<DGTestNode *> {
|
|
|
56 using NodeRef = DGTestNode *;
|
|
|
57
|
|
|
58 static DGTestNode *DGTestGetTargetNode(DGEdge<DGTestNode, DGTestEdge> *P) {
|
|
|
59 return &P->getTargetNode();
|
|
|
60 }
|
|
|
61
|
|
|
62 // Provide a mapped iterator so that the GraphTrait-based implementations can
|
|
|
63 // find the target nodes without having to explicitly go through the edges.
|
|
|
64 using ChildIteratorType =
|
|
|
65 mapped_iterator<DGTestNode::iterator, decltype(&DGTestGetTargetNode)>;
|
|
|
66 using ChildEdgeIteratorType = DGTestNode::iterator;
|
|
|
67
|
|
|
68 static NodeRef getEntryNode(NodeRef N) { return N; }
|
|
|
69 static ChildIteratorType child_begin(NodeRef N) {
|
|
|
70 return ChildIteratorType(N->begin(), &DGTestGetTargetNode);
|
|
|
71 }
|
|
|
72 static ChildIteratorType child_end(NodeRef N) {
|
|
|
73 return ChildIteratorType(N->end(), &DGTestGetTargetNode);
|
|
|
74 }
|
|
|
75
|
|
|
76 static ChildEdgeIteratorType child_edge_begin(NodeRef N) {
|
|
|
77 return N->begin();
|
|
|
78 }
|
|
|
79 static ChildEdgeIteratorType child_edge_end(NodeRef N) { return N->end(); }
|
|
|
80 };
|
|
|
81
|
|
|
82 template <>
|
|
|
83 struct GraphTraits<DGTestGraph *> : public GraphTraits<DGTestNode *> {
|
|
|
84 using nodes_iterator = DGTestGraph::iterator;
|
|
|
85 static NodeRef getEntryNode(DGTestGraph *DG) { return *DG->begin(); }
|
|
|
86 static nodes_iterator nodes_begin(DGTestGraph *DG) { return DG->begin(); }
|
|
|
87 static nodes_iterator nodes_end(DGTestGraph *DG) { return DG->end(); }
|
|
|
88 };
|
|
|
89
|
|
|
90 //===--------------------------------------------------------------------===//
|
|
|
91 // Test various modification and query functions.
|
|
|
92 //===--------------------------------------------------------------------===//
|
|
|
93
|
|
|
94 TEST(DirectedGraphTest, AddAndConnectNodes) {
|
|
|
95 DGTestGraph DG;
|
|
|
96 DGTestNode N1, N2, N3;
|
|
|
97 DGTestEdge E1(N1), E2(N2), E3(N3);
|
|
|
98
|
|
|
99 // Check that new nodes can be added successfully.
|
|
|
100 EXPECT_TRUE(DG.addNode(N1));
|
|
|
101 EXPECT_TRUE(DG.addNode(N2));
|
|
|
102 EXPECT_TRUE(DG.addNode(N3));
|
|
|
103
|
|
|
104 // Check that duplicate nodes are not added to the graph.
|
|
|
105 EXPECT_FALSE(DG.addNode(N1));
|
|
|
106
|
|
|
107 // Check that nodes can be connected using valid edges with no errors.
|
|
|
108 EXPECT_TRUE(DG.connect(N1, N2, E2));
|
|
|
109 EXPECT_TRUE(DG.connect(N2, N3, E3));
|
|
|
110 EXPECT_TRUE(DG.connect(N3, N1, E1));
|
|
|
111
|
|
|
112 // The graph looks like this now:
|
|
|
113 //
|
|
|
114 // +---------------+
|
|
|
115 // v |
|
|
|
116 // N1 -> N2 -> N3 -+
|
|
|
117
|
|
|
118 // Check that already connected nodes with the given edge are not connected
|
|
|
119 // again (ie. edges are between nodes are not duplicated).
|
|
|
120 EXPECT_FALSE(DG.connect(N3, N1, E1));
|
|
|
121
|
|
|
122 // Check that there are 3 nodes in the graph.
|
|
|
123 EXPECT_TRUE(DG.size() == 3);
|
|
|
124
|
|
|
125 // Check that the added nodes can be found in the graph.
|
|
|
126 EXPECT_NE(DG.findNode(N3), DG.end());
|
|
|
127
|
|
|
128 // Check that nodes that are not part of the graph are not found.
|
|
|
129 DGTestNode N4;
|
|
|
130 EXPECT_EQ(DG.findNode(N4), DG.end());
|
|
|
131
|
|
|
132 // Check that findIncommingEdgesToNode works correctly.
|
|
|
133 EdgeListTy EL;
|
|
|
134 EXPECT_TRUE(DG.findIncomingEdgesToNode(N1, EL));
|
|
|
135 EXPECT_TRUE(EL.size() == 1);
|
|
|
136 EXPECT_EQ(*EL[0], E1);
|
|
|
137 }
|
|
|
138
|
|
|
139 TEST(DirectedGraphTest, AddRemoveEdge) {
|
|
|
140 DGTestGraph DG;
|
|
|
141 DGTestNode N1, N2, N3;
|
|
|
142 DGTestEdge E1(N1), E2(N2), E3(N3);
|
|
|
143 DG.addNode(N1);
|
|
|
144 DG.addNode(N2);
|
|
|
145 DG.addNode(N3);
|
|
|
146 DG.connect(N1, N2, E2);
|
|
|
147 DG.connect(N2, N3, E3);
|
|
|
148 DG.connect(N3, N1, E1);
|
|
|
149
|
|
|
150 // The graph looks like this now:
|
|
|
151 //
|
|
|
152 // +---------------+
|
|
|
153 // v |
|
|
|
154 // N1 -> N2 -> N3 -+
|
|
|
155
|
|
|
156 // Check that there are 3 nodes in the graph.
|
|
|
157 EXPECT_TRUE(DG.size() == 3);
|
|
|
158
|
|
|
159 // Check that the target nodes of the edges are correct.
|
|
|
160 EXPECT_EQ(E1.getTargetNode(), N1);
|
|
|
161 EXPECT_EQ(E2.getTargetNode(), N2);
|
|
|
162 EXPECT_EQ(E3.getTargetNode(), N3);
|
|
|
163
|
|
|
164 // Remove the edge from N1 to N2.
|
|
|
165 N1.removeEdge(E2);
|
|
|
166
|
|
|
167 // The graph looks like this now:
|
|
|
168 //
|
|
|
169 // N2 -> N3 -> N1
|
|
|
170
|
|
|
171 // Check that there are no incoming edges to N2.
|
|
|
172 EdgeListTy EL;
|
|
|
173 EXPECT_FALSE(DG.findIncomingEdgesToNode(N2, EL));
|
|
|
174 EXPECT_TRUE(EL.empty());
|
|
|
175
|
|
|
176 // Put the edge from N1 to N2 back in place.
|
|
|
177 N1.addEdge(E2);
|
|
|
178
|
|
|
179 // Check that E2 is the only incoming edge to N2.
|
|
|
180 EL.clear();
|
|
|
181 EXPECT_TRUE(DG.findIncomingEdgesToNode(N2, EL));
|
|
|
182 EXPECT_EQ(*EL[0], E2);
|
|
|
183 }
|
|
|
184
|
|
|
185 TEST(DirectedGraphTest, hasEdgeTo) {
|
|
|
186 DGTestGraph DG;
|
|
|
187 DGTestNode N1, N2, N3;
|
|
|
188 DGTestEdge E1(N1), E2(N2), E3(N3), E4(N1);
|
|
|
189 DG.addNode(N1);
|
|
|
190 DG.addNode(N2);
|
|
|
191 DG.addNode(N3);
|
|
|
192 DG.connect(N1, N2, E2);
|
|
|
193 DG.connect(N2, N3, E3);
|
|
|
194 DG.connect(N3, N1, E1);
|
|
|
195 DG.connect(N2, N1, E4);
|
|
|
196
|
|
|
197 // The graph looks like this now:
|
|
|
198 //
|
|
|
199 // +-----+
|
|
|
200 // v |
|
|
|
201 // N1 -> N2 -> N3
|
|
|
202 // ^ |
|
|
|
203 // +-----------+
|
|
|
204
|
|
|
205 EXPECT_TRUE(N2.hasEdgeTo(N1));
|
|
|
206 EXPECT_TRUE(N3.hasEdgeTo(N1));
|
|
|
207 }
|
|
|
208
|
|
|
209 TEST(DirectedGraphTest, AddRemoveNode) {
|
|
|
210 DGTestGraph DG;
|
|
|
211 DGTestNode N1, N2, N3;
|
|
|
212 DGTestEdge E1(N1), E2(N2), E3(N3);
|
|
|
213 DG.addNode(N1);
|
|
|
214 DG.addNode(N2);
|
|
|
215 DG.addNode(N3);
|
|
|
216 DG.connect(N1, N2, E2);
|
|
|
217 DG.connect(N2, N3, E3);
|
|
|
218 DG.connect(N3, N1, E1);
|
|
|
219
|
|
|
220 // The graph looks like this now:
|
|
|
221 //
|
|
|
222 // +---------------+
|
|
|
223 // v |
|
|
|
224 // N1 -> N2 -> N3 -+
|
|
|
225
|
|
|
226 // Check that there are 3 nodes in the graph.
|
|
|
227 EXPECT_TRUE(DG.size() == 3);
|
|
|
228
|
|
|
229 // Check that a node in the graph can be removed, but not more than once.
|
|
|
230 EXPECT_TRUE(DG.removeNode(N1));
|
|
|
231 EXPECT_EQ(DG.findNode(N1), DG.end());
|
|
|
232 EXPECT_FALSE(DG.removeNode(N1));
|
|
|
233
|
|
|
234 // The graph looks like this now:
|
|
|
235 //
|
|
|
236 // N2 -> N3
|
|
|
237
|
|
|
238 // Check that there are 2 nodes in the graph and only N2 is connected to N3.
|
|
|
239 EXPECT_TRUE(DG.size() == 2);
|
|
|
240 EXPECT_TRUE(N3.getEdges().empty());
|
|
|
241 EdgeListTy EL;
|
|
|
242 EXPECT_FALSE(DG.findIncomingEdgesToNode(N2, EL));
|
|
|
243 EXPECT_TRUE(EL.empty());
|
|
|
244 }
|
|
|
245
|
|
|
246 TEST(DirectedGraphTest, SCC) {
|
|
|
247
|
|
|
248 DGTestGraph DG;
|
|
|
249 DGTestNode N1, N2, N3, N4;
|
|
|
250 DGTestEdge E1(N1), E2(N2), E3(N3), E4(N4);
|
|
|
251 DG.addNode(N1);
|
|
|
252 DG.addNode(N2);
|
|
|
253 DG.addNode(N3);
|
|
|
254 DG.addNode(N4);
|
|
|
255 DG.connect(N1, N2, E2);
|
|
|
256 DG.connect(N2, N3, E3);
|
|
|
257 DG.connect(N3, N1, E1);
|
|
|
258 DG.connect(N3, N4, E4);
|
|
|
259
|
|
|
260 // The graph looks like this now:
|
|
|
261 //
|
|
|
262 // +---------------+
|
|
|
263 // v |
|
|
|
264 // N1 -> N2 -> N3 -+ N4
|
|
|
265 // | ^
|
|
|
266 // +--------+
|
|
|
267
|
|
|
268 // Test that there are two SCCs:
|
|
|
269 // 1. {N1, N2, N3}
|
|
|
270 // 2. {N4}
|
|
|
271 using NodeListTy = SmallPtrSet<DGTestNode *, 3>;
|
|
|
272 SmallVector<NodeListTy, 4> ListOfSCCs;
|
|
|
273 for (auto &SCC : make_range(scc_begin(&DG), scc_end(&DG)))
|
|
|
274 ListOfSCCs.push_back(NodeListTy(SCC.begin(), SCC.end()));
|
|
|
275
|
|
|
276 EXPECT_TRUE(ListOfSCCs.size() == 2);
|
|
|
277
|
|
|
278 for (auto &SCC : ListOfSCCs) {
|
|
|
279 if (SCC.size() > 1)
|
|
|
280 continue;
|
|
|
281 EXPECT_TRUE(SCC.size() == 1);
|
|
|
282 EXPECT_TRUE(SCC.count(&N4) == 1);
|
|
|
283 }
|
|
|
284 for (auto &SCC : ListOfSCCs) {
|
|
|
285 if (SCC.size() <= 1)
|
|
|
286 continue;
|
|
|
287 EXPECT_TRUE(SCC.size() == 3);
|
|
|
288 EXPECT_TRUE(SCC.count(&N1) == 1);
|
|
|
289 EXPECT_TRUE(SCC.count(&N2) == 1);
|
|
|
290 EXPECT_TRUE(SCC.count(&N3) == 1);
|
|
|
291 EXPECT_TRUE(SCC.count(&N4) == 0);
|
|
|
292 }
|
|
|
293 }
|
|
|
294
|
|
|
295 } // namespace llvm
|
