hypergraphx 0.0.5

use std::{fmt::Debug, hash::Hash};

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

use crate::prelude::*;
pub mod uniform;
use uniform::UniformHypergraph;
pub type DiGraph<N, E> = UniformHypergraph<N, E, 1>;

/// The graph's node type.
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct Node<N> {
    pub weight: N,
    pub(crate) in_edges: Vec<usize>,
    pub(crate) out_edges: Vec<usize>,
}

/// The graph's edge type.
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct Edge<E> {
    pub weight: E,
    pub(crate) source: Vec<usize>,
    pub(crate) target: Vec<usize>,
}

impl<E> Edge<E> {
    /// Return the source node index.
    pub fn source(&self) -> &[usize] {
        self.source.as_slice()
    }

    /// Return the target node index.
    pub fn target(&self) -> &[usize] {
        self.target.as_slice()
    }

    pub fn connects(&self, a: usize, b: usize) -> bool {
        self.source.contains(&a) && self.target.contains(&b)
    }
}

#[derive(Debug, Clone)]
pub struct Hypergraph<N, E> {
    pub(crate) nodes: Vec<Node<N>>,
    pub(crate) edges: Vec<Edge<E>>,
}

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,
            in_edges: Vec::new(),
            out_edges: Vec::new(),
        });
        self.nodes.len() - 1
    }

    pub fn add_edge(
        &mut self,
        weight: E,
        mut source_indices: Vec<usize>,
        mut target_indices: Vec<usize>,
    ) -> Result<usize, HypergraphErrors> {
        source_indices.retain(|&n| n < self.nodes.len());
        if source_indices.is_empty() {
            return Err(HypergraphErrors::EdgeTooSmall);
        }
        target_indices.retain(|&n| n < self.nodes.len());
        if target_indices.is_empty() {
            return Err(HypergraphErrors::EdgeTooSmall);
        }
        let edge = Edge {
            weight,
            source: source_indices.clone(),
            target: target_indices.clone(),
        };
        self.edges.push(edge);
        let edge_index = self.edges.len() - 1;

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

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

        Ok(edge_index)
    }

    pub fn add_nodes(&mut self, weights: impl Iterator<Item = N>) {
        self.nodes.extend(weights.map(|w| Node {
            weight: w,
            in_edges: Vec::new(),
            out_edges: Vec::new(),
        }));
    }

    pub fn add_edges(
        &mut self,
        edges: impl Iterator<Item = (E, Vec<usize>, Vec<usize>)>,
    ) -> Result<(), HypergraphErrors> {
        for (w, s, t) in edges {
            self.add_edge(w, s, t)?;
        }
        Ok(())
    }

    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.in_edges {
                if let Some(edge) = self.edges.get_mut(edge_index) {
                    edge.target.retain(|&n| n != node_index);
                    if edge.target.len() < 1 {
                        // If the edge has less than 2 nodes, remove it
                        out_edges.push(edge_index);
                    }
                }
            }

            for &edge_index in &removed_node.out_edges {
                if let Some(edge) = self.edges.get_mut(edge_index) {
                    edge.source.retain(|&n| n != node_index);
                    if edge.source.len() < 1 {
                        // 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.out_edges.iter() {
                    if let Some(edge) = self.edges.get_mut(edge_index) {
                        edge.source.iter_mut().for_each(|n| {
                            if *n == l {
                                *n = node_index; // Update moved node's index
                            }
                        });
                    }
                }
                for &edge_index in moved_node.in_edges.iter() {
                    if let Some(edge) = self.edges.get_mut(edge_index) {
                        edge.target.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.in_edges {
                if let Some(edge) = self.edges.get_mut(edge_index) {
                    edge.target.retain(|&n| n != node_index);
                    if edge.target.len() < 1 {
                        // If the edge has less than 2 nodes, remove it
                        out_edges.push(edge_index);
                    }
                }
            }

            for &edge_index in &removed_node.out_edges {
                if let Some(edge) = self.edges.get_mut(edge_index) {
                    edge.source.retain(|&n| n != node_index);
                    if edge.source.len() < 1 {
                        // 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.in_edges.iter() {
                    if let Some(edge) = self.edges.get_mut(edge_index) {
                        edge.target.iter_mut().for_each(|n| {
                            if *n == l {
                                *n = node_index; // Update moved node's index
                            }
                        });
                    }
                }

                for &edge_index in moved_node.out_edges.iter() {
                    if let Some(edge) = self.edges.get_mut(edge_index) {
                        edge.source.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];
            // Remove this edge from the nodes it connects
            for &node_index in &removed_edge.source {
                if let Some(node) = self.nodes.get_mut(node_index) {
                    node.out_edges.retain(|&e| e != edge_index);
                }
            }

            for &node_index in &removed_edge.target {
                if let Some(node) = self.nodes.get_mut(node_index) {
                    node.in_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.source.iter() {
                    if let Some(node) = self.nodes.get_mut(node_index) {
                        node.out_edges.iter_mut().for_each(|e| {
                            if *e == l {
                                *e = edge_index; // Update moved edge's index
                            }
                        });
                    }
                }

                for &node_index in moved_edge.target.iter() {
                    if let Some(node) = self.nodes.get_mut(node_index) {
                        node.in_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];
                // Remove this edge from the nodes it connects
                for &node_index in &removed_edge.source {
                    if let Some(node) = self.nodes.get_mut(node_index) {
                        node.out_edges.retain(|&e| e != edge_index);
                    }
                }

                for &node_index in &removed_edge.target {
                    if let Some(node) = self.nodes.get_mut(node_index) {
                        node.in_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.source.iter() {
                    if let Some(node) = self.nodes.get_mut(node_index) {
                        node.out_edges.iter_mut().for_each(|e| {
                            if *e == l {
                                *e = edge_index; // Update moved edge's index
                            }
                        });
                    }
                }

                for &node_index in moved_edge.target.iter() {
                    if let Some(node) = self.nodes.get_mut(node_index) {
                        node.in_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_in_neighbours(&self, node_index: usize) -> Option<HashSet<&usize>> {
        if node_index >= self.nodes.len() {
            return None;
        }
        let mut out = self.nodes[node_index]
            .in_edges
            .iter()
            .flat_map(|e| {
                if let Some(edge) = self.edges.get(*e) {
                    edge.source.iter().collect::<Vec<_>>()
                } else {
                    std::iter::empty().collect()
                }
            })
            .collect::<HashSet<_>>();

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

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

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

    pub fn get_in_edges(&self, node_index: usize) -> Option<&Vec<usize>> {
        if node_index >= self.nodes.len() {
            return None;
        }
        Some(&self.nodes[node_index].in_edges)
    }
    pub fn get_out_edges(&self, node_index: usize) -> Option<&Vec<usize>> {
        if node_index >= self.nodes.len() {
            return None;
        }
        Some(&self.nodes[node_index].out_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 {
            if let Some(node) = self.nodes.get(node_index) {
                let new_index = new_nodes.len();
                new_nodes.push(Node {
                    weight: node.weight.clone(),
                    in_edges: vec![],
                    out_edges: vec![],
                });
                node_map[node_index] = Some(new_index);
            }
        }

        let mut u = node_indices
            .iter()
            .map(|i| &self.nodes[*i])
            .flat_map(|n| {
                n.in_edges
                    .iter()
                    .chain(n.out_edges.iter())
                    .map(|x| (*x, &self.edges[*x]))
            })
            .collect::<HashSet<_>>();

        u.retain(|(_i, e)| {
            !e.source.is_empty()
                && e.source.iter().all(|&n| node_map[n].is_some())
                && !e.target.is_empty()
                && e.target.iter().all(|&n| node_map[n].is_some())
        });

        subgraph.nodes = new_nodes;

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

        subgraph
    }

    pub fn shgraph_by_order<const ORDER: usize>(&self) -> UniformHypergraph<N, E, ORDER>
    where
        E: Clone + Eq + Hash,
        N: Clone,
    {
        let new_edges = self
            .edges
            .iter()
            .filter(|e| e.source.len() <= ORDER && e.target.len() <= ORDER)
            .cloned()
            .collect::<Vec<_>>();

        let new_nodes = new_edges
            .iter()
            .flat_map(|e| e.source.iter().chain(e.target.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.source.len() > ORDER || e.target.len() > ORDER)
            .map(|(i, _)| i)
            .collect::<Vec<_>>();

        subgraph.remove_edges(v);

        UniformHypergraph::try_from(subgraph).unwrap()
    }

    fn tarjan_inner(
        &self,
        curr_idx: &mut usize,
        curr: usize,
        aux: &mut Vec<TarjanState>,
        stack: &mut Vec<usize>,
        components: &mut Vec<Vec<usize>>,
    ) where
        E: Clone + Eq + Hash + Debug,
        N: Clone + Eq + Hash + Debug,
    {
        let neighbours = {
            let state = &mut aux[curr];

            state.index = Some(*curr_idx);
            state.lowlink = Some(*curr_idx);
            *curr_idx += 1;
            state.on_stack = true;

            let neighbours = self.get_out_neighbours(curr);

            stack.push(curr);
            neighbours
        }
        .unwrap();

        for n in neighbours {
            let nb = aux[*n];
            if nb.index.is_none() {
                // Successor has not been visited yet
                self.tarjan_inner(curr_idx, *n, aux, stack, components);
                let nb = aux[*n];
                let state = &mut aux[curr];
                state.lowlink = Some(state.lowlink.unwrap().min(nb.lowlink.unwrap()));
            } else if nb.on_stack {
                // Successor is on the stack
                let state = &mut aux[curr];
                state.lowlink = Some(state.lowlink.unwrap().min(nb.index.unwrap()));
            }
        }

        let state = aux[curr];
        if state.lowlink == state.index {
            // Found a strongly connected component
            let mut component = Vec::new();
            while let Some(node_index) = stack.pop() {
                let node_state = &mut aux[node_index];
                node_state.on_stack = false;
                component.push(node_index);
                if node_index == curr {
                    break;
                }
            }

            components.push(component);
        }
    }

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

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

    pub fn detach_source_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.source.iter().position(|&n| n == node_index) {
                    edge.source.remove(pos);
                    if let Some(node) = self.nodes.get_mut(node_index) {
                        node.out_edges.retain(|&e| e != edge_index);
                    }
                }
                true
            })
            .unwrap_or(false);

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

    pub fn detach_target_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.target.iter().position(|&n| n == node_index) {
                    edge.target.remove(pos);
                    if let Some(node) = self.nodes.get_mut(node_index) {
                        node.in_edges.retain(|&e| e != edge_index);
                    }
                }
                true
            })
            .unwrap_or(false);

        (
            out,
            if self
                .edges
                .get_mut(edge_index)
                .map(|e| e.target.is_empty())
                .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>,
    true
);

/* impl<'a, N: 'a, E: 'a> MatrixRepresentation<'a> for Hypergraph<N, E>
where
    N: Clone + Eq + Hash + Debug,
    E: Clone + Eq + Hash + Debug,
{
    fn binary_incidence_matrix(&self) -> CsMatrix<i8> {
        let mut irows = Vec::new();
        let mut icols = Vec::new();
        let mut vals = Vec::new();

        for (edge_index, edge) in self.edges.iter().enumerate() {
            for &node_index in &edge.source {
                irows.push(node_index);
                icols.push(edge_index);
                vals.push(1);
            }
            for &node_index in &edge.target {
                irows.push(node_index);
                icols.push(edge_index);
                vals.push(-1);
            }
        }

        let matrix =
            CsMatrix::from_triplet(self.nodes.len(), self.edges.len(), &irows, &icols, &vals);
        matrix
    }
    fn adjacency_matrix(&self) -> DMatrix<usize> {
        let l = self.nodes.len();
        let mut mat = DMatrix::<usize>::zeros(l, l);

        for (node_index, _) in self.nodes.iter().enumerate() {
            let n = self.get_out_neighbours(node_index).unwrap();
            for &neighbour in n {
                mat[(node_index, neighbour)] += 1;
            }
        }

        mat
    }

    fn dual_adjacency_matrix(&self) -> DMatrix<usize> {
        let l = self.node_count();
        let mut mat = DMatrix::<usize>::zeros(l, l);

        for (node_index, _) in self.nodes().enumerate() {
            let n = self.get_out_neighbours(node_index).unwrap();
            for &neighbour in n {
                mat[(neighbour, node_index)] += 1;
            }
        }

        mat
    }
    fn laplacian_matrix(&'a self) -> DMatrix<usize> {
        let dseq = Matrix::<usize, Dyn, Const<1>, _>::from(self.out_degree_sequence());
        let out = DMatrix::<usize>::from_diagonal(&dseq);

        return out - self.adjacency_matrix();
    }
} */

#[derive(Debug, Clone, Copy)]
pub(crate) struct TarjanState {
    pub(crate) lowlink: Option<usize>,
    pub(crate) index: Option<usize>,
    pub(crate) on_stack: bool,
}

impl Default for TarjanState {
    fn default() -> Self {
        Self {
            lowlink: None,
            index: None,
            on_stack: false,
        }
    }
}

impl<'a, N: 'a, E: 'a> DiGraphProperties<'a> for Hypergraph<N, E>
where
    N: Clone + Eq + Hash + Debug,
    E: Clone + Eq + Hash + Debug,
{
    fn source(
        &self,
        edge_index: <Self as GraphBasics<'a>>::EdgeIndex,
    ) -> Option<hashbrown::HashSet<usize>> {
        let edge = self.edges.get(edge_index)?;
        let sources = edge
            .source
            .iter()
            .map(|&n| n)
            .collect::<hashbrown::HashSet<_>>();
        Some(sources)
    }

    fn target(
        &self,
        edge_index: <Self as GraphBasics<'a>>::EdgeIndex,
    ) -> Option<hashbrown::HashSet<usize>> {
        let edge = self.edges.get(edge_index)?;
        let targets = edge
            .target
            .iter()
            // .filter_map(|&n| self.nodes.get(n).map(|node| (n, node)))
            .map(|&n| n)
            .collect::<HashSet<_>>();
        Some(targets)
    }

    fn in_neighbours(&'a self, node_index: usize) -> Option<hashbrown::HashSet<usize>> {
        Some(
            self.get_in_neighbours(node_index)?
                .into_iter()
                // .filter_map(|&n| self.nodes.get(n).map(|node| (n, node)))
                .map(|&n| n)
                .collect(),
        )
    }
    fn out_neighbours(&self, node_index: usize) -> Option<hashbrown::HashSet<usize>> {
        Some(
            self.get_out_neighbours(node_index)?
                .into_iter()
                // .filter_map(|&n| self.nodes.get(n).map(|node| (n, node)))
                .map(|&n| n)
                .collect(),
        )
    }

    fn in_edges(&self, node_index: usize) -> Option<hashbrown::HashSet<usize>> {
        Some(
            self.get_in_edges(node_index)?
                .iter()
                // .filter_map(|&e| self.edges.get(e).map(|edge| (e, edge)))
                .map(|&e| e)
                .collect(),
        )
    }

    fn out_edges(&self, node_index: usize) -> Option<hashbrown::HashSet<usize>> {
        Some(
            self.get_out_edges(node_index)?
                .iter()
                // .filter_map(|&e| self.edges.get(e).map(|edge| (e, edge)))
                .map(|&e| e)
                .collect(),
        )
    }

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

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

    fn weakly_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_out_neighbours(node_index)
                                .unwrap()
                                .iter()
                                .chain(self.get_in_neighbours(node_index).unwrap().iter())
                                .cloned(),
                        );
                    }
                }

                components.push(component);
            }
        }

        components
    }

    fn weak_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_in_neighbours(node_index)
                        .unwrap()
                        .iter()
                        .chain(self.get_out_neighbours(node_index).unwrap().iter())
                        .cloned(),
                );
            }
        }

        Some(component)
    }

    type Subgraph = Self;

    fn strongly_connected_components(&self) -> Vec<Vec<usize>> {
        let mut idx = 0;
        let mut aux = vec![TarjanState::default(); self.node_count()];

        let mut stack = vec![];
        let mut out = vec![];
        for x in 0..aux.len() {
            if aux[x].index.is_none() {
                self.tarjan_inner(&mut idx, x, &mut aux, &mut stack, &mut out);
            }
        }
        out
    }

    fn condense(&self) -> DiGraph<(), ()> {
        let mut idx = 0;
        let mut aux = vec![TarjanState::default(); self.node_count()];

        let mut stack = vec![];
        let mut out = vec![];
        let mut lens = vec![0];
        for x in 0..aux.len() {
            if aux[x].index.is_none() {
                self.tarjan_inner(&mut idx, x, &mut aux, &mut stack, &mut out);
                lens.push(out.len());
            }
        }
        // out
        let mut dag = DiGraph::new();
        dag.add_nodes(vec![(); out.len()].into_iter());
        for (i, j) in lens.iter().tuple_windows() {
            for (s, t) in (*i..*j).rev().tuple_windows() {
                dag.add_edge((), [s], [t]).unwrap();
            }
        }

        dag
    }
    fn strong_component(&self, node_index: usize) -> Option<Vec<usize>> {
        let mut idx = 0;
        let mut aux = vec![TarjanState::default(); self.node_count()];

        let mut stack = vec![];
        let mut out = vec![];
        self.tarjan_inner(&mut idx, node_index, &mut aux, &mut stack, &mut out);
        let l = out.len();
        if l > 0 && out[l - 1].contains(&node_index) {
            Some(out.pop().unwrap())
        } else {
            None
        }
    }

    fn extract_strong_component(&self, node_index: usize) -> Option<Self::Subgraph> {
        let component = self.strong_component(node_index)?;
        Some(self.induced_shgraph(&component))
    }

    fn extract_weak_component(&self, node_index: usize) -> Option<Self::Subgraph> {
        let component = self.weak_component(node_index)?;
        Some(self.induced_shgraph(&component))
    }

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

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

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

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

impl<'a, N: 'a + Clone + Eq + Hash, E: 'a + Clone + Eq + Hash> HypergraphBasics<'a>
    for Hypergraph<N, E>
{
    fn uniform(&self) -> bool {
        if self.edges.is_empty() {
            return true;
        }
        let first_len = self.edges[0].source.len();
        self.edges
            .iter()
            .all(|e| e.source.len() == first_len && e.target.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(),
                in_edges: e.source.clone(),  // Will be filled later
                out_edges: e.target.clone(), // Will be filled later
            })
            .collect();

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

impl<'a, N: 'a, E: 'a> DirectedHypergraphProperties<'a, N, E> for Hypergraph<N, E>
where
    N: Clone + Eq + Hash + Debug,
    E: Clone + Eq + Hash + Debug,
{
    fn in_order(&self, edge_index: usize) -> Option<usize> {
        self.edges.get(edge_index).map(|edge| edge.source.len())
    }
    fn out_order(&self, edge_index: usize) -> Option<usize> {
        self.edges.get(edge_index).map(|edge| edge.target.len())
    }

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

        out
    }
}

impl_weights!(Hypergraph<N, E>);