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)

	DirectedGraph (const DGraphType &G)

	DirectedGraph (DGraphType &&RHS)

DGraphType &	operator= (const DGraphType &G)

DGraphType &	operator= (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

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

Definition at line 217 of file DirectedGraph.h.

References llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::DirectedGraph< NodeType, EdgeType >::findNode(), N, llvm::DirectedGraph< NodeType, EdgeType >::Nodes, and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by llvm::DataDependenceGraph::addNode(), and llvm::DirectedGraph< NodeType, EdgeType >::DirectedGraph().

◆ back() [1/2]

template<class NodeType , class EdgeType >

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

inline

Definition at line 202 of file DirectedGraph.h.

References llvm::SmallVectorTemplateCommon< T, typename >::back(), and llvm::DirectedGraph< NodeType, EdgeType >::Nodes.

◆ back() [2/2]

template<class NodeType , class EdgeType >

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

inline

Definition at line 201 of file DirectedGraph.h.

References llvm::SmallVectorTemplateCommon< T, typename >::back(), and llvm::DirectedGraph< NodeType, EdgeType >::Nodes.

◆ begin() [1/2]

template<class NodeType , class EdgeType >

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

inline

Definition at line 197 of file DirectedGraph.h.

References llvm::SmallVectorTemplateCommon< T, typename >::begin(), and llvm::DirectedGraph< NodeType, EdgeType >::Nodes.

◆ begin() [2/2]

template<class NodeType , class EdgeType >

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

inline

Definition at line 195 of file DirectedGraph.h.

References llvm::SmallVectorTemplateCommon< T, typename >::begin(), and llvm::DirectedGraph< NodeType, EdgeType >::Nodes.

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

Definition at line 198 of file DirectedGraph.h.

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

◆ end() [2/2]

template<class NodeType , class EdgeType >

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

inline

Definition at line 196 of file DirectedGraph.h.

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

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

Find the given node N in the table.

Definition at line 207 of file DirectedGraph.h.

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

Referenced by llvm::DirectedGraph< NodeType, EdgeType >::addNode(), llvm::DirectedGraph< NodeType, EdgeType >::connect(), llvm::DirectedGraph< NodeType, EdgeType >::findNode(), and llvm::DirectedGraph< NodeType, EdgeType >::removeNode().

◆ front() [1/2]

template<class NodeType , class EdgeType >

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

inline

Definition at line 200 of file DirectedGraph.h.

References llvm::SmallVectorTemplateCommon< T, typename >::front(), and llvm::DirectedGraph< NodeType, EdgeType >::Nodes.

◆ front() [2/2]

template<class NodeType , class EdgeType >

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

inline

Definition at line 199 of file DirectedGraph.h.

References llvm::SmallVectorTemplateCommon< T, typename >::front(), and llvm::DirectedGraph< NodeType, EdgeType >::Nodes.

◆ 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

Definition at line 204 of file DirectedGraph.h.

References llvm::DirectedGraph< NodeType, EdgeType >::Nodes, and llvm::SmallVectorBase< Size_T >::size().

Member Data Documentation

◆ Nodes

template<class NodeType , class EdgeType >

NodeListTy llvm::DirectedGraph< NodeType, EdgeType >::Nodes

protected

Definition at line 275 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/4]

◆ DirectedGraph() [2/4]

◆ DirectedGraph() [3/4]

◆ DirectedGraph() [4/4]

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]

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ removeNode()

◆ size()

Member Data Documentation

◆ Nodes