Class ScyllaGraphAlgorithms

Static utility class providing fundamental graph algorithms that operate on any graph implementing IScyllaGraph or IScyllaReadOnlyGraph.

All algorithms are non-allocating where possible: a reusable edge buffer is grown lazily on the stack of each call so that typical traversals avoid heap allocations beyond the visited set and priority queue. The initial buffer size is DEFAULT_EDGE_BUFFER_SIZE (16 edges); it is reallocated to exact size if a node has more outgoing edges.

Algorithms that require a concrete node list (TopologicalSort(IScyllaGraph, out int[]), ConnectedComponents(IScyllaReadOnlyGraph, out ScyllaMap<int, int>), StronglyConnectedComponents(IScyllaReadOnlyGraph, out ScyllaMap<int, int>)) require the graph to implement IScyllaReadOnlyGraph so they can call CopyAllNodes(Span<ScyllaGraphNode>).

Complexity summaries use standard graph notation where V is the vertex (node) count and E is the edge count.

Inheritance

object

ScyllaGraphAlgorithms

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Namespace: Scylla.Core.Structures

Assembly: ScyllaCore.dll

Syntax

public static class ScyllaGraphAlgorithms

Methods

AStar(IScyllaGraph, int, int, Func<int, float>)

Computes the shortest path between two nodes using the A* algorithm: Dijkstra's search guided by an admissible heuristic estimate of the remaining cost to the target.

A* expands nodes in order of f = g + h, where g is the known cost from the source and h is heuristic's estimate of the cost to the target. When the heuristic never overestimates the true remaining cost (is admissible), the path returned is optimal. A heuristic that returns 0 for every node degrades A* to Dijkstra.

Like Dijkstra(IScyllaGraph, int, int), this uses lazy deletion (stale queue entries are skipped when popped) and requires non-negative edge weights; a negative weight throws InvalidOperationException.

Declaration

public static ScyllaGraphPath AStar(IScyllaGraph graph, int sourceID, int targetID, Func<int, float> heuristic)

Parameters

Type	Name	Description
IScyllaGraph	graph	The graph to search. Edge weights come from Weight. Must not be null.
int	sourceID	The ID of the starting node. Must exist in graph.
int	targetID	The ID of the destination node. Must exist in graph.
Func<int, float>	heuristic	A function estimating the remaining cost from a given node to targetID. Must be non-negative and, for an optimal result, admissible (never greater than the true remaining cost). For a unit-cost hex grid, id => HexCoord.Distance(adapter.NodeToCoord(id), targetCoord) is admissible.

Returns

Type	Description
ScyllaGraphPath	A valid ScyllaGraphPath from sourceID to targetID, or CreateInvalid() when no path exists.

Exceptions

Type	Condition
ArgumentNullException	Thrown when graph or heuristic is null.
ArgumentException	Thrown when sourceID or targetID does not exist.
InvalidOperationException	Thrown when a negative-weight edge is encountered.

See Also

Dijkstra(IScyllaGraph, int, int)

ScyllaGraphPath

BFS(IScyllaGraph, int, ScyllaBitArray, Func<int, bool>)

Performs a breadth-first search (BFS) using a caller-supplied visited set, enabling multi-source BFS or incremental searches without re-allocating the visited tracking structure.

The visited bit array is NOT cleared before use. Any nodes whose bit is already set are treated as pre-visited and will not be enqueued. This allows callers to seed multiple sources by setting the bits for previously processed nodes before each call.

Nodes whose ID is greater than or equal to visited.Capacity are silently skipped to guard against graphs where node IDs may exceed the pre-sized capacity.

Time complexity: O(V + E). Space complexity: O(V) for the queue.

Declaration

public static int BFS(IScyllaGraph graph, int sourceID, ScyllaBitArray visited, Func<int, bool> visitor = null)

Parameters

Type	Name	Description
IScyllaGraph	graph	The graph to search. Must not be null.
int	sourceID	The ID of the node from which traversal begins. Must be in the range [0, visited.Capacity).
ScyllaBitArray	visited	Pre-allocated bit array used to track which nodes have been enqueued. Its capacity must be at least sourceID + 1. The array is modified in place - bits are set for every node enqueued during this call. Must not be null.
Func<int, bool>	visitor	Optional callback. Return false to stop the search early. Pass null to visit all reachable nodes.

Returns

