use slab::Slab;
use std::borrow::Borrow;
use std::collections::{HashMap, HashSet};
use std::hash::Hash;
mod iterators;
use iterators::{LabelIter, VertexIter};

pub type VertexIndex = usize;
pub type EdgeIndex = (VertexIndex, VertexIndex);

#[derive(Default, Clone)]
struct Vertex<V: Hash + Eq + Clone> {
    pub preset: HashSet<VertexIndex>,
    pub posset: HashSet<VertexIndex>,
    pub aliases: HashSet<V>,
}

impl<V: Hash + Eq + Clone> Vertex<V> {
    pub fn new() -> Self {
        Vertex {
            preset: HashSet::new(),
            posset: HashSet::new(),
            aliases: HashSet::new(),
        }
    }

    #[inline]
    pub fn is_parallel(&self, other: &Self) -> bool {
        (self.preset.is_empty() && other.preset.is_empty()
            || !self.preset.is_disjoint(&other.preset))
            && (self.posset.is_empty() && other.posset.is_empty()
                || !self.posset.is_disjoint(&other.posset))
    }
}

pub struct Graph<V: Hash + Eq + Clone> {
    nodes: Slab<Vertex<V>>,
    trunks: HashSet<VertexIndex>,
    leaves: HashSet<VertexIndex>,
    aliases: HashMap<V, HashSet<VertexIndex>>,
}

impl<V: Eq + Hash + Clone> Graph<V> {
    #[inline]
    pub fn new() -> Self {
        Graph {
            nodes: Slab::new(),
            trunks: HashSet::new(),
            leaves: HashSet::new(),
            aliases: HashMap::new(),
        }
    }

    #[inline]
    pub fn insert(&mut self, label: V) -> VertexIndex {
        let node = Vertex::new();
        let index = self.nodes.insert(node);
        self.trunks.insert(index);
        self.leaves.insert(index);
        self.append_label(index, label);
        index
    }

    fn remove_vertex_node(&mut self, vertex: VertexIndex) -> Vertex<V> {
        let node = self.nodes.get(vertex).unwrap();
        let posset: Vec<VertexIndex> = node.posset.iter().cloned().collect();
        let preset: Vec<VertexIndex> = node.posset.iter().cloned().collect();

        for dst in posset {
            self.disconnect((vertex, dst));
        }

        for src in preset {
            self.disconnect((src, vertex));
        }

        self.trunks.remove(&vertex);
        self.leaves.remove(&vertex);

        let node = self.nodes.remove(vertex);
        for id in node.aliases.iter() {
            let set = self.aliases.get_mut(id).unwrap();
            set.remove(&vertex);
            if set.is_empty() {
                self.aliases.remove(id);
            }
        }

        node
    }

    #[inline]
    pub fn remove(&mut self, vertex: VertexIndex) -> bool {
        if self.nodes.contains(vertex) {
            self.remove_vertex_node(vertex);
            true
        } else {
            false
        }
    }

