assert-graph-iso 0.1.0

/*!
## assert-graph-iso

A test utility to check if two property graphs are equal, i.e., isomorphic.
The check is performed by computing a canonical string representation for each graph.
If the canonical representations are identical, the graphs are considered isomorphic.
The crate is supposed to be used as a test utility, it is not designed for large scale graph comparisons.


### Property graph data model

A property graph consists of nodes and relationships.
Nodes have zero or more labels, relationships have zero or one relationship type.
Both, nodes and relationships have properties, organized as key-value-pairs.
Relationships are directed, starting at a source node and pointing at a target node.


### Usage

The crate contains a `Graph` trait which defines a property graph.
Users are supposed to implement the trait for their custom graph implemention.
The crate also provides a `gdl` feature which allows for simple graph definition using a declarative language.
Check out the [gdl on crates.io](https://crates.io/crates/gdl) for more information about the language.

Testing for equality:

```rust
use ::gdl::Graph as GdlGraph;
use assert_graph_iso::*;

let g1 = "(a), (b), (a)-[:REL { foo:42 }]->(b)".parse::<GdlGraph>().unwrap();
let g2 = "(a), (b), (b)-[:REL { foo:42 }]->(a)".parse::<GdlGraph>().unwrap();

assert!(equals(&g1, &g2))
```

Compare the canonical representations for easier debugging:

```rust
use ::gdl::Graph as GdlGraph;
use assert_graph_iso::*;

let g1 = "(a:Label1), (b:Label2), (a)-->(b)".parse::<GdlGraph>().unwrap();
let g2 = "(a:Label2), (b:Label1), (b)-->(a)".parse::<GdlGraph>().unwrap();

assert_eq!(canonicalize(&g1), canonicalize(&g2))
```


## License

Apache 2.0 or MIT
*/
use std::collections::HashMap;

use graph::PropertyIterator;

#[cfg(feature = "gdl")]
pub mod gdl;
pub mod graph;

pub use graph::Graph;

pub fn equals(left: &impl Graph, right: &impl Graph) -> bool {
    let left = canonicalize(left);
    let right = canonicalize(right);
    left.eq(&right)
}

pub fn canonicalize<G: Graph>(graph: &G) -> String {
    let canonical_nodes = canonical_nodes(graph);

    let mut out_adjacencies = HashMap::<&G::NodeId, Vec<String>>::new();
    let mut in_adjacencies = HashMap::<&G::NodeId, Vec<String>>::new();

    graph.nodes().for_each(|source_node| {
        graph.outgoing_relationships(source_node).for_each(
            |((target_node, rel_type), rel_properties)| {
                let canonical_source = canonical_nodes.get(source_node).unwrap();
                let canonical_target = canonical_nodes.get(target_node).unwrap();

                let sorted_properties = canonical_properties::<G>(rel_properties);

                let canonical_out_relationship = format!(
                    "()-[:{} {}]->{}",
                    rel_type, sorted_properties, canonical_target
                );

                let canonical_in_relationship = format!(
                    "()<-[:{} {}]-{}",
                    rel_type, sorted_properties, canonical_source
                );

                out_adjacencies
                    .entry(source_node)
                    .or_insert(Vec::new())
                    .push(canonical_out_relationship);

                in_adjacencies
                    .entry(target_node)
                    .or_insert(Vec::new())
                    .push(canonical_in_relationship);
            },
        )
    });

    let mut canonical_out_adjacencies = out_adjacencies
        .into_iter()
        .map(|(node, mut relationships)| {
            relationships.sort();
            (node, relationships.join(", "))
        })
        .collect::<HashMap<_, _>>();

    let mut canonical_in_adjacencies = in_adjacencies
        .into_iter()
        .map(|(node, mut relationships)| {
            relationships.sort();
            (node, relationships.join(", "))
        })
        .collect::<HashMap<_, _>>();

    &canonical_out_adjacencies;
    &canonical_in_adjacencies;

    let mut matrix = canonical_nodes
        .into_iter()
        .map(|(node, canonical_node)| {
            format!(
                "{} => out: {} in: {}",
                canonical_node,
                canonical_out_adjacencies.remove(node).unwrap_or_default(),
                canonical_in_adjacencies.remove(node).unwrap_or_default()
            )
        })
        .collect::<Vec<_>>();

    matrix.sort();
    matrix.join("\n")
}

fn canonical_nodes<G: Graph>(graph: &G) -> HashMap<&G::NodeId, String> {
    graph
        .nodes()
        .map(|node| {
            let mut node_labels = graph
                .node_labels(node)
                .map(|label| format!("{}", label))
                .collect::<Vec<_>>();

            node_labels.sort();
            node_labels.dedup();

            let sorted_labels = node_labels
                .into_iter()
                .map(|label| format!(":{}", label))
                .collect::<String>();

            let sorted_properties = canonical_properties::<G>(graph.node_properties(node));

            (node, format!("({} {})", sorted_labels, sorted_properties))
        })
        .collect::<HashMap<_, _>>()
}

fn canonical_properties<G: Graph>(
    properties: PropertyIterator<&G::PropertyKey, &G::PropertyValue>,
) -> String {
    let mut properties = properties
        .map(|(key, value)| format!("{}: {}", key, value))
        .collect::<Vec<_>>();

    properties.dedup();
    properties.sort();

    let sorted_properties = properties.join(", ");
    if sorted_properties.is_empty() {
        String::new()
    } else {
        format!("{{ {} }}", sorted_properties)
    }
}

