snark_tool/graph/undirected/simple_graph/
graph.rs

1use crate::graph::edge::{Edge, EdgeConstructor};
2use crate::graph::graph::{Graph, GraphConstructor};
3use crate::graph::undirected::edge::UndirectedEdge;
4use crate::graph::undirected::vertex::VertexWithEdges;
5use crate::graph::undirected::UndirectedGraph;
6use crate::graph::vertex::{Vertex, VertexConstructor};
7use std::{fmt, slice};
8
9///
10/// undirected, without loops or multiple edges
11///
12#[derive(Debug, Clone)]
13pub struct SimpleGraph {
14    pub vertices: Vec<VertexWithEdges>,
15}
16
17impl UndirectedGraph for SimpleGraph {}
18
19impl Graph for SimpleGraph {
20    type V = VertexWithEdges;
21    type E = UndirectedEdge;
22
23    fn size(&self) -> usize {
24        self.vertices.len()
25    }
26
27    fn has_edge(&self, from: usize, to: usize) -> bool {
28        if from >= self.vertices.len() || to >= self.vertices.len() {
29            return false;
30        }
31        let from_vertex = &self.vertices[from];
32        for edge in from_vertex.edges.iter() {
33            if edge.from() == from && edge.to() == to || edge.from() == to && edge.to() == from {
34                return true;
35            }
36        }
37        false
38    }
39
40    fn add_vertex(&mut self) {
41        self.vertices
42            .push(VertexWithEdges::new(self.vertices.len()));
43    }
44
45    fn add_edge(&mut self, from: usize, to: usize) {
46        let edge = UndirectedEdge::new(from, to);
47        if from == to {
48            return;
49        }
50        if self.has_edge(from, to) {
51            return;
52        }
53        while self.vertices.len() <= edge.to() {
54            self.add_non_active_vertex();
55        }
56        let from_vertex = &mut self.vertices[from];
57        from_vertex.add_edge(to, 0);
58        from_vertex.set_active(true);
59        let to_vertex = &mut self.vertices[to];
60        to_vertex.add_edge(from, 0);
61        to_vertex.set_active(true);
62    }
63
64    fn remove_edge(&mut self, from: usize, to: usize) {
65        let edge_to_remove = UndirectedEdge::new(from, to);
66
67        let from_vertex = &mut self.vertices[from];
68        from_vertex.edges.retain(|edge| {
69            edge.from() != edge_to_remove.from() || edge.to() != edge_to_remove.to()
70        });
71
72        let to_vertex = &mut self.vertices[to];
73        to_vertex.edges.retain(|edge| {
74            edge.from() != edge_to_remove.from() || edge.to() != edge_to_remove.to()
75        });
76    }
77
78    fn remove_edges_of_vertex(&mut self, vertex: usize) {
79        if vertex >= self.vertices.len() {
80            return;
81        }
82        let neighbors = self.vertices[vertex].neighbors().clone();
83        self.vertices[vertex].edges = vec![];
84        for neighbor in neighbors {
85            let edge_to_remove = UndirectedEdge::new(vertex, neighbor);
86            self.vertices[neighbor].edges.retain(|edge| {
87                edge_to_remove.from() != edge.from() || edge_to_remove.to() != edge.to()
88            });
89        }
90    }
91
92    fn remove_vertex(&mut self, vertex_index: usize) {
93        self.remove_edges_of_vertex(vertex_index)
94    }
95
96    fn vertices<'a>(&'a self) -> Box<dyn Iterator<Item = &'a VertexWithEdges> + 'a> {
97        Box::new(Vertices::new(self.vertices.iter()))
98    }
99
100    fn edges<'a>(&'a self) -> Box<dyn Iterator<Item = &'a UndirectedEdge> + 'a> {
101        Box::new(Edges::new(&self.vertices))
102    }
103
104    fn edges_of_vertex<'a>(
105        &'a self,
106        vertex: usize,
107    ) -> Box<dyn Iterator<Item = &'a UndirectedEdge> + 'a> {
108        Box::new(self.vertices[vertex].edges.iter())
109    }
110
111    fn neighbors_of_vertex(&self, vertex: usize) -> Vec<usize> {
112        let mut neighbors = vec![];
113        let mut edges = self.edges_of_vertex(vertex);
114        while let Some(edge) = edges.next() {
115            if edge.from() == vertex {
116                neighbors.push(edge.to());
117            } else {
118                neighbors.push(edge.from());
119            }
120        }
121        neighbors
122    }
123}
124
125impl GraphConstructor for SimpleGraph {
126    fn new() -> Self {
127        Self::with_vertices_capacity(20)
128    }
129
130    fn with_capacity(vertices: usize, _edges: usize) -> Self {
131        Self::with_vertices_capacity(vertices)
132    }
133
134    fn with_vertices_capacity(vertices: usize) -> Self {
135        SimpleGraph {
136            vertices: Vec::with_capacity(vertices),
137        }
138    }
139}
140
141impl SimpleGraph {
142    pub fn from_graph<G: Graph>(graph: &G) -> Self {
143        let mut result = SimpleGraph::with_vertices_capacity(graph.size());
144        for edge in graph.edges() {
145            result.add_edge(edge.from(), edge.to());
146        }
147        result
148    }
149
150    pub fn add_vertex_with_index(&mut self, vertex: usize) {
151        while self.size() < vertex + 1 {
152            self.add_non_active_vertex();
153        }
154        self.vertices[vertex].set_active(true);
155    }
156
157    pub fn has_vertex(&self, vertex: usize) -> bool {
158        if vertex >= self.size() {
159            return false;
160        }
161        self.vertices[vertex].active()
162    }
163
164    pub fn first_vertex(&self) -> Option<&VertexWithEdges> {
165        for vertex in self.vertices() {
166            if self.has_vertex(vertex.index()) {
167                return Some(vertex);
168            }
169        }
170        None
171    }
172
173    #[allow(dead_code)]
174    pub fn vertex(&self, index: usize) -> Option<&VertexWithEdges> {
175        if !self.has_vertex(index) {
176            return None;
177        }
178        Some(&self.vertices[index])
179    }
180
181    #[allow(dead_code)]
182    pub fn remove_vertex(&mut self, vertex: usize) {
183        if vertex >= self.vertices.len() {
184            return;
185        }
186        self.remove_edges_of_vertex(vertex);
187        self.vertices[vertex].set_active(false);
188    }
189
190    fn add_non_active_vertex(&mut self) {
191        self.vertices
192            .push(VertexWithEdges::new_non_active(self.vertices.len()));
193    }
194}
195
196/// Vertices
197pub struct Vertices<'a> {
198    vertices: slice::Iter<'a, VertexWithEdges>,
199}
200
201impl<'a> Vertices<'a> {
202    pub fn new(vertices: slice::Iter<'a, VertexWithEdges>) -> Self {
203        Vertices { vertices }
204    }
205}
206
207impl<'a> Iterator for Vertices<'a> {
208    type Item = &'a VertexWithEdges;
209
210    fn next(&mut self) -> Option<Self::Item> {
211        if let Some(vertex) = self.vertices.next() {
212            if vertex.active() {
213                return Some(vertex);
214            }
215            return self.next();
216        }
217        None
218    }
219}
220
221/// Edges
222pub struct Edges<'a> {
223    vertices: &'a Vec<VertexWithEdges>,
224    position: (usize, usize),
225}
226
227impl<'a> Edges<'a> {
228    pub fn new(vertices: &'a Vec<VertexWithEdges>) -> Self {
229        Edges {
230            vertices,
231            position: (0, 0),
232        }
233    }
234}
235
236impl<'a> Iterator for Edges<'a> {
237    type Item = &'a UndirectedEdge;
238    fn next(&mut self) -> Option<Self::Item> {
239        if self.vertices.len() <= self.position.0 {
240            return None;
241        }
242
243        let vertex = &self.vertices[self.position.0];
244        if vertex.edges.len() <= self.position.1 {
245            self.position.0 += 1;
246            self.position.1 = 0;
247            return self.next();
248        }
249
250        let neighboring_edge = &vertex.edges[self.position.1];
251
252        if neighboring_edge.from() != vertex.index() {
253            self.position.1 += 1;
254            return self.next();
255        }
256
257        self.position.1 += 1;
258        Some(neighboring_edge)
259    }
260}
261
262impl fmt::Display for SimpleGraph {
263    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
264        for vertex in &self.vertices {
265            write!(f, "{}: ", vertex.index())?;
266            let mut separ = String::from("");
267            for edge in vertex.edges.iter() {
268                let neighbor = if edge.from() == vertex.index() {
269                    edge.to()
270                } else {
271                    edge.from()
272                };
273                write!(f, "{}{}", separ, neighbor)?;
274                separ = String::from(", ");
275            }
276
277            writeln!(f)?;
278        }
279        Ok(())
280    }
281}
282
283impl PartialEq for SimpleGraph {
284    fn eq(&self, other: &Self) -> bool {
285        if self.size() != other.size() {
286            return false;
287        }
288        if self.vertices[..] != other.vertices[..] {
289            return false;
290        }
291        true
292    }
293}
294
295impl Eq for SimpleGraph {}
snark_tool/graph/undirected/simple_graph/graph.rs

snark_tool/graph/undirected/simple_graph/
graph.rs
