15792950674

Committed 21 Jun 2025 06:21AM UTC coverage: 95.559% (+1.0%) from 94.579%

Build # 15792950674

Build Type

Pull #13

github

Committed by

kaidokert

Commit Message

More edge flex graphs

Pull Request Pull Request #13: Add edge mutability

Run Details

1575 of 1597 new or added lines in 9 files covered. (98.62%)

2 existing lines in 1 file now uncovered.

8134 of 8512 relevant lines covered (95.56%)

37.99 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

96.17

/src/matrix/bit_map_matrix.rs

use crate::{
    containers::maps::MapTrait,
    graph::{Graph, GraphError, GraphWithMutableEdges, GraphWithMutableNodes, NodeIndex},
};

/// A bit-packed adjacency matrix with arbitrary node indices
///
/// This struct combines a [`crate::matrix::bit_matrix::BitMatrix`] for efficient edge storage with an index map
/// that allows arbitrary node indices. It provides the same memory efficiency as
/// BitMatrix while supporting non-contiguous node identifiers.
pub struct BitMapMatrix<const N: usize, const R: usize, NI, M>
where
    NI: NodeIndex,
    M: MapTrait<NI, usize>,
{
    bitmap: super::bit_matrix::BitMatrix<N, R>,
    index_map: M,
    phantom: core::marker::PhantomData<NI>,
}

impl<const N: usize, const R: usize, NI, M> BitMapMatrix<N, R, NI, M>
where
    NI: NodeIndex,
    M: MapTrait<NI, usize>,
{
    /// Creates a new BitMapMatrix with the given bitmap and index mapping
    ///
    /// Validates that all indices in the index_map are within valid bounds for the BitMatrix.
    /// BitMatrix supports node indices in the range 0..8*N.
    pub fn new(
        bitmap: super::bit_matrix::BitMatrix<N, R>,
        index_map: M,
    ) -> Result<Self, GraphError<NI>> {
        // BitMatrix supports indices in range 0..8*N
        let max_valid_index = 8 * N;
        for (node, idx) in index_map.iter() {
            if *idx >= max_valid_index {
                return Err(GraphError::IndexOutOfBounds(*idx, *node));
            }
        }
        Ok(Self::new_unchecked(bitmap, index_map))
    }

    /// Creates a new BitMapMatrix with the given bitmap and index mapping without bounds checking
    ///
    /// # Safety
    /// The caller must ensure that all indices in the index_map are within valid bounds
    /// for the BitMatrix (0..8*N).
    pub fn new_unchecked(bitmap: super::bit_matrix::BitMatrix<N, R>, index_map: M) -> Self {
        Self {
            bitmap,
            index_map,
            phantom: core::marker::PhantomData,
        }
    }
}