    #[inline]
    pub fn posset<'a>(&'a self, vertex: VertexIndex) -> Option<VertexIter<'a>> {
        self.nodes
            .get(vertex)
            .map(|node| VertexIter::new(node.posset.iter()))
    }

    #[inline]
    pub fn preset<'a>(&'a self, vertex: VertexIndex) -> Option<VertexIter<'a>> {
        self.nodes
            .get(vertex)
            .map(|node| VertexIter::new(node.preset.iter()))
    }

    #[inline]
    pub fn indegree(&self, vertex: VertexIndex) -> Option<usize> {
        self.nodes.get(vertex).map(|node| node.preset.len())
    }

    #[inline]
    pub fn outdegree(&self, vertex: VertexIndex) -> Option<usize> {
        self.nodes.get(vertex).map(|node| node.posset.len())
    }

    #[inline]
    pub fn get<'a, 'b, W>(&'a self, label: &'b W) -> Option<VertexIter<'a>>
    where
        V: Borrow<W>,
        W: Eq + Hash + ?Sized,
    {
        self.aliases
            .get(label)
            .map(|set| VertexIter::new(set.iter()))
    }

    #[inline]
    pub fn labels<'a>(&'a self, vertex: VertexIndex) -> Option<LabelIter<'a, V>> {
        self.nodes
            .get(vertex)
            .map(|node| LabelIter::new(node.aliases.iter()))
    }

    #[inline]
    pub fn count_labeled<W: Borrow<V>>(&self, label: &W) -> Option<usize> {
        self.aliases.get(label.borrow()).map(|set| set.len())
    }

    #[inline]
    pub fn append_label(&mut self, vertex: VertexIndex, label: V) -> bool {
        let set = self.aliases.entry(label.clone()).or_default();

        match self.nodes.get_mut(vertex) {
            None => false,
            Some(node) => {
                node.aliases.insert(label.clone());
                set.insert(vertex);
                true
            }
        }
    }

    pub fn remove_vertex_label(&mut self, label: &V, vertex: VertexIndex) -> bool {
        let node = match self.nodes.get_mut(vertex) {
            None => return false,
            Some(node) => node,
        };
        node.aliases.remove(label);

        let set = match self.aliases.get_mut(label) {
            None => return false,
            Some(set) => set,
        };
        set.remove(&vertex);
        if set.len() == 0 {
            self.aliases.remove(label);
        }

        true
    }

    #[inline]
    pub fn connect(&mut self, src: VertexIndex, dst: VertexIndex) -> Option<EdgeIndex> {
        if !(self.nodes.contains(src) && self.nodes.contains(dst)) {
            return None;
        }

        self.nodes.get_mut(src).unwrap().posset.insert(dst);
        self.nodes.get_mut(dst).unwrap().preset.insert(src);
        self.trunks.remove(&dst);
        self.leaves.remove(&src);

        Some((src, dst))
    }

    pub fn disconnect(&mut self, edge: EdgeIndex) -> bool {
        let (src, dst) = edge;
        if !(self.nodes.contains(src) && self.nodes.contains(dst)) {
            return false;
        }

        let src_node = self.nodes.get_mut(src).unwrap();
        if !src_node.posset.remove(&dst) {
            return false;
        }
        if src_node.posset.is_empty() {
            self.leaves.insert(src);
        }

        let dst_node = self.nodes.get_mut(dst).unwrap();
        if !dst_node.preset.remove(&src) {
            return false;
        }
        if dst_node.preset.is_empty() {
            self.trunks.insert(dst);
        }

        true
    }

    #[inline]
    pub fn trunks<'a>(&'a self) -> VertexIter<'a> {
        VertexIter::new(self.trunks.iter())
    }

    #[inline]
    pub fn leaves<'a>(&'a self) -> VertexIter<'a> {
        VertexIter::new(self.leaves.iter())
    }

    pub fn merge_vertices<'a, I>(&mut self, vertices: I) -> VertexIndex
    where
        I: IntoIterator<Item = VertexIndex>,
    {
        let mut posset = HashSet::new();
        let mut preset = HashSet::new();
        let mut aliases = HashSet::new();
        let mut reflexive = false;

        for vertex in vertices {
            let node = self.nodes.remove(vertex);

            for id in node.posset {
                if id != vertex {
                    posset.insert(id);
                    let other = self.nodes.get_mut(id).unwrap();
                    other.preset.remove(&vertex);
                } else {
                    reflexive = true;
                }
            }
            for id in node.preset {
                if id != vertex {
                    preset.insert(id);
                    let other = self.nodes.get_mut(id).unwrap();
                    other.posset.remove(&vertex);
                } else {
                    reflexive = true;
                }
            }
            for alias in node.aliases {
                let set = self.aliases.get_mut(&alias).unwrap();
                set.remove(&vertex);
                aliases.insert(alias);
            }
        }

        let id = self.nodes.insert(Vertex::new());

        if reflexive {
            posset.insert(id);
            preset.insert(id);
        }

        if !posset.is_empty() {
            self.leaves.remove(&id);
            for &dst in posset.iter() {
                self.trunks.remove(&dst);
                self.nodes.get_mut(dst).unwrap().preset.insert(id);
            }
        };

        if !preset.is_empty() {
            self.trunks.remove(&id);
            for &src in preset.iter() {
                self.leaves.remove(&src);
                self.nodes.get_mut(src).unwrap().posset.insert(id);
            }
        };

        for label in aliases.iter() {
            self.aliases.entry(label.clone()).or_default().insert(id);
        }

        let node = self.nodes.get_mut(id).unwrap();
        node.posset = posset;
        node.preset = preset;
        node.aliases = aliases;

        id
    }

    #[inline]
    pub fn are_vertices_parallel(&self, one: VertexIndex, other: VertexIndex) -> Option<bool> {
        let one = self.nodes.get(one)?;
        let other = self.nodes.get(other)?;

        Some(one.is_parallel(other))
    }
}

