EntropyEngine::Core::Graph::DirectedAcyclicGraph

Cache-friendly directed acyclic graph implementation. More…

#include <DirectedAcyclicGraph.h>

Public Functions

	Name
bool	wouldCreateCycle(uint32_t from, uint32_t to) const Checks if adding an edge would create a cycle.
std::vector< uint32_t >	topologicalSort() const Performs topological sort on the graph.
bool	removeNode(AcyclicNodeHandle< T > node) Removes a node from the graph.
bool	removeEdge(AcyclicNodeHandle< T > from, AcyclicNodeHandle< T > to) Removes a directed edge between two nodes.
void	removeAllEdges(uint32_t nodeIndex) Removes all edges connected to a node.
size_t	nodeCount() const Gets the number of active nodes in the graph.
bool	isHandleValid(const AcyclicNodeHandle< T > & handle) const Validates a node handle.
bool	hasEdge(uint32_t from, uint32_t to) const Checks if a directed edge exists between two nodes.
std::vector< AcyclicNodeHandle< T > >	getParents(const AcyclicNodeHandle< T > & node) const Gets the parents of a node as handles.
std::vector< AcyclicNodeHandle< T > >	getParents(const AcyclicNodeHandle< T > & node)
std::span< const uint32_t >	getOutgoingEdges(uint32_t nodeIndex) const Gets outgoing edges for a node.
T *	getNodeData(AcyclicNodeHandle< T > node) Gets mutable pointer to node data.
const T *	getNodeData(AcyclicNodeHandle< T > node) const Gets const pointer to node data.
std::span< const uint32_t >	getIncomingEdges(uint32_t nodeIndex) const Gets incoming edges for a node.
std::vector< AcyclicNodeHandle< T > >	getChildren(const AcyclicNodeHandle< T > & node) const Gets the children of a node as handles.
std::vector< AcyclicNodeHandle< T > >	getChildren(const AcyclicNodeHandle< T > & node)
void	clear() Clears all nodes and edges from the graph.
AcyclicNodeHandle< T >	addNode(T data) Adds a new node to the graph.
void	addEdge(AcyclicNodeHandle< T > from, AcyclicNodeHandle< T > to) Adds a directed edge from one node to another.
	DirectedAcyclicGraph() Constructs a new DirectedAcyclicGraph instance.

Friends

	Name
class	AcyclicNodeHandle

Detailed Description

template <class T >
class EntropyEngine::Core::Graph::DirectedAcyclicGraph;

Cache-friendly directed acyclic graph implementation.

Template Parameters:

T The type of data to be stored in each node of the graph.

Manages dependencies between entities while preventing cycles. Uses contiguous storage for cache efficiency and generation-based handles for safe node references. Ideal for task scheduling, build systems, and dependency management.

Public Functions Documentation

function wouldCreateCycle

inline bool wouldCreateCycle(
    uint32_t from,
    uint32_t to
) const

Checks if adding an edge would create a cycle.

Parameters:

from Index of potential source node
to Index of potential destination node

Return: true if adding the edge would create a cycle

Uses DFS to check if from is reachable from to.

DirectedAcyclicGraph<int> graph;
auto n1 = graph.addNode(1);
auto n2 = graph.addNode(2);
auto n3 = graph.addNode(3);
graph.addEdge(n1, n2);
graph.addEdge(n2, n3);

// This would create a cycle: n3 -> n1 -> n2 -> n3
bool createsCycle = graph.wouldCreateCycle(n3.getIndex(), n1.getIndex()); // true

function topologicalSort

inline std::vector< uint32_t > topologicalSort() const

Performs topological sort on the graph.

Return: Vector of node indices in topological order

Returns nodes in dependency order using Kahn’s algorithm. For every edge u -> v, node u appears before v in the result.

DirectedAcyclicGraph<std::string> taskGraph;
auto compile = taskGraph.addNode("Compile Source");
auto link = taskGraph.addNode("Link Executable");
auto test = taskGraph.addNode("Run Tests");
auto deploy = taskGraph.addNode("Deploy Application");

taskGraph.addEdge(compile, link);
taskGraph.addEdge(link, test);
taskGraph.addEdge(test, deploy);

std::vector<uint32_t> order = taskGraph.topologicalSort();
for (uint32_t nodeIndex : order) {
    // In a real scenario, you'd get the node data and execute the task
    std::cout << "Executing: " << *taskGraph.getNodeData(AcyclicNodeHandle<std::string>(nullptr, nodeIndex, 0))
<< std::endl;
}
// Expected output order: Compile Source, Link Executable, Run Tests, Deploy Application

