hypergraphx 0.0.5

use std::collections::VecDeque;

use fixedbitset::FixedBitSet;
use hashbrown::{HashMap, HashSet};

use crate::prelude::*;

/// Computed
/// [*matching*](https://en.wikipedia.org/wiki/Matching_(graph_theory)#Definitions)
/// of the graph.
pub struct Matching<'a, G: GraphBasics<'a>> {
    graph: &'a G,
    /// Mapping from node to edge.
    mate: Vec<Option<G::EdgeIndex>>,
}

impl<'a, G> Matching<'a, G>
where
    G: GraphProperties<'a>,
{
    /// Gets the matched counterpart of given node, if there is any.
    ///
    /// Returns `None` if the node is not matched or does not exist.
    pub fn mate(
        &self,
        node: G::NodeIndex,
    ) -> Option<HashSet<G::NodeIndex>> {
        self.mate.get(node.into()).map(|&id| {
            let mut u = self.graph.contained_nodes(id.unwrap()).unwrap().clone();
            u.retain(|&x| x != node);
            u
        })
    }

    /// Iterates over all edges from the matching.
    ///
    /// An edge is represented by its endpoints. The graph is considered
    /// undirected and every pair of matched nodes is reported only once.
    pub fn matched_edges(&'a self) -> impl Iterator<Item = (G::EdgeIndex, G::EdgeRef)> + 'a {
        // MatchedEdges {
        //     graph: &self.graph,
        //     mate: self.mate.iter().collect(),
        // }
        self.mate
            .iter()
            .filter_map(|&mate| mate)
            .map(|e| (e, self.graph.edge(e).unwrap()))
    }

    /// Iterates over all nodes from the matching.
    pub fn nodes(&self) -> MatchedNodes<'_, G> {
        MatchedNodes {
            graph: &self.graph,
            mate: self.mate.as_slice(),
            current: 0,
        }
    }

    /// Returns `true` if given edge is in the matching, or `false` otherwise.
    ///
    /// If any of the nodes does not exist, `false` is returned.
    pub fn contains_edge(&self, a: G::EdgeIndex) -> bool {
        self.mate.contains(Some(a))
    }

    /// Returns `true` if given node is in the matching, or `false` otherwise.
    ///
    /// If the node does not exist, `false` is returned.
    pub fn contains_node(&self, node: G::NodeIndex) -> bool {
        self.mate(node).is_some()
    }

    /// Gets the number of matched **edges**.
    pub fn len(&self) -> usize {
        self.mate
            .iter()
            .filter(|&&mate| mate.is_some())
            .collect::<HashSet<_>>().len()
    }

    /// Returns `true` if the number of matched **edges** is 0.
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }
}

impl<'a, G> Matching<'a, G>
where
    G: GraphProperties<'a>
{
    /// Returns `true` if the matching is perfect.
    ///
    /// A matching is
    /// [*perfect*](https://en.wikipedia.org/wiki/Matching_(graph_theory)#Definitions)
    /// if every node in the graph is incident to an edge from the matching.
    pub fn is_perfect(&self) -> bool {
        !self.mate.contains(None)
    }
}

// trait WithDummy: NodeIndexable {
//     fn dummy_idx(&self) -> usize;
//     fn node_bound_with_dummy(&self) -> usize;
//     /// Convert `i` to a node index, returns None for the dummy node
//     fn try_from_index(&self, i: usize) -> Option<Self::NodeId>;
// }

// impl<G: NodeIndexable> WithDummy for G {
//     fn dummy_idx(&self) -> usize {
//         // Gabow numbers the vertices from 1 to n, and uses 0 as the dummy
//         // vertex. Our vertex indices are zero-based and so we use the node
//         // bound as the dummy node.
//         self.node_bound()
//     }

//     fn node_bound_with_dummy(&self) -> usize {
//         self.node_bound() + 1
//     }

//     fn try_from_index(&self, i: usize) -> Option<Self::NodeId> {
//         if i != self.dummy_idx() {
//             Some(self.from_index(i))
//         } else {
//             None
//         }
//     }
// }

pub struct MatchedNodes<'a, G: GraphBasics<'a>> {
    graph: &'a G,
    mate: &'a [Option<G::EdgeIndex>],
    current: usize,
}

impl<'a, G> Iterator for MatchedNodes<'a, G>
where
    G: GraphBasics<'a>,
{
    type Item = (G::NodeIndex, G::NodeRef);

    fn next(&mut self) -> Option<Self::Item> {
        while self.current != self.mate.len() {
            let current = self.current;
            self.current += 1;

            if self.mate[current].is_some() {
                return Some((current, self.graph.node(current)));
            }
        }

        None
    }
}

pub struct MatchedEdges<'a, G: GraphBasics<'a>> {
    graph: &'a G,
    mate: HashMap<usize, G::EdgeIndex>,
    // current: usize,
}

