Directed graph. More...

#include "llvm/ADT/DirectedGraph.h"

Inheritance diagram for llvm::DirectedGraph< NodeType, EdgeType >:

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)
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/2]

template<class NodeType, class EdgeType>

llvm::DirectedGraph< NodeType, EdgeType >::DirectedGraph ( )

default

◆ DirectedGraph() [2/2]

template<class NodeType, class EdgeType>

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

inlineexplicit

Definition at line 183 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::DirectedGraph< DDGNode, DDGEdge >::DirectedGraph().

◆ back() [1/2]

template<class NodeType, class EdgeType>

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

inline

Definition at line 192 of file DirectedGraph.h.

◆ back() [2/2]

template<class NodeType, class EdgeType>

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

inline

Definition at line 191 of file DirectedGraph.h.

◆ begin() [1/2]

template<class NodeType, class EdgeType>

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

inline

Definition at line 187 of file DirectedGraph.h.

◆ begin() [2/2]

template<class NodeType, class EdgeType>

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

inline

Definition at line 185 of file DirectedGraph.h.

Referenced by llvm::GraphTraits< const DataDependenceGraph * >::nodes_begin(), and llvm::GraphTraits< DataDependenceGraph * >::nodes_begin().

◆ 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.

◆ end() [1/2]

template<class NodeType, class EdgeType>

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

inline

Definition at line 188 of file DirectedGraph.h.

◆ end() [2/2]

template<class NodeType, class EdgeType>

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

inline

Definition at line 186 of file DirectedGraph.h.

Referenced by llvm::GraphTraits< const DataDependenceGraph * >::nodes_end(), and llvm::GraphTraits< DataDependenceGraph * >::nodes_end().

◆ 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.

◆ findNode() [1/2]

template<class NodeType, class EdgeType>

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

inline

Definition at line 201 of file DirectedGraph.h.

◆ findNode() [2/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.

Referenced by llvm::DirectedGraph< DDGNode, DDGEdge >::addNode(), llvm::DirectedGraph< DDGNode, DDGEdge >::connect(), and llvm::DirectedGraph< DDGNode, DDGEdge >::removeNode().

◆ front() [1/2]

template<class NodeType, class EdgeType>

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

inline

Definition at line 190 of file DirectedGraph.h.

◆ front() [2/2]

template<class NodeType, class EdgeType>

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

inline

Definition at line 189 of file DirectedGraph.h.

◆ 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.

◆ 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

Definition at line 265 of file DirectedGraph.h.

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

include/llvm/ADT/DirectedGraph.h

Public Types

Public Member Functions

Protected Types

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ const_iterator

◆ DGraphType

◆ EdgeListTy

◆ iterator

◆ NodeListTy

Constructor & Destructor Documentation

◆ DirectedGraph() [1/2]

◆ DirectedGraph() [2/2]

Member Function Documentation

◆ addNode()

◆ back() [1/2]

◆ back() [2/2]

◆ begin() [1/2]

◆ begin() [2/2]

◆ connect()

◆ end() [1/2]

◆ end() [2/2]

◆ findIncomingEdgesToNode()

◆ findNode() [1/2]

◆ findNode() [2/2]

◆ front() [1/2]

◆ front() [2/2]

◆ removeNode()

◆ size()

Member Data Documentation

◆ Nodes