Class ScyllaAdjacencyListGraph

Primary mutable graph implementation using adjacency lists. Nodes are stored in a ScyllaMap<TKey, TValue> keyed by integer ID, and each node's outgoing edges are stored in a parallel ScyllaMap<TKey, TValue> of List<ScyllaGraphEdge>.

Inheritance
object
ScyllaAdjacencyListGraph
Implements
Inherited Members
Namespace: Scylla.Core.Structures
Assembly: ScyllaCore.dll
Syntax
public sealed class ScyllaAdjacencyListGraph : IScyllaMutableGraph, IScyllaReadOnlyGraph, IScyllaGraph, IScyllaCollection
Remarks

This class supports both directed and undirected graphs as well as weighted and unweighted configurations. For undirected graphs, adding an edge from A to B automatically inserts the reverse edge from B to A so that both adjacency lists remain symmetrical. EdgeCount always reflects logical edge count - undirected edges are counted once, not twice.

Self-loops and parallel edges are opt-in features controlled at construction time via the allowsSelfLoops and allowsParallelEdges parameters (or the fluent ScyllaAdjacencyListGraph.Builder). When self-loops are disabled and fromID == toID, TryAddEdge(int, int, float) returns false. When parallel edges are disabled, attempting to add a duplicate edge also returns false.

For weighted graphs, edge weights are stored as provided. For unweighted graphs, all weights are normalised to 1.0f regardless of the value passed to TryAddEdge(int, int, float).

Thread safety: this class is not thread-safe by default. Use AsSynchronized(object) or call Synchronized(object) on the builder to obtain a lock-based wrapper.

Performance characteristics:

  • Node lookup: O(1) average via open-addressing hash map.
  • Edge lookup / neighbour iteration: O(degree) - linear scan of the per-node edge list.
  • Node removal in a directed graph: O(V + E) because all adjacency lists must be scanned for incoming edges.
  • Node removal in an undirected graph: O(degree) - only the affected neighbour lists are updated.
// Direct construction (directed, weighted)
var graph = new ScyllaAdjacencyListGraph(isDirected: true, isWeighted: true);
graph.TryAddNode(0);
graph.TryAddNode(1);
graph.TryAddEdge(0, 1, 2.5f);

// Using the fluent builder
var graph = ScyllaAdjacencyListGraph.CreateBuilder()
.Directed()
.Weighted()
.WithCapacity(128)
.Synchronized()
.Build();

Constructors

ScyllaAdjacencyListGraph(bool, bool, int, bool, bool)

Creates a new adjacency list graph with the specified structural configuration. All configuration values are immutable after construction.

Declaration
public ScyllaAdjacencyListGraph(bool isDirected = true, bool isWeighted = false, int capacity = 16, bool allowsSelfLoops = false, bool allowsParallelEdges = false)
Parameters
Type Name Description
bool isDirected

true to create a directed graph where edges have an explicit source and target. false to create an undirected graph where edges are bidirectional and are stored symmetrically in both endpoint adjacency lists. Defaults to true.
bool isWeighted

true to store the exact weight passed to TryAddEdge(int, int, float). false to normalise all edge weights to 1.0f regardless of the value provided. Defaults to false.
int capacity

Initial node capacity. Values below 1 are silently clamped to 1. Pre-allocating to the expected node count avoids rehash operations during population. Defaults to 16.
bool allowsSelfLoops

true to allow edges where fromID == toID. false to reject such calls from TryAddEdge(int, int, float). Defaults to false.
bool allowsParallelEdges

true to allow multiple edges between the same ordered pair of nodes. false to reject duplicate edges from TryAddEdge(int, int, float). Defaults to false.

Properties

Capabilities

Gets the capability flags for this collection. Reports HasCapacity and SupportsContains because node capacity can be pre-allocated via EnsureCapacity(int) and containment can be tested via ContainsNode(int) and ContainsEdge(int, int).

Declaration
public ScyllaCollectionCapabilities Capabilities { get; }
Property Value
Type Description
ScyllaCollectionCapabilities

Count

Gets the number of items in the collection, equivalent to NodeCount. Satisfies the IScyllaCollection contract where the primary element type of a graph is its nodes.

Declaration
public int Count { get; }
Property Value
Type Description
int