impl<const N: usize, const R: usize, NI, M> Graph<NI> for BitMapMatrix<N, R, NI, M>
where
    NI: NodeIndex,
    M: MapTrait<NI, usize>,
{
    type Error = GraphError<NI>;

    fn iter_nodes(&self) -> Result<impl Iterator<Item = NI>, Self::Error> {
        Ok(self.index_map.iter().map(|(&k, _)| k))
    }

    fn contains_node(&self, node: NI) -> Result<bool, Self::Error> {
        Ok(self.index_map.contains_key(&node))
    }

    /// Note: Uses linear search for backindexing matrix indices to NI, this is slow.
    ///
    /// TODO: Store back-index ?
    fn iter_edges(&self) -> Result<impl Iterator<Item = (NI, NI)>, Self::Error> {
        Ok(self
            .index_map
            .iter()
            .flat_map(move |(&from_node, &from_idx)| {
                self.index_map
                    .iter()
                    .filter_map(move |(&to_node, &to_idx)| {
                        if self.bitmap.get(from_idx, to_idx) {
                            Some((from_node, to_node))
                        } else {
                            None
                        }
                    })
            }))
    }

    /// Note: Uses linear search for backindexing matrix indices to NI, this is slow.
    ///
    /// TODO: Store back-index ?
    fn outgoing_edges(&self, node: NI) -> Result<impl Iterator<Item = NI>, Self::Error> {
        // Fast direct lookup of matrix index for this node
        let matrix_idx = self.index_map.get(&node).copied();

        // Get outgoing edges from bitmap, using usize::MAX as fallback (will be filtered out)
        // Note: BitMatrix::get handles out-of-bounds indices safely by returning false,
        // and the filter below ensures we don't return edges for non-existent nodes.
        // The map_err is needed to convert GraphError<usize> to GraphError<NI> for the trait implementation.
        let outgoing = self
            .bitmap
            .outgoing_edges(matrix_idx.unwrap_or(usize::MAX))
            .map_err(|_| GraphError::NodeNotFound(node))?;

        // Map matrix indices back to node indices by checking all nodes
        Ok(outgoing
            .filter(move |_| matrix_idx.is_some()) // Filter out everything if node doesn't exist
            .filter_map(move |target_idx| {
                self.index_map
                    .iter()
                    .find(|(_, &idx)| idx == target_idx)
                    .map(|(&node, _)| node)
            }))
    }

    /// Note: Uses linear search for backindexing matrix indices to NI, this is slow.
    ///
    /// TODO: Store back-index ?
    fn incoming_edges(&self, node: NI) -> Result<impl Iterator<Item = NI>, Self::Error> {
        // Fast direct lookup of matrix index for this node
        let matrix_idx = self.index_map.get(&node).copied();

        // Get incoming edges from bitmap, using 0 as fallback (will be filtered out)
        let incoming = self
            .bitmap
            .incoming_edges(matrix_idx.unwrap_or(usize::MAX))
            .map_err(|_| GraphError::NodeNotFound(node))?;

        // Map matrix indices back to node indices by checking all nodes
        Ok(incoming
            .filter(move |_| matrix_idx.is_some()) // Filter out everything if node doesn't exist
            .filter_map(move |source_idx| {
                self.index_map
                    .iter()
                    .find(|(_, &idx)| idx == source_idx)
                    .map(|(&node, _)| node)
            }))
    }
}

impl<const N: usize, const R: usize, NI, M> GraphWithMutableNodes<NI> for BitMapMatrix<N, R, NI, M>
where
    NI: NodeIndex,
    M: MapTrait<NI, usize>,
{
    fn add_node(&mut self, node: NI) -> Result<(), Self::Error> {
        // Check if node already exists
        if self.index_map.contains_key(&node) {
            return Err(GraphError::DuplicateNode(node));
        }

        // Find an unused matrix index (BitMatrix supports 0..8*N)
        let max_index = 8 * N;
        let unused_index = (0..max_index)
            .find(|&idx| !self.index_map.iter().any(|(_, &used_idx)| used_idx == idx))
            .ok_or(GraphError::OutOfCapacity)?;

        // Insert the new node mapping
        self.index_map
            .insert(node, unused_index)
            .map_err(|_| GraphError::OutOfCapacity)?;

        Ok(())
    }

    fn remove_node(&mut self, node: NI) -> Result<(), Self::Error> {
        // Check if node exists
        if !self.index_map.contains_key(&node) {
            return Err(GraphError::NodeNotFound(node));
        }

        // Check if node has incoming edges
        if self.incoming_edges(node)?.next().is_some() {
            return Err(GraphError::NodeHasIncomingEdges(node));
        }

        // Remove the node mapping (bit matrix position becomes available for reuse)
        self.index_map.remove(&node);
        Ok(())
    }
}

