LLVM 20.0.0git
Public Types | Public Member Functions | Protected Types | Protected Attributes | List of all members
llvm::DirectedGraph< NodeType, EdgeType > Class Template Reference

Directed graph. More...

#include "llvm/ADT/DirectedGraph.h"

Inheritance diagram for llvm::DirectedGraph< NodeType, EdgeType >:
Inheritance graph
[legend]

Public Types

using iterator = typename NodeListTy::iterator
 
using const_iterator = typename NodeListTy::const_iterator
 
using DGraphType = DirectedGraph< NodeType, EdgeType >
 

Public Member Functions

 DirectedGraph ()=default
 
 DirectedGraph (NodeType &N)
 
 DirectedGraph (const DGraphType &G)
 
 DirectedGraph (DGraphType &&RHS)
 
DGraphTypeoperator= (const DGraphType &G)
 
DGraphTypeoperator= (const DGraphType &&G)
 
const_iterator begin () const
 
const_iterator end () const
 
iterator begin ()
 
iterator end ()
 
const NodeType & front () const
 
NodeType & front ()
 
const NodeType & back () const
 
NodeType & back ()
 
size_t size () const
 
const_iterator findNode (const NodeType &N) const
 Find the given node N in the table.
 
iterator findNode (const NodeType &N)
 
bool addNode (NodeType &N)
 Add the given node N to the graph if it is not already present.
 
bool findIncomingEdgesToNode (const NodeType &N, SmallVectorImpl< EdgeType * > &EL) const
 Collect in EL all edges that are coming into node N.
 
bool removeNode (NodeType &N)
 Remove the given node N from the graph.
 
bool connect (NodeType &Src, NodeType &Dst, EdgeType &E)
 Assuming nodes Src and Dst are already in the graph, connect node Src to node Dst using the provided edge E.
 

Protected Types

using NodeListTy = SmallVector< NodeType *, 10 >
 
using EdgeListTy = SmallVector< EdgeType *, 10 >
 

Protected Attributes

NodeListTy Nodes
 

Detailed Description

template<class NodeType, class EdgeType>
class llvm::DirectedGraph< NodeType, EdgeType >

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.

Definition at line 173 of file DirectedGraph.h.

Member Typedef Documentation

◆ const_iterator

template<class NodeType , class EdgeType >
using llvm::DirectedGraph< NodeType, EdgeType >::const_iterator = typename NodeListTy::const_iterator

Definition at line 179 of file DirectedGraph.h.

◆ DGraphType

template<class NodeType , class EdgeType >
using llvm::DirectedGraph< NodeType, EdgeType >::DGraphType = DirectedGraph<NodeType, EdgeType>

Definition at line 180 of file DirectedGraph.h.

◆ EdgeListTy

template<class NodeType , class EdgeType >
using llvm::DirectedGraph< NodeType, EdgeType >::EdgeListTy = SmallVector<EdgeType *, 10>
protected

Definition at line 176 of file DirectedGraph.h.

◆ iterator

template<class NodeType , class EdgeType >
using llvm::DirectedGraph< NodeType, EdgeType >::iterator = typename NodeListTy::iterator

Definition at line 178 of file DirectedGraph.h.

◆ NodeListTy

template<class NodeType , class EdgeType >
using llvm::DirectedGraph< NodeType, EdgeType >::NodeListTy = SmallVector<NodeType *, 10>
protected

Definition at line 175 of file DirectedGraph.h.

Constructor & Destructor Documentation

◆ DirectedGraph() [1/4]

template<class NodeType , class EdgeType >
llvm::DirectedGraph< NodeType, EdgeType >::DirectedGraph ( )
default

◆ DirectedGraph() [2/4]

template<class NodeType , class EdgeType >
llvm::DirectedGraph< NodeType, EdgeType >::DirectedGraph ( NodeType &  N)
inlineexplicit

Definition at line 183 of file DirectedGraph.h.

References llvm::DirectedGraph< NodeType, EdgeType >::addNode(), and N.

◆ DirectedGraph() [3/4]

template<class NodeType , class EdgeType >
llvm::DirectedGraph< NodeType, EdgeType >::DirectedGraph ( const DGraphType G)
inline

Definition at line 184 of file DirectedGraph.h.

◆ DirectedGraph() [4/4]

template<class NodeType , class EdgeType >
llvm::DirectedGraph< NodeType, EdgeType >::DirectedGraph ( DGraphType &&  RHS)
inline

Definition at line 185 of file DirectedGraph.h.

Member Function Documentation

◆ addNode()

template<class NodeType , class EdgeType >
bool llvm::DirectedGraph< NodeType, EdgeType >::addNode ( NodeType &  N)
inline

◆ back() [1/2]

template<class NodeType , class EdgeType >
NodeType & llvm::DirectedGraph< NodeType, EdgeType >::back ( )
inline

