src/graphmap.rs

//! **GraphMap\<N, E\>** is an undirected graph where node values are mapping keys.

use std::hash::{Hash};
use std::collections::HashMap;
use std::collections::hash_map::Hasher;
use std::iter::Map;
use std::collections::hash_map::{
    Keys,
};
use std::collections::hash_map::Entry::{
    Occupied,
    Vacant,
};
use std::slice::{
    Iter,
};
use std::fmt;
use std::ops::{Index, IndexMut};

/// **GraphMap\<N, E\>** is an undirected graph, with generic node values **N** and edge weights **E**.
///
/// It uses an combined adjacency list and sparse adjacency matrix representation, using **O(|V|
/// + |E|)** space, and allows testing for edge existance in constant time.
///
/// The node type **N** must implement **Copy** and will be used as node identifier, duplicated
/// into several places in the data structure.
/// It must be suitable as a hash table key (implementing **Eq + Hash**).
/// The node type must also implement **PartialOrd** so that the implementation can
/// order the pair (**a**, **b**) for an edge connecting any two nodes **a** and **b**.
///
/// **GraphMap** does not allow parallel edges, but self loops are allowed.
#[derive(Clone)]
pub struct GraphMap<N: Eq + Hash<Hasher>, E> {
    nodes: HashMap<N, Vec<N>>,
    edges: HashMap<(N, N), E>,
}

impl<N: Eq + Hash<Hasher> + fmt::Show, E: fmt::Show> fmt::Show for GraphMap<N, E>
{
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        self.nodes.fmt(f)
    }
}

#[inline]
fn edge_key<N: Copy + PartialOrd>(a: N, b: N) -> (N, N)
{
    if a <= b { (a, b) } else { (b, a) }
}

#[inline]
fn copy<N: Copy>(n: &N) -> N { *n }

/// A trait group for **GraphMap**'s node identifier.
pub trait NodeTrait : Copy + PartialOrd + Eq + Hash<Hasher> {}
impl<N> NodeTrait for N where N: Copy + PartialOrd + Eq + Hash<Hasher> {}

impl<N, E> GraphMap<N, E> where N: NodeTrait
{
    /// Create a new **GraphMap**.
    pub fn new() -> Self
    {
        GraphMap {
            nodes: HashMap::new(),
            edges: HashMap::new(),
        }
    }

    /// Create a new **GraphMap** with estimated capacity.
    pub fn with_capacity(nodes: usize, edges: usize) -> Self
    {
        GraphMap {
            nodes: HashMap::with_capacity(nodes),
            edges: HashMap::with_capacity(edges),
        }
    }

    /// Return the number of nodes in the graph.
    pub fn node_count(&self) -> usize
    {
        self.nodes.len()
    }

    /// Return the number of edges in the graph.
    pub fn edge_count(&self) -> usize
    {
        self.edges.len()
    }

    /// Add node **n** to the graph.
    pub fn add_node(&mut self, n: N) -> N {
        match self.nodes.entry(n) {
            Occupied(_) => {}
            Vacant(ent) => { ent.insert(Vec::new()); }
        }
        n
    }

    /// Return **true** if node **n** was removed.
    pub fn remove_node(&mut self, n: N) -> bool {
        let successors = match self.nodes.remove(&n) {
            None => return false,
            Some(sus) => sus,
        };
        for succ in successors.into_iter() {
            // remove all successor links
            self.remove_single_edge(&succ, &n);
            // Remove all edge values
            self.edges.remove(&edge_key(n, succ));
        }
        true
    }

    /// Return **true** if the node is contained in the graph.
    pub fn contains_node(&self, n: N) -> bool {
        self.nodes.contains_key(&n)
    }

    /// Add an edge connecting **a** and **b** to the graph.
    ///
    /// Inserts nodes **a** and/or **b** if they aren't already part of the graph.
    ///
    /// Return **true** if edge did not previously exist.
    ///
    /// ## Example
    /// ```
    /// use petgraph::GraphMap;
    ///
    /// let mut g = GraphMap::new();
    /// g.add_edge(1, 2, -1);
    /// assert_eq!(g.node_count(), 2);
    /// assert_eq!(g.edge_count(), 1);
    /// ```
    pub fn add_edge(&mut self, a: N, b: N, edge: E) -> bool
    {
        // Use PartialOrd to order the edges
        match self.nodes.entry(a) {
            Occupied(ent) => { ent.into_mut().push(b); }
            Vacant(ent) => { ent.insert(vec![b]); }
        }
        match self.nodes.entry(b) {
            Occupied(ent) => { ent.into_mut().push(a); }
            Vacant(ent) => { ent.insert(vec![a]); }
        }
        self.edges.insert(edge_key(a, b), edge).is_none()
    }

    /// Remove successor relation from a to b
    ///
    /// Return **true** if it did exist.
    fn remove_single_edge(&mut self, a: &N, b: &N) -> bool
    {
        match self.nodes.get_mut(a) {
            None => false,
            Some(sus) => {
                match sus.iter().position(|elt| elt == b) {
                    Some(index) => { sus.swap_remove(index); true }
                    None => false,
                }
            }
        }
    }