impl<'a, G> Iterator for MatchedEdges<'a, G>
where
    G: GraphBasics<'a>,
{
    type Item = (G::EdgeIndex, G::EdgeRef);

    fn next(&mut self) -> Option<Self::Item> {
        // self.mate.next().map(|edge| (edge, self.graph.edge(edge)))
        while self.current != self.mate.len() {
            let current = self.current;
            self.current += 1;

            if self.mate[current].is_some() {
                return Some((current, self.graph.node(current)));
            }
        }

        None

    }
}

/// \[Generic\] Compute a
/// [*matching*](https://en.wikipedia.org/wiki/Matching_(graph_theory)) using a
/// greedy heuristic.
///
/// The input graph is treated as if undirected. The underlying heuristic is
/// unspecified, but is guaranteed to be bounded by *O(|V| + |E|)*. No
/// guarantees about the output are given other than that it is a valid
/// matching.
///
/// If you require a maximum matching, use [`maximum_matching`][1] function
/// instead.
///
/// [1]: fn.maximum_matching.html
pub fn greedy_matching<'a, G>(graph: &G) -> Matching<'a, G>
where
    G: GraphProperties<'a>,
{
    let (mates, n_edges) = greedy_matching_inner(graph);
    Matching { graph, mate: mates }
}

#[inline]
fn greedy_matching_inner<G>(graph: &G) -> (Vec<Option<<G as GraphBasics<'_>>::NodeIndex>>, usize)
where
    G: GraphProperties,
{
    let mut mate = vec![None; graph.node_bound()];
    let mut n_edges = 0;
    let visited = &mut graph.visit_map();

    for start in graph.node_identifiers() {
        let mut last = Some(start);

        // Function non_backtracking_dfs does not expand the node if it has been
        // already visited.
        non_backtracking_dfs(graph, start, visited, |next| {
            // Alternate matched and unmatched edges.
            if let Some(pred) = last.take() {
                mate[graph.to_index(pred)] = Some(next);
                mate[graph.to_index(next)] = Some(pred);
                n_edges += 1;
            } else {
                last = Some(next);
            }
        });
    }

    (mate, n_edges)
}

fn non_backtracking_dfs<G, F>(graph: &G, source: <G as GraphBasics<'_>>::NodeIndex, visited: &mut FixedBitSet, mut visitor: F)
where
    G: GraphProperties,
    F: FnMut(<G as GraphBasics<'_>>::NodeIndex),
{
    if visited.visit(source) {
        for target in graph.neighbors(source) {
            if !visited.is_visited(&target) {
                visitor(target);
                non_backtracking_dfs(graph, target, visited, visitor);

                // Non-backtracking traversal, stop iterating over the
                // neighbors.
                break;
            }
        }
    }
}

#[derive(Clone, Copy)]
enum Label<'a, G: GraphBasics<'a>> {
    None,
    Start,
    // If node v is outer node, then label(v) = w is another outer node on path
    // from v to start u.
    Vertex(G::NodeIndex),
    // If node v is outer node, then label(v) = (r, s) are two outer vertices
    // (connected by an edge)
    Edge(G::EdgeIndex, [G::NodeIndex; 2]),
    // Flag is a special label used in searching for the join vertex of two
    // paths.
    Flag(G::EdgeIndex),
}

impl<'a, G: GraphBasics<'a>> Label<'a, G> {
    fn is_outer(&self) -> bool {
        self != &Label::None
            && !match self {
                Label::Flag(_) => true,
                _ => false,
            }
    }

    fn is_inner(&self) -> bool {
        !self.is_outer()
    }

    fn to_vertex(&self) -> Option<G::NodeIndex> {
        match *self {
            Label::Vertex(v) => Some(v),
            _ => None,
        }
    }

    fn is_flagged(&self, edge: G::EdgeIndex) -> bool {
        match self {
            Label::Flag(flag) if flag == &edge => true,
            _ => false,
        }
    }
}

impl<'a, G: GraphBasics<'a>> Default for Label<'a, G> {
    fn default() -> Self {
        Label::None
    }
}

impl<'a, G: GraphBasics<'a>> PartialEq for Label<'a, G> {
    fn eq(&self, other: &Self) -> bool {
        match (self, other) {
            (Label::None, Label::None) => true,
            (Label::Start, Label::Start) => true,
            (Label::Vertex(v1), Label::Vertex(v2)) => v1 == v2,
            (Label::Edge(e1, _), Label::Edge(e2, _)) => e1 == e2,
            (Label::Flag(e1), Label::Flag(e2)) => e1 == e2,
            _ => false,
        }
    }
}

