LLVM 20.0.0git
Classes | Public Types | Public Member Functions | List of all members
llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI > Class Template Reference

A Graph object represents a Directed Graph and is used in XRay to compute and store function call graphs and associated statistical information. More...

#include "llvm/XRay/Graph.h"

Classes

class  EdgeView
 A class for ranging over all the edges in the graph. More...
 
class  InOutEdgeView
 A class for ranging over the incoming edges incident to a vertex. More...
 
class  VertexView
 A class for ranging over the vertices in the graph. More...
 

Public Types

typedef VI VertexIdentifier
 These objects are used to name edges and vertices in the graph.
 
typedef std::pair< VI, VI > EdgeIdentifier
 
using VertexValueType = detail::DenseMapPair< VertexIdentifier, VertexAttribute >
 This type is the value_type of all iterators which range over vertices, Determined by the Vertices DenseMap.
 
using EdgeValueType = detail::DenseMapPair< EdgeIdentifier, EdgeAttribute >
 This type is the value_type of all iterators which range over edges, Determined by the Edges DenseMap.
 
using size_type = std::size_t
 
using ConstInEdgeIterator = NeighborEdgeIteratorT< true, false >
 A const iterator type for iterating through the set of edges entering a vertex.
 
using InEdgeIterator = NeighborEdgeIteratorT< false, false >
 An iterator type for iterating through the set of edges leaving a vertex.
 
using ConstOutEdgeIterator = NeighborEdgeIteratorT< true, true >
 A const iterator type for iterating through the set of edges entering a vertex.
 
using OutEdgeIterator = NeighborEdgeIteratorT< false, true >
 An iterator type for iterating through the set of edges leaving a vertex.
 
using ConstVertexIterator = typename VertexMapT::const_iterator
 A const iterator type for iterating through the whole vertex set of the graph.
 
using VertexIterator = typename VertexMapT::iterator
 An iterator type for iterating through the whole vertex set of the graph.
 
using ConstEdgeIterator = typename EdgeMapT::const_iterator
 A const iterator for iterating through the entire edge set of the graph.
 
using EdgeIterator = typename EdgeMapT::iterator
 An iterator for iterating through the entire edge set of the graph.
 

Public Member Functions

void clear ()
 Empty the Graph.
 
VertexView< false > vertices ()
 Returns a view object allowing iteration over the vertices of the graph.
 
VertexView< truevertices () const
 
EdgeView< false > edges ()
 Returns a view object allowing iteration over the edges of the graph.
 
EdgeView< trueedges () const
 
InOutEdgeView< false, trueoutEdges (const VertexIdentifier I)
 Returns a view object allowing iteration over the edges which start at a vertex I.
 
InOutEdgeView< true, trueoutEdges (const VertexIdentifier I) const
 
InOutEdgeView< false, false > inEdges (const VertexIdentifier I)
 Returns a view object allowing iteration over the edges which point to a vertex I.
 
InOutEdgeView< true, false > inEdges (const VertexIdentifier I) const
 
VertexAttribute & operator[] (const VertexIdentifier &I)
 Looks up the vertex with identifier I, if it does not exist it default constructs it.
 
EdgeAttribute & operator[] (const EdgeIdentifier &I)
 Looks up the edge with identifier I, if it does not exist it default constructs it, if it's endpoints do not exist it also default constructs them.
 
Expected< VertexAttribute & > at (const VertexIdentifier &I)
 Looks up a vertex with Identifier I, or an error if it does not exist.
 
Expected< const VertexAttribute & > at (const VertexIdentifier &I) const
 
Expected< EdgeAttribute & > at (const EdgeIdentifier &I)
 Looks up an edge with Identifier I, or an error if it does not exist.
 
Expected< const EdgeAttribute & > at (const EdgeIdentifier &I) const
 
size_type count (const VertexIdentifier &I) const
 Looks for a vertex with identifier I, returns 1 if one exists, and 0 otherwise.
 
size_type count (const EdgeIdentifier &I) const
 Looks for an edge with Identifier I, returns 1 if one exists and 0 otherwise.
 
std::pair< VertexIterator, boolinsert (const std::pair< VertexIdentifier, VertexAttribute > &Val)
 Inserts a vertex into the graph with Identifier Val.first, and Attribute Val.second.
 
std::pair< VertexIterator, boolinsert (std::pair< VertexIdentifier, VertexAttribute > &&Val)
 
std::pair< EdgeIterator, boolinsert (const std::pair< EdgeIdentifier, EdgeAttribute > &Val)
 Inserts an edge into the graph with Identifier Val.first, and Attribute Val.second.
 
