wolf-graph 0.1.0

mod common;
use common::*;

use anyhow::Result;

use wolf_graph::prelude::*;

#[test]
fn test_is_tree() {
    let graph = make_graph();
    assert!(!graph.is_tree(nid!("A")));

    let dag = make_dag();
    assert!(!dag.is_tree(nid!("A")));

    let tree = make_tree();
    assert!(tree.is_tree(nid!("A")));

    let mut g = BlankGraph::new();

    fn is_a_tree(g: &BlankGraph) {
        assert!(g.is_tree(nid!("root")));
    }

    fn is_not_a_tree(g: &BlankGraph, root: NodeID) {
        assert!(!g.is_tree(root));
    }

    // No nodes? Not a tree.
    is_not_a_tree(&g, nid!("root"));

    // Only a root? That's a tree.
    g.add_node(nid!("root")).unwrap();
    is_a_tree(&g);

    // Some other unconnected node? Not a tree.
    g.add_node(nid!("A")).unwrap();
    is_not_a_tree(&g, nid!("root"));

    // Connect them? That's a tree.
    g.add_edge(eid!("rA"), nid!("root"), nid!("A")).unwrap();
    is_a_tree(&g);

    // Add another branch. Still a tree.
    g.add_node(nid!("B")).unwrap();
    g.add_edge(eid!("rB"), nid!("root"), nid!("B")).unwrap();
    is_a_tree(&g);

    // ...But not if we start with a non-root.
    is_not_a_tree(&g, nid!("A"));

    // Add another level to the tree.
    g.add_node(nid!("C")).unwrap();
    g.add_node(nid!("D")).unwrap();
    g.add_node(nid!("E")).unwrap();
    g.add_node(nid!("F")).unwrap();
    g.add_edge(eid!("AC"), nid!("A"), nid!("C")).unwrap();
    g.add_edge(eid!("AD"), nid!("A"), nid!("D")).unwrap();
    g.add_edge(eid!("BE"), nid!("B"), nid!("E")).unwrap();
    g.add_edge(eid!("BF"), nid!("B"), nid!("F")).unwrap();
    is_a_tree(&g);

    // Make a copy
    let undo = g.clone();

    // No cross-edges allowed
    g.add_edge(eid!("CE"), nid!("C"), nid!("E")).unwrap();
    is_not_a_tree(&g, nid!("root"));

    // Restore from backup
    g = undo.clone();
    is_a_tree(&g);

    // No back-edges allowed
    g.add_edge(eid!("Cr"), nid!("C"), nid!("root")).unwrap();
    is_not_a_tree(&g, nid!("root"));

    // Restore from backup again
    g = undo.clone();
    is_a_tree(&g);

    // No multiple edges allowed
    g.add_edge(eid!("BE2"), nid!("B"), nid!("E")).unwrap();
    is_not_a_tree(&g, nid!("root"));

    // Back to a real tree
    g = undo;
    is_a_tree(&g);
}

fn make_test_tree() -> BlankTree {
    Tree::new_with_root_and_graph(nid!("A"), make_tree()).unwrap()
}

