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
20namespace llvm {
21
22//===--------------------------------------------------------------------===//
23// Derived nodes, edges and graph types based on DirectedGraph.
24//===--------------------------------------------------------------------===//
25
26class DGTestNode;
27class DGTestEdge;
28using DGTestNodeBase = DGNode<DGTestNode, DGTestEdge>;
29using DGTestEdgeBase = DGEdge<DGTestNode, DGTestEdge>;
30using DGTestBase = DirectedGraph<DGTestNode, DGTestEdge>;
31
32class DGTestNode : public DGTestNodeBase {
33public:
34 DGTestNode() = default;
35};
36
37class DGTestEdge : public DGTestEdgeBase {
38public:
39 DGTestEdge() = delete;
40 DGTestEdge(DGTestNode &N) : DGTestEdgeBase(N) {}
41};
42
43class DGTestGraph : public DGTestBase {
44public:
45 DGTestGraph() = default;
46 ~DGTestGraph(){};
47};
48
49using EdgeListTy = SmallVector<DGTestEdge *, 2>;
50
51//===--------------------------------------------------------------------===//
52// GraphTraits specializations for the DGTest
53//===--------------------------------------------------------------------===//
54
55template <> 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
82template <>
83struct 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
94TEST(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
139TEST(DirectedGraphTest, AddRemoveEdge) {
140 DGTestGraph DG;
141 DGTestNode N1, N2, N3;
142 DGTestEdge E1(N1), E2(N2), E3(N3);
143 DG.addNode(N&: N1);
144 DG.addNode(N&: N2);
145 DG.addNode(N&: N3);
146 DG.connect(Src&: N1, Dst&: N2, E&: E2);
147 DG.connect(Src&: N2, Dst&: N3, E&: E3);
148 DG.connect(Src&: N3, Dst&: N1, E&: 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(E&: 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(E&: 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
185TEST(DirectedGraphTest, hasEdgeTo) {
186 DGTestGraph DG;
187 DGTestNode N1, N2, N3;
188 DGTestEdge E1(N1), E2(N2), E3(N3), E4(N1);
189 DG.addNode(N&: N1);
190 DG.addNode(N&: N2);
191 DG.addNode(N&: N3);
192 DG.connect(Src&: N1, Dst&: N2, E&: E2);
193 DG.connect(Src&: N2, Dst&: N3, E&: E3);
194 DG.connect(Src&: N3, Dst&: N1, E&: E1);
195 DG.connect(Src&: N2, Dst&: N1, E&: 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
209TEST(DirectedGraphTest, AddRemoveNode) {
210 DGTestGraph DG;
211 DGTestNode N1, N2, N3;
212 DGTestEdge E1(N1), E2(N2), E3(N3);
213 DG.addNode(N&: N1);
214 DG.addNode(N&: N2);
215 DG.addNode(N&: N3);
216 DG.connect(Src&: N1, Dst&: N2, E&: E2);
217 DG.connect(Src&: N2, Dst&: N3, E&: E3);
218 DG.connect(Src&: N3, Dst&: N1, E&: 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
246TEST(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(N&: N1);
252 DG.addNode(N&: N2);
253 DG.addNode(N&: N3);
254 DG.addNode(N&: N4);
255 DG.connect(Src&: N1, Dst&: N2, E&: E2);
256 DG.connect(Src&: N2, Dst&: N3, E&: E3);
257 DG.connect(Src&: N3, Dst&: N1, E&: E1);
258 DG.connect(Src&: N3, Dst&: N4, E&: 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(x: scc_begin(G: &DG), y: scc_end(G: &DG)))
274 ListOfSCCs.push_back(Elt: 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

source code of llvm/unittests/ADT/DirectedGraphTest.cpp