◆ back() [2/2]

template<class NodeType , class EdgeType >
const NodeType & llvm::DirectedGraph< NodeType, EdgeType >::back ( ) const
inline

◆ begin() [1/2]

template<class NodeType , class EdgeType >
iterator llvm::DirectedGraph< NodeType, EdgeType >::begin ( )
inline

◆ begin() [2/2]

template<class NodeType , class EdgeType >
const_iterator llvm::DirectedGraph< NodeType, EdgeType >::begin ( ) const
inline

◆ connect()

template<class NodeType , class EdgeType >
bool llvm::DirectedGraph< NodeType, EdgeType >::connect ( NodeType &  Src,
NodeType &  Dst,
EdgeType &  E 
)
inline

Assuming nodes Src and Dst are already in the graph, connect node Src to node Dst using the provided edge E.

Return true if Src is not already connected to Dst via E, and false otherwise.

Definition at line 265 of file DirectedGraph.h.

References assert(), E, llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::DirectedGraph< NodeType, EdgeType >::findNode(), and llvm::DirectedGraph< NodeType, EdgeType >::Nodes.

Referenced by llvm::DDGBuilder::createDefUseEdge(), llvm::DDGBuilder::createMemoryEdge(), llvm::DDGBuilder::createRootedEdge(), and llvm::DDGBuilder::mergeNodes().

◆ end() [1/2]

template<class NodeType , class EdgeType >
iterator llvm::DirectedGraph< NodeType, EdgeType >::end ( )
inline

◆ end() [2/2]

template<class NodeType , class EdgeType >
const_iterator llvm::DirectedGraph< NodeType, EdgeType >::end ( ) const
inline

◆ findIncomingEdgesToNode()

template<class NodeType , class EdgeType >
bool llvm::DirectedGraph< NodeType, EdgeType >::findIncomingEdgesToNode ( const NodeType &  N,
SmallVectorImpl< EdgeType * > &  EL 
) const
inline

Collect in EL all edges that are coming into node N.

Return true if at least one edge was found, and false otherwise.

Definition at line 226 of file DirectedGraph.h.

References llvm::append_range(), assert(), llvm::SmallVectorImpl< T >::clear(), llvm::SmallVectorBase< Size_T >::empty(), N, and llvm::DirectedGraph< NodeType, EdgeType >::Nodes.

◆ findNode() [1/2]

template<class NodeType , class EdgeType >
iterator llvm::DirectedGraph< NodeType, EdgeType >::findNode ( const NodeType &  N)
inline

Definition at line 211 of file DirectedGraph.h.

References llvm::DirectedGraph< NodeType, EdgeType >::findNode(), and N.

◆ findNode() [2/2]

template<class NodeType , class EdgeType >
const_iterator llvm::DirectedGraph< NodeType, EdgeType >::findNode ( const NodeType &  N) const
inline

◆ front() [1/2]

template<class NodeType , class EdgeType >
NodeType & llvm::DirectedGraph< NodeType, EdgeType >::front ( )
inline

◆ front() [2/2]

template<class NodeType , class EdgeType >
const NodeType & llvm::DirectedGraph< NodeType, EdgeType >::front ( ) const
inline

◆ operator=() [1/2]

template<class NodeType , class EdgeType >
DGraphType & llvm::DirectedGraph< NodeType, EdgeType >::operator= ( const DGraphType &&  G)
inline

Definition at line 190 of file DirectedGraph.h.

References G, and llvm::DirectedGraph< NodeType, EdgeType >::Nodes.

◆ operator=() [2/2]

template<class NodeType , class EdgeType >
DGraphType & llvm::DirectedGraph< NodeType, EdgeType >::operator= ( const DGraphType G)
inline

Definition at line 186 of file DirectedGraph.h.

References G, and llvm::DirectedGraph< NodeType, EdgeType >::Nodes.

◆ removeNode()

template<class NodeType , class EdgeType >
bool llvm::DirectedGraph< NodeType, EdgeType >::removeNode ( NodeType &  N)
inline

Remove the given node 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.

Definition at line 243 of file DirectedGraph.h.

References E, llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::SmallVectorImpl< T >::erase(), llvm::DirectedGraph< NodeType, EdgeType >::findNode(), IT, N, and llvm::DirectedGraph< NodeType, EdgeType >::Nodes.

Referenced by llvm::DDGBuilder::mergeNodes().

◆ size()

template<class NodeType , class EdgeType >
size_t llvm::DirectedGraph< NodeType, EdgeType >::size ( ) const
inline

Member Data Documentation

◆ Nodes

template<class NodeType , class EdgeType >
NodeListTy llvm::DirectedGraph< NodeType, EdgeType >::Nodes
protected

The documentation for this class was generated from the following file: