graph_edge_evolution/

lib.rs

#![feature(augmented_assignments)]
#![feature(op_assign_traits)]

use std::fmt::Debug;
use std::collections::BTreeMap;
use std::ops::AddAssign;
use std::ops::Neg;

pub trait NthEdge: Clone {
    fn edge_index(&self, num_edges: usize, offset: usize) -> Option<usize>;
}

#[derive(Debug, Clone, Copy)]
pub struct NthEdgeI(pub u32);
#[derive(Debug, Clone, Copy)]
pub struct NthEdgeF(pub f32);

impl NthEdge for NthEdgeI {
    fn edge_index(&self, num_edges: usize, offset: usize) -> Option<usize> {
        if num_edges > 0 {
            Some((self.0 as usize + offset) % num_edges)
        } else {
            None
        }
    }
}

impl NthEdge for NthEdgeF {
    fn edge_index(&self, num_edges: usize, offset: usize) -> Option<usize> {
        debug_assert!(self.0 >= 0.0 && self.0 < 1.0);
        if num_edges > 0 {
            let edge = (self.0 * num_edges as f32) as usize;
            debug_assert!(edge < num_edges);
            Some((edge + offset) % num_edges)
        } else {
            None
        }
    }
}

#[test]
fn test_nthedge() {
    let n = NthEdgeI(3);
    assert_eq!(Some(3), n.edge_index(4, 0));
    assert_eq!(Some(0), n.edge_index(3, 0));
    assert_eq!(None, n.edge_index(0, 0));

    assert_eq!(Some(0), NthEdgeF(0.0).edge_index(10, 0));
    assert_eq!(Some(0), NthEdgeF(0.09).edge_index(10, 0));
    assert_eq!(Some(1), NthEdgeF(0.1).edge_index(10, 0));
    assert_eq!(Some(2), NthEdgeF(0.2).edge_index(10, 0));
    assert_eq!(Some(3), NthEdgeF(0.3).edge_index(10, 0));
    assert_eq!(Some(9), NthEdgeF(0.9).edge_index(10, 0));
    assert_eq!(Some(9), NthEdgeF(0.999).edge_index(10, 0));
    assert_eq!(Some(9), NthEdgeF(0.999).edge_index(10, 10));
}

#[derive(Debug, Clone)]
pub enum EdgeOperation<W: Clone, N: Clone, NT: Clone> {
    IncreaseWeight {
        weight: W,
    },
    DecreaseWeight {
        weight: W,
    },
    Duplicate {
        weight: W,
    },
    Split {
        weight: W,
    },
    Loop {
        weight: W,
    },
    Output {
        weight: W,
    },
    Merge {
        n: NT,
    },
    Next {
        n: NT,
    },
    Parent {
        n: NT,
    },
    SetNodeFunction {
        function: N,
    },
    Reverse,

    // Saves the state
    Save,

    // Restores a previously saved state
    Restore,
}

#[derive(Debug, Clone)]
struct Edge<W: Debug + Clone> {
    src: usize,
    dst: usize,
    weight: W,
}

impl<W: Debug + Clone + Default> Edge<W> {
    fn new(src: usize, dst: usize, weight: W) -> Edge<W> {
        Edge {
            src: src,
            dst: dst,
            weight: weight,
        }
    }
}

#[derive(Debug, Clone)]
struct Node<N: Clone + Default + Debug> {
    in_edges: Vec<usize>,
    out_edges: Vec<usize>,
    node_fn: N,
}

impl<N: Default + Clone + Debug> Node<N> {
    fn new() -> Node<N> {
        Node {
            in_edges: Vec::new(),
            out_edges: Vec::new(),
            node_fn: N::default(),
        }
    }

    fn is_empty(&self) -> bool {
        self.in_edges.is_empty() && self.out_edges.is_empty()
    }
}

#[derive(Debug, Clone)]
struct State {
    from_node: usize,
    to_node: usize,
    link_in_to_node: usize,
}

#[derive(Debug)]
pub struct GraphBuilder<W: Debug + Default + Clone, N: Debug + Default + Clone> {
    edges: BTreeMap<usize, Edge<W>>,
    nodes: Vec<Node<N>>,
    next_edge_id: usize,
    current_state: State,
    states: Vec<State>,
}