Type	Description
int	The number of nodes dequeued and visited during this call.

Exceptions

Type	Condition
ArgumentNullException	Thrown when graph or visited is null.
ArgumentOutOfRangeException	Thrown when sourceID is outside the range [0, visited.Capacity).

BFS(IScyllaGraph, int, Func<int, bool>)

Performs a breadth-first search (BFS) starting from the specified source node, visiting nodes in order of increasing hop distance from the source.

This overload allocates a fresh ScyllaBitArray sized to maxNodeID + 1 so the caller does not need to manage the visited set. Use the overload that accepts an explicit ScyllaBitArray when performing multi-source BFS or when the visited set needs to persist across multiple searches.

Time complexity: O(V + E). Space complexity: O(V) for the visited set and queue.

Declaration

public static int BFS(IScyllaGraph graph, int sourceID, Func<int, bool> visitor = null)

Parameters

Type	Name	Description
IScyllaGraph	graph	The graph to search. Must implement IScyllaReadOnlyGraph so that the maximum node ID can be determined for visited-set sizing. Must not be null.
int	sourceID	The ID of the node from which traversal begins. Must exist in graph.
Func<int, bool>	visitor	Optional callback invoked once per visited node. Receives the node ID and returns a bool: return true to continue, false to stop the search immediately. The node that caused the early exit is counted in the return value. Pass null to visit all reachable nodes.

Returns

Type	Description
int	The number of nodes that were visited (including the source). If visitor returns false, the count reflects nodes visited up to and including the node that triggered the stop.

Exceptions

Type	Condition
ArgumentNullException	Thrown when graph is null.
ArgumentException	Thrown when sourceID does not exist in graph.

ConnectedComponents(IScyllaReadOnlyGraph, out ScyllaMap<int, int>)

Computes connected components for an undirected graph using union-find (a ScyllaDisjointSet with path compression and union-by-rank).

Because node IDs can be sparse (non-contiguous integers), the algorithm first builds a dense index mapping: each node ID is mapped to a sequential index 0..N-1. The returned ScyllaDisjointSet operates on these dense indices. Use nodeIDMapping to translate between a node ID and its disjoint-set index.

Two nodes belong to the same component if and only if dsu.Find(nodeIDMapping[a]) == dsu.Find(nodeIDMapping[b]). The number of components is dsu.ComponentCount.

For directed graphs, pass the graph to this method to compute weakly connected components (all edges treated as undirected). To compute strongly connected components in a directed graph, use StronglyConnectedComponents(IScyllaReadOnlyGraph, out ScyllaMap<int, int>) instead.

Time complexity: O((V + E) * alpha(V)), where alpha is the inverse Ackermann function (effectively constant). Space complexity: O(V) for the disjoint set and the node ID mapping.

Declaration

public static ScyllaDisjointSet ConnectedComponents(IScyllaReadOnlyGraph graph, out ScyllaMap<int, int> nodeIDMapping)

Parameters

Type	Name	Description
IScyllaReadOnlyGraph	graph	The graph to analyze. Must implement IScyllaReadOnlyGraph so all nodes can be enumerated via CopyAllNodes(Span<ScyllaGraphNode>). Should be undirected for standard connected-component semantics. Must not be null.
ScyllaMap<int, int>	nodeIDMapping	When this method returns, contains a ScyllaMap<TKey, TValue> from node ID (key) to dense disjoint-set index (value, in range [0, NodeCount)). Pass any index into Find(int) to determine which component a node belongs to.

Returns

Type	Description
ScyllaDisjointSet	A ScyllaDisjointSet of size NodeCount representing the connected components. Call ComponentCount for the total number of components.

Exceptions

Type	Condition
ArgumentNullException	Thrown when graph is null.

See Also

StronglyConnectedComponents(IScyllaReadOnlyGraph, out ScyllaMap<int, int>)

ScyllaDisjointSet

DFS(IScyllaGraph, int, ScyllaBitArray, Func<int, bool>)

Performs a depth-first search (DFS) using a caller-supplied visited set, enabling multi-source DFS or incremental searches without re-allocating the visited structure.

The visited bit array is NOT cleared before use. Nodes already marked as visited are skipped. This allows callers to seed the visited set across multiple calls.

Nodes pushed onto the stack but not yet popped are not immediately marked visited; the visited bit is set only when a node is popped and processed. This is the standard iterative DFS pattern, and ensures that a node pushed multiple times from different parents is processed only once.