EdgeCount

Gets the number of logical edges in the graph. For undirected graphs, each undirected edge is counted once even though it is stored as two directed entries in the adjacency lists.

Declaration
public int EdgeCount { get; }
Property Value
Type Description
int

IsEmpty

Gets a value indicating whether the graph contains no nodes. An empty graph also has no edges.

Declaration
public bool IsEmpty { get; }
Property Value
Type Description
bool

NodeCount

Gets the number of nodes currently in the graph.

Declaration
public int NodeCount { get; }
Property Value
Type Description
int

Properties

Gets the combined structural property flags describing this graph instance. The flags are computed on demand from the immutable configuration fields set at construction time. Mutable is always included because this class implements IScyllaMutableGraph.

Declaration
public ScyllaGraphProperties Properties { get; }
Property Value
Type Description
ScyllaGraphProperties

A bitmask of ScyllaGraphProperties values reflecting whether the graph is directed, weighted, allows self-loops, allows parallel edges, and is mutable.

SyncRoot

Gets the synchronization root object. Returns null for unsynchronized instances. The synchronized wrapper returned by AsSynchronized(object) provides a non-null SyncRoot.

Declaration
public object SyncRoot { get; }
Property Value
Type Description
object

ThreadSafety

Gets the thread-safety classification of this instance. Returns Unsynchronized for the base class. Use AsSynchronized(object) to obtain a synchronized wrapper.

Declaration
public ScyllaCollectionThreadSafety ThreadSafety { get; }
Property Value
Type Description
ScyllaCollectionThreadSafety

Methods

AsSynchronized(object)

Creates and returns a thread-safe synchronized wrapper around this graph instance. All graph operations on the returned wrapper are serialized through a shared lock.

Declaration
public ScyllaAdjacencyListGraph.SynchronizedScyllaAdjacencyListGraph AsSynchronized(object syncRoot = null)
Parameters
Type Name Description
object syncRoot

An optional external object to use as the lock. Pass a shared lock object when synchronizing multiple collections atomically. When null, a new private object is created.
Returns
Type Description
ScyllaAdjacencyListGraph.SynchronizedScyllaAdjacencyListGraph

A new ScyllaAdjacencyListGraph.SynchronizedScyllaAdjacencyListGraph that wraps this instance.
Remarks

The properties Properties and Capabilities are cached at wrapper-construction time so they can be read without acquiring the lock. All other operations - including reads of NodeCount, EdgeCount, and IsEmpty - take the lock individually. Compound check-then-act sequences are still subject to TOCTOU races unless the caller holds SyncRoot for the duration of the compound operation.

Clear()

Removes all nodes and edges from the graph and resets EdgeCount to zero. The pre-allocated internal storage capacity is retained.

Declaration
public void Clear()

ContainsEdge(int, int)

Returns true if the graph contains an edge directed from fromID to toID.

Declaration
public bool ContainsEdge(int fromID, int toID)
Parameters
Type Name Description
int fromID

Source node ID.
int toID

Target node ID.
Returns
Type Description
bool

true if the edge exists; otherwise false.
Remarks

For undirected graphs, checking only from→to is sufficient because edges are stored symmetrically in both endpoint adjacency lists during TryAddEdge(int, int, float). The check performs a linear scan of fromID's edge list, so its cost is O(out-degree of fromID).

ContainsNode(int)

Returns true if the graph contains a node with the specified ID.

Declaration
public bool ContainsNode(int nodeID)
Parameters
Type Name Description
int nodeID

The integer ID of the node to look up.
Returns
Type Description
bool

true if a node with nodeID exists; otherwise false.

CopyAllEdges(Span<ScyllaGraphEdge>)

Copies all logical edge descriptors in the graph into the provided span. For undirected graphs, each edge is emitted exactly once: the copy is included when FromID <= ToID, so the symmetric reverse entry is skipped. For directed graphs, every stored directed edge is copied. If the span is smaller than EdgeCount, copying stops when the span is full.

Declaration
public int CopyAllEdges(Span<ScyllaGraphEdge> destination)
Parameters
Type Name Description
Span<ScyllaGraphEdge> destination

Span that receives the ScyllaGraphEdge descriptors.
Returns
Type Description
int

The number of edges copied into destination.