impl<W: Debug + Default + Clone + AddAssign<W>, N: Debug + Default + Clone> GraphBuilder<W, N> {
    pub fn new() -> GraphBuilder<W, N> {
        // we begin with an empty node and a virtual edge.

        GraphBuilder {
            edges: BTreeMap::new(),
            nodes: vec![Node::new()],
            next_edge_id: 0,

            // link_in_to_node: 0 points to a non-existing "virtual" edge
            current_state: State {
                from_node: 0,
                to_node: 0,
                link_in_to_node: 0,
            },
            states: Vec::new(),
        }
    }

    /// Saves the current state to the internal state stack.
    pub fn save(&mut self) {
        let state = self.get_state();
        self.states.push(state);
    }

    /// Restore a previously saved state. Returns false, if
    /// no saved state exists on the stack.
    pub fn restore(&mut self) -> bool {
        if let Some(state) = self.states.pop() {
            self.set_state(state);
            true
        } else {
            false
        }
    }

    fn get_state(&self) -> State {
        self.current_state.clone()
    }

    fn set_state(&mut self, state: State) {
        self.current_state = state;
    }

    pub fn count_nodes(&self) -> usize {
        let mut count = 0;
        self.visit_nodes(|_, _| count += 1);
        count
    }

    // iterate over all non-empty nodes.
    #[inline]
    pub fn visit_nodes<F: FnMut(usize, &N)>(&self, mut callback: F) {
        for (i, node) in self.nodes.iter().enumerate() {
            if !node.is_empty() {
                callback(i, &node.node_fn);
            }
        }
    }

    #[inline]
    pub fn visit_edges<F: FnMut((usize, usize), &W)>(&self, mut callback: F) {
        for (i, node) in self.nodes.iter().enumerate() {
            if !node.is_empty() {
                for out_edge in node.out_edges.iter() {
                    let edge = &self.edges[out_edge];
                    debug_assert!(edge.src == i);
                    callback((edge.src, edge.dst), &edge.weight);
                }
            }
        }
    }

    pub fn to_edge_list(&self) -> Vec<Option<(N, Vec<(usize, W)>)>> {
        self.nodes
            .iter()
            .map(|n| {
                if n.is_empty() {
                    None
                } else {
                    Some((n.node_fn.clone(),
                          n.out_edges
                           .iter()
                           .map(|oe| {
                               let edge = &self.edges[oe];
                               (edge.dst, edge.weight.clone())
                           })
                           .collect()))
                }
            })
            .collect()
    }

    pub fn apply_operation<NT: NthEdge>(&mut self, op: EdgeOperation<W, N, NT>)
        where W: Neg<Output = W>
    {
        match op {
            EdgeOperation::IncreaseWeight  {weight: w} => self.update_edge_weight(w),
            EdgeOperation::DecreaseWeight  {weight: w} => self.update_edge_weight(-w),
            EdgeOperation::Duplicate       {weight: w} => self.duplicate(w),
            EdgeOperation::Split           {weight: w} => self.split(w),
            EdgeOperation::Loop            {weight: w} => self.add_self_loop(w),
            EdgeOperation::Output          {weight: w} => self.output(w),
            EdgeOperation::Merge           {n} => self.merge(n),
            EdgeOperation::Next            {n} => self.next(n),
            EdgeOperation::Parent          {n} => self.parent(n),
            EdgeOperation::SetNodeFunction {function: f} => self.set_node_function(f),
            EdgeOperation::Reverse => self.reverse(),
            EdgeOperation::Save => self.save(),
            EdgeOperation::Restore => {
                let _ = self.restore();
            }
        }
    }

    /// creates an output node and connects it to the from neuron.
    /// does not change the link
    fn output(&mut self, weight: W) {
        let from = self.current_state.from_node;
        let output_node = self.new_node();
        let edge_idx = self.create_new_edge_with_weight(from, output_node, weight);
        self.insert_edge(edge_idx);
    }

