hypergraphx 0.0.5

//! Your basic, no frills, undirected Hypergraph. Each `Hypergraph` stores a list of `Node`s and `Edge`s.
//! Both `Node` and `Edge` are generic over their weights, and store mutual incidence information.
//!     This makes accessing the neighbours of a node very efficient, thus speeding up BFS.
//!
//! Undirected Hypergraphs are formally just a family of subsets of a given set, here the set of nodes.
//! So we'll implement a partial order hierarchy, and union, intersection, and symmetric difference
//! operations for edges. (TODO)
//!
use std::{fmt::Debug, hash::Hash};

use hashbrown::HashSet;
use itertools::Itertools;

use crate::{HypergraphErrors, impl_graph_basics, impl_weights, traits::*};
pub mod uniform;
use uniform::UniformHypergraph;

/// A type alias for a plain old graph. Ideally, even if you only want normal graphs,
/// this library should provide a flexible and performant interface for working with them.
pub type Graph<N, E> = UniformHypergraph<N, E, 2>;

/// The graph's node type. It is not meant to be interacted with independent of the overarching graph.
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct Node<N> {
    pub weight: N,
    /// To avoid cyclic references (and for convenience) we store the indices of the incident edges.
    /// This allows us to quickly find the edges connected to a node, *if* we have a reference to the
    /// graph itself.
    pub(crate) edges: Vec<usize>,
}

/// The graph's edge type. Unlike graphs, nodes and edges in hypergraphs are symmetric,
/// in that multiple nodes can belong to the same edge and multiple edges can be incident on the same node.
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct Edge<E> {
    pub weight: E,
    /// To avoid cyclic references (and for convenience) we store the indices of the inner nodes.
    pub(crate) nodes: Vec<usize>,
}

impl<E> Edge<E> {
    /// A simple function to check if the edge connects two nodes.
    pub fn connects(&self, a: usize, b: usize) -> bool {
        self.nodes.contains(&a) && self.nodes.contains(&b)
    }
}

/// This struct is probably why you're here.
///
/// We store both nodes and edges in Vec<>s instead of Set data structures (BTreeSet, HashSet, etc.),
/// for cache-friendliness and quicker access.
/// The `Hypergraph` struct is generic over the *weights* of the nodes and edges.
///
/// I *might* add a `NodeSet` and `EdgeSet` type in the future, or maybe make a new Graph type with some other inner store.
#[derive(Debug, Clone)]
pub struct Hypergraph<N, E> {
    pub(crate) nodes: Vec<Node<N>>,
    pub(crate) edges: Vec<Edge<E>>,
}

impl<N, E> Default for Hypergraph<N, E> {
    fn default() -> Self {
        Self::new()
    }
}

impl<N, E> Hypergraph<N, E> {
    pub fn new() -> Self {
        Self {
            nodes: Vec::new(),
            edges: Vec::new(),
        }
    }

    pub fn add_node(&mut self, weight: N) -> usize {
        self.nodes.push(Node {
            weight,
            edges: Vec::new(),
        });
        self.nodes.len() - 1
    }

    pub fn add_edge(
        &mut self,
        weight: E,
        mut node_indices: Vec<usize>,
    ) -> Result<usize, HypergraphErrors> {
        node_indices.retain(|&n| n < self.nodes.len());
        if node_indices.len() < 2 {
            return Err(HypergraphErrors::EdgeTooSmall);
        }

        let edge = Edge {
            weight,
            nodes: node_indices,
        };
        self.edges.push(edge);
        let edge_index = self.edges.len() - 1;

        for &node_index in &self.edges[edge_index].nodes {
            if let Some(node) = self.nodes.get_mut(node_index) {
                node.edges.push(edge_index);
            }
        }

        Ok(edge_index)
    }

    pub fn add_nodes(&mut self, weights: impl Iterator<Item = N>) -> Vec<usize> {
        weights.into_iter().map(|w| self.add_node(w)).collect()
    }

    pub fn add_edges(
        &mut self,
        edges: impl Iterator<Item = (E, Vec<usize>)>,
    ) -> Result<Vec<usize>, HypergraphErrors> {
        edges
            .map(|(weight, nodes)| self.add_edge(weight, nodes))
            .collect()
    }

