rs-graph 0.6.3

// 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 builder::Builder;

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

/// 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.node_id(u), h.node_id(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, 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()
}

#[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);
    }
}