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;
DGTestEdge(DGTestNode & N)40 DGTestEdge(DGTestNode &N) : DGTestEdgeBase(N) {}
41 };
42
43 class DGTestGraph : public DGTestBase {
44 public:
45 DGTestGraph() = default;
~DGTestGraph()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
DGTestGetTargetNodellvm::GraphTraits58 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
getEntryNodellvm::GraphTraits68 static NodeRef getEntryNode(NodeRef N) { return N; }
child_beginllvm::GraphTraits69 static ChildIteratorType child_begin(NodeRef N) {
70 return ChildIteratorType(N->begin(), &DGTestGetTargetNode);
71 }
child_endllvm::GraphTraits72 static ChildIteratorType child_end(NodeRef N) {
73 return ChildIteratorType(N->end(), &DGTestGetTargetNode);
74 }
75
child_edge_beginllvm::GraphTraits76 static ChildEdgeIteratorType child_edge_begin(NodeRef N) {
77 return N->begin();
78 }
child_edge_endllvm::GraphTraits79 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;
getEntryNodellvm::GraphTraits85 static NodeRef getEntryNode(DGTestGraph *DG) { return *DG->begin(); }
nodes_beginllvm::GraphTraits86 static nodes_iterator nodes_begin(DGTestGraph *DG) { return DG->begin(); }
nodes_endllvm::GraphTraits87 static nodes_iterator nodes_end(DGTestGraph *DG) { return DG->end(); }
88 };
89
90 //===--------------------------------------------------------------------===//
91 // Test various modification and query functions.
92 //===--------------------------------------------------------------------===//
93
TEST(DirectedGraphTest,AddAndConnectNodes)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
TEST(DirectedGraphTest,AddRemoveEdge)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
TEST(DirectedGraphTest,hasEdgeTo)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
TEST(DirectedGraphTest,AddRemoveNode)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
TEST(DirectedGraphTest,SCC)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
296