std::pair< EdgeIterator, boolinsert (std::pair< EdgeIdentifier, EdgeAttribute > &&Val)
 Inserts an edge into the graph with Identifier Val.first, and Attribute Val.second.
 

Detailed Description

template<typename VertexAttribute, typename EdgeAttribute, typename VI = int32_t>
class llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >

A Graph object represents a Directed Graph and is used in XRay to compute and store function call graphs and associated statistical information.

The graph takes in four template parameters, these are:

Graph is CopyConstructible, CopyAssignable, MoveConstructible and MoveAssignable but is not EqualityComparible or LessThanComparible.

Usage Example Graph with weighted edges and vertices: Graph<int, int, int> G;

G[1] = 0; G[2] = 2; G[{1,2}] = 1; G[{2,1}] = -1; for(const auto &v : G.vertices()){ // Do something with the vertices in the graph; } for(const auto &e : G.edges()){ // Do something with the edges in the graph; }

Usage Example with StrRef keys. Graph<int, double, StrRef> StrG; char va[] = "Vertex A"; char vaa[] = "Vertex A"; char vb[] = "Vertex B"; // Vertices are referenced by String Refs. G[va] = 0; G[vb] = 1; G[{va, vb}] = 1.0; cout() << G[vaa] << " " << G[{vaa, vb}]; //prints "0 1.0".

Definition at line 74 of file Graph.h.

Member Typedef Documentation

◆ ConstEdgeIterator

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
using llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::ConstEdgeIterator = typename EdgeMapT::const_iterator

A const iterator for iterating through the entire edge set of the graph.

Has a const EdgeValueType as its value_type

Definition at line 298 of file Graph.h.

◆ ConstInEdgeIterator

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
using llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::ConstInEdgeIterator = NeighborEdgeIteratorT<true, false>

A const iterator type for iterating through the set of edges entering a vertex.

Has a const EdgeValueType as its value_type

Definition at line 175 of file Graph.h.

◆ ConstOutEdgeIterator

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
using llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::ConstOutEdgeIterator = NeighborEdgeIteratorT<true, true>

A const iterator type for iterating through the set of edges entering a vertex.

Has a const EdgeValueType as its value_type

Definition at line 186 of file Graph.h.

◆ ConstVertexIterator

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
using llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::ConstVertexIterator = typename VertexMapT::const_iterator

A const iterator type for iterating through the whole vertex set of the graph.

Has a const VertexValueType as its value_type

Definition at line 261 of file Graph.h.

◆ EdgeIdentifier

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
typedef std::pair<VI, VI> llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::EdgeIdentifier

Definition at line 78 of file Graph.h.

◆ EdgeIterator

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
using llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::EdgeIterator = typename EdgeMapT::iterator

An iterator for iterating through the entire edge set of the graph.

Has an EdgeValueType as its value_type

Definition at line 303 of file Graph.h.

◆ EdgeValueType

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
using llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::EdgeValueType = detail::DenseMapPair<EdgeIdentifier, EdgeAttribute>

This type is the value_type of all iterators which range over edges, Determined by the Edges DenseMap.

Definition at line 87 of file Graph.h.

◆ InEdgeIterator

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
using llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::InEdgeIterator = NeighborEdgeIteratorT<false, false>

An iterator type for iterating through the set of edges leaving a vertex.

Has an EdgeValueType as its value_type

Definition at line 180 of file Graph.h.

◆ OutEdgeIterator

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
using llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::OutEdgeIterator = NeighborEdgeIteratorT<false, true>

An iterator type for iterating through the set of edges leaving a vertex.

Has an EdgeValueType as its value_type

Definition at line 191 of file Graph.h.

◆ size_type

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
using llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::size_type = std::size_t

Definition at line 89 of file Graph.h.

◆ VertexIdentifier

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
typedef VI llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::VertexIdentifier

These objects are used to name edges and vertices in the graph.

Definition at line 77 of file Graph.h.

◆ VertexIterator

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
using llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::VertexIterator = typename VertexMapT::iterator

An iterator type for iterating through the whole vertex set of the graph.

Has a VertexValueType as its value_type

Definition at line 266 of file Graph.h.

◆ VertexValueType

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
using llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::VertexValueType = detail::DenseMapPair<VertexIdentifier, VertexAttribute>

This type is the value_type of all iterators which range over vertices, Determined by the Vertices DenseMap.

Definition at line 82 of file Graph.h.

Member Function Documentation

◆ at() [1/4]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
Expected< EdgeAttribute & > llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::at ( const EdgeIdentifier I)
inline

Looks up an edge with Identifier I, or an error if it does not exist.

Definition at line 414 of file Graph.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), and I.