Neighbor ordering: neighbors are pushed in reverse order so that the first neighbor returned by GetNeighborsNonAlloc(int, Span<ScyllaGraphEdge>) is processed first, matching recursive DFS ordering.

Nodes with IDs outside [0, visited.Capacity) are silently skipped.

Time complexity: O(V + E). Space complexity: O(V) for the stack.

Declaration

public static int DFS(IScyllaGraph graph, int sourceID, ScyllaBitArray visited, Func<int, bool> visitor = null)

Parameters

Type	Name	Description
IScyllaGraph	graph	The graph to search. Must not be null.
int	sourceID	The ID of the node at which traversal begins. Must be in the range [0, visited.Capacity).
ScyllaBitArray	visited	Pre-allocated bit array for tracking visited nodes. Modified in place - bits are set for every node visited during this call. Must not be null.
Func<int, bool>	visitor	Optional callback. Return false to stop the search early. Pass null to visit all reachable nodes.

Returns

Type	Description
int	The number of nodes visited during this call.

Exceptions

Type	Condition
ArgumentNullException	Thrown when graph or visited is null.
ArgumentOutOfRangeException	Thrown when sourceID is outside the range [0, visited.Capacity).

DFS(IScyllaGraph, int, Func<int, bool>)

Performs a depth-first search (DFS) starting from the specified source node using an iterative (stack-based) approach, which avoids C# call-stack overflow on deep graphs.

Neighbor ordering is preserved: neighbors are pushed onto the internal stack in reverse order so that the first neighbor returned by GetNeighborsNonAlloc(int, Span<ScyllaGraphEdge>) is processed first. This mimics the ordering you would get from a recursive DFS.

This overload allocates a fresh ScyllaBitArray sized to maxNodeID + 1. Use the overload that accepts an explicit ScyllaBitArray for multi-source DFS or when the visited set must persist across calls.

Time complexity: O(V + E). Space complexity: O(V) for the visited set and stack.

Declaration

public static int DFS(IScyllaGraph graph, int sourceID, Func<int, bool> visitor = null)

Parameters

Type	Name	Description
IScyllaGraph	graph	The graph to search. Must implement IScyllaReadOnlyGraph for visited-set sizing. Must not be null.
int	sourceID	The ID of the node at which traversal begins. Must exist in graph.
Func<int, bool>	visitor	Optional callback invoked once per visited node. Returns false to stop the search early. Pass null to visit all reachable nodes.

Returns

Type	Description
int	The number of nodes visited. If visitor returns false, the count reflects nodes visited up to and including the node that triggered the stop.

Exceptions

Type	Condition
ArgumentNullException	Thrown when graph is null.
ArgumentException	Thrown when sourceID does not exist in graph.

Dijkstra(IScyllaGraph, int, int)

Computes the shortest path between two nodes using Dijkstra's algorithm with a min-heap priority queue.

All edge weights in the graph must be non-negative. If a negative-weight edge is encountered during traversal, an InvalidOperationException is thrown immediately. For graphs with negative weights, use the Bellman-Ford algorithm instead.

The algorithm uses a lazy-deletion approach: nodes are re-enqueued with updated costs rather than performing a decrease-key operation. Stale entries in the priority queue are discarded when popped (status check: skip if already STATUS_CLOSED).

If sourceID equals targetID, a valid single-node path with zero cost is returned immediately without any traversal.

Time complexity: O((V + E) log V) with the binary min-heap used internally. Space complexity: O(V) for the search state array and priority queue.

Declaration

public static ScyllaGraphPath Dijkstra(IScyllaGraph graph, int sourceID, int targetID)

Parameters

Type	Name	Description
IScyllaGraph	graph	The graph to search. Edge weights are read from Weight; for unweighted graphs all edges are treated as weight 1.0. Must not be null.
int	sourceID	The ID of the starting node. Must exist in graph.
int	targetID	The ID of the destination node. Must exist in graph.

Returns

Type	Description
ScyllaGraphPath	A ScyllaGraphPath where IsValid is true and NodeIDs contains the sequence of node IDs from sourceID to targetID (inclusive) with minimum total cost. If no path exists between the two nodes, returns CreateInvalid() with IsValid set to false.

Exceptions

