aboutsummaryrefslogtreecommitdiffstats
path: root/contrib/libs/llvm16/include/llvm/ADT/DirectedGraph.h
blob: bc560c4f27c45a541a2b5468bbfc6635264356d8 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
#pragma once

#ifdef __GNUC__
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wunused-parameter"
#endif

//===- llvm/ADT/DirectedGraph.h - Directed Graph ----------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
///
/// \file
/// This file defines the interface and a base class implementation for a
/// directed graph.
///
//===----------------------------------------------------------------------===//

#ifndef LLVM_ADT_DIRECTEDGRAPH_H
#define LLVM_ADT_DIRECTEDGRAPH_H

#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"

namespace llvm {

/// Represent an edge in the directed graph.
/// The edge contains the target node it connects to.
template <class NodeType, class EdgeType> class DGEdge {
public:
  DGEdge() = delete;
  /// Create an edge pointing to the given node \p N.
  explicit DGEdge(NodeType &N) : TargetNode(N) {}
  explicit DGEdge(const DGEdge<NodeType, EdgeType> &E)
      : TargetNode(E.TargetNode) {}
  DGEdge<NodeType, EdgeType> &operator=(const DGEdge<NodeType, EdgeType> &E) {
    TargetNode = E.TargetNode;
    return *this;
  }

  /// Static polymorphism: delegate implementation (via isEqualTo) to the
  /// derived class.
  bool operator==(const DGEdge &E) const {
    return getDerived().isEqualTo(E.getDerived());
  }
  bool operator!=(const DGEdge &E) const { return !operator==(E); }

  /// Retrieve the target node this edge connects to.
  const NodeType &getTargetNode() const { return TargetNode; }
  NodeType &getTargetNode() {
    return const_cast<NodeType &>(
        static_cast<const DGEdge<NodeType, EdgeType> &>(*this).getTargetNode());
  }

  /// Set the target node this edge connects to.
  void setTargetNode(const NodeType &N) { TargetNode = N; }

protected:
  // As the default implementation use address comparison for equality.
  bool isEqualTo(const EdgeType &E) const { return this == &E; }

  // Cast the 'this' pointer to the derived type and return a reference.
  EdgeType &getDerived() { return *static_cast<EdgeType *>(this); }
  const EdgeType &getDerived() const {
    return *static_cast<const EdgeType *>(this);
  }

  // The target node this edge connects to.
  NodeType &TargetNode;
};

/// Represent a node in the directed graph.
/// The node has a (possibly empty) list of outgoing edges.
template <class NodeType, class EdgeType> class DGNode {
public:
  using EdgeListTy = SetVector<EdgeType *>;
  using iterator = typename EdgeListTy::iterator;
  using const_iterator = typename EdgeListTy::const_iterator;

  /// Create a node with a single outgoing edge \p E.
  explicit DGNode(EdgeType &E) : Edges() { Edges.insert(&E); }
  DGNode() = default;

  explicit DGNode(const DGNode<NodeType, EdgeType> &N) : Edges(N.Edges) {}
  DGNode(DGNode<NodeType, EdgeType> &&N) : Edges(std::move(N.Edges)) {}

  DGNode<NodeType, EdgeType> &operator=(const DGNode<NodeType, EdgeType> &N) {
    Edges = N.Edges;
    return *this;
  }
  DGNode<NodeType, EdgeType> &operator=(const DGNode<NodeType, EdgeType> &&N) {
    Edges = std::move(N.Edges);
    return *this;
  }

  /// Static polymorphism: delegate implementation (via isEqualTo) to the
  /// derived class.
  friend bool operator==(const NodeType &M, const NodeType &N) {
    return M.isEqualTo(N);
  }
  friend bool operator!=(const NodeType &M, const NodeType &N) {
    return !(M == N);
  }

  const_iterator begin() const { return Edges.begin(); }
  const_iterator end() const { return Edges.end(); }
  iterator begin() { return Edges.begin(); }
  iterator end() { return Edges.end(); }
  const EdgeType &front() const { return *Edges.front(); }
  EdgeType &front() { return *Edges.front(); }
  const EdgeType &back() const { return *Edges.back(); }
  EdgeType &back() { return *Edges.back(); }

  /// Collect in \p EL, all the edges from this node to \p N.
  /// Return true if at least one edge was found, and false otherwise.
  /// Note that this implementation allows more than one edge to connect
  /// a given pair of nodes.
  bool findEdgesTo(const NodeType &N, SmallVectorImpl<EdgeType *> &EL) const {
    assert(EL.empty() && "Expected the list of edges to be empty.");
    for (auto *E : Edges)
      if (E->getTargetNode() == N)
        EL.push_back(E);
    return !EL.empty();
  }

  /// Add the given edge \p E to this node, if it doesn't exist already. Returns
  /// true if the edge is added and false otherwise.
  bool addEdge(EdgeType &E) { return Edges.insert(&E); }

  /// Remove the given edge \p E from this node, if it exists.
  void removeEdge(EdgeType &E) { Edges.remove(&E); }

  /// Test whether there is an edge that goes from this node to \p N.
  bool hasEdgeTo(const NodeType &N) const {
    return (findEdgeTo(N) != Edges.end());
  }

  /// Retrieve the outgoing edges for the node.
  const EdgeListTy &getEdges() const { return Edges; }
  EdgeListTy &getEdges() {
    return const_cast<EdgeListTy &>(
        static_cast<const DGNode<NodeType, EdgeType> &>(*this).Edges);
  }

  /// Clear the outgoing edges.
  void clear() { Edges.clear(); }

protected:
  // As the default implementation use address comparison for equality.
  bool isEqualTo(const NodeType &N) const { return this == &N; }

  // Cast the 'this' pointer to the derived type and return a reference.
  NodeType &getDerived() { return *static_cast<NodeType *>(this); }
  const NodeType &getDerived() const {
    return *static_cast<const NodeType *>(this);
  }

  /// Find an edge to \p N. If more than one edge exists, this will return
  /// the first one in the list of edges.
  const_iterator findEdgeTo(const NodeType &N) const {
    return llvm::find_if(
        Edges, [&N](const EdgeType *E) { return E->getTargetNode() == N; });
  }

  // The list of outgoing edges.
  EdgeListTy Edges;
};

/// Directed graph
///
/// The graph is represented by a table of nodes.
/// Each node contains a (possibly empty) list of outgoing edges.
/// Each edge contains the target node it connects to.
template <class NodeType, class EdgeType> class DirectedGraph {
protected:
  using NodeListTy = SmallVector<NodeType *, 10>;
  using EdgeListTy = SmallVector<EdgeType *, 10>;
public:
  using iterator = typename NodeListTy::iterator;
  using const_iterator = typename NodeListTy::const_iterator;
  using DGraphType = DirectedGraph<NodeType, EdgeType>;

  DirectedGraph() = default;
  explicit DirectedGraph(NodeType &N) : Nodes() { addNode(N); }
  DirectedGraph(const DGraphType &G) : Nodes(G.Nodes) {}
  DirectedGraph(DGraphType &&RHS) : Nodes(std::move(RHS.Nodes)) {}
  DGraphType &operator=(const DGraphType &G) {
    Nodes = G.Nodes;
    return *this;
  }
  DGraphType &operator=(const DGraphType &&G) {
    Nodes = std::move(G.Nodes);
    return *this;
  }

  const_iterator begin() const { return Nodes.begin(); }
  const_iterator end() const { return Nodes.end(); }
  iterator begin() { return Nodes.begin(); }
  iterator end() { return Nodes.end(); }
  const NodeType &front() const { return *Nodes.front(); }
  NodeType &front() { return *Nodes.front(); }
  const NodeType &back() const { return *Nodes.back(); }
  NodeType &back() { return *Nodes.back(); }

  size_t size() const { return Nodes.size(); }

  /// Find the given node \p N in the table.
  const_iterator findNode(const NodeType &N) const {
    return llvm::find_if(Nodes,
                         [&N](const NodeType *Node) { return *Node == N; });
  }
  iterator findNode(const NodeType &N) {
    return const_cast<iterator>(
        static_cast<const DGraphType &>(*this).findNode(N));
  }

  /// Add the given node \p N to the graph if it is not already present.
  bool addNode(NodeType &N) {
    if (findNode(N) != Nodes.end())
      return false;
    Nodes.push_back(&N);
    return true;
  }

  /// Collect in \p EL all edges that are coming into node \p N. Return true
  /// if at least one edge was found, and false otherwise.
  bool findIncomingEdgesToNode(const NodeType &N, SmallVectorImpl<EdgeType*> &EL) const {
    assert(EL.empty() && "Expected the list of edges to be empty.");
    EdgeListTy TempList;
    for (auto *Node : Nodes) {
      if (*Node == N)
        continue;
      Node->findEdgesTo(N, TempList);
      llvm::append_range(EL, TempList);
      TempList.clear();
    }
    return !EL.empty();
  }

  /// Remove the given node \p N from the graph. If the node has incoming or
  /// outgoing edges, they are also removed. Return true if the node was found
  /// and then removed, and false if the node was not found in the graph to
  /// begin with.
  bool removeNode(NodeType &N) {
    iterator IT = findNode(N);
    if (IT == Nodes.end())
      return false;
    // Remove incoming edges.
    EdgeListTy EL;
    for (auto *Node : Nodes) {
      if (*Node == N)
        continue;
      Node->findEdgesTo(N, EL);
      for (auto *E : EL)
        Node->removeEdge(*E);
      EL.clear();
    }
    N.clear();
    Nodes.erase(IT);
    return true;
  }

  /// Assuming nodes \p Src and \p Dst are already in the graph, connect node \p
  /// Src to node \p Dst using the provided edge \p E. Return true if \p Src is
  /// not already connected to \p Dst via \p E, and false otherwise.
  bool connect(NodeType &Src, NodeType &Dst, EdgeType &E) {
    assert(findNode(Src) != Nodes.end() && "Src node should be present.");
    assert(findNode(Dst) != Nodes.end() && "Dst node should be present.");
    assert((E.getTargetNode() == Dst) &&
           "Target of the given edge does not match Dst.");
    return Src.addEdge(E);
  }

protected:
  // The list of nodes in the graph.
  NodeListTy Nodes;
};

} // namespace llvm

#endif // LLVM_ADT_DIRECTEDGRAPH_H

#ifdef __GNUC__
#pragma GCC diagnostic pop
#endif