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