mod adjacency;
use crate::geometry::distance::nonnegative;
use crate::{Error, Result};
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct WeightedEdge {
pub vertices: [usize; 2],
pub value: f64,
}
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct Neighbor {
pub vertex: usize,
pub value: f64,
}
#[derive(Clone, Debug)]
pub struct WeightedGraph {
edges: Vec<WeightedEdge>,
offsets: Vec<usize>,
neighbors: Vec<Neighbor>,
max_edge: f64,
}
impl WeightedGraph {
pub fn new(vertex_count: usize, mut edges: Vec<WeightedEdge>) -> Result<Self> {
let mut max_edge: f64 = 0.0;
for (index, edge) in edges.iter_mut().enumerate() {
let [a, b] = edge.vertices;
if a >= vertex_count || b >= vertex_count {
return Err(Error::InvalidGraph {
edge: index,
reason: "endpoint outside vertex range",
});
}
if a == b {
return Err(Error::InvalidGraph {
edge: index,
reason: "self-loop",
});
}
edge.vertices.sort_unstable();
edge.value = nonnegative(edge.value, "edge", Some(index))?;
max_edge = max_edge.max(edge.value);
}
edges.sort_unstable_by_key(|e| e.vertices);
for (index, pair) in edges.windows(2).enumerate() {
if pair[0].vertices == pair[1].vertices {
return Err(Error::InvalidGraph {
edge: index + 1,
reason: "duplicate edge in sorted input",
});
}
}
let (offsets, neighbors) = adjacency::build(vertex_count, &edges)?;
Ok(Self {
edges,
offsets,
neighbors,
max_edge,
})
}
pub fn vertex_count(&self) -> usize {
self.offsets.len() - 1
}
pub fn edge_count(&self) -> usize {
self.edges.len()
}
pub fn edges(&self) -> &[WeightedEdge] {
&self.edges
}
pub fn neighbors(&self, vertex: usize) -> Option<&[Neighbor]> {
if vertex >= self.vertex_count() {
return None;
}
Some(&self.neighbors[self.offsets[vertex]..self.offsets[vertex + 1]])
}
pub fn edge_value(&self, a: usize, b: usize) -> Option<f64> {
let neighbors = self.neighbors(a)?;
neighbors
.binary_search_by_key(&b, |v| v.vertex)
.ok()
.map(|i| neighbors[i].value)
}
pub fn max_edge(&self) -> f64 {
self.max_edge
}
}