rs-graph 0.7.0

// Copyright (c) 2016, 2017 Frank Fischer <frank-fischer@shadow-soft.de>
//
// This program is free software: you can redistribute it and/or
// modify it under the terms of the GNU General Public License as
// published by the Free Software Foundation, either version 3 of the
// License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see  <http://www.gnu.org/licenses/>
//

//! General algorithms working on graphs.

use graph::{Graph, Digraph, IndexGraph, IndexDigraph};
use vec::NodeVec;
use builder::Builder;

use std::collections::HashSet;
use std::cmp::{min, max};
use std::usize;

/// Returns the complement of `g`.
///
/// # Example
///
/// ```
/// use rs_graph::{LinkedListGraph, Graph, Builder};
/// use rs_graph::algorithms::complement;
/// use rs_graph::classes::cycle;
/// use std::cmp::{min, max};
///
/// let g: LinkedListGraph = cycle(5);
/// let h: LinkedListGraph = complement(&g);
///
/// assert_eq!(h.num_nodes(), 5);
/// assert_eq!(h.num_edges(), 5);
///
/// let mut edges: Vec<_> = h.edges().map(|e| {
///     let (u, v) = h.enodes(e);
///     let (u, v) = (h.node2id(u), h.node2id(v));
///     (min(u,v), max(u,v))
/// }).collect();
/// edges.sort();
/// assert_eq!(edges, vec![(0,2), (0,3), (1,3), (1,4), (2,4)]);
/// ```
///
/// Note that this function assumes that `g` is a simple graph (no
/// loops or double edges). It will work on multi-graphs, too, but
/// only adjacencies are respected, no multiplicities.
pub fn complement<'g, 'h, G, H>(g: &'g G) -> H
    where G: IndexGraph<'g>,
          H: Graph<'h>,
{
    let mut edges = HashSet::new();
    for e in g.edges() {
        let (u, v) = g.enodes(e);
        edges.insert((min(g.node_id(u), g.node_id(v)),
                      max(g.node_id(u), g.node_id(v))));
    }

    let n = g.num_nodes();
    let mut h = H::Builder::with_capacities(n, n * (n-1) / 2 - g.num_edges());
    let nodes = h.add_nodes(n);
    for i in 0..n {
        for j in i..n {
            if i < j && !edges.contains(&(i, j)) {
                h.add_edge(nodes[i], nodes[j]);
            }
        }
    }
    h.to_graph()
}


/// Returns the inverse directed graph of `g`.
///
/// For $G=(V,A)$ the returned graph is $G=(V,A')$ with
/// $A' := \{(v,u) \colon (u,v) \in A\}$.
///
/// # Example
///
/// ```
/// use rs_graph::{LinkedListGraph, IndexGraph, Graph, Digraph, Builder};
/// use rs_graph::algorithms::inverse;
///
/// let mut g = LinkedListGraph::<usize>::new();
///
/// g.add_nodes(18);
/// for u in g.nodes() {
///     for v in g.nodes() {
///         if g.node_id(v) > 0 && g.node_id(u) % g.node_id(v) == 0 {
///           g.add_edge(u, v);
///         }
///     }
/// }
///
/// let h: LinkedListGraph = inverse(&g);
/// assert_eq!(g.num_nodes(), h.num_nodes());
/// assert_eq!(g.num_edges(), h.num_edges());
/// for e in h.edges() {
///     let (u,v) = (h.node_id(h.src(e)), h.node_id(h.snk(e)));
///     assert!(u > 0 && v % u == 0);
/// }
/// ```
pub fn inverse<'g, 'h, G, H>(g: &'g G) -> H
    where G: IndexDigraph<'g>,
          H: Digraph<'h>,
{
    let mut h = H::Builder::with_capacities(g.num_nodes(), g.num_edges());
    let nodes = h.add_nodes(g.num_nodes());
    for e in g.edges() {
        h.add_edge(nodes[g.node_id(g.snk(e))], nodes[g.node_id(g.src(e))]);
    }
    h.to_graph()
}

/// Determines if a graph is connected.
///
/// The empty graph is connected.
///
/// # Example
///
/// ```
/// use rs_graph::{LinkedListGraph, Graph, Builder, classes, algorithms};
///
/// let mut g: LinkedListGraph = classes::cycle(5);
/// assert!(algorithms::is_connected(&g));
///
/// g.add_node();
/// assert!(!algorithms::is_connected(&g));
///
/// ```
pub fn is_connected<'g, G>(g: &'g G) -> bool
    where G: IndexGraph<'g>
{
    if g.num_nodes() == 0 { return true; }

    let mut seen = nodevec![g; false];
    let mut q = vec![g.id2node(0)];

    while let Some(u) = q.pop() {
        for (_, v) in g.neighs(u) {
            if !seen[v] {
                seen[v] = true;
                q.push(v);
            }
        }
    }

    seen.into_iter().all(|&u| u)
}

/// Determines all components of a graph.
///
/// The function numbers all components and assigns each node the
/// number its containing component. The number of components is
/// returned.
///
/// The empty graph has 0 components.
///
/// # Example
///
/// ```
/// use rs_graph::{LinkedListGraph, Graph, Builder, classes, algorithms};
///
/// let mut g: LinkedListGraph = classes::cycle(5);
/// {
///     let (ncomps, comps) = algorithms::components(&g);
///     assert_eq!(ncomps, 1);
///     for u in g.nodes() { assert_eq!(comps[u], 0); }
/// }
///
/// let v = g.add_node();
/// {
///     let (ncomps, comps) = algorithms::components(&g);
///     assert_eq!(ncomps, 2);
///     for u in g.nodes() { assert_eq!(comps[u], if u == v { 1 } else { 0 }); }
/// }
/// ```
pub fn components<'g, G>(g: &'g G) -> (usize, NodeVec<'g, G, usize>)
    where G: IndexGraph<'g>
{
    if g.num_nodes() == 0 { return (0, nodevec![g; 0]); }

    let mut components = nodevec![g; usize::MAX];
    let mut q = vec![];
    let mut nodes = g.nodes();
    let mut ncomponents = 0;

    loop {
        // find next node that has not been seen, yet
        while let Some(u) = nodes.next() {
            if components[u] == usize::MAX {
                // found a node, start new component
                components[u] = ncomponents;
                q.push(u);
                ncomponents += 1;
                break;
            }
        }

        // no unseen node found -> stop
        if q.is_empty() { return (ncomponents, components); }

        // do dfs from this node
        while let Some(u) = q.pop() {
            for (_, v) in g.neighs(u) {
                if components[v] != components[u] {
                    components[v] = components[u];
                    q.push(v);
                }
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use {Graph, IndexGraph, LinkedListGraph};
    use linkedlistgraph::Edge;
    use classes::*;
    use algorithms::complement;
    use std::cmp::{min, max};

    #[test]
    fn test_complement() {
        let g: LinkedListGraph = cycle(5);
        let h: LinkedListGraph = complement(&g);
        let l: LinkedListGraph = complement(&h);

        fn to_id(g: &LinkedListGraph, e: Edge) -> (usize, usize) {
            let (u, v) = g.enodes(e);
            let (u, v) = (g.node_id(u), g.node_id(v));
            (min(u, v), max(u, v))
        }

        let mut gedges: Vec<_> = g.edges().map(|e| to_id(&g, e)).collect();
        gedges.sort();

        let mut hedges: Vec<_> = h.edges().map(|e| to_id(&h, e)).collect();
        hedges.sort();

        let mut ledges: Vec<_> = g.edges().map(|e| to_id(&l, e)).collect();
        ledges.sort();

        assert_eq!(hedges, vec![(0, 2), (0, 3), (1, 3), (1, 4), (2, 4)]);
        assert_eq!(gedges, ledges);
    }
}