hypergraphx 0.0.5

//! Hypergraphs have many types of cycles.
//!
//! Wikipedia talks about five kinds. The Berge cycle, which is your normal graph cycle,
//! the Tight cycle, which only works on uniform hypergraphs, and ɑ, β, and γ acyclicity.
//! I won't be doing the greeks here for the foreseeable future, just the acyclicity algos.

use std::{marker::PhantomData, sync::mpsc, thread};

use fixedbitset::FixedBitSet;
use hashbrown::HashSet;
use itertools::Itertools;

use crate::prelude::*;

/// Needs an inner type because cycles have different validity condition for different graphs.
pub trait Cycle<'a, T: GraphType> {
    type Inner: GraphBasics<'a> + CommonProperties<'a, T>;
    fn underlying_graph(&self) -> &Self::Inner;
    fn len(&self) -> usize;
    fn nodes(&self) -> impl Iterator<Item = <Self::Inner as GraphBasics<'a>>::NodeIndex>;
    fn forms_cycle(
        state: &CycleState<'a, T, Self::Inner>,
        new_edge: <Self::Inner as GraphBasics<'a>>::EdgeIndex,
        new_nodes: &HashSet<<Self::Inner as GraphBasics<'a>>::NodeIndex>,
    ) -> Option<Self>
    where
        Self: Sized;
}

pub struct CycleState<'a, T: GraphType, Inner: CommonProperties<'a, T>> {
    B: Vec<HashSet<Inner::NodeIndex>>,
    stack: Vec<usize>,
    blocked: FixedBitSet,
    curr_src: usize,
    _pd: PhantomData<T>,
}

impl<'a, T: GraphType, Inner: CommonProperties<'a, T>> CycleState<'a, T, Inner> {
    pub fn new(inner: &'a Inner) -> Self {
        Self {
            B: vec![HashSet::new(); inner.node_count()],
            stack: vec![],
            blocked: inner.visit_map(),
            curr_src: 0,
            _pd: PhantomData,
        }
    }
}

/// From https://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF
pub struct AllCycles<
    'a,
    T: GraphType,
    Inner: CommonProperties<'a, T>,
    Cyc: Cycle<'a, T, Inner = Inner>,
> where
    Inner::NodeIndex: Send + Sync,
{
    inner: &'a Inner,
    state: CycleState<'a, T, Inner>,
    _pd: PhantomData<Cyc>,
}

impl<'a, T: GraphType, Inner: CommonProperties<'a, T>, Cyc: Cycle<'a, T, Inner = Inner>>
    AllCycles<'a, T, Inner, Cyc>
where
    Inner::NodeIndex: Send + Sync,
{
    pub fn new(inner: &'a Inner) -> Self {
        Self {
            inner,
            state: CycleState::new(inner),
            _pd: PhantomData,
        }
    }
}

fn unblock<'a, T: GraphType, G>(state: &mut CycleState<'a, T, G>, v: usize)
where
    G: CommonProperties<'a, T>,
{
    let mut q = vec![v];
    while let Some(node) = q.pop() {
        state.blocked.remove(node.into());
        for &w in state.B[node].iter() {
            if state.blocked.contains(w.into()) {
                q.push(w.into());
            }
        }
        state.B[node].clear();
    }
}

