graphlang/
graph.rs

1use serde::{Deserialize, Serialize};
2
3use crate::primitives::{Index, Label};
4use crate::{Edge, Isomorphism, Node};
5
6/// A `Graph` is in principle a owning tuple of Nodes and Edges.
7#[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    /// Returns all nodes connected to the given node id
42    pub fn neighbours(&self, nodeid: &I) -> Vec<Node<I, NL>> {
43        let mut neighbours = Vec::new();
44
45        // Check if there exists a edge (node, id) or (id, node)
46        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    /// Removes edges that either come from or incident on invalid nodes.
67    ///
68    /// # Examples
69    ///
70    /// ```
71    /// use graphlang::{Node,Edge,Graph,are_graphs_isomorph};
72    /// let mut graph = Graph {
73    ///         nodes: vec![ Node::new(0u32, "a"), Node::new(1, "a") ],
74    ///         edges: vec![ Edge::new_unlabeled(0, 1), Edge::new_unlabeled(0, 2), Edge::new_unlabeled(2, 3) ] };
75    /// let reference = Graph {
76    ///         nodes: vec![ Node::new(0u32, "a"), Node::new(1, "a") ],
77    ///         edges: vec![ Edge::new_unlabeled(0, 1) ] };
78    ///
79    /// graph.cleanup_edges();
80    /// assert_eq!(&reference, &graph );
81    /// ```
82    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    /// Assumes that the mapping between it and the graph is the identity.
109    /// So Node(1) in g adds Node(1) in self. If this is not desired
110    /// apply an isomorphism explicitly using `translate_copy`.
111    /// If then node already exists it replaces the label.
112    pub fn insert(&mut self, g: &Self) {
113        // Add nodes
114        for n in &g.nodes {
115            if !self.nodes.contains(n) {
116                self.nodes.push(n.clone());
117            } // TODO: Replace otherwise?
118        }
119        // Add edges
120        for e in &g.edges {
121            if !self.edges.contains(e) {
122                self.edges.push(e.clone());
123            } // TODO: Replace otherwise?
124        }
125    }
126
127    /// Assumes that the mapping between it and the graph is the identity.
128    /// So Node(1) in g removes Node(1) in self. If this is not desired
129    /// apply an isomorphism explicitly using `translate_copy`
130    /// If then node does not exists it skips it.
131    pub fn remove(&mut self, g: &Self) {
132        // Remove nodes
133        self.nodes = self
134            .nodes
135            .iter()
136            .filter(|n| !g.nodes.contains(n))
137            .cloned()
138            .collect();
139
140        // Remove edges
141        self.cleanup_edges();
142    }
143
144    /// Modifies a graph inplace by translating all ids using an isomorphism. If it contains nodes that are not
145    /// covered by the isomorphism they are not modified, which can lead to invalid graphs.
146    /// This behaviour should be reconsidered.
147    pub fn translate(&mut self, g: &Isomorphism<I>) -> bool {
148        // Translate nodes:
149        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    /// Returns a graph, that gets translated by an isomorphism. If it contains nodes that are not
168    /// covered by the isomorphism they are not modified, which can lead to invalid graphs.
169    /// This behaviour should be reconsidered.
170    #[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        // Compare nodes
251        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
265//  ------------------------------ DOT FEATURE ------------------------------
266
267use 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.id, &n.label)).unwrap()
280        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    /// Write graph using the dot-format to `output`. It can be easily visualized using `graphviz`
306    ///
307    /// # Examples
308    ///
309    /// ```
310    /// use graphlang::Graph;
311    /// # fn create_graph_somehow() -> Graph<u32,&'static str,()> {
312    /// #   graphlang::predefined::string_grammar().start_graph.clone()
313    /// # }
314    /// # fn test() -> std::io::Result<()> {
315    /// let graph: Graph<_,_,_> = create_graph_somehow();
316    /// let mut f = std::fs::File::create("Example.dot")?;
317    /// graph.write_dot_to(&mut f)?;
318    /// #   Ok(())
319    /// # }
320    /// # test().expect("Doc test for write_dot_to works");
321    /// ```
322    ///
323    /// # Errors
324    /// ...
325    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/// A nonowning `Graph`
331//#[derive(Serialize, Clone, PartialEq, Debug)]
332//pub struct Subgraph<'a, I: Index, NL: Label, EL: Label> {
333//    pub nodes: Vec<&'a Node<I, NL>>,
334//    pub edges: Vec<&'a Edge<I, EL>>,
335//}
336
337#[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}
graphlang/graph.rs

graphlang/
graph.rs