function removeNode

inline bool removeNode(
    AcyclicNodeHandle< T > node
)

Removes a node from the graph.

Parameters:

node Handle of the node to remove

Return: true if successfully removed, false if handle was invalid

Invalidates the handle and removes all connected edges.

DirectedAcyclicGraph<int> graph;
auto node1 = graph.addNode(1);
auto node2 = graph.addNode(2);
graph.addEdge(node1, node2);

bool removed = graph.removeNode(node1);
// removed will be true
bool isValid = graph.isHandleValid(node1);
// isValid will be false

function removeEdge

inline bool removeEdge(
    AcyclicNodeHandle< T > from,
    AcyclicNodeHandle< T > to
)

Removes a directed edge between two nodes.

Parameters:

from The source node handle
to The target node handle

Return: true if edge was removed, false if it didn’t exist

function removeAllEdges

inline void removeAllEdges(
    uint32_t nodeIndex
)

Removes all edges connected to a node.

Parameters:

nodeIndex Index of the node to disconnect

Disconnects both incoming and outgoing edges. O(degree) complexity.

DirectedAcyclicGraph<int> graph;
auto n1 = graph.addNode(1);
auto n2 = graph.addNode(2);
auto n3 = graph.addNode(3);
graph.addEdge(n1, n2);
graph.addEdge(n3, n2);

graph.removeAllEdges(n2.getIndex());
// Now, n1 -> n2 and n3 -> n2 edges are removed.

function nodeCount

inline size_t nodeCount() const

Gets the number of active nodes in the graph.

Return: Count of occupied node slots

function isHandleValid

inline bool isHandleValid(
    const AcyclicNodeHandle< T > & handle
) const

Validates a node handle.

Parameters:

handle The handle to validate

Return: true if handle is valid and points to an active node

Checks if the handle refers to an existing node by verifying index bounds, occupancy status, and generation count.

DirectedAcyclicGraph<int> graph;
auto node1 = graph.addNode(10);
auto node2 = graph.addNode(20);

bool valid1 = graph.isHandleValid(node1); // true
graph.removeNode(node1);
bool valid1_after_remove = graph.isHandleValid(node1); // false

function hasEdge

inline bool hasEdge(
    uint32_t from,
    uint32_t to
) const

Checks if a directed edge exists between two nodes.

Parameters:

from Index of the source node
to Index of the destination node

Return: true if edge exists from from to to

DirectedAcyclicGraph<int> graph;
auto nodeA = graph.addNode(1);
auto nodeB = graph.addNode(2);
graph.addEdge(nodeA, nodeB);

bool has = graph.hasEdge(nodeA.getIndex(), nodeB.getIndex()); // true
bool has_reverse = graph.hasEdge(nodeB.getIndex(), nodeA.getIndex()); // false

function getParents

inline std::vector< AcyclicNodeHandle< T > > getParents(
    const AcyclicNodeHandle< T > & node
) const

Gets the parents of a node as handles.

Parameters:

node The child node handle

Return: Vector of parent node handles

auto parent1 = graph.addNode("Parent 1");
auto parent2 = graph.addNode("Parent 2");
auto child = graph.addNode("Child");
graph.addEdge(parent1, child);
graph.addEdge(parent2, child);

auto parents = graph.getParents(child);
for (auto parent : parents) {
    std::cout << "Parent: " << parent.getData()->name << std::endl;
}

function getParents

inline std::vector< AcyclicNodeHandle< T > > getParents(
    const AcyclicNodeHandle< T > & node
)

function getOutgoingEdges

inline std::span< const uint32_t > getOutgoingEdges(
    uint32_t nodeIndex
) const

Gets outgoing edges for a node.

Parameters:

nodeIndex Index of the node

Return: Span of indices this node points to

DirectedAcyclicGraph<int> graph;
auto n1 = graph.addNode(1);
auto n2 = graph.addNode(2);
auto n3 = graph.addNode(3);
graph.addEdge(n1, n2);
graph.addEdge(n1, n3);

for (uint32_t neighborIndex : graph.getOutgoingEdges(n1.getIndex())) {
    // Process neighborIndex (e.g., get its data)
    std::cout << "Node 1 has outgoing edge to: " << neighborIndex << std::endl;
}

function getNodeData

inline T * getNodeData(
    AcyclicNodeHandle< T > node
)

Gets mutable pointer to node data.

Parameters:

node Handle to the node

Return: Pointer to the node’s data, or nullptr if invalid

Returns nullptr if the handle is invalid.