/// \[Generic\] Compute the [*maximum
/// matching*](https://en.wikipedia.org/wiki/Matching_(graph_theory)) using
/// [Gabow's algorithm][1].
///
/// [1]: https://dl.acm.org/doi/10.1145/321941.321942
///
/// The input graph is treated as if undirected. The algorithm runs in
/// *O(|V|³)*. An algorithm with a better time complexity might be used in the
/// future.
///
/// **Panics** if `g.node_bound()` is `std::usize::MAX`.
///
/// # Examples
///
/// ```
/// use petgraph::prelude::*;
/// use petgraph::algo::maximum_matching;
///
/// // The example graph:
/// //
/// //    +-- b ---- d ---- f
/// //   /    |      |
/// //  a     |      |
/// //   \    |      |
/// //    +-- c ---- e
/// //
/// // Maximum matching: { (a, b), (c, e), (d, f) }
///
/// let mut graph: UnGraph<(), ()> = UnGraph::new_undirected();
/// let a = graph.add_node(());
/// let b = graph.add_node(());
/// let c = graph.add_node(());
/// let d = graph.add_node(());
/// let e = graph.add_node(());
/// let f = graph.add_node(());
/// graph.extend_with_edges(&[(a, b), (a, c), (b, c), (b, d), (c, e), (d, e), (d, f)]);
///
/// let matching = maximum_matching(&graph);
/// assert!(matching.contains_edge(a, b));
/// assert!(matching.contains_edge(c, e));
/// assert_eq!(matching.mate(d), Some(f));
/// assert_eq!(matching.mate(f), Some(d));
/// ```
pub fn maximum_matching<'a, G>(graph: &G) -> Matching<'a, G>
where
    G: GraphProperties
{
    // The dummy identifier needs an unused index
    assert_ne!(
        graph.node_bound(),
        std::usize::MAX,
        "The input graph capacity should be strictly less than std::usize::MAX."
    );

    // Greedy algorithm should create a fairly good initial matching. The hope
    // is that it speeds up the computation by doing les work in the complex
    // algorithm.
    let (mut mate, mut n_edges) = greedy_matching_inner(graph);

    // Gabow's algorithm uses a dummy node in the mate array.
    mate.push(None);
    let len = graph.node_bound() + 1;
    debug_assert_eq!(mate.len(), len);

    let mut label: Vec<Label<G>> = vec![Label::None; len];
    let mut first_inner = vec![std::usize::MAX; len];
    let visited = &mut graph.visit_map();

    for start in 0..graph.node_bound() {
        if mate[start].is_some() {
            // The vertex is already matched. A start must be a free vertex.
            continue;
        }

        // Begin search from the node.
        label[start] = Label::Start;
        first_inner[start] = graph.dummy_idx();
        graph.reset_map(visited);

        // start is never a dummy index
        let start = graph.from_index(start);

        // Queue will contain outer vertices that should be processed next. The
        // start vertex is considered an outer vertex.
        let mut queue = VecDeque::new();
        queue.push_back(start);
        // Mark the start vertex so it is not processed repeatedly.
        visited.visit(start);

        'search: while let Some(outer_vertex) = queue.pop_front() {
            for edge in graph.incident_edges(outer_vertex) {
                if edge.source() == edge.target() {
                    // Ignore self-loops.
                    continue;
                }

                let other_vertex = edge.target();
                let other_idx = graph.to_index(other_vertex);

                if mate[other_idx].is_none() && other_vertex != start {
                    // An augmenting path was found. Augment the matching. If
                    // `other` is actually the start node, then the augmentation
                    // must not be performed, because the start vertex would be
                    // incident to two edges, which violates the matching
                    // property.
                    mate[other_idx] = Some(outer_vertex);
                    augment_path(graph, outer_vertex, other_vertex, &mut mate, &label);
                    n_edges += 1;

                    // The path is augmented, so the start is no longer free
                    // vertex. We need to begin with a new start.
                    break 'search;
                } else if label[other_idx].is_outer() {
                    // The `other` is an outer vertex (a label has been set to
                    // it). An odd cycle (blossom) was found. Assign this edge
                    // as a label to all inner vertices in paths P(outer) and
                    // P(other).
                    find_join(
                        graph,
                        edge,
                        &mate,
                        &mut label,
                        &mut first_inner,
                        |labeled| {
                            if visited.visit(labeled) {
                                queue.push_back(labeled);
                            }
                        },
                    );
                } else {
                    let mate_vertex = mate[other_idx];
                    let mate_idx = mate_vertex.map_or(graph.dummy_idx(), |id| graph.to_index(id));

                    if label[mate_idx].is_inner() {
                        // Mate of `other` vertex is inner (no label has been
                        // set to it so far). But it actually is an outer vertex
                        // (it is on a path to the start vertex that begins with
                        // a matched edge, since it is a mate of `other`).
                        // Assign the label of this mate to the `outer` vertex,
                        // so the path for it can be reconstructed using `mate`
                        // and this label.
                        label[mate_idx] = Label::Vertex(outer_vertex);
                        first_inner[mate_idx] = other_idx;
                    }

                    // Add the vertex to the queue only if it's not the dummy and this is its first
                    // discovery.
                    if let Some(mate_vertex) = mate_vertex {
                        if visited.visit(mate_vertex) {
                            queue.push_back(mate_vertex);
                        }
                    }
                }
            }
        }

        // Reset the labels. All vertices are inner for the next search.
        for lbl in label.iter_mut() {
            *lbl = Label::None;
        }
    }

    // Discard the dummy node.
    mate.pop();

    Matching {
        graph,
        mate,
    }
}

