petgraph 0.3.0-alpha.1

//! Graph algorithms.
//!
//! It is a goal to gradually migrate the algorithms to be based on graph traits
//! so that they are generally applicable. For now, most of these use only the
//! **Graph** type.

use std::collections::BinaryHeap;
use std::borrow::{Borrow};
use std::cmp::min;

use super::{
    Graph,
    Undirected,
    EdgeDirection,
    EdgeType,
    Outgoing,
    Incoming,
    Dfs,
};
use scored::MinScored;
use super::visit::{
    Visitable,
    VisitMap,
    IntoNeighbors,
    IntoNeighborsDirected,
    IntoNodeIdentifiers,
    IntoExternals,
    NodeIndexable,
    NodeCompactIndexable,
    IntoEdgeReferences,
    EdgeRef,
};
use super::unionfind::UnionFind;
use super::graph::{
    IndexType,
    NodeIndex,
};

pub use super::isomorphism::{
    is_isomorphic,
    is_isomorphic_matching,
};
pub use super::dijkstra::dijkstra;

/// [Generic] Return the number of connected components of the graph.
///
/// For a directed graph, this is the *weakly* connected components.
pub fn connected_components<G>(g: G) -> usize
    where G: NodeCompactIndexable + IntoEdgeReferences,
{
    let mut vertex_sets = UnionFind::new(g.node_bound());
    for edge in g.edge_references() {
        let (a, b) = (edge.source(), edge.target());

        // union the two vertices of the edge
        vertex_sets.union(G::to_index(a), G::to_index(b));
    }
    let mut labels = vertex_sets.into_labeling();
    labels.sort();
    labels.dedup();
    labels.len()
}


/// [Generic] Return `true` if the input graph contains a cycle.
///
/// Always treats the input graph as if undirected.
pub fn is_cyclic_undirected<G>(g: G) -> bool
    where G: NodeIndexable + IntoEdgeReferences
{
    let mut edge_sets = UnionFind::new(g.node_bound());
    for edge in g.edge_references() {
        let (a, b) = (edge.source(), edge.target());

        // union the two vertices of the edge
        //  -- if they were already the same, then we have a cycle
        if !edge_sets.union(G::to_index(a), G::to_index(b)) {
            return true
        }
    }
    false
}

/*
/// **Deprecated: Renamed to `is_cyclic_undirected`.**
pub fn is_cyclic<N, E, Ty, Ix>(g: &Graph<N, E, Ty, Ix>) -> bool
    where Ty: EdgeType,
          Ix: IndexType,
{
    is_cyclic_undirected(g)
}
*/

/// [Generic] Perform a topological sort of a directed graph `g`.
///
/// Visit each node in order (if it is part of a topological order).
///
/// You can pass `g` as either **&Graph** or **&mut Graph**, and it
/// will be passed on to the visitor closure.
#[inline]
fn toposort_generic<G, F>(g: G, mut visit: F)
    where G: IntoNeighborsDirected + IntoExternals + Visitable,
          F: FnMut(G, G::NodeId),
{
    let mut ordered = g.borrow().visit_map();
    let mut tovisit = Vec::new();

    // find all initial nodes
    tovisit.extend(g.externals(Incoming));

    // Take an unvisited element and find which of its neighbors are next
    while let Some(nix) = tovisit.pop() {
        if ordered.is_visited(&nix) {
            continue;
        }
        visit(g, nix.clone());
        ordered.visit(nix.clone());
        for neigh in g.neighbors_directed(nix, 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| ordered.is_visited(&b)) {
                tovisit.push(neigh);
            }
        }
    }
}

/// [Generic] Return `true` if the input directed graph contains a cycle.
///
/// Using the topological sort algorithm.
pub fn is_cyclic_directed<G>(g: G) -> bool
    where G: IntoNodeIdentifiers + IntoNeighborsDirected + IntoExternals + Visitable,
{
    let mut n_ordered = 0;
    toposort_generic(g, |_, _| n_ordered += 1);
    n_ordered != g.node_count()
}

