Struct CompactGraph 

pub struct CompactGraph {
    pub num_vertices: u16,
    pub num_edges: u16,
    pub free_edge_head: u16,
    pub generation: u16,
    pub num_components: u16,
    pub status: u16,
    pub vertices: [VertexEntry; 256],
    pub edges: [ShardEdge; 1024],
    pub adjacency: [[AdjEntry; 32]; 256],
    /* private fields */
}

Compact graph shard for tile-local storage

Memory layout (~32KB total):

• Vertex entries: 256 * 8 = 2KB
• Edge storage: 1024 * 8 = 8KB
• Adjacency lists: 256 * 32 * 4 = 32KB Total: ~42KB (fits in 64KB tile budget with room for other state)

OPTIMIZATION: Cache-line aligned (64 bytes) for efficient CPU cache usage. Hot fields (num_vertices, num_edges, status) are grouped together.

Note: Actual size is optimized by packing adjacency lists more efficiently.

Fields

num_vertices: u16

Number of active vertices

num_edges: u16

Number of active edges

free_edge_head: u16

Free edge list head (for reuse)

generation: u16

Graph generation (incremented on structural changes)

num_components: u16

Component count

status: u16

Status flags

vertices: [VertexEntry; 256]

Vertex metadata array

edges: [ShardEdge; 1024]

Edge storage array

adjacency: [[AdjEntry; 32]; 256]

Packed adjacency lists Layout: for each vertex, up to MAX_DEGREE neighbors

Implementations

impl CompactGraph

pub const STATUS_VALID: u16 = 1u16

Status: graph is valid

pub const STATUS_DIRTY: u16 = 2u16

Status: graph needs recomputation

pub const STATUS_CONNECTED: u16 = 4u16

Status: graph is connected

pub const fn new() -> Self

Create a new empty graph

pub fn clear(&mut self)

Clear the graph

pub fn add_vertex(&mut self, v: TileVertexId) -> bool

Add or activate a vertex

pub fn remove_vertex(&mut self, v: TileVertexId) -> bool

Remove a vertex (marks as inactive)

pub fn add_edge( &mut self, source: TileVertexId, target: TileVertexId, weight: FixedWeight, ) -> Option<TileEdgeId>

Add an edge between two vertices

pub fn remove_edge( &mut self, source: TileVertexId, target: TileVertexId, ) -> bool

Remove an edge

pub fn update_weight( &mut self, source: TileVertexId, target: TileVertexId, new_weight: FixedWeight, ) -> bool

Update edge weight

pub fn find_edge( &self, source: TileVertexId, target: TileVertexId, ) -> Option<TileEdgeId>

Find edge between two vertices

OPTIMIZATION: Uses unsafe unchecked access after bounds validation. The adjacency scan is a hot path in graph algorithms.

pub unsafe fn find_edge_unchecked( &self, source: TileVertexId, target: TileVertexId, ) -> Option<TileEdgeId>

Find edge between two vertices (unchecked version)

SAFETY: Caller must ensure source < MAX_SHARD_VERTICES and vertex is active

pub fn edge_weight( &self, source: TileVertexId, target: TileVertexId, ) -> Option<FixedWeight>

Get edge weight

pub fn degree(&self, v: TileVertexId) -> u8

Get vertex degree

OPTIMIZATION: Uses unsafe unchecked access after bounds check

pub fn neighbors(&self, v: TileVertexId) -> &[AdjEntry]

Get neighbors of a vertex

OPTIMIZATION: Uses unsafe unchecked slice creation after bounds check

pub unsafe fn neighbors_unchecked(&self, v: TileVertexId) -> &[AdjEntry]

Get neighbors of a vertex (unchecked version)

SAFETY: Caller must ensure v < MAX_SHARD_VERTICES and vertex is active

pub fn is_connected(&self) -> bool

Check if graph is connected (cached, call recompute_components first)

pub fn recompute_components(&mut self) -> u16

Compute connected components using union-find

OPTIMIZATION: Uses iterative path compression (no recursion), unsafe unchecked access, and processes only active edges.

pub const fn memory_size() -> usize

Get memory size of the graph structure

pub fn for_each_active_vertex<F>(&self, f: F)

where F: FnMut(TileVertexId, u8, u16),

Iterate over active vertices with cache-prefetching

OPTIMIZATION: Uses software prefetching hints to reduce cache misses when iterating over vertices sequentially.

Arguments

• f - Callback function receiving (vertex_id, degree, component)

pub fn for_each_active_edge<F>(&self, f: F)

where F: FnMut(TileEdgeId, TileVertexId, TileVertexId, FixedWeight),

Iterate over active edges with cache-prefetching

OPTIMIZATION: Processes edges in cache-line order for better locality.

Arguments

• f - Callback receiving (edge_id, source, target, weight)

pub fn add_edges_batch( &mut self, edges: &[(TileVertexId, TileVertexId, FixedWeight)], ) -> usize

Batch add multiple edges for improved throughput

OPTIMIZATION: Reduces per-edge overhead by batching operations:

• Single dirty flag update
• Deferred component recomputation
• Better cache utilization

Arguments

• edges - Slice of (source, target, weight) tuples

Returns

Number of successfully added edges

pub fn active_edge_weights(&self) -> impl Iterator<Item = FixedWeight> + '_

Get edge weights as a contiguous slice for SIMD processing

OPTIMIZATION: Returns a view of edge weights suitable for SIMD operations (e.g., computing total weight, min/max).

Returns

Iterator of weights from active edges

pub fn total_weight_simd(&self) -> u64

Compute total edge weight using SIMD-friendly accumulation

OPTIMIZATION: Uses parallel lane accumulation for better vectorization.

pub fn min_degree_vertex(&self) -> Option<(TileVertexId, u8)>

Find minimum degree vertex efficiently

OPTIMIZATION: Uses branch prediction hints and early exit for finding cut boundary candidates.

Returns

(vertex_id, degree) of minimum degree active vertex, or None

Trait Implementations

impl Default for CompactGraph

fn default() -> Self

Returns the “default value” for a type.