wolf-graph 0.1.0

mod common;
use common::*;

use anyhow::Result;

use wolf_graph::prelude::*;

#[test]
fn test_is_dag() {
    let graph = make_graph();
    assert!(!graph.is_dag());

    let dag = make_dag();
    assert!(dag.is_dag());

    let tree = make_tree();
    assert!(tree.is_dag());

    let mut g = BlankGraph::new();

    fn is_a_dag(g: &BlankGraph) {
        assert!(g.is_dag());
    }

    fn is_not_a_dag(g: &BlankGraph) {
        assert!(!g.is_dag());
    }

    // Empty? That's a DAG.
    is_a_dag(&g);

    // Only a single node? That's a DAG.
    g.add_node(nid!("A")).unwrap();
    is_a_dag(&g);

    // Two nodes? That's a DAG.
    g.add_node(nid!("B")).unwrap();
    is_a_dag(&g);

    // Connect them? Still a DAG.
    g.add_edge(eid!("AB"), nid!("A"), nid!("B")).unwrap();
    is_a_dag(&g);

    let undo = g.clone();

    // Add a cycle? Not a DAG.
    g.add_edge(eid!("BA"), nid!("B"), nid!("A")).unwrap();
    is_not_a_dag(&g);

    g = undo.clone();

    // Add a self-loop? Still not a DAG.
    g.add_edge(eid!("AA"), nid!("A"), nid!("A")).unwrap();
    is_not_a_dag(&g);

    g = undo.clone();

    // A three-node cycle? Not a DAG.
    g.add_node(nid!("C")).unwrap();
    g.add_edge(eid!("BC"), nid!("B"), nid!("C")).unwrap();
    g.add_edge(eid!("CA"), nid!("C"), nid!("A")).unwrap();
    is_not_a_dag(&g);
}