    /// Remove edge from **a** to **b** from the graph and return the edge weight.
    ///
    /// Return **None** if the edge didn't exist.
    ///
    /// ## Example
    ///
    /// ```
    /// use petgraph::GraphMap;
    ///
    /// let mut g = GraphMap::new();
    /// g.add_node(1);
    /// g.add_node(2);
    /// g.add_edge(1, 2, -1);
    ///
    /// let edge = g.remove_edge(2, 1);
    /// assert_eq!(edge, Some(-1));
    /// assert_eq!(g.edge_count(), 0);
    /// ```
    pub fn remove_edge(&mut self, a: N, b: N) -> Option<E>
    {
        let exist1 = self.remove_single_edge(&a, &b);
        let exist2 = self.remove_single_edge(&b, &a);
        let weight = self.edges.remove(&edge_key(a, b));
        debug_assert!(exist1 == exist2 && exist1 == weight.is_some());
        weight
    }

    /// Return **true** if the edge connecting **a** with **b** is contained in the graph.
    pub fn contains_edge(&self, a: N, b: N) -> bool {
        self.edges.contains_key(&edge_key(a, b))
    }

    /// Return an iterator over the nodes of the graph.
    ///
    /// Iterator element type is **N**.
    pub fn nodes<'a>(&'a self) -> Nodes<'a, N>
    {
        Nodes{iter: self.nodes.keys().map(copy as fn(&N) -> N)}
    }

    /// Return an iterator over the nodes that are connected with **from** by edges.
    ///
    /// If the node **from** does not exist in the graph, return an empty iterator.
    ///
    /// Iterator element type is **N**.
    pub fn neighbors<'a>(&'a self, from: N) -> Neighbors<'a, N>
    {
        Neighbors{iter:
            match self.nodes.get(&from) {
                Some(neigh) => neigh.iter(),
                None => [].iter(),
            }.map(copy as fn(&N) -> N)
        }
    }

    /// Return an iterator over the nodes that are connected with **from** by edges,
    /// paired with the edge weight.
    ///
    /// If the node **from** does not exist in the graph, return an empty iterator.
    ///
    /// Iterator element type is **(N, &'a E)**.
    pub fn edges<'a>(&'a self, from: N) -> Edges<'a, N, E>
    {
        Edges {
            from: from,
            iter: self.neighbors(from),
            edges: &self.edges,
        }
    }

    /// Return a reference to the edge weight connecting **a** with **b**, or
    /// **None** if the edge does not exist in the graph.
    pub fn edge_weight<'a>(&'a self, a: N, b: N) -> Option<&'a E>
    {
        self.edges.get(&edge_key(a, b))
    }

    /// Return a mutable reference to the edge weight connecting **a** with **b**, or
    /// **None** if the edge does not exist in the graph.
    pub fn edge_weight_mut<'a>(&'a mut self, a: N, b: N) -> Option<&'a mut E>
    {
        self.edges.get_mut(&edge_key(a, b))
    }
}

macro_rules! iterator_methods {
    () => (
        #[inline]
        fn next(&mut self) -> Option<<Self as Iterator>::Item>
        {
            self.iter.next()
        }

        #[inline]
        fn size_hint(&self) -> (usize, Option<usize>)
        {
            self.iter.size_hint()
        }
    )
}

pub struct Nodes<'a, N: 'a> {
    iter: Map<&'a N, N, Keys<'a, N, Vec<N>>, fn(&N) -> N>,
}

impl<'a, N> Iterator for Nodes<'a, N>
{
    type Item = N;
    iterator_methods!();
}

pub struct Neighbors<'a, N: 'a> {
    iter: Map<&'a N, N, Iter<'a, N>, fn(&N) -> N>,
}

impl<'a, N> Iterator for Neighbors<'a, N>
{
    type Item = N;
    iterator_methods!();
}

pub struct Edges<'a, N, E: 'a> where N: 'a + NodeTrait
{
    pub from: N,
    pub edges: &'a HashMap<(N, N), E>,
    pub iter: Neighbors<'a, N>,
}

impl<'a, N, E> Iterator for Edges<'a, N, E>
    where N: 'a + NodeTrait, E: 'a
{
    type Item = (N, &'a E);
    fn next(&mut self) -> Option<(N, &'a E)>
    {
        match self.iter.next() {
            None => None,
            Some(b) => {
                let a = self.from;
                match self.edges.get(&edge_key(a, b)) {
                    None => unreachable!(),
                    Some(edge) => {
                        Some((b, edge))
                    }
                }
            }
        }
    }
}

impl<N, E> Index<(N, N)> for GraphMap<N, E> where N: NodeTrait
{
    type Output = E;
    /// Index **GraphMap** by node pairs to access edge weights.
    fn index(&self, index: &(N, N)) -> &E
    {
        self.edge_weight(index.0, index.1).unwrap()
    }
}

impl<N, E> IndexMut<(N, N)> for GraphMap<N, E> where N: NodeTrait
{
    type Output = E;
    /// Index **GraphMap** by node pairs to access edge weights.
    fn index_mut(&mut self, index: &(N, N)) -> &mut E
    {
        self.edge_weight_mut(index.0, index.1).unwrap()
    }
}