impl<const N: usize, const R: usize, NI, M> GraphWithMutableEdges<NI> for BitMapMatrix<N, R, NI, M>
where
    NI: NodeIndex,
    M: MapTrait<NI, usize>,
{
    fn add_edge(&mut self, source: NI, destination: NI) -> Result<(), Self::Error> {
        // Translate node indices to matrix indices
        let source_idx = self
            .index_map
            .get(&source)
            .copied()
            .ok_or(GraphError::EdgeHasInvalidNode(source))?;

        let destination_idx = self
            .index_map
            .get(&destination)
            .copied()
            .ok_or(GraphError::EdgeHasInvalidNode(destination))?;

        // Delegate to underlying BitMatrix implementation
        self.bitmap
            .add_edge(source_idx, destination_idx)
            .map_err(|err| match err {
                GraphError::EdgeHasInvalidNode(_) => {
                    // This shouldn't happen since we validated indices above,
                    // but if it does, convert to source node error
                    GraphError::EdgeHasInvalidNode(source)
                }
                GraphError::OutOfCapacity => GraphError::OutOfCapacity,
                _ => GraphError::EdgeHasInvalidNode(source), // Fallback
            })
    }

    fn remove_edge(&mut self, source: NI, destination: NI) -> Result<(), Self::Error> {
        // Translate node indices to matrix indices
        let source_idx = self
            .index_map
            .get(&source)
            .copied()
            .ok_or(GraphError::EdgeNotFound(source, destination))?;

        let destination_idx = self
            .index_map
            .get(&destination)
            .copied()
            .ok_or(GraphError::EdgeNotFound(source, destination))?;

        // Delegate to underlying BitMatrix implementation
        self.bitmap
            .remove_edge(source_idx, destination_idx)
            .map_err(|err| match err {
                GraphError::EdgeNotFound(_, _) => {
                    // Convert matrix indices back to node indices for error
                    GraphError::EdgeNotFound(source, destination)
                }
                _ => GraphError::EdgeNotFound(source, destination), // Fallback
            })
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::containers::maps::staticdict::Dictionary;
    use crate::tests::{collect, collect_sorted};

    #[test]
    fn test_bit_map_matrix_basic() {
        // Create a simple 2x2 bit matrix with edges: 0->0, 0->1, 1->0
        let bits = [
            [0b00000011u8], // Row 0: edges to nodes 0 and 1
            [0b00000001u8], // Row 1: edge to node 0
            [0b00000000u8], // Row 2: no edges
            [0b00000000u8], // Row 3: no edges
            [0b00000000u8], // Row 4: no edges
            [0b00000000u8], // Row 5: no edges
            [0b00000000u8], // Row 6: no edges
            [0b00000000u8], // Row 7: no edges
        ];
        let bitmap = super::super::bit_matrix::BitMatrix::new_unchecked(bits);

        // Map custom node IDs 'A','B' to matrix indices 0,1
        let mut index_map = Dictionary::<char, usize, 8>::new();
        index_map.insert('A', 0).unwrap();
        index_map.insert('B', 1).unwrap();

        let bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();

        // Test node iteration
        let mut nodes = ['\0'; 8];
        let nodes_slice = collect(bit_map_matrix.iter_nodes().unwrap(), &mut nodes);
        assert_eq!(nodes_slice.len(), 2);

        // Check both nodes are present (order may vary)
        assert!(nodes_slice.contains(&'A'));
        assert!(nodes_slice.contains(&'B'));

        // Test contains_node
        assert!(bit_map_matrix.contains_node('A').unwrap());
        assert!(bit_map_matrix.contains_node('B').unwrap());
        assert!(!bit_map_matrix.contains_node('C').unwrap());

        // Test outgoing edges
        let mut outgoing_a = ['\0'; 8];
        let outgoing_slice = collect(bit_map_matrix.outgoing_edges('A').unwrap(), &mut outgoing_a);
        assert_eq!(outgoing_slice.len(), 2); // A->A, A->B

        let mut outgoing_b = ['\0'; 8];
        let outgoing_slice = collect(bit_map_matrix.outgoing_edges('B').unwrap(), &mut outgoing_b);
        assert_eq!(outgoing_slice, &['A']); // B->A
    }

    #[test]
    fn test_bit_map_matrix_empty() {
        // Empty bitmap
        let bits = [[0u8], [0u8], [0u8], [0u8], [0u8], [0u8], [0u8], [0u8]];
        let bitmap = super::super::bit_matrix::BitMatrix::new_unchecked(bits);

        // Empty index map
        let index_map = Dictionary::<u32, usize, 8>::new();
        let bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();

        // Should have no nodes
        assert_eq!(bit_map_matrix.iter_nodes().unwrap().count(), 0);

        // Should have no edges
        assert_eq!(bit_map_matrix.iter_edges().unwrap().count(), 0);

        // Should not contain any nodes
        assert!(!bit_map_matrix.contains_node(42).unwrap());
    }

    #[test]
    fn test_bit_map_matrix_nonexistent_node() {
        let bits = [
            [0b00000001u8], // Row 0: edge to node 0
            [0b00000000u8],
            [0b00000000u8],
            [0b00000000u8],
            [0b00000000u8],
            [0b00000000u8],
            [0b00000000u8],
            [0b00000000u8],
        ];
        let bitmap = super::super::bit_matrix::BitMatrix::new_unchecked(bits);

        let mut index_map = Dictionary::<u32, usize, 8>::new();
        index_map.insert(100, 0).unwrap();

        let bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();

        // Test outgoing edges for non-existent node should return empty iterator
        assert_eq!(bit_map_matrix.outgoing_edges(999).unwrap().count(), 0);

        // Test incoming edges for non-existent node should return empty iterator
        assert_eq!(bit_map_matrix.incoming_edges(999).unwrap().count(), 0);
    }

    #[test]
    fn test_bit_map_matrix_incoming_edges() {
        // Create a matrix with edges: A->A, A->B, B->A
        let bits = [
            [0b00000011u8], // Row 0: edges to nodes 0 and 1 (A->A, A->B)
            [0b00000001u8], // Row 1: edge to node 0 (B->A)
            [0b00000000u8], // Row 2: no edges
            [0b00000000u8], // Row 3: no edges
            [0b00000000u8], // Row 4: no edges
            [0b00000000u8], // Row 5: no edges
            [0b00000000u8], // Row 6: no edges
            [0b00000000u8], // Row 7: no edges
        ];
        let bitmap = super::super::bit_matrix::BitMatrix::new_unchecked(bits);

        // Map custom node IDs 'A','B' to matrix indices 0,1
        let mut index_map = Dictionary::<char, usize, 8>::new();
        index_map.insert('A', 0).unwrap();
        index_map.insert('B', 1).unwrap();

        let bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();

        // Test incoming edges to A (should be from A and B)
        let mut incoming_a = ['\0'; 8];
        let incoming_slice = collect(bit_map_matrix.incoming_edges('A').unwrap(), &mut incoming_a);
        assert_eq!(incoming_slice.len(), 2); // A->A, B->A
        assert!(incoming_slice.contains(&'A'));
        assert!(incoming_slice.contains(&'B'));

        // Test incoming edges to B (should be from A only)
        let mut incoming_b = ['\0'; 8];
        let incoming_slice = collect(bit_map_matrix.incoming_edges('B').unwrap(), &mut incoming_b);
        assert_eq!(incoming_slice, &['A']); // A->B
    }

    #[test]
    fn test_bit_map_matrix_outgoing_edges_bounds() {
        // Create a matrix with edges: A->A, A->B
        let bits = [
            [0b00000011u8], // Row 0: edges to nodes 0 and 1 (A->A, A->B)
            [0b00000000u8], // Row 1: no edges
            [0b00000000u8], // Row 2: no edges
            [0b00000000u8], // Row 3: no edges
            [0b00000000u8], // Row 4: no edges
            [0b00000000u8], // Row 5: no edges
            [0b00000000u8], // Row 6: no edges
            [0b00000000u8], // Row 7: no edges
        ];
        let bitmap = super::super::bit_matrix::BitMatrix::new_unchecked(bits);

        // Map custom node IDs 'A','B' to matrix indices 0,1
        let mut index_map = Dictionary::<char, usize, 8>::new();
        index_map.insert('A', 0).unwrap();
        index_map.insert('B', 1).unwrap();

        let bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();

        // Test outgoing edges for non-existent node with usize::MAX fallback
        // This should not panic and should return an empty iterator
        let mut outgoing = ['\0'; 8];
        let outgoing_slice = collect(bit_map_matrix.outgoing_edges('C').unwrap(), &mut outgoing);
        assert_eq!(outgoing_slice.len(), 0);

        // Test outgoing edges for non-existent node with 0 fallback
        // This should also not panic and should return an empty iterator
        let mut outgoing = ['\0'; 8];
        let outgoing_slice = collect(bit_map_matrix.outgoing_edges('D').unwrap(), &mut outgoing);
        assert_eq!(outgoing_slice.len(), 0);
    }

    #[test]
    fn test_add_node_to_empty_bit_matrix() {
        let bits = [[0u8], [0u8], [0u8], [0u8], [0u8], [0u8], [0u8], [0u8]];
        let bitmap = super::super::bit_matrix::BitMatrix::new_unchecked(bits);
        let index_map = Dictionary::<u32, usize, 10>::new();

        let mut bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();
        bit_map_matrix.add_node(42).unwrap();

        let mut nodes = [0u32; 2];
        let nodes_slice = collect(bit_map_matrix.iter_nodes().unwrap(), &mut nodes);
        assert_eq!(nodes_slice, &[42]);
        assert_eq!(bit_map_matrix.outgoing_edges(42).unwrap().count(), 0);
    }

    #[test]
    fn test_add_node_to_existing_bit_matrix() {
        let bits = [
            [0b00000001u8], // Row 0: edge to node 0 (self-loop)
            [0b00000000u8],
            [0b00000000u8],
            [0b00000000u8],
            [0b00000000u8],
            [0b00000000u8],
            [0b00000000u8],
            [0b00000000u8],
        ];
        let bitmap = super::super::bit_matrix::BitMatrix::new_unchecked(bits);
        let mut index_map = Dictionary::<char, usize, 10>::new();
        index_map.insert('A', 0).unwrap();

        let mut bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();
        bit_map_matrix.add_node('B').unwrap();

        let mut nodes = ['\0'; 4];
        let nodes_slice = collect_sorted(bit_map_matrix.iter_nodes().unwrap(), &mut nodes);
        assert_eq!(nodes_slice, &['A', 'B']);
        assert_eq!(bit_map_matrix.outgoing_edges('B').unwrap().count(), 0);
        assert_eq!(bit_map_matrix.outgoing_edges('A').unwrap().count(), 1);
    }

    #[test]
    fn test_add_duplicate_node_bit_matrix() {
        let bits = [[0u8], [0u8], [0u8], [0u8], [0u8], [0u8], [0u8], [0u8]];
        let bitmap = super::super::bit_matrix::BitMatrix::new_unchecked(bits);
        let mut index_map = Dictionary::<u32, usize, 8>::new();
        index_map.insert(100, 0).unwrap();

        let mut bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();

        let result = bit_map_matrix.add_node(100);
        assert!(matches!(result, Err(GraphError::DuplicateNode(100))));

        let mut nodes = [0u32; 2];
        let nodes_slice = collect(bit_map_matrix.iter_nodes().unwrap(), &mut nodes);
        assert_eq!(nodes_slice, &[100]);
    }

    #[test]
    fn test_add_node_capacity_exceeded_bit_matrix() {
        let bits = [[0u8], [0u8], [0u8], [0u8], [0u8], [0u8], [0u8], [0u8]];
        let bitmap = super::super::bit_matrix::BitMatrix::new_unchecked(bits);
        let mut index_map = Dictionary::<u32, usize, 8>::new();
        for i in 0..8 {
            index_map.insert(i as u32, i).unwrap();
        }

        let mut bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();

        let result = bit_map_matrix.add_node(999);
        assert!(matches!(result, Err(GraphError::OutOfCapacity)));

        let mut nodes = [0u32; 10];
        let nodes_slice = collect_sorted(bit_map_matrix.iter_nodes().unwrap(), &mut nodes);
        assert_eq!(nodes_slice, &[0, 1, 2, 3, 4, 5, 6, 7]);
    }

    #[test]
    fn test_add_multiple_nodes_bit_matrix() {
        let bits = [[0u8], [0u8], [0u8], [0u8], [0u8], [0u8], [0u8], [0u8]];
        let bitmap = super::super::bit_matrix::BitMatrix::new_unchecked(bits);
        let index_map = Dictionary::<char, usize, 10>::new();

        let mut bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();
        bit_map_matrix.add_node('X').unwrap();
        bit_map_matrix.add_node('Y').unwrap();
        bit_map_matrix.add_node('Z').unwrap();

        let mut nodes = ['\0'; 4];
        let nodes_slice = collect_sorted(bit_map_matrix.iter_nodes().unwrap(), &mut nodes);
        assert_eq!(nodes_slice, &['X', 'Y', 'Z']);
        assert_eq!(bit_map_matrix.iter_edges().unwrap().count(), 0);
    }

    #[test]
    fn test_add_node_fills_gaps_bit_matrix() {
        let bits = [[0u8], [0u8], [0u8], [0u8], [0u8], [0u8], [0u8], [0u8]];
        let bitmap = super::super::bit_matrix::BitMatrix::new_unchecked(bits);
        let mut index_map = Dictionary::<u32, usize, 10>::new();
        index_map.insert(10, 0).unwrap();
        index_map.insert(30, 2).unwrap();
        index_map.insert(50, 4).unwrap();

        let mut bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();
        bit_map_matrix.add_node(20).unwrap();

        let mut nodes = [0u32; 6];
        let nodes_slice = collect_sorted(bit_map_matrix.iter_nodes().unwrap(), &mut nodes);
        assert_eq!(nodes_slice, &[10, 20, 30, 50]);
    }

    #[test]
    fn test_add_edge_success() {
        use crate::graph::GraphWithMutableEdges;

        let bits = [[0u8]; 8];
        let bitmap = super::super::bit_matrix::BitMatrix::new_unchecked(bits);
        let mut index_map = Dictionary::<char, usize, 10>::new();
        index_map.insert('A', 0).unwrap();
        index_map.insert('B', 1).unwrap();
        index_map.insert('C', 2).unwrap();

        let mut bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();

        // Add edges between existing nodes
        assert!(bit_map_matrix.add_edge('A', 'B').is_ok());
        assert!(bit_map_matrix.add_edge('B', 'C').is_ok());
        assert!(bit_map_matrix.add_edge('A', 'C').is_ok());

        // Verify edges were added
        let edge_count = bit_map_matrix.iter_edges().unwrap().count();
        assert_eq!(edge_count, 3);

        // Verify specific edges exist
        let mut edges = [('\0', '\0'); 8];
        let edges_slice = collect_sorted(bit_map_matrix.iter_edges().unwrap(), &mut edges);
        assert_eq!(edges_slice, &[('A', 'B'), ('A', 'C'), ('B', 'C')]);
    }

    #[test]
    fn test_add_edge_invalid_nodes() {
        use crate::graph::GraphWithMutableEdges;

        let bits = [[0u8]; 8];
        let bitmap = super::super::bit_matrix::BitMatrix::new_unchecked(bits);
        let mut index_map = Dictionary::<char, usize, 10>::new();
        index_map.insert('A', 0).unwrap();
        index_map.insert('B', 1).unwrap();

        let mut bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();

        // Try to add edge with non-existent source node
        let result = bit_map_matrix.add_edge('X', 'B');
        assert!(matches!(result, Err(GraphError::EdgeHasInvalidNode('X'))));

        // Try to add edge with non-existent destination node
        let result = bit_map_matrix.add_edge('A', 'Y');
        assert!(matches!(result, Err(GraphError::EdgeHasInvalidNode('Y'))));

        // Try to add edge with both nodes non-existent
        let result = bit_map_matrix.add_edge('X', 'Y');
        assert!(matches!(result, Err(GraphError::EdgeHasInvalidNode('X'))));
    }

    #[test]
    fn test_remove_edge_success() {
        use crate::graph::GraphWithMutableEdges;

        // Set up matrix with some initial edges
        let bits = [
            [0b00000110u8], // A->B, A->C
            [0b00000100u8], // B->C
            [0b00000000u8], // C->nothing
            [0b00000000u8],
            [0b00000000u8],
            [0b00000000u8],
            [0b00000000u8],
            [0b00000000u8],
        ];
        let bitmap = super::super::bit_matrix::BitMatrix::new_unchecked(bits);
        let mut index_map = Dictionary::<char, usize, 10>::new();
        index_map.insert('A', 0).unwrap();
        index_map.insert('B', 1).unwrap();
        index_map.insert('C', 2).unwrap();

        let mut bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();

        // Verify initial state
        assert_eq!(bit_map_matrix.iter_edges().unwrap().count(), 3);

        // Remove an edge
        assert!(bit_map_matrix.remove_edge('A', 'B').is_ok());

        // Verify edge was removed
        assert_eq!(bit_map_matrix.iter_edges().unwrap().count(), 2);
        let mut edges = [('\0', '\0'); 8];
        let edges_slice = collect_sorted(bit_map_matrix.iter_edges().unwrap(), &mut edges);
        assert_eq!(edges_slice, &[('A', 'C'), ('B', 'C')]);
    }

    #[test]
    fn test_remove_edge_not_found() {
        use crate::graph::GraphWithMutableEdges;

        let bits = [
            [0b00000010u8], // A->B
            [0b00000000u8],
            [0b00000000u8],
            [0b00000000u8],
            [0b00000000u8],
            [0b00000000u8],
            [0b00000000u8],
            [0b00000000u8],
        ];
        let bitmap = super::super::bit_matrix::BitMatrix::new_unchecked(bits);
        let mut index_map = Dictionary::<char, usize, 10>::new();
        index_map.insert('A', 0).unwrap();
        index_map.insert('B', 1).unwrap();
        index_map.insert('C', 2).unwrap();

        let mut bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();

        // Try to remove edge that doesn't exist
        let result = bit_map_matrix.remove_edge('A', 'C');
        assert!(matches!(result, Err(GraphError::EdgeNotFound('A', 'C'))));

        // Try to remove edge with non-existent nodes
        let result = bit_map_matrix.remove_edge('X', 'Y');
        assert!(matches!(result, Err(GraphError::EdgeNotFound('X', 'Y'))));

        // Verify original edge is still there
        assert_eq!(bit_map_matrix.iter_edges().unwrap().count(), 1);
    }

    #[test]
    fn test_add_remove_edge_comprehensive() {
        use crate::graph::GraphWithMutableEdges;

        let bits = [[0u8]; 8];
        let bitmap = super::super::bit_matrix::BitMatrix::new_unchecked(bits);
        let mut index_map = Dictionary::<u32, usize, 10>::new();
        index_map.insert(10, 0).unwrap();
        index_map.insert(20, 1).unwrap();
        index_map.insert(30, 2).unwrap();
        index_map.insert(40, 3).unwrap();

        let mut bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();

        // Start with empty graph
        assert_eq!(bit_map_matrix.iter_edges().unwrap().count(), 0);

        // Add several edges
        assert!(bit_map_matrix.add_edge(10, 20).is_ok());
        assert!(bit_map_matrix.add_edge(20, 30).is_ok());
        assert!(bit_map_matrix.add_edge(30, 40).is_ok());
        assert!(bit_map_matrix.add_edge(10, 40).is_ok());
        assert_eq!(bit_map_matrix.iter_edges().unwrap().count(), 4);

        // Remove some edges
        assert!(bit_map_matrix.remove_edge(20, 30).is_ok());
        assert_eq!(bit_map_matrix.iter_edges().unwrap().count(), 3);

        // Try to remove the same edge again (should fail)
        let result = bit_map_matrix.remove_edge(20, 30);
        assert!(matches!(result, Err(GraphError::EdgeNotFound(20, 30))));

        // Add the edge back
        assert!(bit_map_matrix.add_edge(20, 30).is_ok());
        assert_eq!(bit_map_matrix.iter_edges().unwrap().count(), 4);

        // Verify final edge set
        let mut edges = [(0u32, 0u32); 8];
        let edges_slice = collect_sorted(bit_map_matrix.iter_edges().unwrap(), &mut edges);
        assert_eq!(edges_slice, &[(10, 20), (10, 40), (20, 30), (30, 40)]);
    }

    #[test]
    fn test_self_loops() {
        use crate::graph::GraphWithMutableEdges;

        let bits = [[0u8]; 8];
        let bitmap = super::super::bit_matrix::BitMatrix::new_unchecked(bits);
        let mut index_map = Dictionary::<char, usize, 10>::new();
        index_map.insert('A', 0).unwrap();
        index_map.insert('B', 1).unwrap();

        let mut bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();

        // Add self-loops and regular edges
        assert!(bit_map_matrix.add_edge('A', 'A').is_ok()); // Self-loop
        assert!(bit_map_matrix.add_edge('A', 'B').is_ok());
        assert!(bit_map_matrix.add_edge('B', 'B').is_ok()); // Self-loop

        assert_eq!(bit_map_matrix.iter_edges().unwrap().count(), 3);

        // Remove self-loop
        assert!(bit_map_matrix.remove_edge('A', 'A').is_ok());
        assert_eq!(bit_map_matrix.iter_edges().unwrap().count(), 2);

        // Verify remaining edges
        let mut edges = [('\0', '\0'); 8];
        let edges_slice = collect_sorted(bit_map_matrix.iter_edges().unwrap(), &mut edges);
        assert_eq!(edges_slice, &[('A', 'B'), ('B', 'B')]);
    }

    #[test]
    fn test_edge_idempotency() {
        use crate::graph::GraphWithMutableEdges;

        let bits = [[0u8]; 8];
        let bitmap = super::super::bit_matrix::BitMatrix::new_unchecked(bits);
        let mut index_map = Dictionary::<u32, usize, 10>::new();
        index_map.insert(1, 0).unwrap();
        index_map.insert(2, 1).unwrap();

        let mut bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();

        // Add edge
        assert!(bit_map_matrix.add_edge(1, 2).is_ok());
        assert_eq!(bit_map_matrix.iter_edges().unwrap().count(), 1);

        // Add same edge again (should be idempotent)
        assert!(bit_map_matrix.add_edge(1, 2).is_ok());
        assert_eq!(bit_map_matrix.iter_edges().unwrap().count(), 1);
    }
}

kaidokert / heapless-graphs-rs / 15792950674

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous