DirectedGraph🔗
#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 31 May 2022 at 15:52:33 CEST