llvm/unittests/ADT/DirectedGraphTest.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-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