fera-graph 0.2.0

// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this
// file, You can obtain one at http://mozilla.org/MPL/2.0/.

//! [Khan]'s topological sort algoritm.
//!
//! [Khan]: https://en.wikipedia.org/wiki/Topological_sorting#Kahn.27s_algorithm

use prelude::*;
use params::*;

use std::ops::DerefMut;

generic_struct! {
    #[must_use]
    pub struct KhanAlg(graph, degree, queue)
}

pub trait Khan: WithEdge<Kind = Directed> + Adjacency {
    fn khan(&self) -> KhanAlg<&Self, NewVertexProp<Self, u32>, Owned<Vec<Vertex<Self>>>> {
        KhanAlg(self, NewVertexProp(self, 0), Owned(vec![]))
    }

    fn topological_sort(&self) -> Result<Vec<Vertex<Self>>, CycleFound>
    where
        Self: VertexList + WithVertexProp<u32>,
    {
        self.khan().into_iter().collect()
    }
}

impl<G: WithEdge<Kind = Directed> + Adjacency> Khan for G {}


impl<'a, G, D, Q> IntoIterator for KhanAlg<&'a G, D, Q>
where
    G: WithEdge<Kind = Directed>
        + Adjacency
        + VertexList,
    D: ParamDerefMut,
    D::Target: VertexPropMut<G, u32>,
    Q: ParamDerefMut<Target = Vec<Vertex<G>>>,
{
    type Item = Result<Vertex<G>, CycleFound>;
    type IntoIter = Iter<'a, G, D::Output, Q::Output>;

    fn into_iter(self) -> Self::IntoIter {
        let KhanAlg(g, degree, queue) = self;
        let mut degree = degree.build();
        let mut queue = queue.build();
        for u in g.vertices() {
            for v in g.out_neighbors(u) {
                degree[v] += 1;
            }
        }
        queue.extend(g.vertices().filter(|&v| degree[v] == 0));
        Iter {
            g,
            rem: g.num_vertices(),
            degree,
            queue,
        }
    }
}

pub struct Iter<'a, G: 'a, D, Q> {
    g: &'a G,
    rem: usize,
    degree: D,
    queue: Q,
}

impl<'a, G, D, Q> Iterator for Iter<'a, G, D, Q>
where
    G: WithEdge<Kind = Directed> + Adjacency,
    D: DerefMut,
    D::Target: VertexPropMut<G, u32>,
    Q: DerefMut<Target = Vec<Vertex<G>>>,
{
    type Item = Result<Vertex<G>, CycleFound>;

    fn next(&mut self) -> Option<Self::Item> {
        if let Some(u) = self.queue.pop() {
            for v in self.g.out_neighbors(u) {
                self.degree[v] -= 1;
                if self.degree[v] == 0 {
                    self.queue.push(v);
                }
            }
            self.rem -= 1;
            Some(Ok(u))
        } else if self.rem != 0 {
            Some(Err(CycleFound))
        } else {
            None
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.queue.len(), Some(self.rem))
    }
}

#[derive(Default, Debug, PartialEq, Eq)]
pub struct CycleFound;


pub fn is_topological_sorted<G>(g: &G, vertices: &[Vertex<G>]) -> bool
where
    G: WithEdge<Kind = Directed> + EdgeList + WithVertexProp<usize>,
{
    let mut pos = g.default_vertex_prop(0usize);
    for (i, &v) in vertices.iter().enumerate() {
        if pos[v] != 0 {
            return false;
        }
        pos[v] = i;
    }
    g.edges_ends().all(|(u, v)| pos[u] < pos[v])
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test() {
        let g: StaticDigraph =
            graph! {
            5,
            (0, 2),
            (0, 4),
            (1, 4),
            (0, 1),
            (3, 2),
            (4, 3),
        };

        assert_eq!(Ok(vec![0, 1, 4, 3, 2]), g.topological_sort());

        let g: StaticDigraph =
            graph! {
            3,
            (0, 1),
            (1, 2),
            (2, 0),
        };

        assert_eq!(Err(CycleFound), g.topological_sort());
    }
}