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