    pub fn remove_node(&mut self, node_index: usize) -> Option<Node<N>> {
        if node_index < self.nodes.len() {
            let removed_node = &self.nodes[node_index];
            let mut out_edges = vec![];
            // Remove edges connected to this node
            for &edge_index in removed_node.edges.iter() {
                if let Some(edge) = self.edges.get_mut(edge_index) {
                    edge.nodes.retain(|&n| n != node_index);
                    if edge.nodes.len() < 2 {
                        // If the edge has less than 2 nodes, remove it
                        out_edges.push(edge_index);
                    }
                }
            }

            out_edges.sort_unstable();
            out_edges.dedup();
            self.remove_edges(out_edges);
            let removed_node = self.nodes.swap_remove(node_index);

            let l = self.nodes.len();
            if l > node_index {
                let moved_node = &mut self.nodes[node_index];
                for &edge_index in moved_node.edges.iter() {
                    if let Some(edge) = self.edges.get_mut(edge_index) {
                        edge.nodes.iter_mut().for_each(|n| {
                            if *n == l {
                                *n = node_index; // Update moved node's index
                            }
                        });
                    }
                }
            }
            Some(removed_node)
        } else {
            None
        }
    }

    pub fn remove_nodes(&mut self, node_indices: Vec<usize>) -> Vec<Node<N>> {
        for &node_index in node_indices.iter() {
            let removed_node = &self.nodes[node_index];
            let mut out_edges = vec![];
            // Remove edges connected to this node
            for &edge_index in removed_node.edges.iter() {
                if let Some(edge) = self.edges.get_mut(edge_index) {
                    edge.nodes.retain(|&n| n != node_index);
                    if edge.nodes.len() < 2 {
                        // If the edge has less than 2 nodes, remove it
                        out_edges.push(edge_index);
                    }
                }
            }

            out_edges.sort_unstable();
            out_edges.dedup();
            self.remove_edges(out_edges);
        }

        for (count, &node_index) in node_indices.iter().enumerate() {
            let l = self.nodes.len() - count - 1;
            if l > node_index {
                let moved_node = &mut self.nodes[l];
                for &edge_index in moved_node.edges.iter() {
                    if let Some(edge) = self.edges.get_mut(edge_index) {
                        edge.nodes.iter_mut().for_each(|n| {
                            if *n == l {
                                *n = node_index; // Update moved node's index
                            }
                        });
                    }
                }
            }
        }

        node_indices
            .into_iter()
            .filter_map(|node_index| {
                if node_index < self.nodes.len() {
                    Some(self.nodes.swap_remove(node_index))
                } else {
                    None
                }
            })
            .collect()
    }

    pub fn remove_edge(&mut self, edge_index: usize) -> Option<Edge<E>> {
        if edge_index < self.edges.len() {
            let removed_edge = &self.edges[edge_index];
            // let out_nodes = vec![];
            // Remove this edge from the nodes it connects
            for &node_index in &removed_edge.nodes {
                if let Some(node) = self.nodes.get_mut(node_index) {
                    node.edges.retain(|&e| e != edge_index);
                }
            }
            let removed_edge = self.edges.swap_remove(edge_index);

            let l = self.edges.len();
            if l > edge_index {
                let moved_edge = &mut self.edges[edge_index];
                for &node_index in moved_edge.nodes.iter() {
                    if let Some(node) = self.nodes.get_mut(node_index) {
                        node.edges.iter_mut().for_each(|e| {
                            if *e == l {
                                *e = edge_index; // Update moved edge's index
                            }
                        });
                    }
                }
            }

            Some(removed_edge)
        } else {
            None
        }
    }

    pub fn remove_edges(&mut self, edge_indices: Vec<usize>) -> Vec<Edge<E>> {
        for &edge_index in edge_indices.iter() {
            if edge_index < self.edges.len() {
                let removed_edge = &self.edges[edge_index];
                // let out_nodes = vec![];
                // Remove this edge from the nodes it connects
                for &node_index in &removed_edge.nodes {
                    if let Some(node) = self.nodes.get_mut(node_index) {
                        node.edges.retain(|&e| e != edge_index);
                    }
                }
            }
        }

        for (count, &edge_index) in edge_indices.iter().rev().enumerate() {
            let l = self.edges.len() - count - 1;
            if l > edge_index {
                let moved_edge = &mut self.edges[l];
                for &node_index in moved_edge.nodes.iter() {
                    if let Some(node) = self.nodes.get_mut(node_index) {
                        node.edges.iter_mut().for_each(|e| {
                            if *e == l {
                                *e = edge_index; // Update moved edge's index
                            }
                        });
                    }
                }
            }
        }

        edge_indices
            .into_iter()
            .rev()
            .filter_map(|edge_index| {
                if edge_index < self.edges.len() {
                    Some(self.edges.swap_remove(edge_index))
                } else {
                    None
                }
            })
            .collect()
    }