    /// changes the node function of the current to-node.
    fn set_node_function(&mut self, node_fn: N) {
        self.nodes[self.current_state.to_node].node_fn = node_fn;
    }

    fn get_current_edge(&self) -> Option<usize> {
        let to_node = &self.nodes[self.current_state.to_node];
        if let Some(&edge_idx) = to_node.in_edges.get(self.current_state.link_in_to_node) {
            let edge = &self.edges[&edge_idx];
            if edge.src == self.current_state.from_node && edge.dst == self.current_state.to_node {
                Some(edge_idx)
            } else {
                None
            }
        } else {
            None
        }
    }

    /// decrease-weight or increase-weight, depending on the sign of the weight.
    /// Updates the weight of the current edge, or in case of a virtual edge,
    /// creates a new edge with that weight.
    pub fn update_edge_weight(&mut self, weight: W) {
        let (from, to) = (self.current_state.from_node, self.current_state.to_node);
        let cur_edge = self.get_current_edge();

        if let Some(edge_idx) = cur_edge {
            let e = self.get_mut_edge(edge_idx);
            assert!(e.src == from);
            assert!(e.dst == to);
            e.weight += weight;
        } else {
            // Virtual edge. Create!
            let edge_idx = self.create_new_edge_with_weight(from, to, weight);
            self.current_state.link_in_to_node = self.nodes[to].in_edges.len();
            self.insert_edge(edge_idx);
        }
    }

    /// Adds a loop to the current edge's target neuron.
    pub fn add_self_loop(&mut self, weight: W) {
        let to = self.current_state.to_node;
        let edge_idx = self.create_new_edge_with_weight(to, to, weight);
        self.current_state.link_in_to_node = self.nodes[to].in_edges.len();
        self.current_state.from_node = to;
        self.insert_edge(edge_idx);
    }

    fn get_mut_edge(&mut self, edge_idx: usize) -> &mut Edge<W> {
        self.edges.get_mut(&edge_idx).unwrap()
    }

    /// Change from-node of current link to it's n-th sibling.
    /// The n-th sibling is the current+n-th incoming node into the to-node.
    pub fn next<NT: NthEdge>(&mut self, n: NT) {
        let to_node = &self.nodes[self.current_state.to_node];
        if let Some(new_n) = n.edge_index(to_node.in_edges.len(),
                                          self.current_state.link_in_to_node) {
            let sibling_edge = to_node.in_edges[new_n];
            let new_from = self.edges[&sibling_edge].src;
            self.current_state.from_node = new_from;
            self.current_state.link_in_to_node = new_n;
        }
    }

    /// Change from-node of current link to n-th input edge of current from node.
    /// If no input edge exists, the edge is left as is. TODO: Test case
    /// The n-th input node is not deleted.
    /// NOTE: Does not modify the graph itself, only changes the current link.
    pub fn parent<NT: NthEdge>(&mut self, n: NT) {
        let from = self.current_state.from_node;
        let edge_idx = n.edge_index(self.nodes[from].in_edges.len(), 0);
        if let Some(idx) = edge_idx {
            let new_from = self.edges[&self.nodes[from].in_edges[idx]].src;
            self.current_state.from_node = new_from;
            self.current_state.link_in_to_node = idx;
        } else {
            // XXX
            // self.current_state.link_in_to_node = 0;
            return;
        }
    }

    /// Copy all incoming edges of from-node into to-node, then replace from-node with to-node.
    /// The current link is removed.
    /// Do not create a self-loop for links between A and B.
    fn merge<NT: NthEdge>(&mut self, n: NT) {
        // 1. delete current edge.
        // 2. modify all outgoing edges of A. replace the .src to B.
        // 3. copy all incoming edges of A to B.
        // 4. set the n-th incoming edge into A as new current edge.

        let (from, to) = (self.current_state.from_node, self.current_state.to_node);

        // 1. delete current edge (if exists)
        if let Some(edge_idx) = self.get_current_edge() {
            let edge = self.edges.remove(&edge_idx).unwrap();
            debug_assert!(edge.src == from);
            debug_assert!(edge.dst == to);
            self.nodes[from].out_edges.retain(|&i| i != edge_idx);
            self.nodes[to].in_edges.retain(|&i| i != edge_idx);
        }

        if from == to {
            return;
        }

        // 2. modify all outgoing edges of A.
        let mut new_out_edges = Vec::new();
        for &out_edge in self.nodes[from].out_edges.iter() {
            let edge = self.edges.get_mut(&out_edge).unwrap();
            debug_assert!(edge.src == from);
            edge.src = to;
            new_out_edges.push(out_edge);
        }
        self.nodes[to].out_edges.extend(new_out_edges);

        // 3. copy all incoming edges of A to B. Modify them.
        let mut new_in_edges = Vec::new();
        for &in_edge in self.nodes[from].in_edges.iter() {
            let edge = self.edges.get_mut(&in_edge).unwrap();
            debug_assert!(edge.dst == from);
            edge.dst = to;
            new_in_edges.push(in_edge);
        }
        self.nodes[to].in_edges.extend(new_in_edges);

        // remove from node (TODO: improve)
        self.nodes[from].out_edges.clear();
        self.nodes[from].in_edges.clear();

        // 4.
        let edges = &self.nodes[to].in_edges;
        if let Some(idx) = n.edge_index(edges.len(), 0) {
            // we use the n-th in edge as new current edge
            self.current_state.link_in_to_node = edges[idx];
            self.current_state.from_node = self.edges[&self.current_state.link_in_to_node].src;
            debug_assert!(self.edges[&self.current_state.link_in_to_node].dst == to);
        } else {
            self.current_state.link_in_to_node = 0;
            self.current_state.from_node = to;
        }
    }

    /// Split the current edge in two, and insert a node in the middle of it.
    /// If ```A -> B``` is the current edge, this will result into ```A -> N -> B```
    /// with ```N -> B``` being the next current edge.
    /// There is no A -> B link after this operation, that's why we delete the edge,
    /// so that backtracking cannot later make use of it.
    fn split(&mut self, weight: W) {
        let (from, to) = (self.current_state.from_node, self.current_state.to_node);

        // create intermediate node
        let middle_node = self.new_node();

        // Move current link from (A,B) to (A,C) (or create a new with weight 0.0).
        let cur_edge = self.get_current_edge();
        if let Some(edge_idx) = cur_edge {
            // new to_node is middle_node.
            self.get_mut_edge(edge_idx).dst = middle_node;

            // remove from incoming edges.
            self.nodes[to].in_edges.retain(|&i| i != edge_idx);
            // add to incoming edges of new to_node
            self.nodes[middle_node].in_edges.push(edge_idx);
        } else {
            // current edge is virtual. Create a edge with weight 0.0.
            let edge_idx = self.create_new_edge_with_weight(from, middle_node, W::default());
            self.insert_edge(edge_idx);
        }

        // Add new link from middle_node to `B` with `weight`
        let edge_idx = self.create_new_edge_with_weight(middle_node, to, weight);
        self.current_state.link_in_to_node = self.insert_edge(edge_idx);
        self.current_state.from_node = middle_node;
    }

    /// Duplicates the current edge. The new edge becomes the new current edge.
    fn duplicate(&mut self, weight: W) {
        let (from, to) = (self.current_state.from_node, self.current_state.to_node);
        let edge_idx = self.create_new_edge_with_weight(from, to, weight);
        self.current_state.link_in_to_node = self.insert_edge(edge_idx);
    }

    /// Reverse the current edge.
    fn reverse(&mut self) {
        let (from, to) = (self.current_state.from_node, self.current_state.to_node);

        // Delete current link
        let cur_edge = self.get_current_edge();
        let orig_weight = if let Some(edge_idx) = cur_edge {
            // delete edge
            let edge = self.edges.remove(&edge_idx).unwrap();
            self.nodes[from].out_edges.retain(|&i| i != edge_idx);
            self.nodes[to].in_edges.retain(|&i| i != edge_idx);
            edge.weight
        } else {
            // If current edge does not exist, just change the state.
            W::default()
        };

        // Add new reversed link
        let edge_idx = self.create_new_edge_with_weight(to, from, orig_weight);
        let new_state = State {
            link_in_to_node: self.insert_edge(edge_idx),
            to_node: from,
            from_node: to,
        };
        self.current_state = new_state;
    }

