include/llvm/ADT/DirectedGraph.h

   1 //===- llvm/ADT/DirectedGraph.h - Directed Graph ----------------*- 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 the interface and a base class implementation for a
  10 // directed graph.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_ADT_DIRECTEDGRAPH_H
  15 #define LLVM_ADT_DIRECTEDGRAPH_H
  16
  17 #include "llvm/ADT/GraphTraits.h"
  18 #include "llvm/ADT/SetVector.h"
  19 #include "llvm/ADT/SmallVector.h"
  20 #include "llvm/Support/Debug.h"
  21 #include "llvm/Support/raw_ostream.h"
  22
  23 namespace llvm {
  24
  25 /// Represent an edge in the directed graph.
  26 /// The edge contains the target node it connects to.
  27 template <class NodeType, class EdgeType> class DGEdge {
  28 public:
  29   DGEdge() = delete;
  30   /// Create an edge pointing to the given node \p N.
  31   explicit DGEdge(NodeType &N) : TargetNode(N) {}
  32   explicit DGEdge(const DGEdge<NodeType, EdgeType> &E)
  33       : TargetNode(E.TargetNode) {}
  34   DGEdge<NodeType, EdgeType> &operator=(const DGEdge<NodeType, EdgeType> &E) {
  35     TargetNode = E.TargetNode;
  36     return *this;
  37   }
  38
  39   /// Static polymorphism: delegate implementation (via isEqualTo) to the
  40   /// derived class.
  41   bool operator==(const EdgeType &E) const { return getDerived().isEqualTo(E); }
  42   bool operator!=(const EdgeType &E) const { return !operator==(E); }
  43
  44   /// Retrieve the target node this edge connects to.
  45   const NodeType &getTargetNode() const { return TargetNode; }
  46   NodeType &getTargetNode() {
  47     return const_cast<NodeType &>(
  48         static_cast<const DGEdge<NodeType, EdgeType> &>(*this).getTargetNode());
  49   }
  50
  51 protected:
  52   // As the default implementation use address comparison for equality.
  53   bool isEqualTo(const EdgeType &E) const { return this == &E; }
  54
  55   // Cast the 'this' pointer to the derived type and return a reference.
  56   EdgeType &getDerived() { return *static_cast<EdgeType *>(this); }
  57   const EdgeType &getDerived() const {
  58     return *static_cast<const EdgeType *>(this);
  59   }
  60
  61   // The target node this edge connects to.
  62   NodeType &TargetNode;
  63 };
  64
  65 /// Represent a node in the directed graph.
  66 /// The node has a (possibly empty) list of outgoing edges.
  67 template <class NodeType, class EdgeType> class DGNode {
  68 public:
  69   using EdgeListTy = SetVector<EdgeType *>;
  70   using iterator = typename EdgeListTy::iterator;
  71   using const_iterator = typename EdgeListTy::const_iterator;
  72
  73   /// Create a node with a single outgoing edge \p E.
  74   explicit DGNode(EdgeType &E) : Edges() { Edges.insert(&E); }
  75   DGNode() = default;
  76
  77   explicit DGNode(const DGNode<NodeType, EdgeType> &N) : Edges(N.Edges) {}
  78   DGNode(DGNode<NodeType, EdgeType> &&N) : Edges(std::move(N.Edges)) {}
  79
  80   DGNode<NodeType, EdgeType> &operator=(const DGNode<NodeType, EdgeType> &N) {
  81     Edges = N.Edges;
  82     return *this;
  83   }
  84   DGNode<NodeType, EdgeType> &operator=(const DGNode<NodeType, EdgeType> &&N) {
  85     Edges = std::move(N.Edges);
  86     return *this;
  87   }
  88
  89   /// Static polymorphism: delegate implementation (via isEqualTo) to the
  90   /// derived class.
  91   bool operator==(const NodeType &N) const { return getDerived().isEqualTo(N); }
  92   bool operator!=(const NodeType &N) const { return !operator==(N); }
  93
  94   const_iterator begin() const { return Edges.begin(); }
  95   const_iterator end() const { return Edges.end(); }
  96   iterator begin() { return Edges.begin(); }
  97   iterator end() { return Edges.end(); }
  98   const EdgeType &front() const { return *Edges.front(); }
  99   EdgeType &front() { return *Edges.front(); }
 100   const EdgeType &back() const { return *Edges.back(); }
 101   EdgeType &back() { return *Edges.back(); }
 102
 103   /// Collect in \p EL, all the edges from this node to \p N.
 104   /// Return true if at least one edge was found, and false otherwise.
 105   /// Note that this implementation allows more than one edge to connect
 106   /// a given pair of nodes.
 107   bool findEdgesTo(const NodeType &N, SmallVectorImpl<EdgeType *> &EL) const {
 108     assert(EL.empty() && "Expected the list of edges to be empty.");
 109     for (auto *E : Edges)
 110       if (E->getTargetNode() == N)
 111         EL.push_back(E);
 112     return !EL.empty();
 113   }
 114
 115   /// Add the given edge \p E to this node, if it doesn't exist already. Returns
 116   /// true if the edge is added and false otherwise.
 117   bool addEdge(EdgeType &E) { return Edges.insert(&E); }
 118
 119   /// Remove the given edge \p E from this node, if it exists.
 120   void removeEdge(EdgeType &E) { Edges.remove(&E); }
 121
 122   /// Test whether there is an edge that goes from this node to \p N.
 123   bool hasEdgeTo(const NodeType &N) const {
 124     return (findEdgeTo(N) != Edges.end());
 125   }
 126
 127   /// Retrieve the outgoing edges for the node.
 128   const EdgeListTy &getEdges() const { return Edges; }
 129   EdgeListTy &getEdges() {
 130     return const_cast<EdgeListTy &>(
 131         static_cast<const DGNode<NodeType, EdgeType> &>(*this).Edges);
 132   }
 133
 134   /// Clear the outgoing edges.
 135   void clear() { Edges.clear(); }
 136
 137 protected:
 138   // As the default implementation use address comparison for equality.
 139   bool isEqualTo(const NodeType &N) const { return this == &N; }
 140
 141   // Cast the 'this' pointer to the derived type and return a reference.
 142   NodeType &getDerived() { return *static_cast<NodeType *>(this); }
 143   const NodeType &getDerived() const {
 144     return *static_cast<const NodeType *>(this);
 145   }
 146
 147   /// Find an edge to \p N. If more than one edge exists, this will return
 148   /// the first one in the list of edges.
 149   const_iterator findEdgeTo(const NodeType &N) const {
 150     return llvm::find_if(
 151         Edges, [&N](const EdgeType *E) { return E->getTargetNode() == N; });
 152   }
 153
 154   // The list of outgoing edges.
 155   EdgeListTy Edges;
 156 };
 157
 158 /// Directed graph
 159 ///
 160 /// The graph is represented by a table of nodes.
 161 /// Each node contains a (possibly empty) list of outgoing edges.
 162 /// Each edge contains the target node it connects to.
 163 template <class NodeType, class EdgeType> class DirectedGraph {
 164 protected:
 165   using NodeListTy = SmallVector<NodeType *, 10>;
 166   using EdgeListTy = SmallVector<EdgeType *, 10>;
 167 public:
 168   using iterator = typename NodeListTy::iterator;
 169   using const_iterator = typename NodeListTy::const_iterator;
 170   using DGraphType = DirectedGraph<NodeType, EdgeType>;
 171
 172   DirectedGraph() = default;
 173   explicit DirectedGraph(NodeType &N) : Nodes() { addNode(N); }
 174   DirectedGraph(const DGraphType &G) : Nodes(G.Nodes) {}
 175   DirectedGraph(DGraphType &&RHS) : Nodes(std::move(RHS.Nodes)) {}
 176   DGraphType &operator=(const DGraphType &G) {
 177     Nodes = G.Nodes;
 178     return *this;
 179   }
 180   DGraphType &operator=(const DGraphType &&G) {
 181     Nodes = std::move(G.Nodes);
 182     return *this;
 183   }
 184
 185   const_iterator begin() const { return Nodes.begin(); }
 186   const_iterator end() const { return Nodes.end(); }
 187   iterator begin() { return Nodes.begin(); }
 188   iterator end() { return Nodes.end(); }
 189   const NodeType &front() const { return *Nodes.front(); }
 190   NodeType &front() { return *Nodes.front(); }
 191   const NodeType &back() const { return *Nodes.back(); }
 192   NodeType &back() { return *Nodes.back(); }
 193
 194   size_t size() const { return Nodes.size(); }
 195
 196   /// Find the given node \p N in the table.
 197   const_iterator findNode(const NodeType &N) const {
 198     return llvm::find_if(Nodes,
 199                          [&N](const NodeType *Node) { return *Node == N; });
 200   }
 201   iterator findNode(const NodeType &N) {
 202     return const_cast<iterator>(
 203         static_cast<const DGraphType &>(*this).findNode(N));
 204   }
 205
 206   /// Add the given node \p N to the graph if it is not already present.
 207   bool addNode(NodeType &N) {
 208     if (findNode(N) != Nodes.end())
 209       return false;
 210     Nodes.push_back(&N);
 211     return true;
 212   }
 213
 214   /// Collect in \p EL all edges that are coming into node \p N. Return true
 215   /// if at least one edge was found, and false otherwise.
 216   bool findIncomingEdgesToNode(const NodeType &N, SmallVectorImpl<EdgeType*> &EL) const {
 217     assert(EL.empty() && "Expected the list of edges to be empty.");
 218     EdgeListTy TempList;
 219     for (auto *Node : Nodes) {
 220       if (*Node == N)
 221         continue;
 222       Node->findEdgesTo(N, TempList);
 223       EL.insert(EL.end(), TempList.begin(), TempList.end());
 224       TempList.clear();
 225     }
 226     return !EL.empty();
 227   }
 228
 229   /// Remove the given node \p N from the graph. If the node has incoming or
 230   /// outgoing edges, they are also removed. Return true if the node was found
 231   /// and then removed, and false if the node was not found in the graph to
 232   /// begin with.
 233   bool removeNode(NodeType &N) {
 234     iterator IT = findNode(N);
 235     if (IT == Nodes.end())
 236       return false;
 237     // Remove incoming edges.
 238     EdgeListTy EL;
 239     for (auto *Node : Nodes) {
 240       if (*Node == N)
 241         continue;
 242       Node->findEdgesTo(N, EL);
 243       for (auto *E : EL)
 244         Node->removeEdge(*E);
 245       EL.clear();
 246     }
 247     N.clear();
 248     Nodes.erase(IT);
 249     return true;
 250   }
 251
 252   /// Assuming nodes \p Src and \p Dst are already in the graph, connect node \p
 253   /// Src to node \p Dst using the provided edge \p E. Return true if \p Src is
 254   /// not already connected to \p Dst via \p E, and false otherwise.
 255   bool connect(NodeType &Src, NodeType &Dst, EdgeType &E) {
 256     assert(findNode(Src) != Nodes.end() && "Src node should be present.");
 257     assert(findNode(Dst) != Nodes.end() && "Dst node should be present.");
 258     assert((E.getTargetNode() == Dst) &&
 259            "Target of the given edge does not match Dst.");
 260     return Src.addEdge(E);
 261   }
 262
 263 protected:
 264   // The list of nodes in the graph.
 265   NodeListTy Nodes;
 266 };
 267
 268 } // namespace llvm
 269
 270 #endif // LLVM_ADT_DIRECTEDGRAPH_H