◆ at() [2/4]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
Expected< const EdgeAttribute & > llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::at ( const EdgeIdentifier I) const
inline

◆ at() [3/4]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
Expected< VertexAttribute & > llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::at ( const VertexIdentifier I)
inline

Looks up a vertex with Identifier I, or an error if it does not exist.

Definition at line 395 of file Graph.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), and I.

◆ at() [4/4]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
Expected< const VertexAttribute & > llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::at ( const VertexIdentifier I) const
inline

◆ clear()

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
void llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::clear ( )
inline

◆ count() [1/2]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
size_type llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::count ( const EdgeIdentifier I) const
inline

Looks for an edge with Identifier I, returns 1 if one exists and 0 otherwise.

Definition at line 440 of file Graph.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::count(), and I.

◆ count() [2/2]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
size_type llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::count ( const VertexIdentifier I) const
inline

Looks for a vertex with identifier I, returns 1 if one exists, and 0 otherwise.

Definition at line 434 of file Graph.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::count(), and I.

◆ edges() [1/2]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
EdgeView< false > llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::edges ( )
inline

Returns a view object allowing iteration over the edges of the graph.

also allows access to the size of the edge set.

Definition at line 355 of file Graph.h.

◆ edges() [2/2]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
EdgeView< true > llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::edges ( ) const
inline

Definition at line 357 of file Graph.h.

◆ inEdges() [1/2]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
InOutEdgeView< false, false > llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::inEdges ( const VertexIdentifier  I)
inline

Returns a view object allowing iteration over the edges which point to a vertex I.

Definition at line 371 of file Graph.h.

References I.

◆ inEdges() [2/2]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
InOutEdgeView< true, false > llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::inEdges ( const VertexIdentifier  I) const
inline

Definition at line 375 of file Graph.h.

References I.

◆ insert() [1/4]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
std::pair< EdgeIterator, bool > llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::insert ( const std::pair< EdgeIdentifier, EdgeAttribute > &  Val)
inline

Inserts an edge into the graph with Identifier Val.first, and Attribute Val.second.

If the key is already in the map, it returns false and doesn't update the value.

Definition at line 458 of file Graph.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert().

◆ insert() [2/4]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
std::pair< VertexIterator, bool > llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::insert ( const std::pair< VertexIdentifier, VertexAttribute > &  Val)
inline

Inserts a vertex into the graph with Identifier Val.first, and Attribute Val.second.

Definition at line 445 of file Graph.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert().

◆ insert() [3/4]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
std::pair< EdgeIterator, bool > llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::insert ( std::pair< EdgeIdentifier, EdgeAttribute > &&  Val)
inline

Inserts an edge into the graph with Identifier Val.first, and Attribute Val.second.

If the key is already in the map, it returns false and doesn't update the value.

Definition at line 475 of file Graph.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::try_emplace().

◆ insert() [4/4]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
std::pair< VertexIterator, bool > llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::insert ( std::pair< VertexIdentifier, VertexAttribute > &&  Val)
inline

◆ operator[]() [1/2]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
EdgeAttribute & llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::operator[] ( const EdgeIdentifier I)
inline

Looks up the edge with identifier I, if it does not exist it default constructs it, if it's endpoints do not exist it also default constructs them.

Definition at line 386 of file Graph.h.

References I, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::try_emplace().

◆ operator[]() [2/2]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
VertexAttribute & llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::operator[] ( const VertexIdentifier I)
inline

Looks up the vertex with identifier I, if it does not exist it default constructs it.

Definition at line 381 of file Graph.h.

References I.

◆ outEdges() [1/2]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
InOutEdgeView< false, true > llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::outEdges ( const VertexIdentifier  I)
inline

Returns a view object allowing iteration over the edges which start at a vertex I.

Definition at line 361 of file Graph.h.

References I.

◆ outEdges() [2/2]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
InOutEdgeView< true, true > llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::outEdges ( const VertexIdentifier  I) const
inline

Definition at line 365 of file Graph.h.

References I.

◆ vertices() [1/2]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
VertexView< false > llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::vertices ( )
inline

Returns a view object allowing iteration over the vertices of the graph.

also allows access to the size of the vertex set.

Definition at line 349 of file Graph.h.

◆ vertices() [2/2]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
VertexView< true > llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::vertices ( ) const
inline

Definition at line 351 of file Graph.h.


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