    /// Returns the incoming edge index of the target node.
    fn insert_edge(&mut self, edge_idx: usize) -> usize {
        let edge = self.edges.get(&edge_idx).unwrap().clone(); // XXX
        self.nodes[edge.src].out_edges.push(edge_idx);
        let idx = self.nodes[edge.dst].in_edges.len();
        self.nodes[edge.dst].in_edges.push(edge_idx);
        idx
    }

    /// Allocates a new Edge and returns new edge index.
    fn create_new_edge_with_weight(&mut self, from: usize, to: usize, weight: W) -> usize {
        let edge_id = self.next_edge_id;
        let edge = Edge::new(from, to, weight);
        self.next_edge_id += 1;
        self.edges.insert(edge_id, edge);
        return edge_id;
    }

    fn new_node(&mut self) -> usize {
        let node_id = self.nodes.len();
        let node = Node::new();
        self.nodes.push(node);
        return node_id;
    }
}

#[cfg(test)]
fn edge_list<W: Debug + Default + Clone + AddAssign<W>, N: Debug + Default + Clone>
    (builder: &GraphBuilder<W, N>)
     -> Vec<Vec<(usize, W)>> {
    builder.to_edge_list()
           .into_iter()
           .map(|n| {
               match n {
                   Some((_, b)) => b,
                   None => vec![],
               }
           })
           .collect()
}

#[test]
fn test_empty() {
    let builder: GraphBuilder<f32, usize> = GraphBuilder::new();
    let v: Vec<Vec<(usize, f32)>> = vec![vec![]];
    assert_eq!(v, edge_list(&builder));
}

#[test]
fn test_split() {
    let mut builder: GraphBuilder<f32, usize> = GraphBuilder::new();
    builder.update_edge_weight(0.0);

    // start with a single node, self-connected with zero weight
    assert_eq!(vec![vec![(0, 0.0)]], edge_list(&builder));

    builder.split(1.0);
    assert_eq!(vec![vec![(1, 0.0)], vec![(0, 1.0)]], edge_list(&builder));

    builder.split(2.0);
    assert_eq!(vec![vec![(1, 0.0)], vec![(2, 1.0)], vec![(0, 2.0)]],
               edge_list(&builder));

    builder.split(3.0);
    assert_eq!(vec![vec![(1, 0.0)], vec![(2, 1.0)], vec![(3, 2.0)], vec![(0, 3.0)]],
               edge_list(&builder));
}

#[test]
fn test_duplicate() {
    let mut builder: GraphBuilder<f32, usize> = GraphBuilder::new();
    builder.update_edge_weight(0.0);

    // start with a single node, self-connected with zero weight
    assert_eq!(vec![vec![(0, 0.0)]], edge_list(&builder));

    builder.duplicate(1.0);
    assert_eq!(vec![vec![(0, 0.0), (0, 1.0)]], edge_list(&builder));

    builder.split(0.25);
    assert_eq!(vec![vec![(0, 0.0), (1, 1.0)], vec![(0, 0.25)]],
               edge_list(&builder));

    builder.duplicate(2.0);
    assert_eq!(vec![vec![(0, 0.0), (1, 1.0)], vec![(0, 0.25), (0, 2.0)]],
               edge_list(&builder));
}

#[test]
fn test_reverse() {
    let mut builder: GraphBuilder<f32, usize> = GraphBuilder::new();
    builder.update_edge_weight(0.0);

    // start with a single node, self-connected with zero weight
    assert_eq!(vec![vec![(0, 0.0)]], edge_list(&builder));

    builder.split(1.0);
    assert_eq!(vec![vec![(1, 0.0)], vec![(0, 1.0)]], edge_list(&builder));

    builder.reverse();
    assert_eq!(vec![vec![(1, 0.0), (1, 1.0)], vec![]], edge_list(&builder));
}

