296 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// This file defines concrete derivations of the directed-graph base classes10// 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() = default;47};48 49using EdgeListTy = SmallVector<DGTestEdge *, 2>;50 51//===--------------------------------------------------------------------===//52// GraphTraits specializations for the DGTest53//===--------------------------------------------------------------------===//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 can63 // 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 connected119 // 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(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 -> N1170 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 185TEST(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 -> N3202 // ^ |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(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 -> N3237 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(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 -+ N4265 // | ^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(llvm::from_range, SCC));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 llvm296