petgraph 0.2.6

//! Graph visitor algorithms.
//!

use fixedbitset::FixedBitSet;
use std::collections::{
    HashSet,
    VecDeque,
};
use std::hash::Hash;

use super::{
    graphmap,
    graph,
    EdgeType,
    EdgeDirection,
    Graph,
    GraphMap,
    Incoming,
    Outgoing,
};

use graph::{
    IndexType,
};
#[cfg(feature = "stable_graph")]
use graph::stable::StableGraph;

/// Base trait for graphs that defines the node identifier.
pub trait Graphlike {
    type NodeId: Clone;
}

/// NeighborIter gives access to the neighbors iterator.
pub trait NeighborIter<'a> : Graphlike {
    type Iter: Iterator<Item=Self::NodeId>;

    /// Return an iterator that visits all neighbors of the node **n**.
    fn neighbors(&'a self, n: Self::NodeId) -> Self::Iter;
}

impl<'a, N, E: 'a, Ty, Ix> NeighborIter<'a> for Graph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType,
{
    type Iter = graph::Neighbors<'a, E, Ix>;
    fn neighbors(&'a self, n: graph::NodeIndex<Ix>) -> graph::Neighbors<'a, E, Ix>
    {
        Graph::neighbors(self, n)
    }
}

#[cfg(feature = "stable_graph")]
impl<'a, N, E: 'a, Ty, Ix> NeighborIter<'a> for StableGraph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType,
{
    type Iter = graph::stable::Neighbors<'a, E, Ix>;
    fn neighbors(&'a self, n: graph::NodeIndex<Ix>)
        -> graph::stable::Neighbors<'a, E, Ix>
    {
        StableGraph::neighbors(self, n)
    }
}

impl<'a, N: 'a, E> NeighborIter<'a> for GraphMap<N, E>
where N: Copy + Ord + Hash
{
    type Iter = graphmap::Neighbors<'a, N>;
    fn neighbors(&'a self, n: N) -> graphmap::Neighbors<'a, N>
    {
        GraphMap::neighbors(self, n)
    }
}

/// Wrapper type for walking the graph as if it is undirected
pub struct AsUndirected<G>(pub G);

/// Wrapper type for walking the graph as if all edges are reversed.
pub struct Reversed<G>(pub G);

impl<'a, 'b, N, E: 'a, Ty, Ix> NeighborIter<'a> for AsUndirected<&'b Graph<N, E, Ty, Ix>> where
    Ty: EdgeType,
    Ix: IndexType,
{
    type Iter = graph::Neighbors<'a, E, Ix>;

    fn neighbors(&'a self, n: graph::NodeIndex<Ix>) -> graph::Neighbors<'a, E, Ix>
    {
        Graph::neighbors_undirected(self.0, n)
    }
}

impl<'a, 'b, N, E: 'a, Ty, Ix> NeighborIter<'a> for Reversed<&'b Graph<N, E, Ty, Ix>> where
    Ty: EdgeType,
    Ix: IndexType,
{
    type Iter = graph::Neighbors<'a, E, Ix>;
    fn neighbors(&'a self, n: graph::NodeIndex<Ix>) -> graph::Neighbors<'a, E, Ix>
    {
        Graph::neighbors_directed(self.0, n, EdgeDirection::Incoming)
    }
}

/// NeighborsDirected gives access to neighbors of both `Incoming` and `Outgoing`
/// edges of a node.
pub trait NeighborsDirected<'a> : Graphlike {
    type NeighborsDirected: Iterator<Item=Self::NodeId>;

    /// Return an iterator that visits all neighbors of the node **n**.
    fn neighbors_directed(&'a self, n: Self::NodeId,
                          d: EdgeDirection) -> Self::NeighborsDirected;
}

impl<'a, N, E: 'a, Ty, Ix> NeighborsDirected<'a> for Graph<N, E, Ty, Ix>
    where Ty: EdgeType,
          Ix: IndexType,
{
    type NeighborsDirected = graph::Neighbors<'a, E, Ix>;
    fn neighbors_directed(&'a self, n: graph::NodeIndex<Ix>,
                          d: EdgeDirection) -> graph::Neighbors<'a, E, Ix>
    {
        Graph::neighbors_directed(self, n, d)
    }
}

#[cfg(feature = "stable_graph")]
impl<'a, N, E: 'a, Ty, Ix> NeighborsDirected<'a> for StableGraph<N, E, Ty, Ix>
    where Ty: EdgeType,
          Ix: IndexType,
{
    type NeighborsDirected = graph::stable::Neighbors<'a, E, Ix>;
    fn neighbors_directed(&'a self, n: graph::NodeIndex<Ix>, d: EdgeDirection)
        -> graph::stable::Neighbors<'a, E, Ix>
    {
        StableGraph::neighbors_directed(self, n, d)
    }
}

impl<'a, 'b,  G> NeighborsDirected<'a> for Reversed<&'b G>
    where G: NeighborsDirected<'a>,
{
    type NeighborsDirected = <G as NeighborsDirected<'a>>::NeighborsDirected;
    fn neighbors_directed(&'a self, n: G::NodeId,
                          d: EdgeDirection) -> Self::NeighborsDirected
    {
        self.0.neighbors_directed(n, d.opposite())
    }
}

/// Externals returns an iterator of all nodes that either have either no
/// incoming or no outgoing edges.
pub trait Externals<'a> : Graphlike {
    type Externals: Iterator<Item=Self::NodeId>;

    /// Return an iterator of all nodes with no edges in the given direction
    fn externals(&'a self, d: EdgeDirection) -> Self::Externals;
}

impl<'a, N: 'a, E, Ty, Ix> Externals<'a> for Graph<N, E, Ty, Ix>
    where Ty: EdgeType,
          Ix: IndexType,
{
    type Externals = graph::Externals<'a, N, Ty, Ix>;
    fn externals(&'a self, d: EdgeDirection) -> graph::Externals<'a, N, Ty, Ix> {
        Graph::externals(self, d)
    }
}

impl<'a, 'b,  G> Externals<'a> for Reversed<&'b G>
    where G: Externals<'a>,
{
    type Externals = <G as Externals<'a>>::Externals;
    fn externals(&'a self, d: EdgeDirection) -> Self::Externals {
        self.0.externals(d.opposite())
    }
}

/// A mapping for storing the visited status for NodeId `N`.
pub trait VisitMap<N> {
    /// Return **true** if the value is not already present.
    fn visit(&mut self, N) -> bool;
    fn is_visited(&self, &N) -> bool;
}

impl<Ix> VisitMap<graph::NodeIndex<Ix>> for FixedBitSet where
    Ix: IndexType,
{
    fn visit(&mut self, x: graph::NodeIndex<Ix>) -> bool {
        let present = self.contains(x.index());
        self.insert(x.index());
        !present
    }
    fn is_visited(&self, x: &graph::NodeIndex<Ix>) -> bool {
        self.contains(x.index())
    }
}

impl<Ix> VisitMap<graph::EdgeIndex<Ix>> for FixedBitSet where
    Ix: IndexType,
{
    fn visit(&mut self, x: graph::EdgeIndex<Ix>) -> bool {
        let present = self.contains(x.index());
        self.insert(x.index());
        !present
    }
    fn is_visited(&self, x: &graph::EdgeIndex<Ix>) -> bool {
        self.contains(x.index())
    }
}

impl<N: Eq + Hash> VisitMap<N> for HashSet<N> {
    fn visit(&mut self, x: N) -> bool {
        self.insert(x)
    }
    fn is_visited(&self, x: &N) -> bool {
        self.contains(x)
    }
}

/// A graph that can create a visitor map.
pub trait Visitable : Graphlike {
    type Map: VisitMap<Self::NodeId>;
    fn visit_map(&self) -> Self::Map;
}

/// A graph that can reset and resize its visitor map.
pub trait Revisitable : Visitable {
    fn reset_map(&self, &mut Self::Map);
}

impl<N, E, Ty, Ix> Graphlike for Graph<N, E, Ty, Ix> where
    Ix: IndexType,
{
    type NodeId = graph::NodeIndex<Ix>;
}

impl<N, E, Ty, Ix> Visitable for Graph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType,
{
    type Map = FixedBitSet;
    fn visit_map(&self) -> FixedBitSet { FixedBitSet::with_capacity(self.node_count()) }
}

impl<N, E, Ty, Ix> Revisitable for Graph<N, E, Ty, Ix>
    where Ty: EdgeType,
          Ix: IndexType,
{
    fn reset_map(&self, map: &mut Self::Map) {
        map.clear();
        map.grow(self.node_count());
    }
}

#[cfg(feature = "stable_graph")]
impl<N, E, Ty, Ix> Graphlike for StableGraph<N, E, Ty, Ix> where
    Ix: IndexType,
{
    type NodeId = graph::NodeIndex<Ix>;
}

#[cfg(feature = "stable_graph")]
impl<N, E, Ty, Ix> Visitable for StableGraph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType,
{
    type Map = FixedBitSet;
    fn visit_map(&self) -> FixedBitSet { FixedBitSet::with_capacity(self.node_count()) }
}

#[cfg(feature = "stable_graph")]
impl<N, E, Ty, Ix> Revisitable for StableGraph<N, E, Ty, Ix>
    where Ty: EdgeType,
          Ix: IndexType,
{
    fn reset_map(&self, map: &mut Self::Map) {
        map.clear();
        map.grow(self.node_count());
    }
}

impl<'a, G> Revisitable for Reversed<&'a G>
    where G: Revisitable
{
    fn reset_map(&self, map: &mut Self::Map) {
        self.0.reset_map(map);
    }
}

impl<N: Clone, E> Graphlike for GraphMap<N, E>
{
    type NodeId = N;
}

impl<N, E> Visitable for GraphMap<N, E>
    where N: Copy + Ord + Hash
{
    type Map = HashSet<N>;
    fn visit_map(&self) -> HashSet<N> { HashSet::with_capacity(self.node_count()) }
}

impl<N, E> Revisitable for GraphMap<N, E>
    where N: Copy + Ord + Hash
{
    fn reset_map(&self, map: &mut Self::Map) {
        map.clear();
    }
}

impl<'a, G: Graphlike> Graphlike for AsUndirected<&'a G>
{
    type NodeId = G::NodeId;
}

impl<'a, G: Graphlike> Graphlike for Reversed<&'a G>
{
    type NodeId = G::NodeId;
}

impl<'a, G: Visitable> Visitable for AsUndirected<&'a G>
{
    type Map = G::Map;
    fn visit_map(&self) -> G::Map {
        self.0.visit_map()
    }
}

impl<'a, G: Visitable> Visitable for Reversed<&'a G>
{
    type Map = G::Map;
    fn visit_map(&self) -> G::Map {
        self.0.visit_map()
    }
}

/// Create or access the adjacency matrix of a graph
pub trait GetAdjacencyMatrix : Graphlike {
    type AdjMatrix;
    fn adjacency_matrix(&self) -> Self::AdjMatrix;
    fn is_adjacent(&self, matrix: &Self::AdjMatrix, a: Self::NodeId, b: Self::NodeId) -> bool;
}

/// The **GraphMap** keeps an adjacency matrix internally.
impl<N, E> GetAdjacencyMatrix for GraphMap<N, E>
    where N: Copy + Ord + Hash
{
    type AdjMatrix = ();
    #[inline]
    fn adjacency_matrix(&self) { }
    #[inline]
    fn is_adjacent(&self, _: &(), a: N, b: N) -> bool {
        self.contains_edge(a, b)
    }
}

/// A depth first search (DFS) of a graph.
///
/// Using a **Dfs** you can run a traversal over a graph while still retaining
/// mutable access to it, if you use it like the following example:
///
/// ```
/// use petgraph::{Graph, Dfs};
///
/// let mut graph = Graph::<_,()>::new();
/// let a = graph.add_node(0);
///
/// let mut dfs = Dfs::new(&graph, a);
/// while let Some(nx) = dfs.next(&graph) {
///     // we can access `graph` mutably here still
///     graph[nx] += 1;
/// }
///
/// assert_eq!(graph[a], 1);
/// ```
///
/// **Note:** The algorithm may not behave correctly if nodes are removed
/// during iteration. It may not necessarily visit added nodes or edges.
#[derive(Clone, Debug)]
pub struct Dfs<N, VM> {
    /// The stack of nodes to visit
    pub stack: Vec<N>,
    /// The map of discovered nodes
    pub discovered: VM,
}

impl<N, VM> Dfs<N, VM>
    where N: Clone,
          VM: VisitMap<N>,
{
    /// Create a new **Dfs**, using the graph's visitor map, and put **start**
    /// in the stack of nodes to visit.
    pub fn new<G>(graph: &G, start: N) -> Self
        where G: Visitable<NodeId=N, Map=VM>
    {
        let mut dfs = Dfs::empty(graph);
        dfs.move_to(start);
        dfs
    }

    /// Create a new **Dfs** using the graph's visitor map, and no stack.
    pub fn empty<G>(graph: &G) -> Self
        where G: Visitable<NodeId=N, Map=VM>
    {
        Dfs {
            stack: Vec::new(),
            discovered: graph.visit_map(),
        }
    }

    /// Keep the discovered map, but clear the visit stack and restart
    /// the dfs from a particular node.
    pub fn move_to(&mut self, start: N)
    {
        self.discovered.visit(start.clone());
        self.stack.clear();
        self.stack.push(start);
    }

    /// Return the next node in the dfs, or **None** if the traversal is done.
    pub fn next<'a, G>(&mut self, graph: &'a G) -> Option<N> where
        G: Graphlike<NodeId=N>,
        G: NeighborIter<'a>,
    {
        while let Some(node) = self.stack.pop() {
            for succ in graph.neighbors(node.clone()) {
                if self.discovered.visit(succ.clone()) {
                    self.stack.push(succ);
                }
            }

            return Some(node);
        }
        None
    }
}

/// An iterator for a depth first traversal of a graph.
pub struct DfsIter<'a, G: 'a + Visitable>
{
    graph: &'a G,
    dfs: Dfs<G::NodeId, G::Map>,
}

impl<'a, G: Visitable> DfsIter<'a, G>
{
    pub fn new(graph: &'a G, start: G::NodeId) -> Self
    {
        // Inline the code from Dfs::new to
        // work around rust bug #22841
        let mut dfs = Dfs::empty(graph);
        dfs.move_to(start);
        DfsIter {
            graph: graph,
            dfs: dfs,
        }
    }

    /// Keep the discovered map, but clear the visit stack and restart
    /// the DFS traversal from a particular node.
    pub fn move_to(&mut self, start: G::NodeId)
    {
        self.dfs.move_to(start)
    }
}

impl<'a, G: 'a + Visitable> Iterator for DfsIter<'a, G> where
    G: NeighborIter<'a>,
{
    type Item = G::NodeId;

    #[inline]
    fn next(&mut self) -> Option<G::NodeId>
    {
        self.dfs.next(self.graph)
    }

    fn size_hint(&self) -> (usize, Option<usize>)
    {
        // Very vauge info about size of traversal
        (self.dfs.stack.len(), None)
    }
}

impl<'a, G: Visitable> Clone for DfsIter<'a, G> where Dfs<G::NodeId, G::Map>: Clone
{
    fn clone(&self) -> Self {
        DfsIter {
            graph: self.graph,
            dfs: self.dfs.clone(),
        }
    }
}

/// A breadth first search (BFS) of a graph.
///
/// Using a **Bfs** you can run a traversal over a graph while still retaining
/// mutable access to it, if you use it like the following example:
///
/// ```
/// use petgraph::{Graph, Bfs};
///
/// let mut graph = Graph::<_,()>::new();
/// let a = graph.add_node(0);
///
/// let mut bfs = Bfs::new(&graph, a);
/// while let Some(nx) = bfs.next(&graph) {
///     // we can access `graph` mutably here still
///     graph[nx] += 1;
/// }
///
/// assert_eq!(graph[a], 1);
/// ```
///
/// **Note:** The algorithm may not behave correctly if nodes are removed
/// during iteration. It may not necessarily visit added nodes or edges.
#[derive(Clone)]
pub struct Bfs<N, VM> {
    /// The queue of nodes to visit
    pub stack: VecDeque<N>,
    /// The map of discovered nodes
    pub discovered: VM,
}

impl<N, VM> Bfs<N, VM>
    where N: Clone,
          VM: VisitMap<N>,
{
    /// Create a new **Bfs**, using the graph's visitor map, and put **start**
    /// in the stack of nodes to visit.
    pub fn new<G>(graph: &G, start: N) -> Self
        where G: Visitable<NodeId=N, Map=VM>
    {
        let mut discovered = graph.visit_map();
        discovered.visit(start.clone());
        let mut stack = VecDeque::new();
        stack.push_front(start.clone());
        Bfs {
            stack: stack,
            discovered: discovered,
        }
    }

    /// Return the next node in the dfs, or **None** if the traversal is done.
    pub fn next<'a, G>(&mut self, graph: &'a G) -> Option<N> where
        G: Graphlike<NodeId=N>,
        G: NeighborIter<'a>,
    {
        while let Some(node) = self.stack.pop_front() {
            for succ in graph.neighbors(node.clone()) {
                if self.discovered.visit(succ.clone()) {
                    self.stack.push_back(succ);
                }
            }

            return Some(node);
        }
        None
    }

}

/// An iterator for a breadth first traversal of a graph.
pub struct BfsIter<'a, G: 'a + Visitable> {
    graph: &'a G,
    bfs: Bfs<G::NodeId, G::Map>,
}

impl<'a, G: Visitable> BfsIter<'a, G> where
    G::NodeId: Clone,
{
    pub fn new(graph: &'a G, start: G::NodeId) -> Self
    {
        // Inline the code from Bfs::new to
        // work around rust bug #22841
        let mut discovered = graph.visit_map();
        discovered.visit(start.clone());
        let mut stack = VecDeque::new();
        stack.push_front(start.clone());
        let bfs = Bfs {
            stack: stack,
            discovered: discovered,
        };
        BfsIter {
            graph: graph,
            bfs: bfs,
        }
    }
}

impl<'a, G: 'a + Visitable> Iterator for BfsIter<'a, G> where
    G::NodeId: Clone,
    G: NeighborIter<'a>,
{
    type Item = G::NodeId;
    fn next(&mut self) -> Option<G::NodeId>
    {
        self.bfs.next(self.graph)
    }

    fn size_hint(&self) -> (usize, Option<usize>)
    {
        (self.bfs.stack.len(), None)
    }
}

impl<'a, G: Visitable> Clone for BfsIter<'a, G> where Bfs<G::NodeId, G::Map>: Clone
{
    fn clone(&self) -> Self {
        BfsIter {
            graph: self.graph,
            bfs: self.bfs.clone(),
        }
    }
}


/// A topological order traversal for a graph.
#[derive(Clone)]
pub struct Topo<N, VM> {
    tovisit: Vec<N>,
    ordered: VM,
}

impl<N, VM> Topo<N, VM>
    where N: Clone,
          VM: VisitMap<N>,
{
    /// Create a new `Topo`, using the graph's visitor map, and put all
    /// initial nodes in the to-visit list.
    pub fn new<'a, G>(graph: &'a G) -> Self
        where G: Externals<'a> + Visitable<NodeId=N, Map=VM>,
    {
        let mut topo = Self::empty(graph);
        topo.tovisit.extend(graph.externals(Incoming));
        topo
    }

    /* Private until it has a use */
    /// Create a new `Topo`, using the graph's visitor map with *no* starting
    /// index specified.
    fn empty<G>(graph: &G) -> Self
        where G: Visitable<NodeId=N, Map=VM>
    {
        Topo {
            ordered: graph.visit_map(),
            tovisit: Vec::new(),
        }
    }

    /// Clear visited state, and put all initial nodes into the visit list.
    pub fn reset<'a, G>(&mut self, graph: &'a G)
        where G: Externals<'a> + Revisitable<NodeId=N, Map=VM>,
    {
        graph.reset_map(&mut self.ordered);
        self.tovisit.clear();
        self.tovisit.extend(graph.externals(Incoming));
    }

    /// Return the next node in the current topological order traversal, or
    /// `None` if the traversal is at the end.
    ///
    /// *Note:* The graph may not have a complete topological order, and the only
    /// way to know is to run the whole traversal and make sure it visits every node.
    pub fn next<'a, G>(&mut self, g: &'a G) -> Option<N>
        where G: NeighborsDirected<'a> + Visitable<NodeId=N, Map=VM>,
    {
        // Take an unvisited element and find which of its neighbors are next
        while let Some(nix) = self.tovisit.pop() {
            if self.ordered.is_visited(&nix) {
                continue;
            }
            self.ordered.visit(nix.clone());
            for neigh in g.neighbors_directed(nix.clone(), Outgoing) {
                // Look at each neighbor, and those that only have incoming edges
                // from the already ordered list, they are the next to visit.
                if g.neighbors_directed(neigh.clone(), Incoming).all(|b| self.ordered.is_visited(&b)) {
                    self.tovisit.push(neigh);
                }
            }
            return Some(nix);
        }
        None
    }
}

/// A topological order traversal for a subgraph.
///
/// SubTopo starts at a node, and does a topological order traversal of
/// all nodes reachable from the starting point.
#[derive(Clone)]
pub struct SubTopo<N, VM> {
    tovisit: Vec<N>,
    notvisited: VecDeque<N>,
    ordered: VM,
}

impl<N, VM> SubTopo<N, VM>
    where N: Clone,
          VM: VisitMap<N>,
{
    /// Create a new `SubTopo`, using the graph's visitor map, and put single
    /// node in the to-visit list.
    pub fn from_node<'a, G>(graph: &'a G, node: N) -> Self
        where G: Externals<'a> + Visitable<NodeId=N, Map=VM>,
    {
        let mut topo = Self::empty(graph);
        topo.tovisit.push(node);
        topo
    }

    /* Private until it has a use */
    /// Create a new `SubTopo`, using the graph's visitor map with *no* starting
    /// index specified.
    fn empty<G>(graph: &G) -> Self
        where G: Visitable<NodeId=N, Map=VM>
    {
        SubTopo {
            ordered: graph.visit_map(),
            tovisit: Vec::new(),
            notvisited: VecDeque::new(),
        }
    }

    /// Clear visited state, and put a single node into the visit list.
    pub fn reset_with_node<'a, G>(&mut self, graph: &'a G, node: N)
        where G: Revisitable<NodeId=N, Map=VM>,
    {
        graph.reset_map(&mut self.ordered);
        self.tovisit.clear();
        self.tovisit.push(node);
    }

    /// Return the next node in the current topological order traversal, or
    /// `None` if the traversal is at the end.
    ///
    /// *Note:* The subgraph may not have a complete topological order.
    /// If there is a cycle in the subgraph, then nodes of that cycle *are* included in this traversal. 
    pub fn next<'a, G>(&mut self, g: &'a G) -> Option<N>
        where G: NeighborsDirected<'a> + Visitable<NodeId=N, Map=VM>,
    {
        // Take an unvisited element and find which of its neighbors are next
        loop {
            while let Some(nix) = self.tovisit.pop() {
                if self.ordered.is_visited(&nix) {
                    continue;
                }
                self.ordered.visit(nix.clone());
                for neigh in g.neighbors_directed(nix.clone(), Outgoing) {
                    // Look at each neighbor, and those that only have incoming edges
                    // from the already ordered list, they are the next to visit.
                    if g.neighbors_directed(neigh.clone(), Incoming).all(|b| self.ordered.is_visited(&b)) {
                        self.tovisit.push(neigh);
                    } else {
                        self.notvisited.push_back(neigh);
                    }
                }
                return Some(nix);
            }
            if let Some(nix) = self.notvisited.pop_front() {
                self.tovisit.push(nix);
            } else {
                return None;
            }
        }
    }
}