fn find_join<G, F>(
    graph: &G,
    edge: <G as GraphBasics<'_>>::EdgeRef,
    mate: &[Option<<G as GraphBasics<'_>>::NodeIndex>],
    label: &mut [Label<G>],
    first_inner: &mut [usize],
    mut visitor: F,
) where
    G: GraphProperties,
    F: FnMut(<G as GraphBasics<'_>>::NodeIndex),
{
    // Simultaneously traverse the inner vertices on paths P(source) and
    // P(target) to find a join vertex - an inner vertex that is shared by these
    // paths.
    let source = graph.to_index(edge.source());
    let target = graph.to_index(edge.target());

    let mut left = first_inner[source];
    let mut right = first_inner[target];

    if left == right {
        // No vertices can be labeled, since both paths already refer to a
        // common vertex - the join.
        return;
    }

    // Flag the (first) inner vertices. This ensures that they are assigned the
    // join as their first inner vertex.
    let flag = Label::Flag(edge.id());
    label[left] = flag;
    label[right] = flag;

    // Find the join.
    let join = loop {
        // Swap the sides. Do not swap if the right side is already finished.
        if right != graph.dummy_idx() {
            std::mem::swap(&mut left, &mut right);
        }

        // Set left to the next inner vertex in P(source) or P(target).
        // The unwraps are safe because left is not the dummy node.
        let left_mate = graph.to_index(mate[left].unwrap());
        let next_inner = label[left_mate].to_vertex().unwrap();
        left = first_inner[graph.to_index(next_inner)];

        if !label[left].is_flagged(edge.id()) {
            // The inner vertex is not flagged yet, so flag it.
            label[left] = flag;
        } else {
            // The inner vertex is already flagged. It means that the other side
            // had to visit it already. Therefore it is the join vertex.
            break left;
        }
    };

    // Label all inner vertices on P(source) and P(target) with the found join.
    for endpoint in [source, target].iter().copied() {
        let mut inner = first_inner[endpoint];
        while inner != join {
            // Notify the caller about labeling a vertex.
            if let Some(ix) = graph.try_from_index(inner) {
                visitor(ix);
            }

            label[inner] = Label::Edge(edge.id(), [edge.source(), edge.target()]);
            first_inner[inner] = join;
            let inner_mate = graph.to_index(mate[inner].unwrap());
            let next_inner = label[inner_mate].to_vertex().unwrap();
            inner = first_inner[graph.to_index(next_inner)];
        }
    }

    for (vertex_idx, vertex_label) in label.iter().enumerate() {
        // To all outer vertices that are on paths P(source) and P(target) until
        // the join, se the join as their first inner vertex.
        if vertex_idx != graph.dummy_idx()
            && vertex_label.is_outer()
            && label[first_inner[vertex_idx]].is_outer()
        {
            first_inner[vertex_idx] = join;
        }
    }
}

fn augment_path<'a, G>(
    graph: &'a G,
    outer: G::NodeIndex,
    other: G::NodeIndex,
    mate: &mut [Option<G::NodeIndex>],
    label: &[Label<'a, G>],
) where
    G: GraphProperties<'a>,
{
    let outer_idx = graph.to_index(outer);

    let temp = mate[outer_idx];
    let temp_idx = temp.map_or(graph.dummy_idx(), |id| graph.to_index(id));
    mate[outer_idx] = Some(other);

    if mate[temp_idx] != Some(outer) {
        // We are at the end of the path and so the entire path is completely
        // rematched/augmented.
    } else if let Label::Vertex(vertex) = label[outer_idx] {
        // The outer vertex has a vertex label which refers to another outer
        // vertex on the path. So we set this another outer node as the mate for
        // the previous mate of the outer node.
        mate[temp_idx] = Some(vertex);
        if let Some(temp) = temp {
            augment_path(graph, vertex, temp, mate, label);
        }
    } else if let Label::Edge(_, [source, target]) = label[outer_idx] {
        // The outer vertex has an edge label which refers to an edge in a
        // blossom. We need to augment both directions along the blossom.
        augment_path(graph, source, target, mate, label);
        augment_path(graph, target, source, mate, label);
    } else {
        panic!("Unexpected label when augmenting path");
    }
}