1use serde::{Deserialize, Serialize};
2
3use crate::primitives::{Index, Label};
4use crate::{Edge, Isomorphism, Node};
5
6#[derive(Serialize, Deserialize, Clone, Debug)]
8pub struct Graph<I: Index, NL: Label, EL: Label> {
9 pub nodes: Vec<Node<I, NL>>,
10 pub edges: Vec<Edge<I, EL>>,
11}
12
13impl<I: Index, NL: Label, EL: Label> Graph<I, NL, EL> {
14 pub fn contains_edge_with_ids(&self, edge: &(I, I)) -> bool {
15 for e in &self.edges {
16 if e.from == edge.0 && e.to == edge.1 {
17 return true;
18 }
19 }
20 false
21 }
22
23 pub fn contains_node_with_id(&self, node: &I) -> bool {
24 for n in &self.nodes {
25 if &n.id == node {
26 return true;
27 }
28 }
29 false
30 }
31
32 pub fn get_node_by_id(&self, idx: &I) -> Option<&Node<I, NL>> {
33 for n in &self.nodes {
34 if &n.id == idx {
35 return Some(n);
36 }
37 }
38 None
39 }
40
41 pub fn neighbours(&self, nodeid: &I) -> Vec<Node<I, NL>> {
43 let mut neighbours = Vec::new();
44
45 for edge in &self.edges {
47 if &edge.from == nodeid {
48 let node = self
49 .get_node_by_id(&edge.to.clone())
50 .expect("Edges contain only valid node ids");
51 if !neighbours.contains(node) {
52 neighbours.push(node.clone());
53 }
54 } else if &edge.to == nodeid {
55 let node = self
56 .get_node_by_id(&edge.from.clone())
57 .expect("Edges contain only valid node ids");
58 if !neighbours.contains(node) {
59 neighbours.push(node.clone());
60 }
61 }
62 }
63 neighbours
64 }
65
66 pub fn cleanup_edges(&mut self) {
83 self.edges = self
84 .edges
85 .iter()
86 .filter(|e| {
87 let mut found_src = false;
88 let mut found_dst = false;
89 for n in &self.nodes {
90 if n.id == e.from {
91 found_src = true;
92 if found_src && found_dst {
93 break;
94 }
95 } else if n.id == e.to {
96 found_dst = true;
97 if found_src && found_dst {
98 break;
99 }
100 }
101 }
102 found_src && found_dst
103 })
104 .cloned()
105 .collect();
106 }
107
108 pub fn insert(&mut self, g: &Self) {
113 for n in &g.nodes {
115 if !self.nodes.contains(n) {
116 self.nodes.push(n.clone());
117 } }
119 for e in &g.edges {
121 if !self.edges.contains(e) {
122 self.edges.push(e.clone());
123 } }
125 }
126
127 pub fn remove(&mut self, g: &Self) {
132 self.nodes = self
134 .nodes
135 .iter()
136 .filter(|n| !g.nodes.contains(n))
137 .cloned()
138 .collect();
139
140 self.cleanup_edges();
142 }
143
144 pub fn translate(&mut self, g: &Isomorphism<I>) -> bool {
148 for node in &mut self.nodes {
150 if let Some(id) = g.0.get(&node.id) {
151 node.id = id.clone();
152 } else {
153 return false;
154 }
155 }
156 for edge in &mut self.edges {
157 if let (Some(from), Some(to)) = (g.0.get(&edge.from), g.0.get(&edge.to)) {
158 edge.from = from.clone();
159 edge.to = to.clone();
160 } else {
161 return false;
162 }
163 }
164 true
165 }
166
167 #[must_use]
171 pub fn translate_copy(&self, g: &Isomorphism<I>) -> Self {
172 let mut s = self.clone();
173 s.translate(g);
174 s
175 }
176}
177
178impl<I: Index> From<Graph<I, &str, ()>> for Graph<I, String, ()> {
179 fn from(g: Graph<I, &str, ()>) -> Self {
180 let nodes = g
181 .nodes
182 .iter()
183 .map(|n| Node::new(n.id.clone(), n.label.to_owned()))
184 .collect();
185 Self {
186 nodes,
187 edges: g.edges,
188 }
189 }
190}
191
192impl<I: Index, NL: Label, EL: Label> core::ops::Add for Graph<I, NL, EL> {
193 type Output = Self;
194 fn add(mut self, rhs: Self) -> Self::Output {
195 self.insert(&rhs);
196 self
197 }
198}
199
200impl<'a, I: Index, NL: Label, EL: Label> core::ops::Add<&'a Graph<I, NL, EL>>
201 for &'a Graph<I, NL, EL>
202{
203 type Output = Graph<I, NL, EL>;
204 fn add(self, rhs: Self) -> Self::Output {
205 let mut s = self.clone();
206 s.insert(rhs);
207 s
208 }
209}
210
211impl<I: Index, NL: Label, EL: Label> core::ops::Sub for Graph<I, NL, EL> {
212 type Output = Self;
213 fn sub(mut self, rhs: Self) -> Self::Output {
214 self.remove(&rhs);
215 self
216 }
217}
218
219impl<'a, I: Index, NL: Label, EL: Label> core::ops::Sub<&'a Graph<I, NL, EL>>
220 for &'a Graph<I, NL, EL>
221{
222 type Output = Graph<I, NL, EL>;
223 fn sub(self, rhs: Self) -> Self::Output {
224 let mut s = self.clone();
225 s.remove(rhs);
226 s
227 }
228}
229
230impl<'a, I: Index, NL: Label, EL: Label> core::ops::Sub<&'a [I]> for &'a Graph<I, NL, EL> {
231 type Output = Graph<I, NL, EL>;
232 fn sub(self, rhs: &'a [I]) -> Self::Output {
233 let nodes = self
234 .nodes
235 .iter()
236 .filter(|n| !rhs.contains(&n.id))
237 .cloned()
238 .collect();
239 let mut graph = Graph {
240 nodes,
241 edges: self.edges.clone(),
242 };
243 graph.cleanup_edges();
244 graph
245 }
246}
247
248impl<I: Index, NL: Label, EL: Label> PartialEq for Graph<I, NL, EL> {
249 fn eq(&self, other: &Self) -> bool {
250 for n in &self.nodes {
252 if !other.nodes.contains(n) {
253 return false;
254 }
255 }
256 for e in &self.edges {
257 if !other.edges.contains(e) {
258 return false;
259 }
260 }
261 true
262 }
263}
264
265use std::borrow::Cow;
268
269impl<'a, I: Index, NL: Label, EL: Label> dot::Labeller<'a, Node<I, NL>, Edge<I, EL>>
270 for Graph<I, NL, EL>
271{
272 fn graph_id(&'a self) -> dot::Id<'a> {
273 log::warn!("Labelling graph");
274 dot::Id::new("TODOGraphIdentifier").unwrap()
275 }
276
277 fn node_id(&'a self, n: &Node<I, NL>) -> dot::Id<'a> {
278 log::warn!("Labelling node: {:?}", n);
279 dot::Id::new(format!("N{:?}", &n.id)).unwrap()
281 }
282}
283
284impl<'a, I: Index, NL: Label, EL: Label> dot::GraphWalk<'a, Node<I, NL>, Edge<I, EL>>
285 for Graph<I, NL, EL>
286{
287 fn nodes(&'a self) -> dot::Nodes<'a, Node<I, NL>> {
288 Cow::Borrowed(&self.nodes[..])
289 }
290
291 fn edges(&'a self) -> dot::Edges<'a, Edge<I, EL>> {
292 Cow::Borrowed(&self.edges[..])
293 }
294
295 fn source(&self, e: &Edge<I, EL>) -> Node<I, NL> {
296 self.get_node_by_id(&e.from).unwrap().clone()
297 }
298
299 fn target(&self, e: &Edge<I, EL>) -> Node<I, NL> {
300 self.get_node_by_id(&e.to).unwrap().clone()
301 }
302}
303
304impl<I: Index, NL: Label, EL: Label> Graph<I, NL, EL> {
305 pub fn write_dot_to<W: std::io::Write>(&self, output: &mut W) -> std::io::Result<()> {
326 dot::render(self, output)
327 }
328}
329
330#[cfg(test)]
338mod tests {
339 use super::*;
340
341 #[test]
342 fn insert() {
343 let _ = pretty_env_logger::try_init_timed();
344 let g = Graph {
345 nodes: vec![Node::new(0u32, "a")],
346 edges: vec![],
347 };
348 let h = Graph {
349 nodes: vec![Node::new(1, "a")],
350 edges: vec![Edge::new_unlabeled(0, 1)],
351 };
352 let r = Graph {
353 nodes: vec![Node::new(0u32, "a"), Node::new(1, "a")],
354 edges: vec![Edge::new_unlabeled(0, 1)],
355 };
356 assert_eq!(&g + &h, r.clone());
357 assert_eq!(g.clone() + h.clone(), r.clone());
358 let d = {
359 let mut g = g.clone();
360 g.insert(&h);
361 g
362 };
363 assert_eq!(d, r);
364 }
365
366 #[test]
367 fn remove() {
368 let _ = pretty_env_logger::try_init_timed();
369 let g = Graph {
370 nodes: vec![Node::new(0u32, "a"), Node::new(1, "a")],
371 edges: vec![Edge::new_unlabeled(0, 1)],
372 };
373 let h = Graph {
374 nodes: vec![Node::new(1, "a")],
375 edges: vec![Edge::new_unlabeled(0, 1)],
376 };
377 let r = Graph {
378 nodes: vec![Node::new(0, "a")],
379 edges: vec![],
380 };
381 assert_eq!(&g - &h, r.clone());
382 assert_eq!(g.clone() - h.clone(), r.clone());
383 let d = {
384 let mut g = g.clone();
385 g.remove(&h);
386 g
387 };
388 assert_eq!(d, r);
389 }
390
391 #[test]
392 fn cleanup_edges() {
393 let _ = pretty_env_logger::try_init_timed();
394 let mut g = Graph {
395 nodes: vec![Node::new(0u32, "a")],
396 edges: vec![Edge::new_unlabeled(0, 1), Edge::new_unlabeled(2, 3)],
397 };
398 g.cleanup_edges();
399 let d = Graph {
400 nodes: vec![Node::new(0u32, "a")],
401 edges: vec![],
402 };
403 assert_eq!(g, d);
404 }
405
406 #[test]
407 fn node_neighbours() {
408 let _ = pretty_env_logger::try_init_timed();
409 let g = Graph {
410 nodes: vec![
411 Node::new(0u32, "a"),
412 Node::new(1, "a"),
413 Node::new(2, "a"),
414 Node::new(3, "a"),
415 ],
416 edges: vec![
417 Edge::new_unlabeled(0, 1),
418 Edge::new_unlabeled(1, 2),
419 Edge::new_unlabeled(1, 3),
420 ],
421 };
422 let reference: Vec<_> = [Node::new(0u32, "a"), Node::new(2, "a"), Node::new(3, "a")].into();
423 assert_eq!(reference, g.neighbours(&1));
424 }
425
426 #[test]
427 fn node_neighbours_extended() {
428 let graph = Graph {
429 nodes: vec![
430 Node::new(0u32, "a"),
431 Node::new(1, "a"),
432 Node::new(2, "a"),
433 Node::new(3, "a"),
434 ],
435 edges: vec![
436 Edge::new_unlabeled(0, 1),
437 Edge::new_unlabeled(1, 2),
438 Edge::new_unlabeled(1, 3),
439 Edge::new_unlabeled(3, 0),
440 ],
441 };
442 assert_eq!(
443 graph.neighbours(&1),
444 vec![
445 Node::new(0u32, "a"),
446 Node::new(2u32, "a"),
447 Node::new(3u32, "a"),
448 ]
449 );
450 assert_eq!(graph.neighbours(&2), vec![Node::new(1u32, "a"),]);
451 assert_eq!(
452 graph.neighbours(&3),
453 vec![Node::new(1u32, "a"), Node::new(0u32, "a"),]
454 );
455 }
456
457 #[test]
458 fn graph_difference_used_for_reduced_query_graph_gen() {
459 let _ = pretty_env_logger::try_init_timed();
460 let g = Graph {
461 nodes: vec![
462 Node::new(0u32, "a"),
463 Node::new(1, "a"),
464 Node::new(2, "a"),
465 Node::new(3, "a"),
466 ],
467 edges: vec![
468 Edge::new_unlabeled(0, 1),
469 Edge::new_unlabeled(1, 2),
470 Edge::new_unlabeled(1, 3),
471 Edge::new_unlabeled(3, 0),
472 ],
473 };
474 let nodes_to_remove = vec![1, 2];
475 let reduced_query: Graph<_, _, _> = &g - &nodes_to_remove[..];
476
477 let reference = Graph {
478 nodes: vec![Node::new(0u32, "a"), Node::new(3, "a")],
479 edges: vec![Edge::new_unlabeled(3, 0)],
480 };
481 assert_eq!(reference, reduced_query);
482 }
483}