#[test]
fn test_update_edge_weight() {
    let mut builder: GraphBuilder<f32, usize> = GraphBuilder::new();
    builder.update_edge_weight(0.0);

    // start with a single node, self-connected with zero weight
    assert_eq!(vec![vec![(0, 0.0)]], edge_list(&builder));

    builder.update_edge_weight(4.0);
    assert_eq!(vec![vec![(0, 4.0)]], edge_list(&builder));

    builder.update_edge_weight(-4.0);
    assert_eq!(vec![vec![(0, 0.0)]], edge_list(&builder));
}

#[test]
fn test_add_self_loop() {
    let mut builder: GraphBuilder<f32, usize> = GraphBuilder::new();
    builder.update_edge_weight(0.0);

    // start with a single node, self-connected with zero weight
    assert_eq!(vec![vec![(0, 0.0)]], edge_list(&builder));

    builder.add_self_loop(1.0);
    assert_eq!(vec![vec![(0, 0.0), (0, 1.0)]], edge_list(&builder));
}

#[test]
fn test_next() {
    let mut builder: GraphBuilder<f32, usize> = GraphBuilder::new();
    builder.update_edge_weight(0.0);

    // start with a single node, self-connected with zero weight
    assert_eq!(vec![vec![(0, 0.0)]], edge_list(&builder));

    builder.split(1.0);
    assert_eq!(vec![vec![(1, 0.0)], vec![(0, 1.0)]], edge_list(&builder));

    builder.split(2.0);
    assert_eq!(vec![vec![(1, 0.0)], vec![(2, 1.0)], vec![(0, 2.0)]],
               edge_list(&builder));

    builder.split(3.0);
    assert_eq!(vec![vec![(1, 0.0)], vec![(2, 1.0)], vec![(3, 2.0)], vec![(0, 3.0)]],
               edge_list(&builder));

    // does not change anything, because there is only one edge (no sibling).
    builder.next(NthEdgeI(1));
    assert_eq!(vec![vec![(1, 0.0)], vec![(2, 1.0)], vec![(3, 2.0)], vec![(0, 3.0)]],
               edge_list(&builder));

    builder.duplicate(5.0);
    assert_eq!(vec![vec![(1, 0.0)], vec![(2, 1.0)], vec![(3, 2.0)], vec![(0, 3.0), (0, 5.0)]],
               edge_list(&builder));

    builder.update_edge_weight(1.0);
    assert_eq!(vec![vec![(1, 0.0)], vec![(2, 1.0)], vec![(3, 2.0)], vec![(0, 3.0), (0, 6.0)]],
               edge_list(&builder));

    builder.next(NthEdgeI(0));
    builder.update_edge_weight(1.0);
    assert_eq!(vec![vec![(1, 0.0)], vec![(2, 1.0)], vec![(3, 2.0)], vec![(0, 3.0), (0, 7.0)]],
               edge_list(&builder));


    builder.next(NthEdgeI(1));
    builder.update_edge_weight(1.0);
    assert_eq!(vec![vec![(1, 0.0)], vec![(2, 1.0)], vec![(3, 2.0)], vec![(0, 4.0), (0, 7.0)]],
               edge_list(&builder));

    builder.next(NthEdgeI(2));
    builder.update_edge_weight(1.0);
    assert_eq!(vec![vec![(1, 0.0)], vec![(2, 1.0)], vec![(3, 2.0)], vec![(0, 5.0), (0, 7.0)]],
               edge_list(&builder));
}

#[test]
fn test_parent() {
    let mut builder: GraphBuilder<f32, usize> = GraphBuilder::new();
    builder.update_edge_weight(0.0);

    // start with a single node, self-connected with zero weight
    assert_eq!(vec![vec![(0, 0.0)]], edge_list(&builder));

    builder.parent(NthEdgeI(0));
    assert_eq!(vec![vec![(0, 0.0)]], edge_list(&builder));
    builder.parent(NthEdgeI(3));
    assert_eq!(vec![vec![(0, 0.0)]], edge_list(&builder));

    builder.split(1.0);
    assert_eq!(vec![vec![(1, 0.0)], vec![(0, 1.0)]], edge_list(&builder));

    builder.parent(NthEdgeI(0));
    assert_eq!(vec![vec![(1, 0.0)], vec![(0, 1.0)]], edge_list(&builder));

    // XXX: add more tests
}

