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(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 | |
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(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 | |
209 | TEST(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 | |
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(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 | |