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
23namespace llvm {
24
25/// Represent an edge in the directed graph.
26/// The edge contains the target node it connects to.
27template <class NodeType, class EdgeType> class DGEdge {
28public:
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
56protected:
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.
72template <class NodeType, class EdgeType> class DGNode {
73public:
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
146protected:
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.
172template <class NodeType, class EdgeType> class DirectedGraph {
173protected:
174 using NodeListTy = SmallVector<NodeType *, 10>;
175 using EdgeListTy = SmallVector<EdgeType *, 10>;
176public:
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
272protected:
273 // The list of nodes in the graph.
274 NodeListTy Nodes;
275};
276
277} // namespace llvm
278
279#endif // LLVM_ADT_DIRECTEDGRAPH_H
280