oxgraph-algo 0.3.0

//! Tests for the substrate-agnostic graph algorithms (topological sort,
//! strongly/weakly connected components, unweighted shortest paths) over an
//! in-test topology view.

#![cfg(feature = "alloc")]

use oxgraph_algo::{
    ToposortError, connected_components, shortest_path_lengths, strongly_connected_components,
    topological_sort,
};
use oxgraph_topology::{ElementIndex, ElementSuccessors, TopologyBase};
use proptest::prelude::*;

/// Minimal directed adjacency-list view implementing only the traits the
/// algorithms need. Element ids are dense `usize` slots.
struct FixtureGraph {
    /// Successor list per dense element index.
    adjacency: Vec<Vec<usize>>,
}

impl FixtureGraph {
    /// Builds a view from a per-node successor list.
    const fn new(adjacency: Vec<Vec<usize>>) -> Self {
        Self { adjacency }
    }

    /// Returns every node id, the usual full induced set.
    fn all(&self) -> Vec<usize> {
        (0..self.adjacency.len()).collect()
    }
}

impl TopologyBase for FixtureGraph {
    type ElementId = usize;
    type RelationId = usize;
}

impl ElementIndex for FixtureGraph {
    fn element_bound(&self) -> usize {
        self.adjacency.len()
    }

    fn element_index(&self, element: usize) -> usize {
        element
    }
}

impl ElementSuccessors for FixtureGraph {
    type Successors<'view>
        = core::iter::Copied<core::slice::Iter<'view, usize>>
    where
        Self: 'view;

    fn element_successors(&self, element: usize) -> Self::Successors<'_> {
        self.adjacency[element].iter().copied()
    }
}

/// Sorts components and their members for order-insensitive comparison.
fn normalize(mut components: Vec<Vec<usize>>) -> Vec<Vec<usize>> {
    for component in &mut components {
        component.sort_unstable();
    }
    components.sort_unstable();
    components
}

#[test]
fn topological_sort_orders_a_dag() {
    let graph = FixtureGraph::new(vec![vec![1, 2], vec![3], vec![3], vec![]]);
    let Ok(order) = topological_sort(&graph, &graph.all()) else {
        panic!("dag is acyclic");
    };
    assert_eq!(order.len(), 4);
    let mut position = [0usize; 4];
    for (rank, &node) in order.iter().enumerate() {
        position[node] = rank;
    }
    for (source, targets) in graph.adjacency.iter().enumerate() {
        for &target in targets {
            assert!(position[source] < position[target]);
        }
    }
}

#[test]
fn topological_sort_detects_a_cycle() {
    let graph = FixtureGraph::new(vec![vec![1], vec![2], vec![0]]);
    assert_eq!(
        topological_sort(&graph, &graph.all()),
        Err(ToposortError::Cycle)
    );
}

#[test]
fn topological_sort_treats_a_self_loop_as_a_cycle() {
    let graph = FixtureGraph::new(vec![vec![0]]);
    assert_eq!(
        topological_sort(&graph, &graph.all()),
        Err(ToposortError::Cycle)
    );
}

#[test]
fn strongly_connected_components_partition_cycles() {
    // {0,1,2} form a cycle; 3 is a sink reachable from the cycle.
    let graph = FixtureGraph::new(vec![vec![1], vec![2], vec![0, 3], vec![]]);
    let components = normalize(strongly_connected_components(&graph, &graph.all()));
    assert_eq!(components, vec![vec![0, 1, 2], vec![3]]);
}

#[test]
fn connected_components_group_weakly_reachable_nodes() {
    // 0->1 and 2->3 form two pairs; 4 is isolated.
    let graph = FixtureGraph::new(vec![vec![1], vec![], vec![3], vec![], vec![]]);
    let components = normalize(connected_components(&graph, &graph.all()));
    assert_eq!(components, vec![vec![0, 1], vec![2, 3], vec![4]]);
}

#[test]
fn shortest_path_lengths_layer_by_hops() {
    // 0->1->2 and 0->3.
    let graph = FixtureGraph::new(vec![vec![1, 3], vec![2], vec![], vec![]]);
    let mut distances = shortest_path_lengths(&graph, 0, &graph.all());
    distances.sort_unstable();
    assert_eq!(distances, vec![(0, 0), (1, 1), (2, 2), (3, 1)]);
}

#[test]
fn shortest_path_lengths_reject_an_absent_source() {
    let graph = FixtureGraph::new(vec![vec![1], vec![]]);
    assert!(shortest_path_lengths(&graph, 5, &graph.all()).is_empty());
}

proptest! {
    /// A topological order of any DAG places every edge's source before its
    /// target. DAGs are generated by only allowing forward edges `i -> j` with
    /// `i < j`.
    #[test]
    fn topological_sort_respects_every_edge(
        node_count in 1usize..8,
        raw_edges in proptest::collection::vec((0usize..8, 0usize..8), 0..20),
    ) {
        let mut adjacency = vec![Vec::new(); node_count];
        for (source, target) in raw_edges {
            if source < node_count && target < node_count && source < target {
                adjacency[source].push(target);
            }
        }
        let graph = FixtureGraph::new(adjacency);
        let Ok(order) = topological_sort(&graph, &graph.all()) else {
            panic!("forward-only graph should be acyclic");
        };
        prop_assert_eq!(order.len(), node_count);
        let mut position = vec![0usize; node_count];
        for (rank, &node) in order.iter().enumerate() {
            position[node] = rank;
        }
        for (source, targets) in graph.adjacency.iter().enumerate() {
            for &target in targets {
                prop_assert!(position[source] < position[target]);
            }
        }
    }
}