Template Class DirectedGraph

Nested Relationships

Nested Types

Inheritance Relationships

Derived Type

Class Documentation

template<typename VertexType, int32_t VERTEX_LIMIT, int32_t DEGREE_LIMIT>
class DirectedGraph

Subclassed by DirectedAcyclicGraph< VertexType, VERTEX_LIMIT, DEGREE_LIMIT >

Public Types

using Index_t = int32_t
using AdjacencyList = iox::cxx::vector<VertexType*, DEGREE_LIMIT>

Public Functions

virtual ~DirectedGraph() = default
inline bool addVertex(VertexType *vertex)

add a vertex to the graph

Parameters:

vertex – [in] vertex to be added

Returns:

pointer true if the vertex was added successfully, false otherwise (e.g. capacity reached or vertex already exists)

inline virtual bool addEdge(VertexType *fromVertex, VertexType *toVertex)

add an edge between fromVertex and toVertex to the graph

Parameters:

  • fromVertex – [in]

  • toVertex – [in]

Returns:

pointer true if the edge was added successfully, false otherwise (e.g. vertices do not exist)

inline Index_t getIndex(VertexType const *vertex)

get the internal index of a given vertex

Parameters:

vertex – [in] vertex of which the index is requested

Returns:

internal index of vertex, -1 if vertex does not exist

inline const AdjacencyList *getSuccessors(VertexType const *vertex)

get the direct successors of a given vertex in the graph

Parameters:

vertex – [in] vertex of which the successors are requested

Returns:

pointer to the list of successors, nullptr if vertex does not exist

inline const AdjacencyList *getPredecessors(VertexType const *vertex)

get the direct predecessors of a given vertex in the graph

Parameters:

vertex – [in] vertex of which the predecessors are requested

Returns:

pointer to the list of predecessors, nullptr if vertex does not exist

inline const AdjacencyList *getSuccessors(Index_t index)

get the direct successors of a given vertex index in the graph

Parameters:

index – [in] index of vertex of which the successors are requested

Returns:

pointer to the list of successors, nullptr if index does not exist in the graph

inline const AdjacencyList *getPredecessors(Index_t index)

get the direct predecessors of a given vertex index in the graph

Parameters:

index – [in] index of vertex of which the predecessors are requested

Returns:

pointer to the list of predecessors, nullptr if index does not exist in the graph

inline iox::cxx::vector<VertexType*, VERTEX_LIMIT> getSources()

get the source vertices of the graph, i.e. vertices without incoming edges

Returns:

vector filled with source vertices (might be empty if e.g. the graph is a cycle)

inline iox::cxx::vector<VertexType*, VERTEX_LIMIT> getSinks()

get the sink vertices of the graph, i.e. vertices without outgoing edges

Returns:

vector filled with sink vertices (might be empty if e.g. the graph is a cycle)

inline bool isSource(VertexType const *vertex)

check whether the given vertex is a source

Parameters:

vertex – [in] to be checked

Returns:

true iff the vertex is a source

inline bool isSink(VertexType const *vertex)

check whether the given vertex is a sink

Parameters:

vertex – [in] to be checked

Returns:

true if the vertex is a sink

inline size_t numberOfVertices()

get the number of vertices

Returns:

number of vertices

inline size_t numberOfEdges()

get the number of edges

Returns:

number of edges

Public Static Attributes

static constexpr Index_t INVALID_INDEX = -1

Protected Types

using AdjacencyIndexList = iox::cxx::vector<Index_t, DEGREE_LIMIT>

Protected Functions

inline Index_t findVertex(VertexType const *vertex) const
inline bool isValid(Index_t index)

Protected Attributes

iox::cxx::vector<VertexData, VERTEX_LIMIT> m_vertices
size_t m_numEdges = {0}
struct VertexData

Public Functions

inline explicit VertexData(VertexType *vertex)

Public Members

VertexType *vertex
AdjacencyIndexList predecessorIndices
AdjacencyIndexList successorIndices
AdjacencyList predecessors
AdjacencyList successors