    pub fn get_neighbours(&self, node_index: usize) -> Option<HashSet<&usize>> {
        if node_index >= self.nodes.len() {
            return None;
        }
        let mut out = self.nodes[node_index]
            .edges
            .iter()
            .flat_map(|e| {
                if let Some(edge) = self.edges.get(*e) {
                    edge.nodes.iter().collect::<Vec<_>>()
                } else {
                    std::iter::empty().collect()
                }
            })
            .collect::<HashSet<_>>();

        out.remove(&node_index);
        Some(out)
    }

    pub fn get_incident_edges(&self, node_index: usize) -> Option<&Vec<usize>> {
        if node_index >= self.nodes.len() {
            return None;
        }
        Some(&self.nodes[node_index].edges)
    }

    pub fn induced_shgraph(&self, node_indices: &[usize]) -> Self
    where
        E: Clone + Eq + Hash,
        N: Clone,
    {
        let mut subgraph = Self::new();
        let mut node_map = vec![None; self.nodes.len()];

        let mut new_nodes = vec![];

        for &node_index in node_indices.iter() {
            if let Some(node) = self.nodes.get(node_index) {
                let new_index = new_nodes.len();
                new_nodes.push(Node {
                    weight: node.weight.clone(),
                    edges: Vec::new(),
                });
                node_map[node_index] = Some(new_index);
            }
        }

        let mut u = node_indices
            .iter()
            .map(|i| &self.nodes[*i])
            .flat_map(|n| n.edges.iter().map(|x| (*x, &self.edges[*x])))
            .collect::<HashSet<_>>();
        u.retain(|(_i, e)| !e.nodes.is_empty() && e.nodes.iter().all(|&n| node_map[n].is_some()));

        subgraph.nodes = new_nodes;

        for (_, edge) in &u {
            let new_nodes: Vec<usize> = edge.nodes.iter().filter_map(|&n| node_map[n]).collect();
            if !new_nodes.is_empty() {
                let _ = subgraph.add_edge(edge.weight.clone(), new_nodes);
            }
        }

        subgraph
    }

    pub fn shgraph_by_order(&self, order: usize) -> Self
    where
        E: Clone + Eq + Hash,
        N: Clone,
    {
        // let mut subgraph = Self::new();
        let new_edges = self
            .edges
            .iter()
            .filter(|e| e.nodes.len() <= order)
            .cloned()
            .collect::<Vec<_>>();

        let new_nodes = new_edges
            .iter()
            .flat_map(|e| e.nodes.iter())
            .cloned()
            .collect::<HashSet<_>>();

        let mut subgraph = self.induced_shgraph(&new_nodes.into_iter().collect::<Vec<_>>());

        let v = subgraph
            .edges
            .iter()
            .enumerate()
            .filter(|(_, e)| e.nodes.len() > order)
            .map(|(i, _)| i)
            .collect::<Vec<_>>();

        subgraph.remove_edges(v);

        subgraph
    }

    pub fn include_node(&mut self, edge_index: usize, node_index: usize) -> bool {
        self.edges
            .get_mut(edge_index)
            .map(|edge| {
                if !edge.nodes.contains(&node_index) {
                    edge.nodes.push(node_index);
                    if let Some(node) = self.nodes.get_mut(node_index) {
                        node.edges.push(edge_index);
                    }
                }
                true
            })
            .unwrap_or(false)
    }

    pub fn detach_node(&mut self, edge_index: usize, node_index: usize) -> (bool, Option<Edge<E>>) {
        let out = self
            .edges
            .get_mut(edge_index)
            .map(|edge| {
                if let Some(pos) = edge.nodes.iter().position(|&n| n == node_index) {
                    edge.nodes.remove(pos);
                    if let Some(node) = self.nodes.get_mut(node_index) {
                        node.edges.retain(|&e| e != edge_index);
                    }
                }
                true
            })
            .unwrap_or(false);

        (
            out,
            if self
                .edges
                .get_mut(edge_index)
                .map(|e| e.nodes.len() < 2)
                .unwrap_or(false)
            {
                // If the edge has no target nodes left, remove it
                self.remove_edge(edge_index)
            } else {
                None
            },
        )
    }
}

impl_graph_basics!(
    Hypergraph<N, E>,
    &'a Node<N>,
    &'a Edge<E>,
    false
);

