llvm/ADT/DirectedGraph.h

0001 //===- llvm/ADT/DirectedGraph.h - Directed Graph ----------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 ///
0009 /// \file
0010 /// This file defines the interface and a base class implementation for a
0011 /// directed graph.
0012 ///
0013 //===----------------------------------------------------------------------===//
0014
0015 #ifndef LLVM_ADT_DIRECTEDGRAPH_H
0016 #define LLVM_ADT_DIRECTEDGRAPH_H
0017
0018 #include "llvm/ADT/GraphTraits.h"
0019 #include "llvm/ADT/SetVector.h"
0020 #include "llvm/ADT/SmallVector.h"
0021 #include "llvm/Support/Debug.h"
0022 #include "llvm/Support/raw_ostream.h"
0023
0024 namespace llvm {
0025
0026 /// Represent an edge in the directed graph.
0027 /// The edge contains the target node it connects to.
0028 template <class NodeType, class EdgeType> class DGEdge {
0029 public:
0030   DGEdge() = delete;
0031   /// Create an edge pointing to the given node \p N.
0032   explicit DGEdge(NodeType &N) : TargetNode(N) {}
0033   explicit DGEdge(const DGEdge<NodeType, EdgeType> &E)
0034       : TargetNode(E.TargetNode) {}
0035   DGEdge<NodeType, EdgeType> &operator=(const DGEdge<NodeType, EdgeType> &E) {
0036     TargetNode = E.TargetNode;
0037     return *this;
0038   }
0039
0040   /// Static polymorphism: delegate implementation (via isEqualTo) to the
0041   /// derived class.
0042   bool operator==(const DGEdge &E) const {
0043     return getDerived().isEqualTo(E.getDerived());
0044   }
0045   bool operator!=(const DGEdge &E) const { return !operator==(E); }
0046
0047   /// Retrieve the target node this edge connects to.
0048   const NodeType &getTargetNode() const { return TargetNode; }
0049   NodeType &getTargetNode() {
0050     return const_cast<NodeType &>(
0051         static_cast<const DGEdge<NodeType, EdgeType> &>(*this).getTargetNode());
0052   }
0053
0054   /// Set the target node this edge connects to.
0055   void setTargetNode(const NodeType &N) { TargetNode = N; }
0056
0057 protected:
0058   // As the default implementation use address comparison for equality.
0059   bool isEqualTo(const EdgeType &E) const { return this == &E; }
0060
0061   // Cast the 'this' pointer to the derived type and return a reference.
0062   EdgeType &getDerived() { return *static_cast<EdgeType *>(this); }
0063   const EdgeType &getDerived() const {
0064     return *static_cast<const EdgeType *>(this);
0065   }
0066
0067   // The target node this edge connects to.
0068   NodeType &TargetNode;
0069 };
0070
0071 /// Represent a node in the directed graph.
0072 /// The node has a (possibly empty) list of outgoing edges.
0073 template <class NodeType, class EdgeType> class DGNode {
0074 public:
0075   using EdgeListTy = SetVector<EdgeType *>;
0076   using iterator = typename EdgeListTy::iterator;
0077   using const_iterator = typename EdgeListTy::const_iterator;
0078
0079   /// Create a node with a single outgoing edge \p E.
0080   explicit DGNode(EdgeType &E) : Edges() { Edges.insert(&E); }
0081   DGNode() = default;
0082
0083   explicit DGNode(const DGNode<NodeType, EdgeType> &N) : Edges(N.Edges) {}
0084   DGNode(DGNode<NodeType, EdgeType> &&N) : Edges(std::move(N.Edges)) {}
0085
0086   DGNode<NodeType, EdgeType> &operator=(const DGNode<NodeType, EdgeType> &N) {
0087     Edges = N.Edges;
0088     return *this;
0089   }
0090   DGNode<NodeType, EdgeType> &operator=(const DGNode<NodeType, EdgeType> &&N) {
0091     Edges = std::move(N.Edges);
0092     return *this;
0093   }
0094
0095   /// Static polymorphism: delegate implementation (via isEqualTo) to the
0096   /// derived class.
0097   friend bool operator==(const NodeType &M, const NodeType &N) {
0098     return M.isEqualTo(N);
0099   }
0100   friend bool operator!=(const NodeType &M, const NodeType &N) {
0101     return !(M == N);
0102   }
0103
0104   const_iterator begin() const { return Edges.begin(); }
0105   const_iterator end() const { return Edges.end(); }
0106   iterator begin() { return Edges.begin(); }
0107   iterator end() { return Edges.end(); }
0108   const EdgeType &front() const { return *Edges.front(); }
0109   EdgeType &front() { return *Edges.front(); }
0110   const EdgeType &back() const { return *Edges.back(); }
0111   EdgeType &back() { return *Edges.back(); }
0112
0113   /// Collect in \p EL, all the edges from this node to \p N.
0114   /// Return true if at least one edge was found, and false otherwise.
0115   /// Note that this implementation allows more than one edge to connect
0116   /// a given pair of nodes.
0117   bool findEdgesTo(const NodeType &N, SmallVectorImpl<EdgeType *> &EL) const {
0118     assert(EL.empty() && "Expected the list of edges to be empty.");
0119     for (auto *E : Edges)
0120       if (E->getTargetNode() == N)
0121         EL.push_back(E);
0122     return !EL.empty();
0123   }
0124
0125   /// Add the given edge \p E to this node, if it doesn't exist already. Returns
0126   /// true if the edge is added and false otherwise.
0127   bool addEdge(EdgeType &E) { return Edges.insert(&E); }
0128
0129   /// Remove the given edge \p E from this node, if it exists.
0130   void removeEdge(EdgeType &E) { Edges.remove(&E); }
0131
0132   /// Test whether there is an edge that goes from this node to \p N.
0133   bool hasEdgeTo(const NodeType &N) const {
0134     return (findEdgeTo(N) != Edges.end());
0135   }
0136
0137   /// Retrieve the outgoing edges for the node.
0138   const EdgeListTy &getEdges() const { return Edges; }
0139   EdgeListTy &getEdges() {
0140     return const_cast<EdgeListTy &>(
0141         static_cast<const DGNode<NodeType, EdgeType> &>(*this).Edges);
0142   }
0143
0144   /// Clear the outgoing edges.
0145   void clear() { Edges.clear(); }
0146
0147 protected:
0148   // As the default implementation use address comparison for equality.
0149   bool isEqualTo(const NodeType &N) const { return this == &N; }
0150
0151   // Cast the 'this' pointer to the derived type and return a reference.
0152   NodeType &getDerived() { return *static_cast<NodeType *>(this); }
0153   const NodeType &getDerived() const {
0154     return *static_cast<const NodeType *>(this);
0155   }
0156
0157   /// Find an edge to \p N. If more than one edge exists, this will return
0158   /// the first one in the list of edges.
0159   const_iterator findEdgeTo(const NodeType &N) const {
0160     return llvm::find_if(
0161         Edges, [&N](const EdgeType *E) { return E->getTargetNode() == N; });
0162   }
0163
0164   // The list of outgoing edges.
0165   EdgeListTy Edges;
0166 };
0167
0168 /// Directed graph
0169 ///
0170 /// The graph is represented by a table of nodes.
0171 /// Each node contains a (possibly empty) list of outgoing edges.
0172 /// Each edge contains the target node it connects to.
0173 template <class NodeType, class EdgeType> class DirectedGraph {
0174 protected:
0175   using NodeListTy = SmallVector<NodeType *, 10>;
0176   using EdgeListTy = SmallVector<EdgeType *, 10>;
0177 public:
0178   using iterator = typename NodeListTy::iterator;
0179   using const_iterator = typename NodeListTy::const_iterator;
0180   using DGraphType = DirectedGraph<NodeType, EdgeType>;
0181
0182   DirectedGraph() = default;
0183   explicit DirectedGraph(NodeType &N) : Nodes() { addNode(N); }
0184   DirectedGraph(const DGraphType &G) : Nodes(G.Nodes) {}
0185   DirectedGraph(DGraphType &&RHS) : Nodes(std::move(RHS.Nodes)) {}
0186   DGraphType &operator=(const DGraphType &G) {
0187     Nodes = G.Nodes;
0188     return *this;
0189   }
0190   DGraphType &operator=(const DGraphType &&G) {
0191     Nodes = std::move(G.Nodes);
0192     return *this;
0193   }
0194
0195   const_iterator begin() const { return Nodes.begin(); }
0196   const_iterator end() const { return Nodes.end(); }
0197   iterator begin() { return Nodes.begin(); }
0198   iterator end() { return Nodes.end(); }
0199   const NodeType &front() const { return *Nodes.front(); }
0200   NodeType &front() { return *Nodes.front(); }
0201   const NodeType &back() const { return *Nodes.back(); }
0202   NodeType &back() { return *Nodes.back(); }
0203
0204   size_t size() const { return Nodes.size(); }
0205
0206   /// Find the given node \p N in the table.
0207   const_iterator findNode(const NodeType &N) const {
0208     return llvm::find_if(Nodes,
0209                          [&N](const NodeType *Node) { return *Node == N; });
0210   }
0211   iterator findNode(const NodeType &N) {
0212     return const_cast<iterator>(
0213         static_cast<const DGraphType &>(*this).findNode(N));
0214   }
0215
0216   /// Add the given node \p N to the graph if it is not already present.
0217   bool addNode(NodeType &N) {
0218     if (findNode(N) != Nodes.end())
0219       return false;
0220     Nodes.push_back(&N);
0221     return true;
0222   }
0223
0224   /// Collect in \p EL all edges that are coming into node \p N. Return true
0225   /// if at least one edge was found, and false otherwise.
0226   bool findIncomingEdgesToNode(const NodeType &N, SmallVectorImpl<EdgeType*> &EL) const {
0227     assert(EL.empty() && "Expected the list of edges to be empty.");
0228     EdgeListTy TempList;
0229     for (auto *Node : Nodes) {
0230       if (*Node == N)
0231         continue;
0232       Node->findEdgesTo(N, TempList);
0233       llvm::append_range(EL, TempList);
0234       TempList.clear();
0235     }
0236     return !EL.empty();
0237   }
0238
0239   /// Remove the given node \p N from the graph. If the node has incoming or
0240   /// outgoing edges, they are also removed. Return true if the node was found
0241   /// and then removed, and false if the node was not found in the graph to
0242   /// begin with.
0243   bool removeNode(NodeType &N) {
0244     iterator IT = findNode(N);
0245     if (IT == Nodes.end())
0246       return false;
0247     // Remove incoming edges.
0248     EdgeListTy EL;
0249     for (auto *Node : Nodes) {
0250       if (*Node == N)
0251         continue;
0252       Node->findEdgesTo(N, EL);
0253       for (auto *E : EL)
0254         Node->removeEdge(*E);
0255       EL.clear();
0256     }
0257     N.clear();
0258     Nodes.erase(IT);
0259     return true;
0260   }
0261
0262   /// Assuming nodes \p Src and \p Dst are already in the graph, connect node \p
0263   /// Src to node \p Dst using the provided edge \p E. Return true if \p Src is
0264   /// not already connected to \p Dst via \p E, and false otherwise.
0265   bool connect(NodeType &Src, NodeType &Dst, EdgeType &E) {
0266     assert(findNode(Src) != Nodes.end() && "Src node should be present.");
0267     assert(findNode(Dst) != Nodes.end() && "Dst node should be present.");
0268     assert((E.getTargetNode() == Dst) &&
0269            "Target of the given edge does not match Dst.");
0270     return Src.addEdge(E);
0271   }
0272
0273 protected:
0274   // The list of nodes in the graph.
0275   NodeListTy Nodes;
0276 };
0277
0278 } // namespace llvm
0279
0280 #endif // LLVM_ADT_DIRECTEDGRAPH_H