#[cfg(test)]
mod tests {
    use crate::*;

    #[test]
    fn parallel_vertices() {
        let mut graph = Graph::new();
        let a = graph.insert("a");
        let b = graph.insert("b");
        let c = graph.insert("c");
        let d = graph.insert("d");
        let e = graph.insert("e");
        let f = graph.insert("f");
        let g = graph.insert("g");
        let h = graph.insert("h");
        let i = graph.insert("i");
        graph.connect(a, c);
        graph.connect(b, c);
        graph.connect(b, d);
        graph.connect(c, e);
        graph.connect(c, h);
        graph.connect(c, f);
        graph.connect(d, f);
        graph.connect(h, g);
        graph.connect(g, c);
        graph.connect(d, i);
        assert_eq!(graph.are_vertices_parallel(b, a), Some(true));
        assert_eq!(graph.are_vertices_parallel(a, b), Some(true));
        assert_eq!(graph.are_vertices_parallel(e, f), Some(true));
        assert_eq!(graph.are_vertices_parallel(f, e), Some(true));
        assert_eq!(graph.are_vertices_parallel(c, d), Some(true));
        assert_eq!(graph.are_vertices_parallel(d, c), Some(true));

        assert_eq!(graph.are_vertices_parallel(h, g), Some(false));
        assert_eq!(graph.are_vertices_parallel(g, h), Some(false));
        assert_eq!(graph.are_vertices_parallel(d, f), Some(false));
        assert_eq!(graph.are_vertices_parallel(f, d), Some(false));
        assert_eq!(graph.are_vertices_parallel(b, d), Some(false));
        assert_eq!(graph.are_vertices_parallel(d, b), Some(false));
        assert_eq!(graph.are_vertices_parallel(b, f), Some(false));
        assert_eq!(graph.are_vertices_parallel(f, b), Some(false));
        assert_eq!(graph.are_vertices_parallel(h, f), Some(false));
        assert_eq!(graph.are_vertices_parallel(f, h), Some(false));
        assert_eq!(graph.are_vertices_parallel(e, h), Some(false));
        assert_eq!(graph.are_vertices_parallel(h, f), Some(false));
        assert_eq!(graph.are_vertices_parallel(d, e), Some(false));
        assert_eq!(graph.are_vertices_parallel(e, d), Some(false));
        assert_eq!(graph.are_vertices_parallel(g, a), Some(false));
        assert_eq!(graph.are_vertices_parallel(a, g), Some(false));
        assert_eq!(graph.are_vertices_parallel(i, h), Some(false));
        assert_eq!(graph.are_vertices_parallel(h, i), Some(false));
    }

    #[test]
    fn merge_vertices() {
        let mut graph = Graph::new();
        let a = graph.insert("a");
        let b = graph.insert("b");
        let c = graph.insert("c");
        let d = graph.insert("d");
        let e = graph.insert("e");
        let f = graph.insert("f");
        let g = graph.insert("g");
        let h = graph.insert("h");
        graph.connect(a, c);
        graph.connect(b, c);
        graph.connect(b, d);
        graph.connect(c, e);
        graph.connect(c, h);
        graph.connect(c, f);
        graph.connect(d, f);
        graph.connect(h, g);
        graph.connect(g, c);

        let a_pos: HashSet<VertexIndex> = graph.posset(a).unwrap().collect();
        let a_pre: HashSet<VertexIndex> = graph.preset(a).unwrap().collect();
        let labeled_a: HashSet<VertexIndex> = graph.get("a").unwrap().collect();
        assert_eq!(a_pre, vec![].into_iter().collect());
        assert_eq!(a_pos, vec![c].into_iter().collect());
        assert_eq!(labeled_a, vec![a].into_iter().collect());

        let b_pos: HashSet<VertexIndex> = graph.posset(b).unwrap().collect();
        let b_pre: HashSet<VertexIndex> = graph.preset(b).unwrap().collect();
        let labeled_b: HashSet<VertexIndex> = graph.get("b").unwrap().collect();
        assert_eq!(b_pre, vec![].into_iter().collect());
        assert_eq!(b_pos, vec![c, d].into_iter().collect());
        assert_eq!(labeled_b, vec![b].into_iter().collect());

        let c_pos: HashSet<VertexIndex> = graph.posset(c).unwrap().collect();
        let c_pre: HashSet<VertexIndex> = graph.preset(c).unwrap().collect();
        let labeled_c: HashSet<VertexIndex> = graph.get("c").unwrap().collect();
        assert_eq!(c_pre, vec![g, a, b].into_iter().collect());
        assert_eq!(c_pos, vec![e, f, h].into_iter().collect());
        assert_eq!(labeled_c, vec![c].into_iter().collect());

        let d_pos: HashSet<VertexIndex> = graph.posset(d).unwrap().collect();
        let d_pre: HashSet<VertexIndex> = graph.preset(d).unwrap().collect();
        let labeled_d: HashSet<VertexIndex> = graph.get("d").unwrap().collect();
        assert_eq!(d_pre, vec![b].into_iter().collect());
        assert_eq!(d_pos, vec![f].into_iter().collect());
        assert_eq!(labeled_d, vec![d].into_iter().collect());

        let e_pos: HashSet<VertexIndex> = graph.posset(e).unwrap().collect();
        let e_pre: HashSet<VertexIndex> = graph.preset(e).unwrap().collect();
        let labeled_e: HashSet<VertexIndex> = graph.get("e").unwrap().collect();
        assert_eq!(e_pos, vec![].into_iter().collect());
        assert_eq!(e_pre, vec![c].into_iter().collect());
        assert_eq!(labeled_e, vec![e].into_iter().collect());

        let f_pos: HashSet<VertexIndex> = graph.posset(f).unwrap().collect();
        let f_pre: HashSet<VertexIndex> = graph.preset(f).unwrap().collect();
        let labeled_f: HashSet<VertexIndex> = graph.get("f").unwrap().collect();
        assert_eq!(f_pos, vec![].into_iter().collect());
        assert_eq!(f_pre, vec![c, d].into_iter().collect());
        assert_eq!(labeled_f, vec![f].into_iter().collect());

        let h_pos: HashSet<VertexIndex> = graph.posset(h).unwrap().collect();
        let h_pre: HashSet<VertexIndex> = graph.preset(h).unwrap().collect();
        let labeled_h: HashSet<VertexIndex> = graph.get("h").unwrap().collect();
        assert_eq!(h_pos, vec![g].into_iter().collect());
        assert_eq!(h_pre, vec![c].into_iter().collect());
        assert_eq!(labeled_h, vec![h].into_iter().collect());

        let g_pos: HashSet<VertexIndex> = graph.posset(g).unwrap().collect();
        let g_pre: HashSet<VertexIndex> = graph.preset(g).unwrap().collect();
        let labeled_g: HashSet<VertexIndex> = graph.get("g").unwrap().collect();
        assert_eq!(g_pos, vec![c].into_iter().collect());
        assert_eq!(g_pre, vec![h].into_iter().collect());
        assert_eq!(labeled_g, vec![g].into_iter().collect());

        let ab = graph.merge_vertices(vec![a, b]);

        let ab_pos: HashSet<VertexIndex> = graph.posset(ab).unwrap().collect();
        let ab_pre: HashSet<VertexIndex> = graph.preset(ab).unwrap().collect();
        let labeled_a: HashSet<VertexIndex> = graph.get("a").unwrap().collect();
        let labeled_b: HashSet<VertexIndex> = graph.get("b").unwrap().collect();
        assert_eq!(ab_pre, vec![].into_iter().collect());
        assert_eq!(ab_pos, vec![c, d].into_iter().collect());
        assert_eq!(labeled_a, vec![ab].into_iter().collect());
        assert_eq!(labeled_b, vec![ab].into_iter().collect());

        let c_pos: HashSet<VertexIndex> = graph.posset(c).unwrap().collect();
        let c_pre: HashSet<VertexIndex> = graph.preset(c).unwrap().collect();
        let labeled_c: HashSet<VertexIndex> = graph.get("c").unwrap().collect();
        assert_eq!(c_pre, vec![g, ab].into_iter().collect());
        assert_eq!(c_pos, vec![e, f, h].into_iter().collect());
        assert_eq!(labeled_c, vec![c].into_iter().collect());

        let d_pos: HashSet<VertexIndex> = graph.posset(d).unwrap().collect();
        let d_pre: HashSet<VertexIndex> = graph.preset(d).unwrap().collect();
        let labeled_d: HashSet<VertexIndex> = graph.get("d").unwrap().collect();
        assert_eq!(d_pre, vec![ab].into_iter().collect());
        assert_eq!(d_pos, vec![f].into_iter().collect());
        assert_eq!(labeled_d, vec![d].into_iter().collect());

        let e_pos: HashSet<VertexIndex> = graph.posset(e).unwrap().collect();
        let e_pre: HashSet<VertexIndex> = graph.preset(e).unwrap().collect();
        let labeled_e: HashSet<VertexIndex> = graph.get("e").unwrap().collect();
        assert_eq!(e_pos, vec![].into_iter().collect());
        assert_eq!(e_pre, vec![c].into_iter().collect());
        assert_eq!(labeled_e, vec![e].into_iter().collect());

        let f_pos: HashSet<VertexIndex> = graph.posset(f).unwrap().collect();
        let f_pre: HashSet<VertexIndex> = graph.preset(f).unwrap().collect();
        let labeled_f: HashSet<VertexIndex> = graph.get("f").unwrap().collect();
        assert_eq!(f_pos, vec![].into_iter().collect());
        assert_eq!(f_pre, vec![c, d].into_iter().collect());
        assert_eq!(labeled_f, vec![f].into_iter().collect());

        let h_pos: HashSet<VertexIndex> = graph.posset(h).unwrap().collect();
        let h_pre: HashSet<VertexIndex> = graph.preset(h).unwrap().collect();
        let labeled_h: HashSet<VertexIndex> = graph.get("h").unwrap().collect();
        assert_eq!(h_pos, vec![g].into_iter().collect());
        assert_eq!(h_pre, vec![c].into_iter().collect());
        assert_eq!(labeled_h, vec![h].into_iter().collect());

        let g_pos: HashSet<VertexIndex> = graph.posset(g).unwrap().collect();
        let g_pre: HashSet<VertexIndex> = graph.preset(g).unwrap().collect();
        let labeled_g: HashSet<VertexIndex> = graph.get("g").unwrap().collect();
        assert_eq!(g_pos, vec![c].into_iter().collect());
        assert_eq!(g_pre, vec![h].into_iter().collect());
        assert_eq!(labeled_g, vec![g].into_iter().collect());

        let cd = graph.merge_vertices(vec![c, d]);

        let ab_pos: HashSet<VertexIndex> = graph.posset(ab).unwrap().collect();
        let ab_pre: HashSet<VertexIndex> = graph.preset(ab).unwrap().collect();
        let labeled_a: HashSet<VertexIndex> = graph.get("a").unwrap().collect();
        let labeled_b: HashSet<VertexIndex> = graph.get("b").unwrap().collect();
        assert_eq!(ab_pre, vec![].into_iter().collect());
        assert_eq!(ab_pos, vec![cd].into_iter().collect());
        assert_eq!(labeled_a, vec![ab].into_iter().collect());
        assert_eq!(labeled_b, vec![ab].into_iter().collect());

        let cd_pos: HashSet<VertexIndex> = graph.posset(cd).unwrap().collect();
        let cd_pre: HashSet<VertexIndex> = graph.preset(cd).unwrap().collect();
        let labeled_c: HashSet<VertexIndex> = graph.get("c").unwrap().collect();
        let labeled_d: HashSet<VertexIndex> = graph.get("d").unwrap().collect();
        assert_eq!(cd_pre, vec![g, ab].into_iter().collect());
        assert_eq!(cd_pos, vec![e, f, h].into_iter().collect());
        assert_eq!(labeled_c, vec![cd].into_iter().collect());
        assert_eq!(labeled_d, vec![cd].into_iter().collect());

        let e_pos: HashSet<VertexIndex> = graph.posset(e).unwrap().collect();
        let e_pre: HashSet<VertexIndex> = graph.preset(e).unwrap().collect();
        let labeled_e: HashSet<VertexIndex> = graph.get("e").unwrap().collect();
        assert_eq!(e_pos, vec![].into_iter().collect());
        assert_eq!(e_pre, vec![cd].into_iter().collect());
        assert_eq!(labeled_e, vec![e].into_iter().collect());

        let f_pos: HashSet<VertexIndex> = graph.posset(f).unwrap().collect();
        let f_pre: HashSet<VertexIndex> = graph.preset(f).unwrap().collect();
        let labeled_f: HashSet<VertexIndex> = graph.get("f").unwrap().collect();
        assert_eq!(f_pos, vec![].into_iter().collect());
        assert_eq!(f_pre, vec![cd].into_iter().collect());
        assert_eq!(labeled_f, vec![f].into_iter().collect());

        let h_pos: HashSet<VertexIndex> = graph.posset(h).unwrap().collect();
        let h_pre: HashSet<VertexIndex> = graph.preset(h).unwrap().collect();
        let labeled_h: HashSet<VertexIndex> = graph.get("h").unwrap().collect();
        assert_eq!(h_pos, vec![g].into_iter().collect());
        assert_eq!(h_pre, vec![cd].into_iter().collect());
        assert_eq!(labeled_h, vec![h].into_iter().collect());

        let g_pos: HashSet<VertexIndex> = graph.posset(g).unwrap().collect();
        let g_pre: HashSet<VertexIndex> = graph.preset(g).unwrap().collect();
        let labeled_g: HashSet<VertexIndex> = graph.get("g").unwrap().collect();
        assert_eq!(g_pos, vec![cd].into_iter().collect());
        assert_eq!(g_pre, vec![h].into_iter().collect());
        assert_eq!(labeled_g, vec![g].into_iter().collect());

        let ef = graph.merge_vertices(vec![e, f]);

        let ab_pos: HashSet<VertexIndex> = graph.posset(ab).unwrap().collect();
        let ab_pre: HashSet<VertexIndex> = graph.preset(ab).unwrap().collect();
        let labeled_a: HashSet<VertexIndex> = graph.get("a").unwrap().collect();
        let labeled_b: HashSet<VertexIndex> = graph.get("b").unwrap().collect();
        assert_eq!(ab_pre, vec![].into_iter().collect());
        assert_eq!(ab_pos, vec![cd].into_iter().collect());
        assert_eq!(labeled_a, vec![ab].into_iter().collect());
        assert_eq!(labeled_b, vec![ab].into_iter().collect());

        let cd_pos: HashSet<VertexIndex> = graph.posset(cd).unwrap().collect();
        let cd_pre: HashSet<VertexIndex> = graph.preset(cd).unwrap().collect();
        let labeled_c: HashSet<VertexIndex> = graph.get("c").unwrap().collect();
        let labeled_d: HashSet<VertexIndex> = graph.get("d").unwrap().collect();
        assert_eq!(cd_pre, vec![g, ab].into_iter().collect());
        assert_eq!(cd_pos, vec![ef, h].into_iter().collect());
        assert_eq!(labeled_c, vec![cd].into_iter().collect());
        assert_eq!(labeled_d, vec![cd].into_iter().collect());

        let ef_pos: HashSet<VertexIndex> = graph.posset(ef).unwrap().collect();
        let ef_pre: HashSet<VertexIndex> = graph.preset(ef).unwrap().collect();
        let labeled_e: HashSet<VertexIndex> = graph.get("e").unwrap().collect();
        let labeled_f: HashSet<VertexIndex> = graph.get("f").unwrap().collect();
        assert_eq!(ef_pos, vec![].into_iter().collect());
        assert_eq!(ef_pre, vec![cd].into_iter().collect());
        assert_eq!(labeled_e, vec![ef].into_iter().collect());
        assert_eq!(labeled_f, vec![ef].into_iter().collect());

        let h_pos: HashSet<VertexIndex> = graph.posset(h).unwrap().collect();
        let h_pre: HashSet<VertexIndex> = graph.preset(h).unwrap().collect();
        let labeled_h: HashSet<VertexIndex> = graph.get("h").unwrap().collect();
        assert_eq!(h_pos, vec![g].into_iter().collect());
        assert_eq!(h_pre, vec![cd].into_iter().collect());
        assert_eq!(labeled_h, vec![h].into_iter().collect());

        let g_pos: HashSet<VertexIndex> = graph.posset(g).unwrap().collect();
        let g_pre: HashSet<VertexIndex> = graph.preset(g).unwrap().collect();
        let labeled_g: HashSet<VertexIndex> = graph.get("g").unwrap().collect();
        assert_eq!(g_pos, vec![cd].into_iter().collect());
        assert_eq!(g_pre, vec![h].into_iter().collect());
        assert_eq!(labeled_g, vec![g].into_iter().collect());
    }