#[test]
fn test_merge_self_loop() {
    let mut builder: GraphBuilder<f32, usize> = GraphBuilder::new();
    builder.update_edge_weight(0.0);

    // start with a single node, self-connected with zero weight
    assert_eq!(vec![vec![(0, 0.0)]], edge_list(&builder));

    builder.merge(NthEdgeI(1));
    let v: Vec<Vec<(usize, f32)>> = vec![vec![]];
    assert_eq!(v, edge_list(&builder));

    let mut nodes = vec![];
    builder.visit_nodes(|i, _| nodes.push(i));
    assert!(nodes.is_empty());
    assert_eq!(0, builder.count_nodes());

    let mut edges = vec![];
    builder.visit_edges(|(i, j), _w| edges.push((i, j)));
    let res: Vec<(usize, usize)> = vec![];
    assert_eq!(res, edges);
}

#[test]
fn test_merge_self_loop2() {
    let mut builder: GraphBuilder<f32, usize> = GraphBuilder::new();
    builder.update_edge_weight(0.0);

    // start with a single node, self-connected with zero weight
    assert_eq!(vec![vec![(0, 0.0)]], edge_list(&builder));

    builder.add_self_loop(1.0);

    assert_eq!(vec![vec![(0, 0.0), (0, 1.0)]], edge_list(&builder));

    builder.merge(NthEdgeI(1));
    assert_eq!(vec![vec![(0, 0.0)]], edge_list(&builder));
}

#[test]
fn test_graph_paper() {
    let mut builder: GraphBuilder<f32, usize> = GraphBuilder::new();

    // figure 2.a
    builder.update_edge_weight(0.25);
    assert_eq!(vec![vec![(0, 0.25)]], edge_list(&builder));

    // figure 2.b
    builder.split(0.8);
    assert_eq!(vec![vec![(1, 0.25)], vec![(0, 0.8)]], edge_list(&builder));

    // figure 2.c
    builder.duplicate(3.0);
    assert_eq!(vec![vec![(1, 0.25)], vec![(0, 0.8), (0, 3.0)]],
               edge_list(&builder));

    // figure 2.d
    builder.reverse();
    assert_eq!(vec![vec![(1, 0.25), (1, 3.0)], vec![(0, 0.8)]],
               edge_list(&builder));

    // figure 2.e
    builder.split(0.8);
    builder.duplicate(2.0);
    builder.reverse();
    assert_eq!(vec![vec![(1, 0.25), (2, 3.0)], vec![(0, 0.8), (2, 2.0)], vec![(1, 0.8)]],
               edge_list(&builder));

    // figure 2.f
    builder.add_self_loop(1.0);
    assert_eq!(vec![vec![(1, 0.25), (2, 3.0)], vec![(0, 0.8), (2, 2.0)], vec![(1, 0.8), (2, 1.0)]],
               edge_list(&builder));

    // figure 2.g1
    builder.split(0.6);
    assert_eq!(vec![vec![(1, 0.25), (2, 3.0)],
                    vec![(0, 0.8), (2, 2.0)],
                    vec![(1, 0.8), (3, 1.0)],
                    vec![(2, 0.6)]],
               edge_list(&builder));

    // figure 2.g2
    builder.duplicate(0.4);
    assert_eq!(vec![vec![(1, 0.25), (2, 3.0)],
                    vec![(0, 0.8), (2, 2.0)],
                    vec![(1, 0.8), (3, 1.0)],
                    vec![(2, 0.6), (2, 0.4)]],
               edge_list(&builder));

    // figure 2.g3
    builder.split(0.6);
    assert_eq!(vec![vec![(1, 0.25), (2, 3.0)],
                    vec![(0, 0.8), (2, 2.0)],
                    vec![(1, 0.8), (3, 1.0)],
                    vec![(2, 0.6), (4, 0.4)],
                    vec![(2, 0.6)]],
               edge_list(&builder));

    // figure 2.g4
    builder.duplicate(0.4);
    assert_eq!(vec![vec![(1, 0.25), (2, 3.0)],
                    vec![(0, 0.8), (2, 2.0)],
                    vec![(1, 0.8), (3, 1.0)],
                    vec![(2, 0.6), (4, 0.4)],
                    vec![(2, 0.6), (2, 0.4)]],
               edge_list(&builder));

    // figure 2.g5
    builder.reverse();
    assert_eq!(vec![vec![(1, 0.25), (2, 3.0)],
                    vec![(0, 0.8), (2, 2.0)],
                    vec![(1, 0.8), (3, 1.0), (4, 0.4)],
                    vec![(2, 0.6), (4, 0.4)],
                    vec![(2, 0.6)]],
               edge_list(&builder));

    assert_eq!(4, builder.get_state().to_node);
    assert_eq!(2, builder.get_state().from_node);
    assert_eq!(1, builder.get_state().link_in_to_node);

    // figure 2.g
    builder.parent(NthEdgeI(1));
    assert_eq!(vec![vec![(1, 0.25), (2, 3.0)],
                    vec![(0, 0.8), (2, 2.0)],
                    vec![(1, 0.8), (3, 1.0), (4, 0.4)],
                    vec![(2, 0.6), (4, 0.4)],
                    vec![(2, 0.6)]],
               edge_list(&builder));

    assert_eq!(4, builder.get_state().to_node);
    assert_eq!(1, builder.get_state().from_node);
    assert_eq!(1, builder.get_state().link_in_to_node);

    // figure 2.h
    builder.merge(NthEdgeI(1));
    assert_eq!(vec![vec![(4, 0.25), (2, 3.0)],
                    vec![],
                    vec![(4, 0.8), (3, 1.0), (4, 0.4)],
                    vec![(2, 0.6), (4, 0.4)],
                    vec![(2, 0.6), (0, 0.8), (2, 2.0)]],
               edge_list(&builder));

}

