LLVM  10.0.0svn
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]
Collaboration diagram for llvm::DirectedGraph< NodeType, EdgeType >:
Collaboration 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. More...
 
iterator findNode (const NodeType &N)
 
bool addNode (NodeType &N)
 Add the given node N to the graph if it is not already present. More...
 
bool findIncomingEdgesToNode (const NodeType &N, SmallVectorImpl< EdgeType *> &EL) const
 Collect in EL all edges that are coming into node N. More...
 
bool removeNode (NodeType &N)
 Remove the given node N from the graph. More...
 
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. More...
 

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 163 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 169 of file DirectedGraph.h.

◆ DGraphType

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

Definition at line 170 of file DirectedGraph.h.

◆ EdgeListTy

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

Definition at line 166 of file DirectedGraph.h.

◆ iterator

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

Definition at line 168 of file DirectedGraph.h.

◆ NodeListTy

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

Definition at line 165 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 173 of file DirectedGraph.h.

◆ DirectedGraph() [3/4]

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

Definition at line 174 of file DirectedGraph.h.

◆ DirectedGraph() [4/4]

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

Definition at line 175 of file DirectedGraph.h.

Member Function Documentation

◆ addNode()

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

Add the given node N to the graph if it is not already present.

Definition at line 207 of file DirectedGraph.h.

Referenced by llvm::DataDependenceGraph::addNode().

◆ back() [1/2]

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

Definition at line 191 of file DirectedGraph.h.

◆ back() [2/2]

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

Definition at line 192 of file DirectedGraph.h.

◆ begin() [1/2]

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

◆ begin() [2/2]

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

Definition at line 187 of file DirectedGraph.h.

◆ 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 255 of file DirectedGraph.h.

References assert().

◆ end() [1/2]

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

◆ end() [2/2]

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

Definition at line 188 of file DirectedGraph.h.

◆ 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 216 of file DirectedGraph.h.

References assert(), llvm::SmallVectorBase::empty(), llvm::SmallVectorTemplateCommon< T >::end(), and llvm::SmallVectorImpl< T >::insert().

◆ findNode() [1/2]

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

Find the given node N in the table.

Definition at line 197 of file DirectedGraph.h.

References llvm::find_if(), and N.

Referenced by llvm::DirectedGraph< NodeType, EdgeType >::findNode().

◆ findNode() [2/2]

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

◆ front() [1/2]

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

Definition at line 189 of file DirectedGraph.h.

◆ front() [2/2]

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

Definition at line 190 of file DirectedGraph.h.

◆ operator=() [1/2]

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

Definition at line 176 of file DirectedGraph.h.

References 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 180 of file DirectedGraph.h.

References G.

◆ 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 233 of file DirectedGraph.h.

References E, and IT.

◆ size()

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

Definition at line 194 of file DirectedGraph.h.

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: