comtesse/
graph.rs

1//! A generic Graph, containing vertices of type `V`, connected by type `E`
2
3use std::iter::repeat_with;
4
5/// A generic Graph, containing vertices of type `V`, connected by type `E`
6///
7/// This is rarely used directly. Instead use [crate::unweighted::Unweighted] or [crate::weighted::Weighted]
8pub struct Graph<V, E> {
9    pub(crate) vertices: Vec<V>,
10    pub(crate) edges: Vec<Vec<E>>,
11}
12
13/// Handle to Vertices in the graph
14#[derive(PartialEq, Eq, PartialOrd, Ord, Hash, Clone, Copy, Debug)]
15pub struct Handle(pub(crate) usize);
16
17impl<V, E> Graph<V, E> {
18    /// Constructs a new, empty `Graph<V>`
19    pub fn new() -> Self {
20        Graph {
21            vertices: vec![],
22            edges: vec![],
23        }
24    }
25
26    /// Constructs a new, empty `Graph<V>` with capacity `size`
27    ///
28    /// The adjacency list will not reallocate if the number of vertices does not exceed `size`
29    pub fn new_with_size(size: usize) -> Self {
30        Graph {
31            edges: Vec::with_capacity(size),
32            vertices: Vec::with_capacity(size),
33        }
34    }
35
36    /// Adds vertex with given `value` to graph. This returns a handle to the inserted element
37    pub fn add_vertex(&mut self, value: V) -> Handle {
38        let handle = self.vertices.len();
39        self.vertices.push(value);
40        self.edges.push(Vec::new());
41        Handle(handle)
42    }
43
44    /// Returns the number of vertices in the graph.
45    pub fn size(&self) -> usize {
46        self.vertices.len()
47    }
48
49    /// Returns the number of edges in the graph.
50    pub fn num_edges(&self) -> usize {
51        self.edges.iter().map(|elem| elem.len()).sum()
52    }
53
54    /// Returns the value associated with `vertex`
55    pub fn vertex_value(&self, vertex: Handle) -> &V {
56        &self.vertices[vertex.0]
57    }
58}
59
60impl<V, E> FromIterator<V> for Graph<V, E> {
61    /// creates a new graph, taking the vertices from the iterator
62    fn from_iter<T: IntoIterator<Item = V>>(iter: T) -> Self {
63        let vertices: Vec<V> = iter.into_iter().collect();
64        let size = vertices.len();
65        Graph {
66            vertices,
67            edges: repeat_with(Vec::new).take(size).collect(),
68        }
69    }
70}
71
72impl<V, E> Default for Graph<V, E> {
73    fn default() -> Self {
74        Self::new()
75    }
76}
77
78impl<V, E> Graph<V, E>
79where
80    V: Eq,
81{
82    /// Returns a handle to the first vertex containing the value
83    /// specified by `vertex_value` or `None` if no such vertex exists
84    pub fn get_vertex(&self, vertex_value: V) -> Option<Handle> {
85        self.vertices
86            .iter()
87            .enumerate()
88            .find(|(_, vertex)| **vertex == vertex_value)
89            .map(|(i, _)| Handle(i))
90    }
91}
comtesse/graph.rs

comtesse/
graph.rs