/// [Generic] Perform a topological sort of a directed graph.
///
/// Return a vector of nodes in topological order: each node is ordered
/// before its successors.
///
/// If the returned vec contains less than all the nodes of the graph, then
/// the graph was cyclic.
pub fn toposort<G>(g: G) -> Vec<G::NodeId>
    where G: IntoNodeIdentifiers + IntoNeighborsDirected + IntoExternals + Visitable,
{
    let mut order = Vec::with_capacity(g.node_count());
    toposort_generic(g, |_, ix| order.push(ix));
    order
}

/// [Generic] Compute the *strongly connected components* using Kosaraju's algorithm.
///
/// Return a vector where each element is an scc.
///
/// For an undirected graph, the sccs are simply the connected components.
pub fn scc<G>(g: G) -> Vec<Vec<G::NodeId>>
    where G: IntoNeighborsDirected + Visitable + IntoNodeIdentifiers,
{
    let mut dfs = Dfs::empty(&g);

    // First phase, reverse dfs pass, compute finishing times.
    // http://stackoverflow.com/a/26780899/161659
    let mut finished = g.visit_map();
    let mut finish_order = Vec::new();
    for i in g.node_identifiers() {
        if dfs.discovered.is_visited(&i) {
            continue
        }

        dfs.stack.push(i);
        while let Some(&nx) = dfs.stack.last() {
            if dfs.discovered.visit(nx) {
                // First time visiting `nx`: Push neighbors, don't pop `nx`
                for succ in g.neighbors_directed(nx, EdgeDirection::Incoming) {
                    if !dfs.discovered.is_visited(&succ) {
                        dfs.stack.push(succ);
                    }
                }
            } else {
                dfs.stack.pop();
                if finished.visit(nx) {
                    // Second time: All reachable nodes must have been finished
                    finish_order.push(nx);
                }
            }
        }
    }

    g.reset_map(&mut dfs.discovered);
    let mut sccs = Vec::new();

    // Second phase
    // Process in decreasing finishing time order
    for i in finish_order.into_iter().rev() {
        if dfs.discovered.is_visited(&i) {
            continue;
        }
        // Move to the leader node.
        dfs.move_to(i);
        //let leader = nindex;
        let mut scc = Vec::new();
        while let Some(nx) = dfs.next(g) {
            scc.push(nx);
        }
        sccs.push(scc);
    }
    sccs
}

/// [Generic] Compute the *strongly connected components* using Tarjan's algorithm.
///
/// Return a vector where each element is an scc.
///
/// For an undirected graph, the sccs are simply the connected components.
pub fn tarjan_scc<G>(g: G) -> Vec<Vec<G::NodeId>>
    where G: IntoNodeIdentifiers + IntoNeighbors + NodeIndexable
{
    #[derive(Copy, Clone)]
    #[derive(Debug)]
    struct NodeData {
        index: Option<usize>,
        lowlink: usize,
        on_stack: bool,
    }

    #[derive(Debug)]
    struct Data<'a, G>
        where G: NodeIndexable, 
          G::NodeId: 'a
    {
        index: usize,
        nodes: Vec<NodeData>,
        stack: Vec<G::NodeId>,
        sccs: &'a mut Vec<Vec<G::NodeId>>,
    }

    fn scc_visit<G>(v: G::NodeId, g: G, data: &mut Data<G>) 
        where G: IntoNeighbors + NodeIndexable
    {
        macro_rules! node {
            ($node:expr) => (data.nodes[G::to_index($node)])
        }

        if node![v].index.is_some() {
            // already visited
            return;
        }

        let v_index = data.index;
        node![v].index = Some(v_index);
        node![v].lowlink = v_index;
        node![v].on_stack = true;
        data.stack.push(v);
        data.index += 1;

        for w in g.neighbors(v) {
            match node![w].index {
                None => {
                    scc_visit(w, g, data);
                    node![v].lowlink = min(node![v].lowlink, node![w].lowlink);
                }
                Some(w_index) => {
                    if node![w].on_stack {
                        // Successor w is in stack S and hence in the current SCC
                        let v_lowlink = &mut node![v].lowlink;
                        *v_lowlink = min(*v_lowlink, w_index);
                    }
                }
            }
        }

        // If v is a root node, pop the stack and generate an SCC
        if let Some(v_index) = node![v].index {
            if node![v].lowlink == v_index {
                let mut cur_scc = Vec::new();
                loop {
                    let w = data.stack.pop().unwrap();
                    node![w].on_stack = false;
                    cur_scc.push(w);
                    if G::to_index(w) == G::to_index(v) { break; }
                }
                data.sccs.push(cur_scc);
            }
        }
    }

    let mut sccs = Vec::new();
    {
        let map = (0..g.node_bound()).map(|_| {
            NodeData { index: None, lowlink: !0, on_stack: false }
        }).collect();

        let mut data = Data {
            index: 0,
            nodes: map,
            stack: Vec::new(),
            sccs: &mut sccs,
        };

        for n in g.node_identifiers() {
            scc_visit(n, g, &mut data);
        }
    }
    sccs
}