CopyAllNodes(Span<ScyllaGraphNode>)

Copies all node descriptors in the graph into the provided span. The enumeration order reflects the internal iteration order of the underlying ScyllaMap<TKey, TValue> and is not guaranteed to be sorted by ID. If the span is smaller than NodeCount, only as many nodes as fit are copied.

Declaration
public int CopyAllNodes(Span<ScyllaGraphNode> destination)
Parameters
Type Name Description
Span<ScyllaGraphNode> destination

Span that receives the ScyllaGraphNode descriptors.
Returns
Type Description
int

The number of nodes copied into destination.

CreateBuilder()

Creates and returns a new fluent ScyllaAdjacencyListGraph.Builder for constructing ScyllaAdjacencyListGraph instances with a readable configuration chain.

Declaration
public static ScyllaAdjacencyListGraph.Builder CreateBuilder()
Returns
Type Description
ScyllaAdjacencyListGraph.Builder

A new ScyllaAdjacencyListGraph.Builder instance with default settings.
See Also

EnsureCapacity(int)

Ensures the internal node and adjacency maps can accommodate at least minNodeCapacity nodes without triggering a rehash or reallocation. Use this before bulk-inserting a known number of nodes to avoid incremental resize overhead.

Declaration
public void EnsureCapacity(int minNodeCapacity)
Parameters
Type Name Description
int minNodeCapacity

The minimum number of nodes the internal storage should be able to hold. Values already met by the current capacity are no-ops.

GetEnumerator()

Returns a value-type ScyllaAdjacencyListGraph.NodeEnumerator that iterates over all nodes in the graph without allocating. Enables allocation-free foreach on the concrete type.

Declaration
public ScyllaAdjacencyListGraph.NodeEnumerator GetEnumerator()
Returns
Type Description
ScyllaAdjacencyListGraph.NodeEnumerator

A new ScyllaAdjacencyListGraph.NodeEnumerator positioned before the first node.

GetNeighborCount(int)

Returns the number of outgoing edges (out-degree) for the specified node, or -1 if the node does not exist.

Declaration
public int GetNeighborCount(int nodeID)
Parameters
Type Name Description
int nodeID

The ID of the node to query.
Returns
Type Description
int

The out-degree of the node, or -1 if the node does not exist.
Remarks

For undirected graphs the returned count represents the degree of the node, because each undirected edge is stored as an outgoing entry in both endpoint adjacency lists. The sentinel value -1 is used (rather than a Try pattern) to keep this hot-path API allocation-free.

GetNeighborsNonAlloc(int, Span<ScyllaGraphEdge>)

Copies the outgoing edges of the specified node into the provided span without allocating. If the destination span is smaller than the node's edge count, only as many edges as fit are copied.

Declaration
public int GetNeighborsNonAlloc(int nodeID, Span<ScyllaGraphEdge> destination)
Parameters
Type Name Description
int nodeID

The ID of the node whose neighbours to copy.
Span<ScyllaGraphEdge> destination

Caller-provided span that receives the ScyllaGraphEdge descriptors. Stack-allocate with stackalloc when the degree is small and known at the call site to avoid heap pressure.
Returns
Type Description
int

The number of edges copied into destination, or -1 if the node does not exist (consistent with GetNeighborCount(int)).

TryAddEdge(int, int, float)

Attempts to add an edge between the specified nodes.

Declaration
public bool TryAddEdge(int fromID, int toID, float weight = 1)
Parameters
Type Name Description
int fromID

ID of the source node. Must already exist in the graph.
int toID

ID of the target node. Must already exist in the graph.
float weight

Desired edge weight. Ignored for unweighted graphs (stored as 1.0f). Defaults to 1.0f.
Returns
Type Description
bool

true if the edge was added; false if either node does not exist, a self-loop is disallowed, a duplicate edge is disallowed, or an internal adjacency lookup fails.
Remarks

The following checks are performed in order before inserting the edge:

  1. Both endpoint nodes must exist in the graph.
  2. If self-loops are disabled and fromID == toID, the call is rejected.
  3. If parallel edges are disabled and the edge already exists, the call is rejected.

For undirected graphs, a reverse edge from toID to fromID is automatically added to keep both adjacency lists symmetric. Self-loops are never mirrored. EdgeCount is incremented only once per logical edge regardless of direction.

