helios::ecs::Dag Class Reference

Directed acyclic graph used to compute the topological execution order of systems within a schedule. More...

#include <dag.hpp>

Public Member Functions
	Dag ()=default
	Dag (const Dag &)=delete
	Dag (Dag &&) noexcept=default
	~Dag ()=default
Dag &	operator= (const Dag &)=delete
Dag &	operator= (Dag &&) noexcept=default
size_t	AddNode (SystemId id)
	Adds a node for id.
auto	AddEdge (SystemId from, SystemId to) -> DagResult< void >
	Adds a directed edge from from to to (from must run before to).
auto	Sort () const -> DagResult< std::vector< SystemId > >
	Performs a topological sort and returns system ids in execution order.
auto	IndexOf (SystemId id) const -> DagResult< size_t >
	Gets the internal index of id.
bool	HasCycle () const
	Checks if this DAG has a cycle.
bool	Reachable (SystemId from, SystemId to) const
	Checks whether to is reachable from from along directed edges.
auto	Nodes () const noexcept -> std::span< const SystemId >
	Gets a read-only view of all nodes (in insertion order).

Detailed Description

Directed acyclic graph used to compute the topological execution order of systems within a schedule.

Definition at line 33 of file dag.hpp.

Constructor & Destructor Documentation

Dag() [1/3]

helios::ecs::Dag::Dag ( )

default

Dag() [2/3]

helios::ecs::Dag::Dag ( const Dag & )

delete

Dag() [3/3]

helios::ecs::Dag::Dag ( Dag && )

defaultnoexcept

~Dag()

helios::ecs::Dag::~Dag ( )

default

Member Function Documentation

AddEdge()

auto helios::ecs::Dag::AddEdge ( SystemId from, SystemId to ) -> DagResult< void >

nodiscard

Adds a directed edge from from to to (from must run before to).

Does not perform per-insertion cycle detection - O(1). Call Sort() after all edges have been added; it detects cycles as a side effect of Kahn's topological sort at O(V+E) total cost.

Returns

Result of the operation

Definition at line 40 of file dag.cpp.

AddNode()

size_t helios::ecs::Dag::AddNode

(

SystemId

id

)

Adds a node for id.

Returns

Internal index of the added node

Definition at line 16 of file dag.cpp.

HasCycle()

bool helios::ecs::Dag::HasCycle ( ) const

nodiscard

Checks if this DAG has a cycle.

Returns

true if a cycle is detected, false otherwise

Definition at line 194 of file dag.cpp.

IndexOf()

auto helios::ecs::Dag::IndexOf ( SystemId id ) const -> DagResult< size_t >

nodiscard

Gets the internal index of id.

Returns

Internal index on success, DagError on failure

Definition at line 26 of file dag.cpp.

Nodes()

auto helios::ecs::Dag::Nodes ( ) const -> std::span< const SystemId >

inlinenodiscardnoexcept

Gets a read-only view of all nodes (in insertion order).

Returns

Read-only span of system ids in insertion order

Definition at line 89 of file dag.hpp.

operator=() [1/2]

Dag & helios::ecs::Dag::operator= ( const Dag & )

delete

operator=() [2/2]

Dag & helios::ecs::Dag::operator= ( Dag && )

defaultnoexcept

Reachable()

bool helios::ecs::Dag::Reachable ( SystemId from, SystemId to ) const

nodiscard

Checks whether to is reachable from from along directed edges.

Parameters

from	Source system id
to	Target system id

Returns

True if a directed path exists from from to to

Definition at line 230 of file dag.cpp.

Sort()

auto helios::ecs::Dag::Sort ( ) const -> DagResult< std::vector< SystemId > >

nodiscard

Performs a topological sort and returns system ids in execution order.

Returns

Sorted ids on success, DagError on failure

Definition at line 65 of file dag.cpp.