adjacency_matrix/static_half/
mod.rs

1use crate::AdjacencyEdge;
2use graph_types::{GraphError, GraphResult, UndirectedEdge};
3use num_traits::{One, Zero};
4use std::{
5    cmp::Ordering,
6    fmt::{Debug, Display},
7    ops::AddAssign,
8};
9mod display;
10
11#[derive(Clone, Debug)]
12pub struct StaticUndirected {
13    /// edges, lower triangular matrix
14    edges: Vec<usize>,
15}
16
17impl StaticUndirected {
18    pub fn new(nodes: usize) -> Self {
19        Self { edges: vec![0; (nodes + 1) * nodes / 2] }
20    }
21    pub fn nodes(&self) -> usize {
22        // edges == (nodes + 1) * nodes / 2
23        (((self.edges.len() * 8 + 1) as f64).sqrt() / 2.0).floor() as usize
24    }
25    pub fn edges(&self) -> usize {
26        self.edges.len()
27    }
28    pub fn max_degree(&self) -> usize {
29        self.edges.iter().max().copied().unwrap_or(0)
30    }
31    pub fn min_degree(&self) -> usize {
32        self.edges.iter().min().copied().unwrap_or(0)
33    }
34    pub fn get_edge<T>(&self, undirected: T) -> GraphResult<usize>
35    where
36        T: Into<UndirectedEdge>,
37    {
38        let edge = undirected.into();
39        let index = edge_index(&edge);
40        match self.edges.get(index) {
41            Some(s) => Ok(*s),
42            None => Err(GraphError::edge_out_of_range(index, self.edges.len())),
43        }
44    }
45    pub fn mut_edge<T>(&mut self, undirected: T) -> GraphResult<&mut usize>
46    where
47        T: Into<UndirectedEdge>,
48    {
49        let edge = undirected.into();
50        let index = edge_index(&edge);
51        let count = self.edges.len();
52        match self.edges.get_mut(index) {
53            Some(s) => Ok(s),
54            None => Err(GraphError::edge_out_of_range(index, count)),
55        }
56    }
57    pub fn set_edge<T>(&mut self, undirected: T, mut connection: usize) -> GraphResult<usize>
58    where
59        T: Into<UndirectedEdge>,
60    {
61        let new = &mut connection;
62        let old = self.mut_edge(undirected)?;
63        std::mem::swap(new, old);
64        Ok(*new)
65    }
66
67    pub fn connect<T>(&mut self, edge: T) -> GraphResult<usize>
68    where
69        T: Into<UndirectedEdge>,
70    {
71        let edge = self.mut_edge(edge)?;
72        *edge = edge.saturating_add(1);
73        Ok(*edge)
74    }
75    pub fn disconnect<T>(&mut self, edge: T) -> GraphResult<usize>
76    where
77        T: Into<UndirectedEdge>,
78    {
79        let edge = self.mut_edge(edge)?;
80        *edge = edge.saturating_sub(1);
81        Ok(*edge)
82    }
83}
84
85fn edge_index(edge: &UndirectedEdge) -> usize {
86    let min_index = edge.min_index();
87    let max_index = edge.max_index();
88    max_index * (max_index + 1) / 2 + min_index
89}
adjacency_matrix/static_half/mod.rs

adjacency_matrix/static_half/
mod.rs