impl<'a, N: 'a, E: 'a> GraphProperties<'a> for Hypergraph<N, E>
where
    N: Clone + Eq + Hash,
    E: Clone + Eq + Debug + Hash,
    // Why do I have to do this? :melt:
    Self: GraphBasics<
            'a,
            NodeRef = &'a Node<N>,
            EdgeRef = &'a Edge<E>,
            NodeIndex = usize,
            EdgeIndex = usize,
        >,
{
    fn neighbours(&'a self, node_index: usize) -> Option<HashSet<usize>> {
        Some(
            self.get_neighbours(node_index)?
                .into_iter()
                .map(|&n| n)
                .collect(),
        )
    }

    fn incident_edges(&self, node_index: usize) -> Option<hashbrown::HashSet<usize>> {
        Some(
            self.get_incident_edges(node_index)?
                .iter()
                .map(|&e| e)
                .collect(),
        )
    }

    fn degree(&self, node_index: usize) -> Option<usize> {
        self.nodes.get(node_index).map(|node| node.edges.len())
    }

    fn connected_components(&self) -> Vec<Vec<usize>> {
        let mut visited = vec![false; self.nodes.len()];
        let mut components = Vec::new();

        for i in 0..self.nodes.len() {
            if !visited[i] {
                let mut component = Vec::new();
                let mut stack = vec![i];

                while let Some(node_index) = stack.pop() {
                    if !visited[node_index] {
                        visited[node_index] = true;
                        component.push(node_index);
                        stack.extend(self.get_neighbours(node_index).unwrap().iter().cloned());
                    }
                }

                components.push(component);
            }
        }

        components
    }

    fn component(&self, node_index: usize) -> Option<Vec<usize>> {
        let mut visited = vec![false; self.nodes.len()];
        let mut component = Vec::new();
        let mut stack = vec![node_index];

        while let Some(node_index) = stack.pop() {
            if !visited[node_index] {
                visited[node_index] = true;
                component.push(node_index);
                stack.extend(self.get_neighbours(node_index)?.iter().cloned());
            }
        }

        Some(component)
    }

    fn extract_component(&'a self, node_index: usize) -> Option<Self>
    where
        E: Clone,
        N: Clone,
    {
        let component_nodes = self.component(node_index)?;
        Some(self.induced_shgraph(&component_nodes))
    }

    type Subgraph = Self;

    fn contained_nodes(&self, edge_index: usize) -> Option<hashbrown::HashSet<usize>> {
        self.edges.get(edge_index).map(|edge| {
            edge.nodes
                .iter()
                // .filter_map(|&n| self.nodes.get(n).map(|node| (n, node)))
                .map(|&n| n)
                .collect()
        })
    }

    fn neighbour_count(&self, node_index: usize) -> Option<usize> {
        self.nodes.get(node_index).map(|node| {
            node.edges
                .iter()
                .map(|e| self.edges[*e].nodes.len() - 1)
                .sum()
        })
    }

    fn degree_by_order(
        &'a self,
        node_index: <Self as GraphBasics<'a>>::NodeIndex,
        order: usize,
    ) -> Option<usize> {
        self.nodes.get(node_index).map(|node| {
            node.edges
                .iter()
                .filter(|e| self.edges[**e].nodes.len() == order)
                .count()
        })
    }
}

impl<'a, N: 'a, E: 'a> HypergraphBasics<'a> for Hypergraph<N, E>
where
    N: Clone + Eq + Hash,
    E: Clone + Eq + Hash,
{
    fn uniform(&self) -> bool {
        if self.edges.is_empty() {
            return true;
        }
        let first_len = self.edges[0].nodes.len();
        self.edges.iter().all(|e| e.nodes.len() == first_len)
    }

    type DualType = Hypergraph<E, N>;

    fn dual(&self) -> Self::DualType {
        let mut out = Hypergraph::new();

        out.nodes = self
            .edges
            .iter()
            .map(|e| Node {
                weight: e.weight.clone(),
                edges: e.nodes.clone(), // Will be filled later
            })
            .collect();

        out.edges = self
            .nodes
            .iter()
            .map(|n| Edge {
                weight: n.weight.clone(),
                nodes: n.edges.clone(),
            })
            .collect();
        out
    }
}

impl<'a, N: 'a, E: 'a> HypergraphProperties<'a, N, E> for Hypergraph<N, E>
where
    N: Clone + Eq + Hash,
    E: Clone + Eq + Hash + Debug,
{
    fn order(&self, edge_index: usize) -> Option<usize> {
        self.edges.get(edge_index).map(|e| e.nodes.len())
    }

    fn graph_view(&self) -> Graph<&N, &E> {
        let mut out = Graph::new();
        out.add_nodes(self.nodes.iter().map(|n| &n.weight));
        for e in &self.edges {
            for (u, v) in e.nodes.iter().tuple_combinations() {
                out.add_edge(&e.weight, [*u, *v]).unwrap();
            }
        }

        out
    }
}

impl_weights!(Hypergraph<N, E>);