#[test]
fn test_creation1() -> Result<()> {
    let mut d1 = BlankDAG::new();
    d1.add_node(nid!("A"))?;
    d1.add_node(nid!("B"))?;
    d1.add_edge(eid!("AB"), nid!("A"), nid!("B"))?;
    assert_eq!(d1, d1);
    recode(&d1, r#"[["A","B"],[["AB","A","B"]]]"#)?;

    let mut d2 = DAG::<Graph<String, (), ()>>::new().setting_data("Hello".to_string());
    d2.add_node(nid!("A"))?;
    d2.add_node(nid!("B"))?;
    d2.add_edge(eid!("AB"), nid!("A"), nid!("B"))?;
    assert_eq!(d2, d2);
    recode(&d2, r#"[["A","B"],[["AB","A","B"]],"Hello"]"#)?;

    let mut d3 = DAG::<Graph<i32, (), ()>>::new().setting_data(1);
    d3.add_node(nid!("A"))?;
    d3.add_node(nid!("B"))?;
    d3.add_edge(eid!("AB"), nid!("A"), nid!("B"))?;
    assert_eq!(d3, d3);
    recode(&d3, r#"[["A","B"],[["AB","A","B"]],1]"#)?;

    let mut d4 = DAG::<Graph<String, (), i32>>::new().setting_data("Hello".to_string());
    d4.add_node(nid!("A"))?;
    d4.add_node(nid!("B"))?;
    d4.add_edge_with_data(eid!("AB"), nid!("A"), nid!("B"), 1)?;
    assert_eq!(d4, d4);
    recode(&d4, r#"[["A","B"],[["AB","A","B",1]],"Hello"]"#)?;

    let mut d5 = DAG::<Graph<i32, (), String>>::new().setting_data(1);
    d5.add_node(nid!("A"))?;
    d5.add_node(nid!("B"))?;
    d5.add_edge_with_data(eid!("AB"), nid!("A"), nid!("B"), "AB".to_string())?;
    assert_eq!(d5, d5);
    recode(&d5, r#"[["A","B"],[["AB","A","B","AB"]],1]"#)?;

    Ok(())
}

#[test]
fn test_creation2() -> Result<()> {
    let mut d1 = BlankDAG::new();
    d1.add_node(nid!("A"))?;
    d1.add_node(nid!("B"))?;
    d1.add_edge(eid!("AB"), nid!("A"), nid!("B"))?;
    assert_eq!(d1, d1);
    recode(&d1, r#"[["A","B"],[["AB","A","B"]]]"#)?;

    let mut d2 = DAG::<Graph<String, i32, ()>>::new().setting_data("Hello".to_string());
    d2.add_node_with_data(nid!("A"), 1)?;
    d2.add_node(nid!("B"))?;
    d2.add_edge(eid!("AB"), nid!("A"), nid!("B"))?;
    assert_eq!(d2, d2);
    recode(&d2, r#"[[["A",1],["B",0]],[["AB","A","B"]],"Hello"]"#)?;

    let mut d3 = DAG::<Graph<i32, (), ()>>::new().setting_data(1);
    d3.add_node(nid!("A"))?;
    d3.add_node(nid!("B"))?;
    d3.add_edge(eid!("AB"), nid!("A"), nid!("B"))?;
    assert_eq!(d3, d3);
    recode(&d3, r#"[["A","B"],[["AB","A","B"]],1]"#)?;

    let mut d4 = DAG::<Graph<String, i32, i32>>::new().setting_data("Hello".to_string());
    d4.add_node_with_data(nid!("A"), 1)?;
    d4.add_node(nid!("B"))?;
    d4.add_edge_with_data(eid!("AB"), nid!("A"), nid!("B"), 1)?;
    assert_eq!(d4, d4);
    recode(&d4, r#"[[["A",1],["B",0]],[["AB","A","B",1]],"Hello"]"#)?;

    let mut d5 = DAG::<Graph<i32, (), String>>::new().setting_data(1);
    d5.add_node(nid!("A"))?;
    d5.add_node(nid!("B"))?;
    d5.add_edge_with_data(eid!("AB"), nid!("A"), nid!("B"), "AB".to_string())?;
    assert_eq!(d5, d5);
    recode(&d5, r#"[["A","B"],[["AB","A","B","AB"]],1]"#)?;

    Ok(())
}

#[test]
fn test_creation3() -> Result<()> {
    let mut d1 = DAG::<Graph<Data, Data, Data>>::new();
    d1.add_node(nid!("A"))?;
    d1.add_node(nid!("B"))?;
    d1.add_edge(eid!("AB"), nid!("A"), nid!("B"))?;
    assert_eq!(d1, d1);
    recode(&d1, r#"[[["A",""],["B",""]],[["AB","A","B",""]],""]"#)?;

    let mut d2 = DAG::<Graph<Data, Data, Data>>::new().setting_data(Data::from([1, 2, 3, 4]));
    d2.add_node_with_data(nid!("A"), Data::from([5, 6, 7, 8]))?;
    d2.add_node_with_data(nid!("B"), Data::from([9, 10, 11, 12]))?;
    d2.add_edge_with_data(eid!("AB"), nid!("A"), nid!("B"), Data::from([13, 14, 15, 16]))?;
    assert_eq!(d2, d2);
    recode(&d2, r#"[[["A","BQYHCA=="],["B","CQoLDA=="]],[["AB","A","B","DQ4PEA=="]],"AQIDBA=="]"#)?;

    Ok(())
}

#[test]
fn test_dag_mutations() -> Result<()> {
    // Fail to create a DAG with a cycle.
    assert!(DAG::new_with_graph(BlankGraph::new()
        .adding_node(nid!("A"))?
        .adding_node(nid!("B"))?
        .adding_edge(eid!("AB"), nid!("A"), nid!("B"))?
        .adding_edge(eid!("BA"), nid!("B"), nid!("A"))?
    ).is_err());

    // Start with an empty graph
    let mut d = BlankDAG::new();
    recode(&d, r#"[[],[]]"#)?;
    assert_eq!(format_ids(d.all_roots()), "[]");
    assert_eq!(format_ids(d.all_leaves()), "[]");

    // Add a couple of nodes
    d.add_node(nid!("A"))?;
    d.add_node(nid!("B"))?;
    recode(&d, r#"[["A","B"],[]]"#)?;
    assert_eq!(format_ids(d.all_roots()), "[A, B]");
    assert_eq!(format_ids(d.all_leaves()), "[A, B]");

    // Connect them
    d.add_edge(eid!("AB"), nid!("A"), nid!("B"))?;
    recode(&d, r#"[["A","B"],[["AB","A","B"]]]"#)?;
    assert_eq!(format_ids(d.all_roots()), "[A]");
    assert_eq!(format_ids(d.all_leaves()), "[B]");

    // Extend the line
    d.add_node(nid!("C"))?;
    d.add_edge(eid!("BC"), nid!("B"), nid!("C"))?;
    recode(&d, r#"[["A","B","C"],[["AB","A","B"],["BC","B","C"]]]"#)?;
    assert_eq!(format_ids(d.all_roots()), "[A]");
    assert_eq!(format_ids(d.all_leaves()), "[C]");

    // Create a branch.
    d.add_node(nid!("D"))?;
    d.add_edge(eid!("BD"), nid!("B"), nid!("D"))?;
    recode(&d, r#"[["A","B","C","D"],[["AB","A","B"],["BC","B","C"],["BD","B","D"]]]"#)?;
    assert_eq!(format_ids(d.all_roots()), "[A]");
    assert_eq!(format_ids(d.all_leaves()), "[C, D]");

    // Add another root and connect it to D
    d.add_node(nid!("E"))?;
    d.add_edge(eid!("ED"), nid!("E"), nid!("D"))?;
    recode(&d, r#"[["A","B","C","D","E"],[["AB","A","B"],["BC","B","C"],["BD","B","D"],["ED","E","D"]]]"#)?;
    assert_eq!(format_ids(d.all_roots()), "[A, E]");
    assert_eq!(format_ids(d.all_leaves()), "[C, D]");

    // Connect C to E
    d.add_edge(eid!("CE"), nid!("C"), nid!("E"))?;
    recode(&d, r#"[["A","B","C","D","E"],[["AB","A","B"],["BC","B","C"],["BD","B","D"],["CE","C","E"],["ED","E","D"]]]"#)?;
    assert_eq!(format_ids(d.all_roots()), "[A]");
    assert_eq!(format_ids(d.all_leaves()), "[D]");

    // Fail to create a cycle by adding an edge from E to A
    assert!(d.add_edge(eid!("EA"), nid!("E"), nid!("A")).is_err());

    // Move edge CE so it now connects A to D
    d.move_edge(eid!("CE"), nid!("A"), nid!("D"))?;
    recode(&d, r#"[["A","B","C","D","E"],[["AB","A","B"],["BC","B","C"],["BD","B","D"],["CE","A","D"],["ED","E","D"]]]"#)?;
    assert_eq!(format_ids(d.all_roots()), "[A, E]");
    assert_eq!(format_ids(d.all_leaves()), "[C, D]");

    // Fail to reverse edge BC
    // SHOULDN'T THIS ACTUALLY WORK?
    assert!(d.move_edge(eid!("BC"), nid!("C"), nid!("B")).is_err());

    Ok(())
}

#[test]
fn test_dag_builders() -> Result<()> {
    // Start with an empty DAG
    let d1 = BlankDAG::new();
    recode(&d1, r#"[[],[]]"#)?;
    assert_eq!(format_ids(d1.all_roots()), "[]");
    assert_eq!(format_ids(d1.all_leaves()), "[]");

    // Add a couple of nodes
    let d2 = d1
        .adding_node(nid!("A"))?
        .adding_node(nid!("B"))?;
    recode(&d2, r#"[["A","B"],[]]"#)?;
    assert_eq!(format_ids(d2.all_roots()), "[A, B]");
    assert_eq!(format_ids(d2.all_leaves()), "[A, B]");

    // Connect them
    let d3 = d2
        .adding_edge(eid!("AB"), nid!("A"), nid!("B"))?;
    recode(&d3, r#"[["A","B"],[["AB","A","B"]]]"#)?;
    assert_eq!(format_ids(d3.all_roots()), "[A]");
    assert_eq!(format_ids(d3.all_leaves()), "[B]");

    // Extend the line
    let d4 = d3
        .adding_node(nid!("C"))?
        .adding_edge(eid!("BC"), nid!("B"), nid!("C"))?;
    recode(&d4, r#"[["A","B","C"],[["AB","A","B"],["BC","B","C"]]]"#)?;
    assert_eq!(format_ids(d4.all_roots()), "[A]");

    // Create a branch.
    let d5 = d4
        .adding_node(nid!("D"))?
        .adding_edge(eid!("BD"), nid!("B"), nid!("D"))?;
    recode(&d5, r#"[["A","B","C","D"],[["AB","A","B"],["BC","B","C"],["BD","B","D"]]]"#)?;
    assert_eq!(format_ids(d5.all_roots()), "[A]");
    assert_eq!(format_ids(d5.all_leaves()), "[C, D]");

    // Add another root and connect it to D
    let d6 = d5
        .adding_node(nid!("E"))?
        .adding_edge(eid!("ED"), nid!("E"), nid!("D"))?;
    recode(&d6, r#"[["A","B","C","D","E"],[["AB","A","B"],["BC","B","C"],["BD","B","D"],["ED","E","D"]]]"#)?;
    assert_eq!(format_ids(d6.all_roots()), "[A, E]");
    assert_eq!(format_ids(d6.all_leaves()), "[C, D]");

    // Connect C to E
    let d7 = d6
        .adding_edge(eid!("CE"), nid!("C"), nid!("E"))?;
    recode(&d7, r#"[["A","B","C","D","E"],[["AB","A","B"],["BC","B","C"],["BD","B","D"],["CE","C","E"],["ED","E","D"]]]"#)?;
    assert_eq!(format_ids(d7.all_roots()), "[A]");
    assert_eq!(format_ids(d7.all_leaves()), "[D]");

    // Fail to create a cycle by adding an edge from E to A
    assert!(d7.adding_edge(eid!("EA"), nid!("E"), nid!("A")).is_err());

    // Move edge CE so it now connects A to D
    let d8 = d7
        .moving_edge(eid!("CE"), nid!("A"), nid!("D"))?;
    recode(&d8, r#"[["A","B","C","D","E"],[["AB","A","B"],["BC","B","C"],["BD","B","D"],["CE","A","D"],["ED","E","D"]]]"#)?;
    assert_eq!(format_ids(d8.all_roots()), "[A, E]");
    assert_eq!(format_ids(d8.all_leaves()), "[C, D]");

    // Fail to reverse edge BC
    assert!(d8.moving_edge(eid!("BC"), nid!("C"), nid!("B")).is_err());

    Ok(())
}

#[test]
fn test_transitive() -> Result<()> {
    let g = BlankDAG::new_with_graph(common::make_dag())?;
    assert_eq!(format_ids(g.transitive_successors(&[nid!("F"), nid!("I")].into())?), "[C, D, E, G, K]");
    assert_eq!(format_ids(g.transitive_predecessors(&[nid!("F"), nid!("I")].into())?), "[B, H, J]");

    let r = ReversedGraph::new(g);
    assert_eq!(format_ids(r.transitive_successors(&[nid!("F"), nid!("I")].into())?), "[B, H, J]");
    assert_eq!(format_ids(r.transitive_predecessors(&[nid!("F"), nid!("I")].into())?), "[C, D, E, G, K]");

    Ok(())
}