/// [Graph] Condense every strongly connected component into a single node and return the result.
///
/// If `make_acyclic` is true, self-loops and multi edges are ignored, guaranteeing that
/// the output is acyclic.
pub fn condensation<N, E, Ty, Ix>(g: Graph<N, E, Ty, Ix>, make_acyclic: bool) -> Graph<Vec<N>, E, Ty, Ix>
    where Ty: EdgeType,
          Ix: IndexType,
{
    let sccs = scc(&g);
    let mut condensed: Graph<Vec<N>, E, Ty, Ix> = Graph::with_capacity(sccs.len(), g.edge_count());

    // Build a map from old indices to new ones.
    let mut node_map = vec![NodeIndex::end(); g.node_count()];
    for comp in sccs {
        let new_nix = condensed.add_node(Vec::new());
        for nix in comp {
            node_map[nix.index()] = new_nix;
        }
    }

    // Consume nodes and edges of the old graph and insert them into the new one.
    let (nodes, edges) = g.into_nodes_edges();
    for (nix, node) in nodes.into_iter().enumerate() {
        condensed[node_map[nix]].push(node.weight);
    }
    for edge in edges {
        let source = node_map[edge.source().index()];
        let target = node_map[edge.target().index()];
        if make_acyclic {
            if source != target {
                condensed.update_edge(source, target, edge.weight);
            }
        } else {
            condensed.add_edge(source, target, edge.weight);
        }
    }
    condensed
}

/// [Graph] Compute a *minimum spanning tree* of a graph.
///
/// Treat the input graph as undirected.
///
/// Using Kruskal's algorithm with runtime **O(|E| log |E|)**. We actually
/// return a minimum spanning forest, i.e. a minimum spanning tree for each connected
/// component of the graph.
///
/// The resulting graph has all the vertices of the input graph (with identical node indices),
/// and **|V| - c** edges, where **c** is the number of connected components in `g`.
pub fn min_spanning_tree<N, E, Ty, Ix>(g: &Graph<N, E, Ty, Ix>)
    -> Graph<N, E, Undirected, Ix>
    where N: Clone,
          E: Clone + PartialOrd,
          Ty: EdgeType,
          Ix: IndexType,
{
    if g.node_count() == 0 {
        return Graph::with_capacity(0, 0)
    }

    // Create a mst skeleton by copying all nodes
    let mut mst = Graph::with_capacity(g.node_count(), g.node_count() - 1);
    for node in g.raw_nodes() {
        mst.add_node(node.weight.clone());
    }

    // Initially each vertex is its own disjoint subgraph, track the connectedness
    // of the pre-MST with a union & find datastructure.
    let mut subgraphs = UnionFind::new(g.node_count());

    let mut sort_edges = BinaryHeap::with_capacity(g.edge_count());
    for edge in g.edge_references() {
        sort_edges.push(MinScored(edge.weight().clone(), (edge.source(), edge.target())));
    }

    // Kruskal's algorithm.
    // Algorithm is this:
    //
    // 1. Create a pre-MST with all the vertices and no edges.
    // 2. Repeat:
    //
    //  a. Remove the shortest edge from the original graph.
    //  b. If the edge connects two disjoint trees in the pre-MST,
    //     add the edge.
    while let Some(MinScored(score, (a, b))) = sort_edges.pop() {
        // check if the edge would connect two disjoint parts
        if subgraphs.union(a.index(), b.index()) {
            mst.add_edge(a, b, score);
        }
    }

    debug_assert!(mst.node_count() == g.node_count());
    debug_assert!(mst.edge_count() < g.node_count());
    mst
}