18bcb0991SDimitry Andric //===- llvm/ADT/DirectedGraph.h - Directed Graph ----------------*- C++ -*-===// 28bcb0991SDimitry Andric // 38bcb0991SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 48bcb0991SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 58bcb0991SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 68bcb0991SDimitry Andric // 78bcb0991SDimitry Andric //===----------------------------------------------------------------------===// 8*1fd87a68SDimitry Andric /// 9*1fd87a68SDimitry Andric /// \file 10*1fd87a68SDimitry Andric /// This file defines the interface and a base class implementation for a 11*1fd87a68SDimitry Andric /// directed graph. 12*1fd87a68SDimitry Andric /// 138bcb0991SDimitry Andric //===----------------------------------------------------------------------===// 148bcb0991SDimitry Andric 158bcb0991SDimitry Andric #ifndef LLVM_ADT_DIRECTEDGRAPH_H 168bcb0991SDimitry Andric #define LLVM_ADT_DIRECTEDGRAPH_H 178bcb0991SDimitry Andric 188bcb0991SDimitry Andric #include "llvm/ADT/GraphTraits.h" 198bcb0991SDimitry Andric #include "llvm/ADT/SetVector.h" 208bcb0991SDimitry Andric #include "llvm/ADT/SmallVector.h" 218bcb0991SDimitry Andric #include "llvm/Support/Debug.h" 228bcb0991SDimitry Andric #include "llvm/Support/raw_ostream.h" 238bcb0991SDimitry Andric 248bcb0991SDimitry Andric namespace llvm { 258bcb0991SDimitry Andric 268bcb0991SDimitry Andric /// Represent an edge in the directed graph. 278bcb0991SDimitry Andric /// The edge contains the target node it connects to. 288bcb0991SDimitry Andric template <class NodeType, class EdgeType> class DGEdge { 298bcb0991SDimitry Andric public: 308bcb0991SDimitry Andric DGEdge() = delete; 318bcb0991SDimitry Andric /// Create an edge pointing to the given node \p N. DGEdge(NodeType & N)328bcb0991SDimitry Andric explicit DGEdge(NodeType &N) : TargetNode(N) {} DGEdge(const DGEdge<NodeType,EdgeType> & E)338bcb0991SDimitry Andric explicit DGEdge(const DGEdge<NodeType, EdgeType> &E) 348bcb0991SDimitry Andric : TargetNode(E.TargetNode) {} 358bcb0991SDimitry Andric DGEdge<NodeType, EdgeType> &operator=(const DGEdge<NodeType, EdgeType> &E) { 368bcb0991SDimitry Andric TargetNode = E.TargetNode; 378bcb0991SDimitry Andric return *this; 388bcb0991SDimitry Andric } 398bcb0991SDimitry Andric 408bcb0991SDimitry Andric /// Static polymorphism: delegate implementation (via isEqualTo) to the 418bcb0991SDimitry Andric /// derived class. 42e8d8bef9SDimitry Andric bool operator==(const DGEdge &E) const { 43e8d8bef9SDimitry Andric return getDerived().isEqualTo(E.getDerived()); 44e8d8bef9SDimitry Andric } 45e8d8bef9SDimitry Andric bool operator!=(const DGEdge &E) const { return !operator==(E); } 468bcb0991SDimitry Andric 478bcb0991SDimitry Andric /// Retrieve the target node this edge connects to. getTargetNode()488bcb0991SDimitry Andric const NodeType &getTargetNode() const { return TargetNode; } getTargetNode()498bcb0991SDimitry Andric NodeType &getTargetNode() { 508bcb0991SDimitry Andric return const_cast<NodeType &>( 518bcb0991SDimitry Andric static_cast<const DGEdge<NodeType, EdgeType> &>(*this).getTargetNode()); 528bcb0991SDimitry Andric } 538bcb0991SDimitry Andric 54480093f4SDimitry Andric /// Set the target node this edge connects to. setTargetNode(const NodeType & N)55480093f4SDimitry Andric void setTargetNode(const NodeType &N) { TargetNode = N; } 56480093f4SDimitry Andric 578bcb0991SDimitry Andric protected: 588bcb0991SDimitry Andric // As the default implementation use address comparison for equality. isEqualTo(const EdgeType & E)598bcb0991SDimitry Andric bool isEqualTo(const EdgeType &E) const { return this == &E; } 608bcb0991SDimitry Andric 618bcb0991SDimitry Andric // Cast the 'this' pointer to the derived type and return a reference. getDerived()628bcb0991SDimitry Andric EdgeType &getDerived() { return *static_cast<EdgeType *>(this); } getDerived()638bcb0991SDimitry Andric const EdgeType &getDerived() const { 648bcb0991SDimitry Andric return *static_cast<const EdgeType *>(this); 658bcb0991SDimitry Andric } 668bcb0991SDimitry Andric 678bcb0991SDimitry Andric // The target node this edge connects to. 688bcb0991SDimitry Andric NodeType &TargetNode; 698bcb0991SDimitry Andric }; 708bcb0991SDimitry Andric 718bcb0991SDimitry Andric /// Represent a node in the directed graph. 728bcb0991SDimitry Andric /// The node has a (possibly empty) list of outgoing edges. 738bcb0991SDimitry Andric template <class NodeType, class EdgeType> class DGNode { 748bcb0991SDimitry Andric public: 758bcb0991SDimitry Andric using EdgeListTy = SetVector<EdgeType *>; 768bcb0991SDimitry Andric using iterator = typename EdgeListTy::iterator; 778bcb0991SDimitry Andric using const_iterator = typename EdgeListTy::const_iterator; 788bcb0991SDimitry Andric 798bcb0991SDimitry Andric /// Create a node with a single outgoing edge \p E. DGNode(EdgeType & E)808bcb0991SDimitry Andric explicit DGNode(EdgeType &E) : Edges() { Edges.insert(&E); } 818bcb0991SDimitry Andric DGNode() = default; 828bcb0991SDimitry Andric DGNode(const DGNode<NodeType,EdgeType> & N)838bcb0991SDimitry Andric explicit DGNode(const DGNode<NodeType, EdgeType> &N) : Edges(N.Edges) {} DGNode(DGNode<NodeType,EdgeType> && N)848bcb0991SDimitry Andric DGNode(DGNode<NodeType, EdgeType> &&N) : Edges(std::move(N.Edges)) {} 858bcb0991SDimitry Andric 868bcb0991SDimitry Andric DGNode<NodeType, EdgeType> &operator=(const DGNode<NodeType, EdgeType> &N) { 878bcb0991SDimitry Andric Edges = N.Edges; 888bcb0991SDimitry Andric return *this; 898bcb0991SDimitry Andric } 908bcb0991SDimitry Andric DGNode<NodeType, EdgeType> &operator=(const DGNode<NodeType, EdgeType> &&N) { 918bcb0991SDimitry Andric Edges = std::move(N.Edges); 928bcb0991SDimitry Andric return *this; 938bcb0991SDimitry Andric } 948bcb0991SDimitry Andric 958bcb0991SDimitry Andric /// Static polymorphism: delegate implementation (via isEqualTo) to the 968bcb0991SDimitry Andric /// derived class. 97e8d8bef9SDimitry Andric friend bool operator==(const NodeType &M, const NodeType &N) { 98e8d8bef9SDimitry Andric return M.isEqualTo(N); 99e8d8bef9SDimitry Andric } 100e8d8bef9SDimitry Andric friend bool operator!=(const NodeType &M, const NodeType &N) { 101e8d8bef9SDimitry Andric return !(M == N); 102e8d8bef9SDimitry Andric } 1038bcb0991SDimitry Andric begin()1048bcb0991SDimitry Andric const_iterator begin() const { return Edges.begin(); } end()1058bcb0991SDimitry Andric const_iterator end() const { return Edges.end(); } begin()1068bcb0991SDimitry Andric iterator begin() { return Edges.begin(); } end()1078bcb0991SDimitry Andric iterator end() { return Edges.end(); } front()1088bcb0991SDimitry Andric const EdgeType &front() const { return *Edges.front(); } front()1098bcb0991SDimitry Andric EdgeType &front() { return *Edges.front(); } back()1108bcb0991SDimitry Andric const EdgeType &back() const { return *Edges.back(); } back()1118bcb0991SDimitry Andric EdgeType &back() { return *Edges.back(); } 1128bcb0991SDimitry Andric 1138bcb0991SDimitry Andric /// Collect in \p EL, all the edges from this node to \p N. 1148bcb0991SDimitry Andric /// Return true if at least one edge was found, and false otherwise. 1158bcb0991SDimitry Andric /// Note that this implementation allows more than one edge to connect 1168bcb0991SDimitry Andric /// a given pair of nodes. findEdgesTo(const NodeType & N,SmallVectorImpl<EdgeType * > & EL)1178bcb0991SDimitry Andric bool findEdgesTo(const NodeType &N, SmallVectorImpl<EdgeType *> &EL) const { 1188bcb0991SDimitry Andric assert(EL.empty() && "Expected the list of edges to be empty."); 1198bcb0991SDimitry Andric for (auto *E : Edges) 1208bcb0991SDimitry Andric if (E->getTargetNode() == N) 1218bcb0991SDimitry Andric EL.push_back(E); 1228bcb0991SDimitry Andric return !EL.empty(); 1238bcb0991SDimitry Andric } 1248bcb0991SDimitry Andric 1258bcb0991SDimitry Andric /// Add the given edge \p E to this node, if it doesn't exist already. Returns 1268bcb0991SDimitry Andric /// true if the edge is added and false otherwise. addEdge(EdgeType & E)1278bcb0991SDimitry Andric bool addEdge(EdgeType &E) { return Edges.insert(&E); } 1288bcb0991SDimitry Andric 1298bcb0991SDimitry Andric /// Remove the given edge \p E from this node, if it exists. removeEdge(EdgeType & E)1308bcb0991SDimitry Andric void removeEdge(EdgeType &E) { Edges.remove(&E); } 1318bcb0991SDimitry Andric 1328bcb0991SDimitry Andric /// Test whether there is an edge that goes from this node to \p N. hasEdgeTo(const NodeType & N)1338bcb0991SDimitry Andric bool hasEdgeTo(const NodeType &N) const { 1348bcb0991SDimitry Andric return (findEdgeTo(N) != Edges.end()); 1358bcb0991SDimitry Andric } 1368bcb0991SDimitry Andric 1378bcb0991SDimitry Andric /// Retrieve the outgoing edges for the node. getEdges()1388bcb0991SDimitry Andric const EdgeListTy &getEdges() const { return Edges; } getEdges()1398bcb0991SDimitry Andric EdgeListTy &getEdges() { 1408bcb0991SDimitry Andric return const_cast<EdgeListTy &>( 1418bcb0991SDimitry Andric static_cast<const DGNode<NodeType, EdgeType> &>(*this).Edges); 1428bcb0991SDimitry Andric } 1438bcb0991SDimitry Andric 1448bcb0991SDimitry Andric /// Clear the outgoing edges. clear()1458bcb0991SDimitry Andric void clear() { Edges.clear(); } 1468bcb0991SDimitry Andric 1478bcb0991SDimitry Andric protected: 1488bcb0991SDimitry Andric // As the default implementation use address comparison for equality. isEqualTo(const NodeType & N)1498bcb0991SDimitry Andric bool isEqualTo(const NodeType &N) const { return this == &N; } 1508bcb0991SDimitry Andric 1518bcb0991SDimitry Andric // Cast the 'this' pointer to the derived type and return a reference. getDerived()1528bcb0991SDimitry Andric NodeType &getDerived() { return *static_cast<NodeType *>(this); } getDerived()1538bcb0991SDimitry Andric const NodeType &getDerived() const { 1548bcb0991SDimitry Andric return *static_cast<const NodeType *>(this); 1558bcb0991SDimitry Andric } 1568bcb0991SDimitry Andric 1578bcb0991SDimitry Andric /// Find an edge to \p N. If more than one edge exists, this will return 1588bcb0991SDimitry Andric /// the first one in the list of edges. findEdgeTo(const NodeType & N)1598bcb0991SDimitry Andric const_iterator findEdgeTo(const NodeType &N) const { 1608bcb0991SDimitry Andric return llvm::find_if( 1618bcb0991SDimitry Andric Edges, [&N](const EdgeType *E) { return E->getTargetNode() == N; }); 1628bcb0991SDimitry Andric } 1638bcb0991SDimitry Andric 1648bcb0991SDimitry Andric // The list of outgoing edges. 1658bcb0991SDimitry Andric EdgeListTy Edges; 1668bcb0991SDimitry Andric }; 1678bcb0991SDimitry Andric 1688bcb0991SDimitry Andric /// Directed graph 1698bcb0991SDimitry Andric /// 1708bcb0991SDimitry Andric /// The graph is represented by a table of nodes. 1718bcb0991SDimitry Andric /// Each node contains a (possibly empty) list of outgoing edges. 1728bcb0991SDimitry Andric /// Each edge contains the target node it connects to. 1738bcb0991SDimitry Andric template <class NodeType, class EdgeType> class DirectedGraph { 1748bcb0991SDimitry Andric protected: 1758bcb0991SDimitry Andric using NodeListTy = SmallVector<NodeType *, 10>; 1768bcb0991SDimitry Andric using EdgeListTy = SmallVector<EdgeType *, 10>; 1778bcb0991SDimitry Andric public: 1788bcb0991SDimitry Andric using iterator = typename NodeListTy::iterator; 1798bcb0991SDimitry Andric using const_iterator = typename NodeListTy::const_iterator; 1808bcb0991SDimitry Andric using DGraphType = DirectedGraph<NodeType, EdgeType>; 1818bcb0991SDimitry Andric 1828bcb0991SDimitry Andric DirectedGraph() = default; DirectedGraph(NodeType & N)1838bcb0991SDimitry Andric explicit DirectedGraph(NodeType &N) : Nodes() { addNode(N); } DirectedGraph(const DGraphType & G)1848bcb0991SDimitry Andric DirectedGraph(const DGraphType &G) : Nodes(G.Nodes) {} DirectedGraph(DGraphType && RHS)1858bcb0991SDimitry Andric DirectedGraph(DGraphType &&RHS) : Nodes(std::move(RHS.Nodes)) {} 1868bcb0991SDimitry Andric DGraphType &operator=(const DGraphType &G) { 1878bcb0991SDimitry Andric Nodes = G.Nodes; 1888bcb0991SDimitry Andric return *this; 1898bcb0991SDimitry Andric } 1908bcb0991SDimitry Andric DGraphType &operator=(const DGraphType &&G) { 1918bcb0991SDimitry Andric Nodes = std::move(G.Nodes); 1928bcb0991SDimitry Andric return *this; 1938bcb0991SDimitry Andric } 1948bcb0991SDimitry Andric begin()1958bcb0991SDimitry Andric const_iterator begin() const { return Nodes.begin(); } end()1968bcb0991SDimitry Andric const_iterator end() const { return Nodes.end(); } begin()1978bcb0991SDimitry Andric iterator begin() { return Nodes.begin(); } end()1988bcb0991SDimitry Andric iterator end() { return Nodes.end(); } front()1998bcb0991SDimitry Andric const NodeType &front() const { return *Nodes.front(); } front()2008bcb0991SDimitry Andric NodeType &front() { return *Nodes.front(); } back()2018bcb0991SDimitry Andric const NodeType &back() const { return *Nodes.back(); } back()2028bcb0991SDimitry Andric NodeType &back() { return *Nodes.back(); } 2038bcb0991SDimitry Andric size()2048bcb0991SDimitry Andric size_t size() const { return Nodes.size(); } 2058bcb0991SDimitry Andric 2068bcb0991SDimitry Andric /// Find the given node \p N in the table. findNode(const NodeType & N)2078bcb0991SDimitry Andric const_iterator findNode(const NodeType &N) const { 2088bcb0991SDimitry Andric return llvm::find_if(Nodes, 2098bcb0991SDimitry Andric [&N](const NodeType *Node) { return *Node == N; }); 2108bcb0991SDimitry Andric } findNode(const NodeType & N)2118bcb0991SDimitry Andric iterator findNode(const NodeType &N) { 2128bcb0991SDimitry Andric return const_cast<iterator>( 2138bcb0991SDimitry Andric static_cast<const DGraphType &>(*this).findNode(N)); 2148bcb0991SDimitry Andric } 2158bcb0991SDimitry Andric 2168bcb0991SDimitry Andric /// Add the given node \p N to the graph if it is not already present. addNode(NodeType & N)2178bcb0991SDimitry Andric bool addNode(NodeType &N) { 2188bcb0991SDimitry Andric if (findNode(N) != Nodes.end()) 2198bcb0991SDimitry Andric return false; 2208bcb0991SDimitry Andric Nodes.push_back(&N); 2218bcb0991SDimitry Andric return true; 2228bcb0991SDimitry Andric } 2238bcb0991SDimitry Andric 2248bcb0991SDimitry Andric /// Collect in \p EL all edges that are coming into node \p N. Return true 2258bcb0991SDimitry Andric /// if at least one edge was found, and false otherwise. findIncomingEdgesToNode(const NodeType & N,SmallVectorImpl<EdgeType * > & EL)2268bcb0991SDimitry Andric bool findIncomingEdgesToNode(const NodeType &N, SmallVectorImpl<EdgeType*> &EL) const { 2278bcb0991SDimitry Andric assert(EL.empty() && "Expected the list of edges to be empty."); 2288bcb0991SDimitry Andric EdgeListTy TempList; 2298bcb0991SDimitry Andric for (auto *Node : Nodes) { 2308bcb0991SDimitry Andric if (*Node == N) 2318bcb0991SDimitry Andric continue; 2328bcb0991SDimitry Andric Node->findEdgesTo(N, TempList); 233e8d8bef9SDimitry Andric llvm::append_range(EL, TempList); 2348bcb0991SDimitry Andric TempList.clear(); 2358bcb0991SDimitry Andric } 2368bcb0991SDimitry Andric return !EL.empty(); 2378bcb0991SDimitry Andric } 2388bcb0991SDimitry Andric 2398bcb0991SDimitry Andric /// Remove the given node \p N from the graph. If the node has incoming or 2408bcb0991SDimitry Andric /// outgoing edges, they are also removed. Return true if the node was found 2418bcb0991SDimitry Andric /// and then removed, and false if the node was not found in the graph to 2428bcb0991SDimitry Andric /// begin with. removeNode(NodeType & N)2438bcb0991SDimitry Andric bool removeNode(NodeType &N) { 2448bcb0991SDimitry Andric iterator IT = findNode(N); 2458bcb0991SDimitry Andric if (IT == Nodes.end()) 2468bcb0991SDimitry Andric return false; 2478bcb0991SDimitry Andric // Remove incoming edges. 2488bcb0991SDimitry Andric EdgeListTy EL; 2498bcb0991SDimitry Andric for (auto *Node : Nodes) { 2508bcb0991SDimitry Andric if (*Node == N) 2518bcb0991SDimitry Andric continue; 2528bcb0991SDimitry Andric Node->findEdgesTo(N, EL); 2538bcb0991SDimitry Andric for (auto *E : EL) 2548bcb0991SDimitry Andric Node->removeEdge(*E); 2558bcb0991SDimitry Andric EL.clear(); 2568bcb0991SDimitry Andric } 2578bcb0991SDimitry Andric N.clear(); 2588bcb0991SDimitry Andric Nodes.erase(IT); 2598bcb0991SDimitry Andric return true; 2608bcb0991SDimitry Andric } 2618bcb0991SDimitry Andric 2628bcb0991SDimitry Andric /// Assuming nodes \p Src and \p Dst are already in the graph, connect node \p 2638bcb0991SDimitry Andric /// Src to node \p Dst using the provided edge \p E. Return true if \p Src is 2648bcb0991SDimitry Andric /// not already connected to \p Dst via \p E, and false otherwise. connect(NodeType & Src,NodeType & Dst,EdgeType & E)2658bcb0991SDimitry Andric bool connect(NodeType &Src, NodeType &Dst, EdgeType &E) { 2668bcb0991SDimitry Andric assert(findNode(Src) != Nodes.end() && "Src node should be present."); 2678bcb0991SDimitry Andric assert(findNode(Dst) != Nodes.end() && "Dst node should be present."); 2688bcb0991SDimitry Andric assert((E.getTargetNode() == Dst) && 2698bcb0991SDimitry Andric "Target of the given edge does not match Dst."); 2708bcb0991SDimitry Andric return Src.addEdge(E); 2718bcb0991SDimitry Andric } 2728bcb0991SDimitry Andric 2738bcb0991SDimitry Andric protected: 2748bcb0991SDimitry Andric // The list of nodes in the graph. 2758bcb0991SDimitry Andric NodeListTy Nodes; 2768bcb0991SDimitry Andric }; 2778bcb0991SDimitry Andric 2788bcb0991SDimitry Andric } // namespace llvm 2798bcb0991SDimitry Andric 2808bcb0991SDimitry Andric #endif // LLVM_ADT_DIRECTEDGRAPH_H 281