dijkstra3d-core 0.1.0

Voxel-grid Dijkstra and rolling-ball invalidation, ported from seung-lab/dijkstra3d and seung-lab/kimimaro
Documentation
//! Deterministic work counters for the integer graph kernels.

use crate::connectivity_graph::ConnectivityGraph;
use crate::dijkstra::{checked_int_distance_bound, IntQueue};
use crate::neighborhood::{neighborhood_masks, neighborhood_offsets, DIRECTIONS_26};
use crate::queue::binary_heap::BinaryHeapQueue;
use crate::queue::bucket::BucketQueue;
use crate::voxel::{ToU64Fast, VolumeShape};
use crate::{Connectivity, Dijkstra3dError, Result};

/// Per-run algorithmic work counters.
///
/// The counters depend on field values, connectivity, source/target, and queue
/// discipline. They do not measure wall time and are independent of distance
/// width and halo storage.
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct WorkStats {
    pub relaxations_attempted: u64,

    pub relaxations_succeeded: u64,

    pub pops: u64,

    pub settled: u64,
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub enum WorkOp {
    /// Single-source, single-target with early stop at `target`
    /// (mirrors `dijkstra_unidirectional_slice_int`).
    Dijkstra {
        /// Source voxel (linear index).
        source: u64,
        /// Target voxel (linear index); the search stops when it settles.
        target: u64,
    },
    /// Single-source, run to completion (mirrors `parental_field_slice_int`).
    ParentalField {
        /// Source voxel (linear index).
        source: u64,
    },
    /// Multi-source, run to completion (mirrors `distance_field_slice_int`).
    DistanceField {
        /// Source voxels (linear indices); all seeded at distance 0.
        sources: Vec<u64>,
    },
}

/// Instrumented work-efficiency measurement for the integer graph kernels.
pub fn work_stats_int<T: ToU64Fast>(
    field: &[T],
    shape: VolumeShape,
    op: &WorkOp,
    connectivity: Connectivity,
    graph: Option<ConnectivityGraph<'_>>,
) -> Result<WorkStats> {
    let total = shape.total();
    if field.len() as u64 != total {
        return Err(Dijkstra3dError::InvalidInput(format!(
            "work_stats_int: slice length {} != shape.total() {}",
            field.len(),
            total
        )));
    }
    if total > u32::MAX as u64 {
        return Err(Dijkstra3dError::InvalidInput(format!(
            "work_stats_int: volume {total} exceeds u32::MAX voxels"
        )));
    }

    // Resolve sources + optional target from the op, validating bounds.
    let (sources, target): (Vec<u64>, Option<u64>) = match op {
        WorkOp::Dijkstra { source, target } => {
            check_bounds(*source, total)?;
            check_bounds(*target, total)?;
            (vec![*source], Some(*target))
        }
        WorkOp::ParentalField { source } => {
            check_bounds(*source, total)?;
            (vec![*source], None)
        }
        WorkOp::DistanceField { sources } => {
            if sources.is_empty() {
                return Err(Dijkstra3dError::InvalidInput(
                    "sources cannot be empty".into(),
                ));
            }
            for &s in sources {
                check_bounds(s, total)?;
            }
            (sources.clone(), None)
        }
    };

    // Mirror the public dispatcher. Only bucket-vs-heap affects the counts
    // through tie-breaking; distance width does not, so this path uses u64.
    let max_weight = field.iter().map(|&v| v.to_u64_fast()).max().unwrap_or(0);
    checked_int_distance_bound(shape, max_weight)?;
    let use_bucket = max_weight < 65_536;

    let stats = if use_bucket {
        run_instrumented(
            field,
            shape,
            &sources,
            target,
            connectivity,
            graph,
            BucketQueue::with_capacity(max_weight as u32),
        )
    } else {
        run_instrumented(
            field,
            shape,
            &sources,
            target,
            connectivity,
            graph,
            BinaryHeapQueue::<u64, u32>::new(),
        )
    };
    Ok(stats)
}

#[inline]
fn check_bounds(idx: u64, total: u64) -> Result<()> {
    if idx >= total {
        return Err(Dijkstra3dError::OutOfBounds {
            idx,
            volume_size: total,
        });
    }
    Ok(())
}

/// Instrumented integer Dijkstra loop, monomorphized over the queue.
fn run_instrumented<T: ToU64Fast, Q: IntQueue>(
    field: &[T],
    shape: VolumeShape,
    sources: &[u64],
    target: Option<u64>,
    connectivity: Connectivity,
    graph: Option<ConnectivityGraph<'_>>,
    mut queue: Q,
) -> WorkStats {
    let total = shape.total() as usize;

    let mut distances = vec![u64::MAX; total];
    for &s in sources {
        distances[s as usize] = 0;
        queue.push_i(0, s as u32);
    }

    let sx_i = shape.sx as i64;
    let sxy_i = (shape.sx * shape.sy) as i64;
    let offsets = neighborhood_offsets(sx_i, sxy_i);
    let masks = neighborhood_masks();
    let neighbor_count = connectivity.count();

    let sx_u = shape.sx as i64;
    let sy_u = shape.sy as i64;
    let sz_u = shape.sz as i64;

    let mut stats = WorkStats::default();

    while let Some((dist, loc)) = queue.pop_i() {
        stats.pops += 1;
        let loc_us = loc as usize;
        // Lazy deletion: a stale entry (a later, smaller distance already
        // settled this voxel). Counted as a pop but not as a settle.
        if dist > distances[loc_us] {
            continue;
        }
        stats.settled += 1;

        // Early termination for the single-target Dijkstra op.
        if let Some(t) = target {
            if loc as u64 == t {
                break;
            }
        }

        let (lx, ly, lz) = shape.coords(loc as u64);
        let current_dist = distances[loc_us];

        for i in 0..neighbor_count {
            let (dx, dy, dz) = DIRECTIONS_26[i];

            let nx = lx as i64 + dx as i64;
            let ny = ly as i64 + dy as i64;
            let nz = lz as i64 + dz as i64;
            if nx < 0 || nx >= sx_u || ny < 0 || ny >= sy_u || nz < 0 || nz >= sz_u {
                continue;
            }

            let neighbor = (loc as i64 + offsets[i]) as u64;

            if let Some(ref g) = graph {
                if !g.allows(loc as u64, masks[i]) {
                    continue;
                }
            }

            // A real, in-bounds, graph-allowed edge: a relaxation attempt.
            stats.relaxations_attempted += 1;

            let neighbor_cost = field[neighbor as usize].to_u64_fast();
            let new_dist = current_dist.saturating_add(neighbor_cost);

            if new_dist < distances[neighbor as usize] {
                distances[neighbor as usize] = new_dist;
                stats.relaxations_succeeded += 1;
                queue.push_i(new_dist, neighbor as u32);
            }
        }
    }

    stats
}

#[cfg(test)]
mod tests {
    use super::*;

    fn uniform(sx: u64, sy: u64, sz: u64, val: u8) -> (Vec<u8>, VolumeShape) {
        let shape = VolumeShape::new(sx, sy, sz);
        (vec![val; shape.total() as usize], shape)
    }

    #[test]
    fn settled_equals_reachable_for_full_traversal() {
        // Uniform positive field, single source, run to completion: every voxel
        // is reachable and finalized exactly once, so settled == voxel count.
        let (field, shape) = uniform(8, 8, 8, 1);
        let stats = work_stats_int(
            &field,
            shape,
            &WorkOp::ParentalField { source: 0 },
            Connectivity::TwentySix,
            None,
        )
        .unwrap();
        assert_eq!(stats.settled, shape.total());
        // Successful relaxations == number of pushes; every settled non-source
        // voxel was pushed at least once, and pops >= settled always.
        assert!(stats.pops >= stats.settled);
        assert!(stats.relaxations_succeeded >= shape.total() - 1);
        assert!(stats.relaxations_attempted >= stats.relaxations_succeeded);
    }

    #[test]
    fn distance_field_multisource_settles_all() {
        let (field, shape) = uniform(6, 6, 6, 2);
        let stats = work_stats_int(
            &field,
            shape,
            &WorkOp::DistanceField {
                sources: vec![0, (shape.total() - 1)],
            },
            Connectivity::Six,
            None,
        )
        .unwrap();
        assert_eq!(stats.settled, shape.total());
    }

    #[test]
    fn dijkstra_early_terminates_before_full_settle() {
        // Single-target search on a large-ish uniform volume settles far fewer
        // voxels than the full volume (early termination at the target).
        let (field, shape) = uniform(16, 16, 16, 1);
        let target = shape.linear(2, 0, 0);
        let stats = work_stats_int(
            &field,
            shape,
            &WorkOp::Dijkstra { source: 0, target },
            Connectivity::Six,
            None,
        )
        .unwrap();
        assert!(stats.settled >= 1);
        assert!(stats.settled < shape.total());
        assert!(stats.pops >= stats.settled);
    }

    #[test]
    fn out_of_bounds_source_errors() {
        let (field, shape) = uniform(4, 4, 4, 1);
        let bad = shape.total() + 10;
        let err = work_stats_int(
            &field,
            shape,
            &WorkOp::ParentalField { source: bad },
            Connectivity::Six,
            None,
        );
        assert!(err.is_err());
    }

    #[test]
    fn work_stats_rejects_unrepresentable_distance_bound() {
        let shape = VolumeShape::new(2, 2, 2);
        let field = vec![u64::MAX; shape.total() as usize];

        let result = work_stats_int(
            &field,
            shape,
            &WorkOp::Dijkstra {
                source: 0,
                target: shape.total() - 1,
            },
            Connectivity::Six,
            None,
        );

        assert!(matches!(result, Err(Dijkstra3dError::InvalidInput(_))));
    }
}