Skip to content

DirectedGraph🔗

More...

#include <directed_graph.hpp>

Inherited by DirectedAcyclicGraph< VertexType, VERTEX_LIMIT, DEGREE_LIMIT >

Protected Classes🔗

Name
struct VertexData

Public Types🔗

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

Protected Types🔗

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

Public Functions🔗

Name
virtual ~DirectedGraph() =default
bool addVertex(VertexType * vertex)
virtual bool addEdge(VertexType * fromVertex, VertexType * toVertex)
Index_t getIndex(VertexType const * vertex)
const AdjacencyList * getSuccessors(VertexType const * vertex)
const AdjacencyList * getPredecessors(VertexType const * vertex)
const AdjacencyList * getSuccessors(Index_t index)
const AdjacencyList * getPredecessors(Index_t index)
iox::cxx::vector< VertexType *, VERTEX_LIMIT > getSources()
iox::cxx::vector< VertexType *, VERTEX_LIMIT > getSinks()
bool isSource(VertexType const * vertex)
bool isSink(VertexType const * vertex)
size_t numberOfVertices()
size_t numberOfEdges()

Protected Functions🔗

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

Public Attributes🔗

Name
constexpr Index_t INVALID_INDEX

Protected Attributes🔗

Name
iox::cxx::vector< VertexData, VERTEX_LIMIT > m_vertices
size_t m_numEdges

Detailed Description🔗

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

Todo: : refine and move to utils

Public Types Documentation🔗

using Index_t🔗

using DirectedGraph< VertexType, VERTEX_LIMIT, DEGREE_LIMIT >::Index_t =  int32_t;

using AdjacencyList🔗

using DirectedGraph< VertexType, VERTEX_LIMIT, DEGREE_LIMIT >::AdjacencyList =  iox::cxx::vector<VertexType*, DEGREE_LIMIT>;

Protected Types Documentation🔗

using AdjacencyIndexList🔗

using DirectedGraph< VertexType, VERTEX_LIMIT, DEGREE_LIMIT >::AdjacencyIndexList =  iox::cxx::vector<Index_t, DEGREE_LIMIT>;

Public Functions Documentation🔗

function ~DirectedGraph🔗

virtual ~DirectedGraph() =default

function addVertex🔗

inline bool addVertex(
    VertexType * vertex
)

Parameters:

  • vertex vertex to be added

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

add a vertex to the graph

function addEdge🔗

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

Parameters:

  • fromVertex
  • toVertex

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

Reimplemented by: DirectedAcyclicGraph::addEdge

add an edge between fromVertex and toVertex to the graph

function getIndex🔗

inline Index_t getIndex(
    VertexType const * vertex
)

Parameters:

  • vertex vertex of which the index is requested

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

get the internal index of a given vertex

function getSuccessors🔗

inline const AdjacencyList * getSuccessors(
    VertexType const * vertex
)

Parameters:

  • vertex vertex of which the successors are requested

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

get the direct successors of a given vertex in the graph

function getPredecessors🔗

inline const AdjacencyList * getPredecessors(
    VertexType const * vertex
)

Parameters:

  • vertex vertex of which the predecessors are requested

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

get the direct predecessors of a given vertex in the graph

function getSuccessors🔗

inline const AdjacencyList * getSuccessors(
    Index_t index
)

Parameters:

  • index index of vertex of which the successors are requested

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

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

function getPredecessors🔗

inline const AdjacencyList * getPredecessors(
    Index_t index
)

Parameters:

  • index index of vertex of which the predecessors are requested

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

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

function getSources🔗

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

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

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

function getSinks🔗

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

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

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

function isSource🔗

inline bool isSource(
    VertexType const * vertex
)

Parameters:

  • vertex to be checked

Return: true iff the vertex is a source

check whether the given vertex is a source

function isSink🔗

inline bool isSink(
    VertexType const * vertex
)

Parameters:

  • vertex to be checked

Return: true if the vertex is a sink

check whether the given vertex is a sink

function numberOfVertices🔗

inline size_t numberOfVertices()

Return: number of vertices

get the number of vertices

function numberOfEdges🔗

inline size_t numberOfEdges()

Return: number of edges

get the number of edges

Protected Functions Documentation🔗

function findVertex🔗

inline Index_t findVertex(
    VertexType const * vertex
) const

function isValid🔗

inline bool isValid(
    Index_t index
)

Public Attributes Documentation🔗

variable INVALID_INDEX🔗

static constexpr Index_t INVALID_INDEX = -1;

Protected Attributes Documentation🔗

variable m_vertices🔗

iox::cxx::vector< VertexData, VERTEX_LIMIT > m_vertices;

variable m_numEdges🔗

size_t m_numEdges {0};

Updated on 17 June 2021 at 11:15:26 CEST