DirectedAcyclicGraph<int> graph;
auto nodeHandle = graph.addNode(100);
int* data = graph.getNodeData(nodeHandle);
if (data) {
    *data = 200; // Modify the node's data
}

function getNodeData

inline const T * getNodeData(
    AcyclicNodeHandle< T > node
) const

Gets const pointer to node data.

Parameters:

node Handle to the node

Return: Const pointer to the node’s data, or nullptr if invalid

Provides read-only access with handle validation.

DirectedAcyclicGraph<std::string> graph;
auto nodeHandle = graph.addNode("Hello World");
const std::string* data = graph.getNodeData(nodeHandle);
if (data) {
    std::cout << *data << std::endl; // Read the node's data
}

function getIncomingEdges

inline std::span< const uint32_t > getIncomingEdges(
    uint32_t nodeIndex
) const

Gets incoming edges for a node.

Parameters:

nodeIndex Index of the node

Return: Span of indices that point to this node

DirectedAcyclicGraph<int> graph;
auto n1 = graph.addNode(1);
auto n2 = graph.addNode(2);
auto n3 = graph.addNode(3);
graph.addEdge(n1, n3);
graph.addEdge(n2, n3);

for (uint32_t predecessorIndex : graph.getIncomingEdges(n3.getIndex())) {
    // Process predecessorIndex
    std::cout << "Node 3 has incoming edge from: " << predecessorIndex << std::endl;
}

function getChildren

inline std::vector< AcyclicNodeHandle< T > > getChildren(
    const AcyclicNodeHandle< T > & node
) const

Gets the children of a node as handles.

Parameters:

node Parent node handle

Return: Vector of child node handles

auto parent = graph.addNode("Parent");
auto child1 = graph.addNode("Child 1");
auto child2 = graph.addNode("Child 2");
graph.addEdge(parent, child1);
graph.addEdge(parent, child2);

auto children = graph.getChildren(parent);
for (auto child : children) {
    std::cout << "Child: " << child.getData()->name << std::endl;
}

function getChildren

inline std::vector< AcyclicNodeHandle< T > > getChildren(
    const AcyclicNodeHandle< T > & node
)

function clear

inline void clear()

Clears all nodes and edges from the graph.

Removes all nodes and edges, resetting the graph to an empty state. All existing handles become invalid after this operation.

DirectedAcyclicGraph<int> graph;
auto n1 = graph.addNode(1);
auto n2 = graph.addNode(2);
graph.addEdge(n1, n2);

graph.clear();
// Graph is now empty, n1 and n2 handles are invalid
bool valid = graph.isHandleValid(n1); // false

function addNode

inline AcyclicNodeHandle< T > addNode(
    T data
)

Adds a new node to the graph.

Parameters:

data The data to store in the node

Return: Handle to the newly added node

Reuses freed slots when available, otherwise extends storage.

DirectedAcyclicGraph<std::string> stringGraph;
auto taskA = stringGraph.addNode("Download Data");
auto taskB = stringGraph.addNode("Process Data");
auto taskC = stringGraph.addNode("Upload Results");

// taskA, taskB, taskC are now valid handles to nodes in the graph.

function addEdge

inline void addEdge(
    AcyclicNodeHandle< T > from,
    AcyclicNodeHandle< T > to
)

Adds a directed edge from one node to another.

Parameters:

from Source node handle
to Destination node handle

Exceptions:

std::invalid_argument If handles invalid, self-loop, or would create cycle

Establishes a dependency where from must precede to. Prevents cycles.

DirectedAcyclicGraph<std::string> buildGraph;
auto compile = buildGraph.addNode("Compile Source");
auto link = buildGraph.addNode("Link Executable");
auto deploy = buildGraph.addNode("Deploy Application");

try {
    buildGraph.addEdge(compile, link); // Link depends on compile
    buildGraph.addEdge(link, deploy);   // Deploy depends on link
    // buildGraph.addEdge(deploy, compile); // This would throw std::invalid_argument (cycle detected)
} catch (const std::invalid_argument& e) {
    std::cerr << "Error adding edge: " << e.what() << std::endl;
}

function DirectedAcyclicGraph

inline DirectedAcyclicGraph()

Constructs a new DirectedAcyclicGraph instance.

Pre-allocates storage for 64 nodes to reduce initial reallocations.

// Create a graph to store integer data
DirectedAcyclicGraph<int> myGraph;

// Add some nodes
auto node1 = myGraph.addNode(10);
auto node2 = myGraph.addNode(20);

Friends

friend AcyclicNodeHandle

friend class AcyclicNodeHandle(
    AcyclicNodeHandle
);

Updated on 2026-01-26 at 17:14:35 -0500