flag-algebra 0.1.11

//! Example of flags: directed graphs.
use crate::combinatorics;
use crate::common::*;
use crate::flag::{Flag, SubClass, SubFlag};
use crate::iterators::{Functions, StreamingIterator};
use canonical_form::Canonize;
use std::fmt;
use std::ops::Neg;

#[derive(PartialEq, Eq, PartialOrd, Ord, Debug, Clone, Copy, Serialize, Deserialize)]
/// The arc between two nodes of a directed graphs.
pub enum Arc {
    /// No arc.
    None,
    /// Arc from the first to the second vertex considered.
    Edge,
    /// Arc from the second to the first vertex considered.
    BackEdge,
}

impl Default for Arc {
    fn default() -> Self {
        None
    }
}

impl Neg for Arc {
    type Output = Self;

    fn neg(self) -> Self {
        match self {
            Edge => BackEdge,
            BackEdge => Edge,
            None => None,
        }
    }
}

use Arc::*;

#[derive(PartialEq, Eq, PartialOrd, Ord, Debug, Clone, Serialize, Deserialize)]
/// Directed graphs.
pub struct Digraph {
    /// Number of vertices.
    size: usize,
    /// Flat matrix of arcs.
    pub edge: AntiSym<Arc>,
}

impl Digraph {
    /// Number of vertices
    pub fn size(&self) -> usize {
        self.size
    }

    /// Out-neigborhood of `v` in `self`.
    pub fn out_nbrs(&self, v: usize) -> Vec<usize> {
        let mut res = Vec::new();
        for u in 0..self.size {
            if u != v && self.edge.get(u, v) == BackEdge {
                res.push(u);
            }
        }
        res
    }
    /// In-neigborhood of `v` in `self`.
    pub fn in_nbrs(&self, v: usize) -> Vec<usize> {
        let mut res = Vec::new();
        for u in 0..self.size {
            if u != v && self.edge.get(u, v) == Edge {
                res.push(u);
            }
        }
        res
    }
    /// Directed graph with `n` vertices and arcs `arcs`.
    pub fn new(n: usize, arcs: &[(usize, usize)]) -> Self {
        let mut new_edge = AntiSym::new(None, n);
        for &(u, v) in arcs {
            assert!(u < n);
            assert!(v < n);
            assert!(u != v);
            assert!(new_edge.get(u, v) == None);
            new_edge.set((u, v), Edge);
        }
        Self {
            size: n,
            edge: new_edge,
        }
    }
    /// Directed graph with `n` vertices and no edge.
    pub fn empty(n: usize) -> Self {
        Self {
            size: n,
            edge: AntiSym::new(None, n),
        }
    }

    fn triangle_free(&self) -> bool {
        for u in 0..self.size {
            // Assume u is the largest vertex
            for v in 0..u {
                if self.edge.get(v, u) == Edge {
                    for w in 0..u {
                        if self.edge.get(u, w) == Edge && self.edge.get(w, v) == Edge {
                            return false;
                        }
                    }
                }
            }
        }
        true
    }

    /// Directed graph obtained from `self` by adding a vertex and every edge
    /// from the rest of the graph to that vertex.
    pub fn add_sink(&self) -> Self {
        let n = self.size;
        let mut edge = self.edge.clone();
        edge.resize(n + 1, None);
        for v in 0..n {
            edge.set((v, n), Edge);
        }
        Self { edge, size: n + 1 }
    }
}

impl fmt::Display for Digraph {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "(V=[{}], E={{", self.size)?;
        for u in 0..self.size {
            for v in 0..self.size {
                if v != u && self.edge.get(u, v) == Edge {
                    if self.size < 10 {
                        write!(f, " {}{}", v, u)?;
                    } else {
                        write!(f, " {}-{}", v, u)?;
                    }
                }
            }
        }
        write!(f, " }})")
    }
}

impl Canonize for Digraph {
    fn size(&self) -> usize {
        self.size
    }
    fn invariant_neighborhood(&self, v: usize) -> Vec<Vec<usize>> {
        assert!(v < self.size);
        vec![self.out_nbrs(v), self.in_nbrs(v)]
    }
    fn apply_morphism(&self, p: &[usize]) -> Self {
        self.induce(&combinatorics::invert(p))
    }
}

impl Flag for Digraph {
    fn induce(&self, p: &[usize]) -> Self {
        let k = p.len();
        let mut res = Self::empty(k);
        for u1 in 0..k {
            for u2 in 0..u1 {
                res.edge.set((u1, u2), self.edge.get(p[u1], p[u2]));
            }
        }
        res
    }

    const NAME: &'static str = "Digraph";

    fn size_zero_flags() -> Vec<Self> {
        vec![Self::empty(0)]
    }

    fn superflags(&self) -> Vec<Self> {
        //FIXME
        let n = self.size;
        let mut res = Vec::new();
        let mut iter = Functions::new(n, 3);
        let arcs = vec![Edge, BackEdge, None];
        while let Some(f) = iter.next() {
            let mut edge = self.edge.clone();
            edge.resize(n + 1, None);
            for v in 0..n {
                edge.set((v, n), arcs[f[v]]);
            }
            res.push(Self { edge, size: n + 1 });
        }
        res
    }
}

/// Indicator for digraph without directed triangle.
#[derive(Debug, Clone, Copy)]
pub enum TriangleFree {}

impl SubFlag<Digraph> for TriangleFree {
    const SUBCLASS_NAME: &'static str = "Triangle-free digraph";

    fn is_in_subclass(flag: &Digraph) -> bool {
        flag.triangle_free()
    }
}

impl<A> SubClass<Digraph, A> {
    pub fn size(&self) -> usize {
        self.content.size()
    }
}