    #[test]
    fn connected_vertices() {
        let mut graph = Graph::new();
        let a = graph.insert("a");
        let b = graph.insert("b");
        let c = graph.insert("c");
        let d = graph.insert("d");
        graph.connect(a, b);
        graph.connect(b, c);
        graph.connect(b, d);
        graph.connect(d, c);

        let a_pos: HashSet<VertexIndex> = graph.posset(a).unwrap().collect();
        let b_pos: HashSet<VertexIndex> = graph.posset(b).unwrap().collect();
        let c_pos: HashSet<VertexIndex> = graph.posset(c).unwrap().collect();
        let d_pos: HashSet<VertexIndex> = graph.posset(d).unwrap().collect();
        let a_pre: HashSet<VertexIndex> = graph.preset(a).unwrap().collect();
        let b_pre: HashSet<VertexIndex> = graph.preset(b).unwrap().collect();
        let c_pre: HashSet<VertexIndex> = graph.preset(c).unwrap().collect();
        let d_pre: HashSet<VertexIndex> = graph.preset(d).unwrap().collect();

        assert_eq!(a_pos, vec![b].into_iter().collect());
        assert_eq!(b_pos, vec![c, d].into_iter().collect());
        assert_eq!(c_pos, vec![].into_iter().collect());
        assert_eq!(d_pos, vec![c].into_iter().collect());
        assert_eq!(a_pre, vec![].into_iter().collect());
        assert_eq!(b_pre, vec![a].into_iter().collect());
        assert_eq!(c_pre, vec![b, d].into_iter().collect());
        assert_eq!(d_pre, vec![b].into_iter().collect());
    }
}