#[test]
fn test_save_restore() {
    let mut builder: GraphBuilder<f32, usize> = GraphBuilder::new();
    builder.update_edge_weight(0.0);

    // start with a single node, self-connected with zero weight
    assert_eq!(vec![vec![(0, 0.0)]], edge_list(&builder));

    builder.save();
    assert_eq!(vec![vec![(0, 0.0)]], edge_list(&builder));

    builder.split(0.5);
    assert_eq!(vec![vec![(1, 0.0)], vec![(0, 0.5)]], edge_list(&builder));

    assert_eq!(true, builder.restore());
    assert_eq!(vec![vec![(1, 0.0)], vec![(0, 0.5)]], edge_list(&builder));

    // there is now a virtual edge between 0 -> 0.
    builder.update_edge_weight(0.7); // this will create a real edge.

    assert_eq!(vec![vec![(1, 0.0), (0, 0.7)], vec![(0, 0.5)]],
               edge_list(&builder));

    builder.split(0.6);
    assert_eq!(vec![vec![(1, 0.0), (2, 0.7)], vec![(0, 0.5)], vec![(0, 0.6)]],
               edge_list(&builder));
}

#[test]
fn test_save_restore2() {
    let mut builder: GraphBuilder<f32, usize> = GraphBuilder::new();
    builder.update_edge_weight(0.0);

    // start with a single node, self-connected with zero weight
    assert_eq!(vec![vec![(0, 0.0)]], edge_list(&builder));

    builder.save();
    assert_eq!(vec![vec![(0, 0.0)]], edge_list(&builder));

    builder.split(0.5);
    assert_eq!(vec![vec![(1, 0.0)], vec![(0, 0.5)]], edge_list(&builder));

    assert_eq!(true, builder.restore());
    assert_eq!(vec![vec![(1, 0.0)], vec![(0, 0.5)]], edge_list(&builder));

    // there is now a virtual edge between 0 -> 0 with weight 0.0.
    builder.split(0.6);
    assert_eq!(vec![vec![(1, 0.0), (2, 0.0)], vec![(0, 0.5)], vec![(0, 0.6)]],
               edge_list(&builder));
}