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/>
//

//! Some common graph classes.

use graph::Graph;
use builder::Builder;

/// Returns a path with `m` edges.
///
/// The path is directed if G is a digraph.
pub fn path<'a, G>(m: usize) -> G
    where G: Graph<'a>
{
    let mut b = G::Builder::with_capacities(m+1, m);
    let nodes: Vec<_> = (0..m + 1).map(|_| b.add_node()).collect();
    for (u, v) in nodes.iter().zip(nodes.iter().skip(1)) {
        b.add_edge(*u, *v);
    }
    b.to_graph()
}

/// Returns a cycle with length `n`.
///
/// The cycle is directed if G is directed
pub fn cycle<'a, G>(n: usize) -> G
    where G: Graph<'a>
{
    let mut b = G::Builder::with_capacities(n, n);
    let nodes: Vec<_> = (0..n).map(|_| b.add_node()).collect();
    for (u, v) in nodes.iter().zip(nodes.iter().cycle().skip(1)) {
        b.add_edge(*u, *v);
    }
    b.to_graph()
}

/// Returns the complete graph on `n` nodes.
pub fn complete_graph<'a, G>(n: usize) -> G
    where G: Graph<'a>
{
    let mut b = G::Builder::with_capacities(n, n*(n-1) / 2);
    let nodes: Vec<_> = (0..n).map(|_| b.add_node()).collect();
    for (i,&u) in nodes.iter().enumerate() {
        for &v in &nodes[i+1 .. ]{
            b.add_edge(u, v);
        }
    }
    b.to_graph()
}

/// Returns a complete bipartite graph on `n+m` nodes.
///
/// The edges will run between the first n nodes and the last m nodes.
/// If G is a digraph, the edges will run in this direction.
pub fn complete_bipartite<'a, G>(n: usize, m: usize) -> G
    where G: Graph<'a>
{
    let mut b = G::Builder::with_capacities(n+m, n*m);
    let nodes: Vec<_> = (0..n + m).map(|_| b.add_node()).collect();
    for &u in &nodes[..n] {
        for &v in &nodes[n..] {
            b.add_edge(u, v);
        }
    }
    b.to_graph()
}

/// Returns a star graph with `n` rays.
///
/// The center node will be the first node. This is equivalent to
/// `complete_bipartite(1,n)`.
///
/// If G is a digraph, the source of all edges will be the center
/// node.
pub fn star<'a, G>(n: usize) -> G
    where G: Graph<'a>
{
    complete_bipartite::<G>(1, n)
}

#[cfg_attr(feature = "cargo-clippy", allow(needless_range_loop))]
/// Returns a hypercube of dimension `d`.
pub fn hypercube<'a, G>(d: u32) -> G
    where G: Graph<'a>
{
    let n = 2usize.pow(d);
    let mut b = G::Builder::with_capacities(n, n * d as usize);
    let nodes: Vec<_> = (0..n).map(|_| b.add_node()).collect();
    for i in 0..n {
        for bit in 0..d {
            if i & (1 << bit) == 0 {
                b.add_edge(nodes[i], nodes[i | (1 << bit)]);
            }
        }
    }
    b.to_graph()
}

#[cfg_attr(feature = "cargo-clippy", allow(needless_range_loop))]
/// Returns a Peterson graph.
pub fn peterson<'a, G>() -> G
    where G: Graph<'a>
{
    let mut b = G::Builder::with_capacities(10, 15);
    let nodes: Vec<_> = (0..10).map(|_| b.add_node()).collect();
    for i in 0..5 {
        b.add_edge(nodes[i], nodes[(i + 1) % 5]);
        b.add_edge(nodes[i + 5], nodes[(i + 2) % 5 + 5]);
        b.add_edge(nodes[i], nodes[i + 5]);
    }
    b.to_graph()
}

#[cfg(test)]
mod tests {

    use super::*;
    use graph::*;
    use Net;
    use std::cmp::{min, max};

    #[test]
    fn test_path() {
        let g = path::<Net>(5);
        assert_eq!(g.num_nodes(), 6);
        assert_eq!(g.num_edges(), 5);
        let mut degrees = vec![0; g.num_nodes()];
        for e in g.edges() {
            let (u,v) = g.enodes(e);
            assert_eq!(min(u.index(), v.index()) + 1, max(u.index(), v.index()));
            degrees[u.index()] += 1;
            degrees[v.index()] += 1;
        }
        assert_eq!(degrees.iter().filter(|x| **x == 1).count(), 2);
        assert_eq!(degrees.iter().filter(|x| **x == 2).count(), g.num_nodes()-2);
    }

    #[test]
    fn test_cycle() {
        let g = cycle::<Net>(42);
        assert_eq!(g.num_nodes(), 42);
        assert_eq!(g.num_edges(), 42);
        let mut degrees = vec![0; g.num_nodes()];
        for e in g.edges() {
            let (u,v) = g.enodes(e);
            let (u,v) = (u.index(), v.index());
            assert!((min(u,v) + 1 == max(u,v)) || (min(u,v) == 0 && max(u,v) == g.num_nodes() - 1));
            degrees[u] += 1;
            degrees[v] += 1;
        }
        assert!(degrees.into_iter().all(|x| x == 2));
    }

    #[test]
    fn test_complete() {
        let n = 12;
        let g = complete_graph::<Net>(n);
        assert_eq!(g.num_nodes(), n);
        assert_eq!(g.num_edges(), n*(n-1) / 2);
        let mut degrees = vec![0; n];
        for e in g.edges() {
            let (u,v) = g.enodes(e);
            degrees[u.index()] += 1;
            degrees[v.index()] += 1;
        }
        assert!(degrees.into_iter().all(|x| x == n-1));
    }

    #[test]
    fn test_complete_bipartite() {
        let n = 13;
        let m = 7;
        let g = complete_bipartite::<Net>(n,m);
        assert_eq!(g.num_nodes(), n+m);
        assert_eq!(g.num_edges(), n*m);
        let mut degrees = vec![0; n+m];
        for e in g.edges() {
            let (u,v) = g.enodes(e);
            let (u,v) = (u.index(), v.index());
            assert!(min(u,v) < n);
            assert!(max(u,v) >= m);
            degrees[u] += 1;
            degrees[v] += 1;
        }
        assert!(degrees[..n].iter().all(|x| *x == m));
        assert!(degrees[n..].iter().all(|x| *x == n));
    }

    #[test]
    fn test_star() {
        let n = 17;
        let g: Net = star(n);
        assert_eq!(g.num_nodes(), n+1);
        assert_eq!(g.num_edges(), n);
        let mut degrees = vec![0; n+1];
        for e in g.edges() {
            let (u,v) = g.enodes(e);
            let (u,v) = (u.index(), v.index());
            assert_eq!(min(u,v), 0);
            degrees[u] += 1;
            degrees[v] += 1;
        }
        assert_eq!(degrees[0], n);
        assert!(degrees[1..].iter().all(|x| *x == 1));
    }

    #[test]
    fn test_hypercube() {
        let g: Net = hypercube(3);
        assert_eq!(g.num_nodes(), 8);
        assert_eq!(g.num_edges(), 12);

        let mut edges: Vec<_> = g.edges().map(|e| (g.src(e).index(), g.snk(e).index())).collect();
        edges.sort();

        assert_eq!(edges,
                   vec![(0, 1), (0, 2), (0, 4), (1, 3), (1, 5), (2, 3), (2, 6), (3, 7), (4, 5), (4, 6), (5, 7), (6, 7)]);
    }
}