Skip to content

DirectedAcyclicGraph🔗

More...

#include <directed_acyclic_graph.hpp>

Inherits from DirectedGraph< VertexType, VERTEX_LIMIT, DEGREE_LIMIT >

Public Types🔗

Name
using typename base_type::Index_t Index_t

Public Functions🔗

Name
DirectedAcyclicGraph()
virtual bool addEdge(VertexType * fromVertex, VertexType * toVertex)

Additional inherited members🔗

Protected Classes inherited from DirectedGraph< VertexType, VERTEX_LIMIT, DEGREE_LIMIT >

Name
struct VertexData

Public Types inherited from DirectedGraph< VertexType, VERTEX_LIMIT, DEGREE_LIMIT >

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

Protected Types inherited from DirectedGraph< VertexType, VERTEX_LIMIT, DEGREE_LIMIT >

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

Public Functions inherited from DirectedGraph< VertexType, VERTEX_LIMIT, DEGREE_LIMIT >

Name
virtual ~DirectedGraph() =default
bool addVertex(VertexType * vertex)
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 inherited from DirectedGraph< VertexType, VERTEX_LIMIT, DEGREE_LIMIT >

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

Public Attributes inherited from DirectedGraph< VertexType, VERTEX_LIMIT, DEGREE_LIMIT >

Name
constexpr Index_t INVALID_INDEX

Protected Attributes inherited from DirectedGraph< VertexType, VERTEX_LIMIT, DEGREE_LIMIT >

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

Todo: : refine and move to utils same functionality as its parent class DirectedGraph, except that adding edges that close a cycle is impossible now (this incurs a checking overhead of course)

Public Types Documentation🔗

using Index_t🔗

using DirectedAcyclicGraph< VertexType, VERTEX_LIMIT, DEGREE_LIMIT >::Index_t =  typename base_type::Index_t;

Public Functions Documentation🔗

function DirectedAcyclicGraph🔗

inline DirectedAcyclicGraph()

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. it would create a cycle)

Reimplements: DirectedGraph::addEdge

add an edge between fromVertex and toVertex to the graph


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