petgraph 0.8.3

use crate::visit::{
    EdgeRef, IntoEdgeReferences, IntoNeighbors, IntoNodeIdentifiers, NodeIndexable,
};

use alloc::{vec, vec::Vec};

/// Find all [bridges](https://en.wikipedia.org/wiki/Bridge_(graph_theory)) in a simple undirected graph.
///
/// # Arguments
/// * `graph`: a simple undirected graph.
///
/// # Returns
/// * `impl Iterator`:  the iterator of edge references `G::EdgeRef` representing the edges
///   of the input graph that are bridges. The order of the edges is arbitrary.
///
/// # Complexity
/// * Time complexity: **O(|V| + |E|)**.
/// * Auxiliary space: **O(|V|)**.
///
/// where **|V|** is the number of nodes and **|E|** is the number of edges.
///
///
/// # Examples
///
/// ```
/// use petgraph::algo::bridges::bridges;
/// use petgraph::graph::UnGraph;
/// use petgraph::visit::EdgeRef;
///
/// // Create the following graph:
/// // 0----1    4
/// //      | __/|
/// // 5----2/---3
///
/// let mut g = UnGraph::new_undirected();
/// let n0 = g.add_node(());
/// let n1 = g.add_node(());
/// let n2 = g.add_node(());
/// let n3 = g.add_node(());
/// let n4 = g.add_node(());
/// let n5 = g.add_node(());
/// let e0 = g.add_edge(n0, n1, ());
/// let e1 = g.add_edge(n1, n2, ());
/// let e2 = g.add_edge(n2, n3, ());
/// let e3 = g.add_edge(n3, n4, ());
/// let e4 = g.add_edge(n2, n4, ());
/// let e5 = g.add_edge(n5, n2, ());
///
/// let bridges: Vec<_> = bridges(&g).map(|edge_ref| edge_ref.id()).collect();
///
/// // The bridges in this graph are the undirected edges {2, 5}, {1, 2}, {0, 1}.
/// assert_eq!(bridges, vec![e0, e1, e5]);
/// ```
pub fn bridges<G>(graph: G) -> impl Iterator<Item = G::EdgeRef>
where
    G: IntoNodeIdentifiers + IntoNeighbors + NodeIndexable + IntoEdgeReferences,
{
    let mut clock: usize = 0usize;
    // If and when a node was visited by the dfs
    let mut visit_time = vec![None; graph.node_bound()];
    // Lowest time on a node that is the target of a back-edge from the subtree rooted
    // at the indexed node.
    let mut earliest_backedge = vec![usize::MAX; graph.node_bound()];

    for start in 0..graph.node_bound() {
        // If node hasn't been visited yet, make it the root of a new dfs-tree in the forest.
        if visit_time[start].is_none() {
            visit_time[start] = Some(clock);
            clock += 1;

            // Perform a DFS starting at start
            let start = graph.from_index(start);
            let mut stack: Vec<(G::NodeId, G::Neighbors)> = vec![(start, graph.neighbors(start))];

            while let Some((stack_frame, rest_of_stack)) = stack.split_last_mut() {
                let &mut (node, ref mut neighbors) = stack_frame;
                let parent = rest_of_stack.last().map(|&(n, _)| n);

                let node_index = graph.to_index(node);

                if let Some(child) = neighbors.next() {
                    // Pre-order DFS
                    if parent != Some(child) {
                        let child_index = graph.to_index(child);

                        if let Some(time) = visit_time[child_index] {
                            earliest_backedge[node_index] = earliest_backedge[node_index].min(time);
                        } else {
                            visit_time[child_index] = Some(clock);
                            clock += 1;
                            stack.push((child, graph.neighbors(child)));
                        }
                    }
                } else {
                    // Post-order DFS
                    if let Some(parent) = parent {
                        let parent_index = graph.to_index(parent);
                        earliest_backedge[parent_index] =
                            earliest_backedge[parent_index].min(earliest_backedge[node_index]);
                    }
                    stack.pop();
                }
            }
        }
    }

    graph.edge_references().filter(move |edge| {
        let source_index = graph.to_index(edge.source());
        let target_index = graph.to_index(edge.target());

        // All nodes have been visited by the time we return, so unwraps are safe.
        // The node with the lower visit time is the "parent" in the dfs-forest created above.
        let (parent, node) =
            if visit_time[source_index].unwrap() < visit_time[target_index].unwrap() {
                (source_index, target_index)
            } else {
                (target_index, source_index)
            };

        // If there's no back-edge to before parent, then this the only way from parent to here
        // is directly from parent, so it's a bridge edge.
        earliest_backedge[node] > visit_time[parent].unwrap()
    })
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::graph::EdgeReference;
    use crate::graph::UnGraph;
    use crate::visit::EdgeRef;

    #[test]
    fn test_bridges() {
        let mut g = UnGraph::<i8, i8>::new_undirected();
        let bridge_nodes = |g: &_| {
            bridges(g)
                .map(|e: EdgeReference<_>| (e.source(), e.target()))
                .collect::<Vec<_>>()
        };

        assert_eq!(bridge_nodes(&g), vec![]);
        let n0 = g.add_node(0);
        assert_eq!(bridge_nodes(&g), vec![]);
        let n1 = g.add_node(1);
        assert_eq!(bridge_nodes(&g), vec![]);
        g.add_edge(n0, n1, 0);
        assert_eq!(bridge_nodes(&g), vec![(n0, n1)]);
        let n2 = g.add_node(2);
        assert_eq!(bridge_nodes(&g), vec![(n0, n1)]);
        g.add_edge(n2, n1, 1);
        assert_eq!(bridge_nodes(&g), vec![(n0, n1), (n2, n1)]);
        g.add_edge(n0, n2, 2);
        assert_eq!(bridge_nodes(&g), vec![]);
        let n3 = g.add_node(3);
        let n4 = g.add_node(4);
        g.add_edge(n2, n3, 3);
        g.add_edge(n3, n4, 4);
        assert_eq!(bridge_nodes(&g), vec![(n2, n3), (n3, n4)]);
        g.add_edge(n3, n0, 5);
        assert_eq!(bridge_nodes(&g), vec![(n3, n4)]);
    }
}