assert_graph_iso/
lib.rs

1/*!
2## assert-graph-iso
3
4A test utility to check if two property graphs are equal, i.e., isomorphic.
5The check is performed by computing a canonical string representation for each graph.
6If the canonical representations are identical, the graphs are considered isomorphic.
7The crate is supposed to be used as a test utility, it is not designed for large scale graph comparisons.
8
9
10### Property graph data model
11
12A property graph consists of nodes and relationships.
13Nodes have zero or more labels, relationships have zero or one relationship type.
14Both, nodes and relationships have properties, organized as key-value-pairs.
15Relationships are directed, starting at a source node and pointing at a target node.
16
17
18### Usage
19
20The crate contains a `Graph` trait which defines a property graph.
21Users are supposed to implement the trait for their custom graph implemention.
22The crate also provides a `gdl` feature which allows for simple graph definition using a declarative language.
23Check out the [gdl on crates.io](https://crates.io/crates/gdl) for more information about the language.
24
25Testing for equality:
26
27```rust
28use ::gdl::Graph as GdlGraph;
29use assert_graph_iso::*;
30
31let g1 = "(a), (b), (a)-[:REL { foo:42 }]->(b)".parse::<GdlGraph>().unwrap();
32let g2 = "(a), (b), (b)-[:REL { foo:42 }]->(a)".parse::<GdlGraph>().unwrap();
33
34assert!(equals(&g1, &g2))
35```
36
37Compare the canonical representations for easier debugging:
38
39```rust
40use ::gdl::Graph as GdlGraph;
41use assert_graph_iso::*;
42
43let g1 = "(a:Label1), (b:Label2), (a)-->(b)".parse::<GdlGraph>().unwrap();
44let g2 = "(a:Label2), (b:Label1), (b)-->(a)".parse::<GdlGraph>().unwrap();
45
46assert_eq!(canonicalize(&g1), canonicalize(&g2))
47```
48
49
50## License
51
52Apache 2.0 or MIT
53*/
54use std::collections::HashMap;
55
56use graph::PropertyIterator;
57
58#[cfg(feature = "gdl")]
59pub mod gdl;
60pub mod graph;
61
62pub use graph::Graph;
63
64pub fn equals(left: &impl Graph, right: &impl Graph) -> bool {
65    let left = canonicalize(left);
66    let right = canonicalize(right);
67    left.eq(&right)
68}
69
70pub fn canonicalize<G: Graph>(graph: &G) -> String {
71    let canonical_nodes = canonical_nodes(graph);
72
73    let mut out_adjacencies = HashMap::<&G::NodeId, Vec<String>>::new();
74    let mut in_adjacencies = HashMap::<&G::NodeId, Vec<String>>::new();
75
76    graph.nodes().for_each(|source_node| {
77        graph.outgoing_relationships(source_node).for_each(
78            |((target_node, rel_type), rel_properties)| {
79                let canonical_source = canonical_nodes.get(source_node).unwrap();
80                let canonical_target = canonical_nodes.get(target_node).unwrap();
81
82                let sorted_properties = canonical_properties::<G>(rel_properties);
83
84                let canonical_out_relationship = format!(
85                    "()-[:{} {}]->{}",
86                    rel_type, sorted_properties, canonical_target
87                );
88
89                let canonical_in_relationship = format!(
90                    "()<-[:{} {}]-{}",
91                    rel_type, sorted_properties, canonical_source
92                );
93
94                out_adjacencies
95                    .entry(source_node)
96                    .or_insert(Vec::new())
97                    .push(canonical_out_relationship);
98
99                in_adjacencies
100                    .entry(target_node)
101                    .or_insert(Vec::new())
102                    .push(canonical_in_relationship);
103            },
104        )
105    });
106
107    let mut canonical_out_adjacencies = out_adjacencies
108        .into_iter()
109        .map(|(node, mut relationships)| {
110            relationships.sort();
111            (node, relationships.join(", "))
112        })
113        .collect::<HashMap<_, _>>();
114
115    let mut canonical_in_adjacencies = in_adjacencies
116        .into_iter()
117        .map(|(node, mut relationships)| {
118            relationships.sort();
119            (node, relationships.join(", "))
120        })
121        .collect::<HashMap<_, _>>();
122
123    &canonical_out_adjacencies;
124    &canonical_in_adjacencies;
125
126    let mut matrix = canonical_nodes
127        .into_iter()
128        .map(|(node, canonical_node)| {
129            format!(
130                "{} => out: {} in: {}",
131                canonical_node,
132                canonical_out_adjacencies.remove(node).unwrap_or_default(),
133                canonical_in_adjacencies.remove(node).unwrap_or_default()
134            )
135        })
136        .collect::<Vec<_>>();
137
138    matrix.sort();
139    matrix.join("\n")
140}
141
142fn canonical_nodes<G: Graph>(graph: &G) -> HashMap<&G::NodeId, String> {
143    graph
144        .nodes()
145        .map(|node| {
146            let mut node_labels = graph
147                .node_labels(node)
148                .map(|label| format!("{}", label))
149                .collect::<Vec<_>>();
150
151            node_labels.sort();
152            node_labels.dedup();
153
154            let sorted_labels = node_labels
155                .into_iter()
156                .map(|label| format!(":{}", label))
157                .collect::<String>();
158
159            let sorted_properties = canonical_properties::<G>(graph.node_properties(node));
160
161            (node, format!("({} {})", sorted_labels, sorted_properties))
162        })
163        .collect::<HashMap<_, _>>()
164}
165
166fn canonical_properties<G: Graph>(
167    properties: PropertyIterator<&G::PropertyKey, &G::PropertyValue>,
168) -> String {
169    let mut properties = properties
170        .map(|(key, value)| format!("{}: {}", key, value))
171        .collect::<Vec<_>>();
172
173    properties.dedup();
174    properties.sort();
175
176    let sorted_properties = properties.join(", ");
177    if sorted_properties.is_empty() {
178        String::new()
179    } else {
180        format!("{{ {} }}", sorted_properties)
181    }
182}
183
184#[cfg(all(not(feature = "gdl"), test))]
185compile_error!("Please run tests with --all-features");
186
187#[cfg(all(feature = "gdl", test))]
188mod tests {
189    use super::*;
190
191    use ::gdl::Graph as GdlGraph;
192    use trim_margin::MarginTrimmable;
193
194    fn from_gdl(gdl: &str) -> GdlGraph {
195        gdl.parse::<GdlGraph>().unwrap()
196    }
197
198    #[test]
199    fn test_topology_equals() {
200        let g1 = from_gdl("(a), (b), (a)-->(b)");
201        let g2 = from_gdl("(a), (b), (a)-->(b)");
202
203        assert_eq!(canonicalize(&g1), canonicalize(&g2))
204    }
205
206    #[test]
207    fn test_topology_not_equals() {
208        let g1 = from_gdl("(a), (b), (a)-->(b)");
209        let g2 = from_gdl("(a), (a)-->(a)");
210        assert_ne!(canonicalize(&g1), canonicalize(&g2))
211    }
212
213    #[test]
214    fn test_topology_and_node_labels_equals() {
215        let g1 = from_gdl("(a:A:B), (b:B), (a)-->(b)");
216        let g2 = from_gdl("(a:A:B), (b:B), (a)-->(b)");
217        assert_eq!(canonicalize(&g1), canonicalize(&g2))
218    }
219
220    #[test]
221    fn test_topology_and_node_labels_not_equals() {
222        let g1 = from_gdl("(a:A:B), (b:B), (a)-->(b)");
223        let g2 = from_gdl("(a:A:B), (b:C), (a)-->(b)");
224        assert_ne!(canonicalize(&g1), canonicalize(&g2))
225    }
226
227    #[test]
228    fn test_topology_and_data_equals() {
229        let g1 = from_gdl("(a {a:2, w:1.0}), (b {w:2, a:3, q:42.0}), (a)-->(b)");
230        let g2 = from_gdl("(a {a:2, w:1.0}), (b {w:2, a:3, q:42.0}), (a)-->(b)");
231        assert_eq!(canonicalize(&g1), canonicalize(&g2))
232    }
233
234    #[test]
235    fn test_parallel_edges() {
236        let g1 = from_gdl("(a), (b), (a)-[{w:1}]->(b), (a)-[{w:2}]->(b)");
237        let g2 = from_gdl("(a), (b), (a)-[{w:2}]->(b), (a)-[{w:1}]->(b)");
238        assert_eq!(canonicalize(&g1), canonicalize(&g2))
239    }
240
241    #[test]
242    fn test_loop() {
243        let g1 = from_gdl("(a), (b), (a)-[{w:1}]->(a), (a)-[{w:2}]->(b)");
244        let g2 = from_gdl("(a), (b), (a)-[{w:2}]->(b), (a)-[{w:1}]->(a)");
245        assert_eq!(canonicalize(&g1), canonicalize(&g2))
246    }
247
248    #[test]
249    fn test_cycle() {
250        let g1 = from_gdl("(a {v:1}), (b {v:2}), (c {v:3}), (a)-->(b)-->(c)-->(a)");
251        let g2 = from_gdl("(a {v:2}), (b {v:3}), (c {v:1}), (a)-->(b)-->(c)-->(a)");
252        assert_eq!(canonicalize(&g1), canonicalize(&g2))
253    }
254
255    #[test]
256    fn test_complete_graph() {
257        let g1 = from_gdl(
258            "(a {v:1}), (b {v:2}), (c {v:3}), (b)<--(a)-->(c), (a)<--(b)-->(c), (a)<--(c)-->(b)",
259        );
260        let g2 = from_gdl(
261            "(a {v:1}), (b {v:2}), (c {v:3}), (b)<--(a)-->(b), (a)<--(b)-->(c), (a)<--(c)-->(b)",
262        );
263        assert_ne!(canonicalize(&g1), canonicalize(&g2))
264    }
265
266    #[test]
267    fn test_complete_homogenic_graph() {
268        let g1 = from_gdl(
269            "(a {v:1}), (b {v:1}), (c {v:1}), (b)<--(a)-->(c), (a)<--(b)-->(c), (a)<--(c)-->(b)",
270        );
271        let g2 = from_gdl(
272            "(a {v:1}), (b {v:1}), (c {v:1}), (b)<--(a)-->(b), (a)<--(b)-->(c), (a)<--(c)-->(b)",
273        );
274        assert_ne!(canonicalize(&g1), canonicalize(&g2))
275    }
276
277    #[test]
278    fn test_canonicalize() {
279        let g = r#"
280              (a:A { c: 42, b: 37, a: 13 })
281            , (b:B { bar: 84 })
282            , (c:C { baz: 19, boz: 84 })
283            , (a)-[:REL { c: 42, b: 37, a: 13 }]->(b)
284            , (b)-[:REL { c: 12 }]->(a)
285            , (b)-[:REL { a: 23 }]->(c)
286            "#
287        .parse::<GdlGraph>()
288        .unwrap();
289
290        let expected = "
291            |(:A { a: 13, b: 37, c: 42 }) => out: ()-[:REL { a: 13, b: 37, c: 42 }]->(:B { bar: 84 }) in: ()<-[:REL { c: 12 }]-(:B { bar: 84 })
292            |(:B { bar: 84 }) => out: ()-[:REL { a: 23 }]->(:C { baz: 19, boz: 84 }), ()-[:REL { c: 12 }]->(:A { a: 13, b: 37, c: 42 }) in: ()<-[:REL { a: 13, b: 37, c: 42 }]-(:A { a: 13, b: 37, c: 42 })
293            |(:C { baz: 19, boz: 84 }) => out:  in: ()<-[:REL { a: 23 }]-(:B { bar: 84 })
294            ".trim_margin().unwrap();
295
296        assert_eq!(expected, canonicalize(&g));
297    }
298}
assert_graph_iso/lib.rs

assert_graph_iso/
lib.rs