#[cfg(all(not(feature = "gdl"), test))]
compile_error!("Please run tests with --all-features");

#[cfg(all(feature = "gdl", test))]
mod tests {
    use super::*;

    use ::gdl::Graph as GdlGraph;
    use trim_margin::MarginTrimmable;

    fn from_gdl(gdl: &str) -> GdlGraph {
        gdl.parse::<GdlGraph>().unwrap()
    }

    #[test]
    fn test_topology_equals() {
        let g1 = from_gdl("(a), (b), (a)-->(b)");
        let g2 = from_gdl("(a), (b), (a)-->(b)");

        assert_eq!(canonicalize(&g1), canonicalize(&g2))
    }

    #[test]
    fn test_topology_not_equals() {
        let g1 = from_gdl("(a), (b), (a)-->(b)");
        let g2 = from_gdl("(a), (a)-->(a)");
        assert_ne!(canonicalize(&g1), canonicalize(&g2))
    }

    #[test]
    fn test_topology_and_node_labels_equals() {
        let g1 = from_gdl("(a:A:B), (b:B), (a)-->(b)");
        let g2 = from_gdl("(a:A:B), (b:B), (a)-->(b)");
        assert_eq!(canonicalize(&g1), canonicalize(&g2))
    }

    #[test]
    fn test_topology_and_node_labels_not_equals() {
        let g1 = from_gdl("(a:A:B), (b:B), (a)-->(b)");
        let g2 = from_gdl("(a:A:B), (b:C), (a)-->(b)");
        assert_ne!(canonicalize(&g1), canonicalize(&g2))
    }

    #[test]
    fn test_topology_and_data_equals() {
        let g1 = from_gdl("(a {a:2, w:1.0}), (b {w:2, a:3, q:42.0}), (a)-->(b)");
        let g2 = from_gdl("(a {a:2, w:1.0}), (b {w:2, a:3, q:42.0}), (a)-->(b)");
        assert_eq!(canonicalize(&g1), canonicalize(&g2))
    }

    #[test]
    fn test_parallel_edges() {
        let g1 = from_gdl("(a), (b), (a)-[{w:1}]->(b), (a)-[{w:2}]->(b)");
        let g2 = from_gdl("(a), (b), (a)-[{w:2}]->(b), (a)-[{w:1}]->(b)");
        assert_eq!(canonicalize(&g1), canonicalize(&g2))
    }

    #[test]
    fn test_loop() {
        let g1 = from_gdl("(a), (b), (a)-[{w:1}]->(a), (a)-[{w:2}]->(b)");
        let g2 = from_gdl("(a), (b), (a)-[{w:2}]->(b), (a)-[{w:1}]->(a)");
        assert_eq!(canonicalize(&g1), canonicalize(&g2))
    }

    #[test]
    fn test_cycle() {
        let g1 = from_gdl("(a {v:1}), (b {v:2}), (c {v:3}), (a)-->(b)-->(c)-->(a)");
        let g2 = from_gdl("(a {v:2}), (b {v:3}), (c {v:1}), (a)-->(b)-->(c)-->(a)");
        assert_eq!(canonicalize(&g1), canonicalize(&g2))
    }

    #[test]
    fn test_complete_graph() {
        let g1 = from_gdl(
            "(a {v:1}), (b {v:2}), (c {v:3}), (b)<--(a)-->(c), (a)<--(b)-->(c), (a)<--(c)-->(b)",
        );
        let g2 = from_gdl(
            "(a {v:1}), (b {v:2}), (c {v:3}), (b)<--(a)-->(b), (a)<--(b)-->(c), (a)<--(c)-->(b)",
        );
        assert_ne!(canonicalize(&g1), canonicalize(&g2))
    }

    #[test]
    fn test_complete_homogenic_graph() {
        let g1 = from_gdl(
            "(a {v:1}), (b {v:1}), (c {v:1}), (b)<--(a)-->(c), (a)<--(b)-->(c), (a)<--(c)-->(b)",
        );
        let g2 = from_gdl(
            "(a {v:1}), (b {v:1}), (c {v:1}), (b)<--(a)-->(b), (a)<--(b)-->(c), (a)<--(c)-->(b)",
        );
        assert_ne!(canonicalize(&g1), canonicalize(&g2))
    }

    #[test]
    fn test_canonicalize() {
        let g = r#"
              (a:A { c: 42, b: 37, a: 13 })
            , (b:B { bar: 84 })
            , (c:C { baz: 19, boz: 84 })
            , (a)-[:REL { c: 42, b: 37, a: 13 }]->(b)
            , (b)-[:REL { c: 12 }]->(a)
            , (b)-[:REL { a: 23 }]->(c)
            "#
        .parse::<GdlGraph>()
        .unwrap();

        let expected = "
            |(: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 })
            |(: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 })
            |(:C { baz: 19, boz: 84 }) => out:  in: ()<-[:REL { a: 23 }]-(:B { bar: 84 })
            ".trim_margin().unwrap();

        assert_eq!(expected, canonicalize(&g));
    }
}