Type	Condition
ArgumentNullException	Thrown when graph is null.
ArgumentException	Thrown when sourceID or targetID does not exist in graph.
InvalidOperationException	Thrown when a negative-weight edge is encountered during traversal. Dijkstra's algorithm is only correct for non-negative edge weights.

See Also

ScyllaGraphPath

ScyllaGraphSearchState

StronglyConnectedComponents(IScyllaReadOnlyGraph, out ScyllaMap<int, int>)

Computes the strongly connected components (SCCs) of a directed graph using Tarjan's algorithm with an explicit call stack to avoid C# stack overflow.

A strongly connected component is a maximal set of nodes such that there is a directed path from every node in the set to every other node in the set.

The iterative implementation uses ScyllaGraphAlgorithms.TarjanFrame records to simulate the recursive call stack. Each frame stores the current node index, the edge index to resume from (to continue iterating neighbors after a child returns), and the index of the pending child whose lowlink must be propagated back to the parent upon resumption.

Lowlink propagation: when a frame is resumed after pushing a child, it immediately updates lowlink[v] = min(lowlink[v], lowlink[child]) before continuing to process remaining neighbors.

Component indices are assigned in the order SCCs are completed (post-order). The first SCC to complete gets index 0. In a DAG of SCCs (the condensation), the SCC that is a sink in the condensation is assigned the lowest index.

Time complexity: O(V + E). Space complexity: O(V) for the index/lowlink/stack/ component arrays plus O(E) for the per-node edge buffer.

Declaration

public static int StronglyConnectedComponents(IScyllaReadOnlyGraph graph, out ScyllaMap<int, int> componentIDs)

Parameters

Type	Name	Description
IScyllaReadOnlyGraph	graph	The directed graph to analyze. Must have the Directed flag set and must implement IScyllaReadOnlyGraph for node enumeration. Must not be null.
ScyllaMap<int, int>	componentIDs	When this method returns, contains a ScyllaMap<TKey, TValue> from node ID (key) to zero-based SCC component index (value). All nodes in the same SCC share the same component index.

Returns

Type	Description
int	The total number of strongly connected components discovered. For a DAG (no cycles), this equals the node count (each node is its own SCC). For a fully strongly connected graph, this returns 1.

Exceptions

Type	Condition
ArgumentNullException	Thrown when graph is null.
ArgumentException	Thrown when graph does not have the Directed flag set.

See Also

ConnectedComponents(IScyllaReadOnlyGraph, out ScyllaMap<int, int>)

TopologicalSort(IScyllaGraph, out int[])

TopologicalSort(IScyllaGraph, out int[])

Computes a topological ordering of all nodes in a directed acyclic graph (DAG) using Kahn's algorithm (BFS-based in-degree reduction).

Kahn's algorithm proceeds in three phases:

1. Compute the in-degree of every node.
2. Seed a queue with all zero-in-degree nodes.
3. Dequeue a node, append it to the result, and decrement the in-degree of each of its neighbors. Re-enqueue any neighbor whose in-degree reaches zero.

If the number of nodes appended equals the total node count, the graph is acyclic and the result is a valid topological order. Otherwise a cycle was detected and the method returns false.

The method requires the graph to implement IScyllaReadOnlyGraph in order to enumerate all nodes via CopyAllNodes(Span<ScyllaGraphNode>). If graph does not implement that interface, an ArgumentException is thrown.

Time complexity: O(V + E). Space complexity: O(V) for in-degree map, queue, and result.

Declaration

public static bool TopologicalSort(IScyllaGraph graph, out int[] result)

Parameters

Type	Name	Description
IScyllaGraph	graph	The directed graph to sort. Must implement IScyllaReadOnlyGraph, must have the Directed flag set, and must not be null.
int[]	result	When this method returns true, contains an array of node IDs in a valid topological order (source nodes before their dependents). When the method returns false (cycle detected), contains an empty array.

Returns

Type	Description
bool	true if the graph is a DAG and a valid topological order was produced; false if a cycle was detected (in which case result is an empty array and no ordering is defined).

Exceptions

Type	Condition
ArgumentNullException	Thrown when graph is null.
ArgumentException	Thrown when graph does not have the Directed flag set, or when it does not implement IScyllaReadOnlyGraph.

See Also

IScyllaGraph

IScyllaReadOnlyGraph

ScyllaGraphPath

ScyllaDisjointSet