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
296