For unweighted graphs, weight is ignored and the stored weight is always 1.0f.

TryAddNode(int, ScyllaGraphNodeFlags)

Attempts to add a new node with the specified ID and flags. The operation also initialises an empty edge list for the node in the adjacency map. If either the node map or the adjacency map insertion fails (e.g. due to a duplicate ID), the operation is fully rolled back so that no partial state is left behind.

Declaration
public bool TryAddNode(int nodeID, ScyllaGraphNodeFlags flags = ScyllaGraphNodeFlags.Walkable)
Parameters
Type Name Description
int nodeID

Integer ID for the new node. Must be unique within this graph instance.
ScyllaGraphNodeFlags flags

Initial property flags for the node. Defaults to Walkable.
Returns
Type Description
bool

true if the node was added successfully; false if a node with nodeID already exists.

TryGetEdge(int, int, out ScyllaGraphEdge)

Attempts to retrieve the edge descriptor for the edge from fromID to toID.

Declaration
public bool TryGetEdge(int fromID, int toID, out ScyllaGraphEdge edge)
Parameters
Type Name Description
int fromID

Source node ID.
int toID

Target node ID.
ScyllaGraphEdge edge

When this method returns true, contains the first matching ScyllaGraphEdge. When this method returns false, contains default(ScyllaGraphEdge).
Returns
Type Description
bool

true if the edge was found; otherwise false.

TryGetNodeFlags(int, out ScyllaGraphNodeFlags)

Attempts to retrieve the ScyllaGraphNodeFlags for the specified node.

Declaration
public bool TryGetNodeFlags(int nodeID, out ScyllaGraphNodeFlags flags)
Parameters
Type Name Description
int nodeID

The ID of the node to query.
ScyllaGraphNodeFlags flags

When this method returns true, contains the node's current flags. When this method returns false, contains default(ScyllaGraphNodeFlags).
Returns
Type Description
bool

true if the node exists; otherwise false.

TryRemoveEdge(int, int)

Attempts to remove the edge(s) from fromID to toID.

Declaration
public bool TryRemoveEdge(int fromID, int toID)
Parameters
Type Name Description
int fromID

Source node ID of the edge to remove.
int toID

Target node ID of the edge to remove.
Returns
Type Description
bool

true if at least one edge was removed; false if no matching edge exists or the source node does not exist.
Remarks

When parallel edges are disabled only the first matching entry is removed (break after the first removal). When parallel edges are enabled, all entries matching toID are removed and EdgeCount is decremented by the number of entries removed.

For undirected graphs the symmetric reverse entries (from toID back to fromID) are also removed, up to the same count as the forward removals, to keep both adjacency lists consistent. Self-loops (fromID == toID) have no reverse entry and are handled correctly by the fromID != toID guard.

TryRemoveNode(int)

Attempts to remove the specified node and all edges incident to it from the graph.

Declaration
public bool TryRemoveNode(int nodeID)
Parameters
Type Name Description
int nodeID

The ID of the node to remove.
Returns
Type Description
bool

true if the node was removed; false if no node with nodeID exists.
Remarks

Directed graphs: outgoing edges are counted in EdgeCount and removed by clearing the node's own adjacency list. A full scan of all other adjacency lists is then required to remove incoming edges that target the deleted node. This second pass is O(V + E) but cannot be avoided without maintaining a separate reverse-adjacency structure.

Undirected graphs: each edge is stored symmetrically, so only the affected neighbour lists need to be updated. For non-self-loop edges the reverse entry is removed from each neighbour's list and EdgeCount is decremented. Self-loops stored in the node's own list are counted once and decremented once; there is no reverse entry to clean up.

TrySetNodeFlags(int, ScyllaGraphNodeFlags)

Attempts to replace the ScyllaGraphNodeFlags for an existing node. The node's ID is preserved; only its flags are updated.

Declaration
public bool TrySetNodeFlags(int nodeID, ScyllaGraphNodeFlags flags)
Parameters
Type Name Description
int nodeID

The ID of the node to update.
ScyllaGraphNodeFlags flags

The new flags value to assign.
Returns
Type Description
bool

true if the flags were updated; false if no node with nodeID exists.

Implements

Extension Methods