#[test]
fn test_tree_codable() -> Result<()> {
    let tree = make_test_tree();
    recode(&tree, r#"["A",[["A","B","C","D","E","F","G","H","I","J","K","L","M","N","O"],[["AB","A","B"],["AC","A","C"],["AD","A","D"],["BI","B","I"],["CH","C","H"],["DE","D","E"],["DF","D","F"],["DG","D","G"],["EM","E","M"],["EN","E","N"],["EO","E","O"],["FL","F","L"],["HJ","H","J"],["HK","H","K"]]]]"#)?;
    Ok(())
}

#[test]
fn test_creation_1() -> Result<()> {
    let mut t1 = BlankTree::new();
    t1.add_node(nid!("A"), None::<NodeID>, eid!("rA"))?;
    t1.add_node(nid!("B"), None::<NodeID>, eid!("rB"))?;
    assert_eq!(t1, t1);
    recode(&t1, r#"["root",[["A","B","root"],[["rA","root","A"],["rB","root","B"]]]]"#)?;

    let mut t2 = Tree::<Graph<String, (), ()>>::new()
        .setting_data("graphData".to_string());
    t2.add_node(nid!("A"), None::<NodeID>, eid!("rA"))?;
    t2.add_node(nid!("B"), None::<NodeID>, eid!("rB"))?;
    assert_eq!(t2, t2);
    recode(&t2, r#"["root",[["A","B","root"],[["rA","root","A"],["rB","root","B"]],"graphData"]]"#)?;

    let mut t3 = Tree::<Graph<(), String, ()>>::new()
        .setting_node_data(nid!("root"), "rootData".to_string())?;
    t3.add_node_with_node_data(nid!("A"), None::<NodeID>, eid!("rA"), "aNodeData".to_string())?;
    t3.add_node_with_node_data(nid!("B"), None::<NodeID>, eid!("rB"), "bNodeData".to_string())?;
    assert_eq!(t3, t3);
    recode(&t3, r#"["root",[[["A","aNodeData"],["B","bNodeData"],["root","rootData"]],[["rA","root","A"],["rB","root","B"]]]]"#)?;

    let mut t4 = Tree::<Graph<(), (), String>>::new();
    t4.add_node_with_edge_data(nid!("A"), None::<NodeID>, eid!("rA"), "raEdgeData".to_string())?;
    t4.add_node_with_edge_data(nid!("B"), None::<NodeID>, eid!("rB"), "rbEdgeData".to_string())?;
    assert_eq!(t4, t4);
    recode(&t4, r#"["root",[["A","B","root"],[["rA","root","A","raEdgeData"],["rB","root","B","rbEdgeData"]]]]"#)?;

    let mut t5 = Tree::<Graph<String, (), String>>::new()
        .setting_data("graphData".to_string());
    t5.add_node_with_edge_data(nid!("A"), None::<NodeID>, eid!("rA"), "raEdgeData".to_string())?;
    t5.add_node_with_edge_data(nid!("B"), None::<NodeID>, eid!("rB"), "rbEdgeData".to_string())?;
    assert_eq!(t5, t5);
    recode(&t5, r#"["root",[["A","B","root"],[["rA","root","A","raEdgeData"],["rB","root","B","rbEdgeData"]],"graphData"]]"#)?;

    let mut t6 = Tree::<Graph<(), String, String>>::new();
    t6.add_node_with_node_and_edge_data(nid!("A"), None::<NodeID>, eid!("rA"), "aNodeData".to_string(), "raEdgeData".to_string())?;
    t6.add_node_with_node_and_edge_data(nid!("B"), None::<NodeID>, eid!("rB"), "bNodeData".to_string(), "rbEdgeData".to_string())?;
    assert_eq!(t6, t6);
    recode(&t6, r#"["root",[[["A","aNodeData"],["B","bNodeData"],["root",""]],[["rA","root","A","raEdgeData"],["rB","root","B","rbEdgeData"]]]]"#)?;

    let mut t7 = Tree::<Graph<String, String, ()>>::new()
        .setting_data("graphData".to_string())
        .setting_node_data(nid!("root"), "rootData".to_string())?;
    t7.add_node_with_node_data(nid!("A"), None::<NodeID>, eid!("rA"), "aNodeData".to_string())?;
    t7.add_node_with_node_data(nid!("B"), None::<NodeID>, eid!("rB"), "bNodeData".to_string())?;
    assert_eq!(t7, t7);
    recode(&t7, r#"["root",[[["A","aNodeData"],["B","bNodeData"],["root","rootData"]],[["rA","root","A"],["rB","root","B"]],"graphData"]]"#)?;

    let mut t8 = Tree::<Graph<String, String, String>>::new()
        .setting_data("graphData".to_string())
        .setting_node_data(nid!("root"), "rootData".to_string())?;
    t8.add_node_with_node_and_edge_data(nid!("A"), None::<NodeID>, eid!("rA"), "aNodeData".to_string(), "raEdgeData".to_string())?;
    t8.add_node_with_node_and_edge_data(nid!("B"), None::<NodeID>, eid!("rB"), "bNodeData".to_string(), "rbEdgeData".to_string())?;
    assert_eq!(t8, t8);
    recode(&t8, r#"["root",[[["A","aNodeData"],["B","bNodeData"],["root","rootData"]],[["rA","root","A","raEdgeData"],["rB","root","B","rbEdgeData"]],"graphData"]]"#)?;

    Ok(())
}

#[test]
fn test_tree_queries() -> Result<()> {
    let root_only_tree = BlankTree::new();
    assert!(!root_only_tree.is_empty());

    let t = make_test_tree();
    assert!(!t.is_empty());
    assert_eq!(t.node_count(), 15);
    assert_eq!(t.edge_count(), 14);
    assert_eq!(format_ids(t.all_nodes()), "[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O]");
    assert_eq!(format_ids(t.all_edges()), "[AB, AC, AD, BI, CH, DE, DF, DG, EM, EN, EO, FL, HJ, HK]");
    assert!(t.has_node(nid!("F")));
    assert!(!t.has_node(nid!("Z")));
    assert!(t.has_edge(eid!("CH")));
    assert!(!t.has_edge(eid!("ZZ")));
    assert!(t.has_edge_from_to(nid!("A"), nid!("C")));
    assert!(!t.has_edge_from_to(nid!("E"), nid!("A")));
    assert!(t.has_edge_between(nid!("A"), nid!("D")));
    assert!(t.has_edge_between(nid!("D"), nid!("F")));
    assert_eq!(t.source(eid!("DE"))?, nid!("D"));
    assert_eq!(t.target(eid!("DE"))?, nid!("E"));
    assert_eq!(t.endpoints(eid!("CH"))?, (nid!("C"), nid!("H")));
    assert_eq!(format_ids(t.out_edges(nid!("E"))?), "[EM, EN, EO]");
    assert_eq!(format_ids(t.in_edges(nid!("E"))?), "[DE]");
    assert_eq!(format_ids(t.incident_edges(nid!("A"))?), "[AB, AC, AD]");
    assert_eq!(t.out_degree(nid!("E"))?, 3);
    assert_eq!(t.in_degree(nid!("E"))?, 1);
    assert_eq!(t.degree(nid!("E"))?, 4);
    assert_eq!(format_ids(t.successors(nid!("D"))?), "[E, F, G]");
    assert_eq!(format_ids(t.predecessors(nid!("D"))?), "[A]");
    assert_eq!(format_ids(t.neighbors(nid!("E"))?), "[D, M, N, O]");
    // assert_eq!(t.node_data(nid!("A"))?.into_owned(), ());
    // assert_eq!(t.edge_data(eid!("AB"))?.into_owned(), ());
    assert_eq!(format_ids(t.all_roots()), "[A]");
    assert_eq!(format_ids(t.non_roots()), "[B, C, D, E, F, G, H, I, J, K, L, M, N, O]");
    assert_eq!(format_ids(t.all_leaves()), "[G, I, J, K, L, M, N, O]");
    assert_eq!(format_ids(t.all_internals()), "[B, C, D, E, F, H]");
    assert!(t.is_leaf(nid!("K"))?);
    assert!(!t.is_leaf(nid!("H"))?);
    assert!(t.is_root(nid!("A"))?);
    assert!(!t.is_root(nid!("H"))?);
    assert!(t.is_internal(nid!("C"))?);
    assert!(!t.is_internal(nid!("A"))?);
    assert!(!t.is_internal(nid!("K"))?);
    // assert_eq!(*t.data(), ());

    // Tree-specific queries
    assert_eq!(t.root(), nid!("A"));
    assert_eq!(t.in_edge(nid!("H"))?, Some(eid!("CH")));
    assert_eq!(t.in_edge(nid!("A"))?, None);
    assert_eq!(t.parent(nid!("H"))?, Some(nid!("C")));
    assert_eq!(t.parent(nid!("A"))?, None);
    assert_eq!(format_ids(t.children(Some(nid!("H")))?), "[J, K]");
    assert!(t.has_children(nid!("H"))?);
    assert!(!t.has_children(nid!("K"))?);

    Ok(())
}

#[test]
fn test_tree_mutations() -> Result<()> {
    // Start with just a root
    let mut t = BlankTree::new();
    assert_eq!(t, t);
    recode(&t, r#"["root",[["root"],[]]]"#)?;
    assert_eq!(format_ids(t.all_roots()), "[root]");
    assert_eq!(format_ids(t.all_leaves()), "[root]");

    // Add a couple children
    t.add_node(nid!("A"), None::<NodeID>, eid!("rA"))?;
    t.add_node(nid!("B"), None::<NodeID>, eid!("rB"))?;
    recode(&t, r#"["root",[["A","B","root"],[["rA","root","A"],["rB","root","B"]]]]"#)?;
    assert_eq!(format_ids(t.all_leaves()), "[A, B]");

    // Add a second layer
    t.add_node(nid!("C"), Some(nid!("A")), eid!("AC"))?;
    t.add_node(nid!("D"), Some(nid!("A")), eid!("AD"))?;
    t.add_node(nid!("E"), Some(nid!("B")), eid!("BE"))?;
    t.add_node(nid!("F"), Some(nid!("B")), eid!("BF"))?;
    recode(&t, r#"["root",[["A","B","C","D","E","F","root"],[["AC","A","C"],["AD","A","D"],["BE","B","E"],["BF","B","F"],["rA","root","A"],["rB","root","B"]]]]"#)?;
    assert_eq!(format_ids(t.all_leaves()), "[C, D, E, F]");

    // Make a backup
    let undo = t.clone();

    // Remove A, promoting its children
    t.remove_node_ungrouping(nid!("A"))?;
    recode(&t, r#"["root",[["B","C","D","E","F","root"],[["AC","root","C"],["AD","root","D"],["BE","B","E"],["BF","B","F"],["rB","root","B"]]]]"#)?;
    assert_eq!(format_ids(t.all_leaves()), "[C, D, E, F]");

    // Remove B, including its children
    t.remove_node_and_children(nid!("B"))?;
    recode(&t, r#"["root",[["C","D","root"],[["AC","root","C"],["AD","root","D"]]]]"#)?;
    assert_eq!(format_ids(t.all_leaves()), "[C, D]");

    // Restore from backup
    t = undo.clone();
    recode(&t, r#"["root",[["A","B","C","D","E","F","root"],[["AC","A","C"],["AD","A","D"],["BE","B","E"],["BF","B","F"],["rA","root","A"],["rB","root","B"]]]]"#)?;
    assert_eq!(format_ids(t.all_leaves()), "[C, D, E, F]");

    // Restore from backup
    t = undo.clone();
    // Remove the children of B
    t.remove_children(nid!("B"))?;
    recode(&t, r#"["root",[["A","B","C","D","root"],[["AC","A","C"],["AD","A","D"],["rA","root","A"],["rB","root","B"]]]]"#)?;
    assert_eq!(format_ids(t.all_leaves()), "[B, C, D]");

    // Restore from backup
    t = undo;
    // Move B under D
    t.move_node(nid!("B"), Some(nid!("D")))?;
    recode(&t, r#"["root",[["A","B","C","D","E","F","root"],[["AC","A","C"],["AD","A","D"],["BE","B","E"],["BF","B","F"],["rA","root","A"],["rB","D","B"]]]]"#)?;
    assert_eq!(format_ids(t.all_leaves()), "[C, E, F]");

    Ok(())
}

#[test]
fn test_tree_builders() -> Result<()> {
    // Start with just a root
    let t1 = BlankTree::new();
    recode(&t1, r#"["root",[["root"],[]]]"#)?;
    assert_eq!(format_ids(t1.all_roots()), "[root]");
    assert_eq!(format_ids(t1.all_leaves()), "[root]");

    let t2 = t1
        .adding_node(nid!("A"), None::<NodeID>, eid!("rA"))?
        .adding_node(nid!("B"), None::<NodeID>, eid!("rB"))?;
    recode(&t2, r#"["root",[["A","B","root"],[["rA","root","A"],["rB","root","B"]]]]"#)?;
    assert_eq!(format_ids(t2.all_leaves()), "[A, B]");

    // Add a second layer
    let t3 = t2
        .adding_node(nid!("C"), Some(nid!("A")), eid!("AC"))?
        .adding_node(nid!("D"), Some(nid!("A")), eid!("AD"))?
        .adding_node(nid!("E"), Some(nid!("B")), eid!("BE"))?
        .adding_node(nid!("F"), Some(nid!("B")), eid!("BF"))?;
    recode(&t3, r#"["root",[["A","B","C","D","E","F","root"],[["AC","A","C"],["AD","A","D"],["BE","B","E"],["BF","B","F"],["rA","root","A"],["rB","root","B"]]]]"#)?;
    assert_eq!(format_ids(t3.all_leaves()), "[C, D, E, F]");

    // Remove A, promoting its children
    let t4 = t3.removing_node_ungrouping(nid!("A"))?;
    recode(&t4, r#"["root",[["B","C","D","E","F","root"],[["AC","root","C"],["AD","root","D"],["BE","B","E"],["BF","B","F"],["rB","root","B"]]]]"#)?;
    assert_eq!(format_ids(t4.all_leaves()), "[C, D, E, F]");

    // Remove B, including its children
    let t5 = t4.removing_node_and_children(nid!("B"))?;
    recode(&t5, r#"["root",[["C","D","root"],[["AC","root","C"],["AD","root","D"]]]]"#)?;
    assert_eq!(format_ids(t5.all_leaves()), "[C, D]");

    // Go back to t3 and move B under D
    let t6 = t3.moving_node(nid!("B"), Some(nid!("D")))?;
    recode(&t6, r#"["root",[["A","B","C","D","E","F","root"],[["AC","A","C"],["AD","A","D"],["BE","B","E"],["BF","B","F"],["rA","root","A"],["rB","D","B"]]]]"#)?;
    assert_eq!(format_ids(t6.all_leaves()), "[C, E, F]");

    Ok(())
}

#[test]
fn test_with_data() -> Result<()> {
    let mut t = Tree::<Graph<TestElemData, TestElemData, TestElemData>>::new();
    recode(&t, r#"["root",[[["root",[0,""]]],[],[0,""]]]"#)?;

    t.with_data(&|data| {
        data.0 = 10;
        data.1 = "dog".to_string();
    });
    recode(&t, r#"["root",[[["root",[0,""]]],[],[10,"dog"]]]"#)?;
    assert_eq!(*t.data(), TestElemData(10, "dog".to_string()));

    t.with_data(&|data| {
        data.0 = 20;
        data.1 = "cat".to_string();
    });
    recode(&t, r#"["root",[[["root",[0,""]]],[],[20,"cat"]]]"#)?;

    t.add_node_with_node_and_edge_data(nid!("A"), Some(nid!("root")), eid!("rA"), TestElemData(1, "ape".to_string()), TestElemData(2, "bat".to_string()))?;
    t.add_node(nid!("B"), Some(nid!("root")), eid!("rC"))?;
    recode(&t, r#"["root",[[["A",[1,"ape"]],["B",[0,""]],["root",[0,""]]],[["rA","root","A",[2,"bat"]],["rC","root","B",[0,""]]],[20,"cat"]]]"#)?;

    t.with_node_data(nid!("A"), &|data| {
        data.0 = 30;
        data.1 = "elephant".to_string();
    })?;
    assert_eq!(t.node_data(nid!("A"))?.into_owned(), TestElemData(30, "elephant".to_string()));

    t.with_edge_data(eid!("rA"), &|data| {
        data.0 = 40;
        data.1 = "fox".to_string();
    })?;
    assert_eq!(t.edge_data(eid!("rA"))?.into_owned(), TestElemData(40, "fox".to_string()));

    recode(&t, r#"["root",[[["A",[30,"elephant"]],["B",[0,""]],["root",[0,""]]],[["rA","root","A",[40,"fox"]],["rC","root","B",[0,""]]],[20,"cat"]]]"#)?;

    Ok(())
}