/// From https://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF
///
/// The implementation is slightly different, though.
///     - The obvious one is the use of an mpsc channel and a separate thread. I tried my best to get around the lack of a `gen`
///     keyword and *will* change it once that gets stabilised. Right now, 'tis a kludge. On the bright side, you won't have
///     an O(#cycles) algorithm running in the same thread as everything else, because that's a doozy.
///     - But also, the original has us inducing |V| subgraphs, and I figured I'd filter the nodes instead.
fn circuit_recursive_mpsc<'a, G, C, T: GraphType>(
    state: &mut CycleState<'a, T, G>,
    inner: &'a G,
    tx: &mpsc::SyncSender<C>,
    v: usize,
) -> bool
where
    G: GraphBasics<'a> + CommonProperties<'a, T>,
    C: Cycle<'a, T, Inner = G>,
{
    let mut f = false;
    state.blocked.insert(v.into());
    state.stack = vec![v.into()];
    // Shouldn't we be pushing onto the stack somewhere here?
    for (e, mut nodes) in inner.neighbours_with_edges(v.into()) {
        nodes.retain(|&x| x.into() <= state.curr_src);
        if let Some(c) = C::forms_cycle(&state, e, &nodes) {
            tx.send(c).unwrap();
            f = true;
        } else {
            for node in nodes {
                if !state.blocked.contains(node.into()) {
                    f |= circuit_recursive_mpsc(state, inner, tx, node.into())
                }
            }
        }
    }

    if f {
        unblock(state, v);
    } else {
        let new_nodes = inner
            .neighbours_or_out_neighbours(v.into())
            .unwrap()
            .filter(|&x| x.into() <= state.curr_src);
        state.B[v].extend(new_nodes);
    }

    assert_eq!(Some(v), state.stack.pop());

    return f;
}

impl<'a, I: Sync, C: Sync + Send, T: GraphType> Iterator for AllCycles<'a, T, I, C>
where
    I: GraphBasics<'a> + CommonProperties<'a, T>,
    C: Cycle<'a, T, Inner = I>,
    I::NodeIndex: Send + Sync,
{
    type Item = C;

    fn next(&mut self) -> Option<Self::Item> {
        let (tx, rx) = mpsc::sync_channel(12);

        thread::scope(|s| {
            s.spawn(|| {
                while self.state.curr_src < self.inner.node_count() {
                    let q = self.state.curr_src;
                    circuit_recursive_mpsc(&mut self.state, self.inner, &tx, q);
                    self.state.curr_src += 1;
                }
            });
        });

        return rx.recv().ok();
    }
}

pub struct BergeCycle<'a, T: GraphBasics<'a>, G> {
    inner: &'a T,
    nodes: Vec<T::NodeIndex>,
    _pd: PhantomData<G>,
}

impl<'a, T, G: GraphType> BergeCycle<'a, T, G>
where
    T: GraphBasics<'a> + CommonProperties<'a, G>,
{
    pub fn new(inner: &'a T, nodes: Vec<T::NodeIndex>, edges: Vec<T::EdgeIndex>) -> Option<Self> {
        assert!(nodes.len() == edges.len());
        assert!(nodes.len() >= 3, "A cycle must have at least 3 nodes.");
        for ((n1, n2), e) in nodes.iter().tuple_windows().zip(edges.iter()) {
            if !inner.connects_nodes(*n1, *n2, *e) {
                return None;
            }
        }
        if !inner.connects_nodes(*nodes.last().unwrap(), nodes[0], *edges.last().unwrap()) {
            return None;
        }
        Some(Self {
            inner,
            nodes,
            _pd: PhantomData,
        })
    }
}

impl<'a, T, G: GraphType> Cycle<'a, G> for BergeCycle<'a, T, G>
where
    T: GraphBasics<'a> + CommonProperties<'a, G>,
{
    type Inner = T;

    fn underlying_graph(&self) -> &Self::Inner {
        self.inner
    }

    fn len(&self) -> usize {
        self.nodes.len()
    }

    fn nodes(&self) -> impl Iterator<Item = <Self::Inner as GraphBasics<'a>>::NodeIndex> {
        self.nodes.iter().copied()
    }

    fn forms_cycle(
        state: &CycleState<'a, G, Self::Inner>,
        new_edge: <Self::Inner as GraphBasics<'a>>::EdgeIndex,
        new_nodes: &HashSet<<Self::Inner as GraphBasics<'a>>::NodeIndex>,
    ) -> Option<Self>
    where
        Self: Sized,
    {
        if new_nodes
            .intersection(
                &state
                    .stack
                    .iter()
                    .map(|x| -> <Self::Inner as GraphBasics<'a>>::NodeIndex { (*x).into() })
                    .collect(),
            )
            .count()
            > 0
        {
            todo!()
        } else {
            None
        }
    }
}