xgraph 3.0.0

//! Bridge detection algorithms for heterogeneous multigraphs.
//!
//! This module provides efficient algorithms to identify bridges in a heterogeneous multigraph.
//! A bridge is an edge whose removal increases the number of connected components in the graph.

#[cfg(feature = "hgraph")]
use crate::core::view::{EdgeId, NodeId};
#[cfg(feature = "hgraph")]
use crate::hgraph::h_graph::HeterogeneousGraph;
#[cfg(feature = "hgraph")]
use std::collections::{HashMap, HashSet};
#[cfg(feature = "hgraph")]
use std::fmt::Debug;

#[cfg(feature = "hgraph")]
#[derive(Debug)]
pub struct BridgeContext {
    visited: HashSet<NodeId>,
    discovery: HashMap<NodeId, u32>,
    lowest: HashMap<NodeId, u32>,
    #[allow(dead_code)]
    parent: HashMap<NodeId, NodeId>,
    bridges: Vec<(NodeId, NodeId, String)>, // (from, to, edge_type)
    time: u32,
}

#[cfg(feature = "hgraph")]
impl BridgeContext {
    /// Creates a new `BridgeContext` with empty state for bridge detection.
    pub fn new() -> Self {
        Self {
            visited: HashSet::new(),
            discovery: HashMap::new(),
            lowest: HashMap::new(),
            parent: HashMap::new(),
            bridges: Vec::new(),
            time: 0,
        }
    }
}

impl Default for BridgeContext {
    fn default() -> Self {
        Self::new()
    }
}

#[cfg(feature = "hgraph")]
#[deprecated(
    since = "3.0.0",
    note = "superseded by `xgraph::core::Bridges`; `find_bridges_by_types` becomes \
            `graph.of_edge_kinds(&[..]).bridges()`"
)]
pub trait HeteroBridges {
    /// Finds all bridges in the graph, considering all edges.
    fn find_bridges(&self) -> Vec<(NodeId, NodeId, String)>;

    /// Sorts bridges by node indices and edge type for consistent output.
    fn sort_bridges(bridges: &mut Vec<(NodeId, NodeId, String)>);

    /// Internal DFS method for bridge detection.
    fn bridge_dfs(&self, node: NodeId, context: &mut BridgeContext);

    fn find_bridges_by_types(&self, edge_types: &[&str]) -> Vec<(NodeId, NodeId, String)>;
    fn bridge_dfs_filtered_by_types(
        &self,
        node: NodeId,
        context: &mut BridgeContext,
        edge_types: &[&str],
    );
}

#[cfg(feature = "hgraph")]
#[cfg(feature = "hgraph")]
#[allow(deprecated)]
impl<W, N, E> HeteroBridges for HeterogeneousGraph<W, N, E>
where
    W: Copy + Default + PartialEq + Debug,
    N: crate::hgraph::h_node::NodeType,
    E: crate::hgraph::h_edge::EdgeType + Default,
{
    fn find_bridges(&self) -> Vec<(NodeId, NodeId, String)> {
        self.labelled_bridges(crate::core::Bridges::bridge_edges(self).unwrap_or_default())
    }

    fn find_bridges_by_types(&self, edge_types: &[&str]) -> Vec<(NodeId, NodeId, String)> {
        let edges =
            crate::core::Bridges::bridge_edges(&self.of_edge_kinds(edge_types)).unwrap_or_default();
        self.labelled_bridges(edges)
    }

    fn sort_bridges(bridges: &mut Vec<(NodeId, NodeId, String)>) {
        bridges.iter_mut().for_each(|(u, v, _)| {
            if u > v {
                std::mem::swap(u, v);
            }
        });
        bridges.sort_unstable_by(|(u1, v1, t1), (u2, v2, t2)| {
            u1.cmp(u2).then_with(|| v1.cmp(v2)).then_with(|| t1.cmp(t2))
        });
    }

    fn bridge_dfs(&self, node: NodeId, context: &mut BridgeContext) {
        let mut state = crate::core::TarjanState::default();
        if crate::core::Bridges::tarjan_from(self, node, &mut state).is_err() {
            return;
        }

        context.visited.extend(state.discovery.keys().copied());
        // `BridgeContext` counts in `u32`; the shared state counts in `NodeId`.
        context
            .discovery
            .extend(state.discovery.iter().map(|(&k, &v)| (k, v as u32)));
        context
            .lowest
            .extend(state.low.iter().map(|(&k, &v)| (k, v as u32)));
        context.time = state.time as u32;
        context.bridges.extend(self.labelled_bridges(state.bridges));
    }

    fn bridge_dfs_filtered_by_types(
        &self,
        node: NodeId,
        context: &mut BridgeContext,
        edge_types: &[&str],
    ) {
        let filtered = self.of_edge_kinds(edge_types);
        let mut state = crate::core::TarjanState::default();
        if crate::core::Bridges::tarjan_from(&filtered, node, &mut state).is_err() {
            return;
        }

        context.visited.extend(state.discovery.keys().copied());
        // `BridgeContext` counts in `u32`; the shared state counts in `NodeId`.
        context
            .discovery
            .extend(state.discovery.iter().map(|(&k, &v)| (k, v as u32)));
        context
            .lowest
            .extend(state.low.iter().map(|(&k, &v)| (k, v as u32)));
        context.time = state.time as u32;
        context.bridges.extend(self.labelled_bridges(state.bridges));
    }
}

#[cfg(feature = "hgraph")]
impl<W, N, E> HeterogeneousGraph<W, N, E>
where
    W: Copy + Default + PartialEq + Debug,
    N: crate::hgraph::h_node::NodeType,
    E: crate::hgraph::h_edge::EdgeType + Default,
{
    /// Turns bridge edge IDs into the `(from, to, kind)` triples this module reports,
    /// normalized and sorted so the output is reproducible.
    fn labelled_bridges(&self, edges: Vec<EdgeId>) -> Vec<(NodeId, NodeId, String)> {
        let mut bridges: Vec<(NodeId, NodeId, String)> = edges
            .into_iter()
            .filter_map(|edge| {
                let (from, to) = crate::core::GraphView::edge_endpoints(self, edge)?;
                let kind = self.edge_kind(edge)?;
                Some(if from <= to {
                    (from, to, kind)
                } else {
                    (to, from, kind)
                })
            })
            .collect();
        bridges.sort_unstable_by(|(u1, v1, t1), (u2, v2, t2)| {
            u1.cmp(u2).then_with(|| v1.cmp(v2)).then_with(|| t1.cmp(t2))
        });
        bridges
    }
}

#[cfg(test)]
#[cfg(feature = "hgraph")]
#[allow(deprecated)]
mod tests {
    use super::*;
    use crate::core::view::NodeId;
    use crate::hgraph::h_edge::EdgeType;
    use crate::hgraph::h_node::NodeType;

    #[derive(Clone, Eq, PartialEq, Hash, Debug)]
    struct TestNode(String);
    impl NodeType for TestNode {
        fn as_string(&self) -> String {
            self.0.clone()
        }
    }

    #[derive(Clone, Debug, Default)]
    struct TestEdge(String);
    impl EdgeType for TestEdge {
        fn as_string(&self) -> String {
            self.0.clone()
        }
    }

    #[test]
    fn test_find_bridges_simple() {
        let mut graph = HeterogeneousGraph::<f64, TestNode, TestEdge>::new(false);
        let n0 = graph.add_node(TestNode("A".to_string()));
        let n1 = graph.add_node(TestNode("B".to_string()));
        let n2 = graph.add_node(TestNode("C".to_string()));

        graph
            .add_edge(n0, n1, 1.0, TestEdge("road".to_string()))
            .unwrap();
        graph
            .add_edge(n1, n2, 2.0, TestEdge("bridge".to_string()))
            .unwrap();

        let bridges = graph.find_bridges();
        assert_eq!(
            bridges,
            vec![(n0, n1, "road".to_string()), (n1, n2, "bridge".to_string())]
        );
    }

    #[test]
    fn test_find_bridges_by_types() {
        let mut graph = HeterogeneousGraph::<f64, TestNode, TestEdge>::new(false);
        let n0 = graph.add_node(TestNode("A".to_string()));
        let n1 = graph.add_node(TestNode("B".to_string()));
        let n2 = graph.add_node(TestNode("C".to_string()));

        graph
            .add_edge(n0, n1, 1.0, TestEdge("road".to_string()))
            .unwrap();
        graph
            .add_edge(n0, n1, 2.0, TestEdge("bridge".to_string()))
            .unwrap();
        graph
            .add_edge(n1, n2, 3.0, TestEdge("bridge".to_string()))
            .unwrap();
        graph
            .add_edge(n2, n0, 4.0, TestEdge("path".to_string()))
            .unwrap();

        // Restricted to "bridge" and "road", nodes 0 and 1 are joined by two parallel
        // edges. Removing either leaves the other, so neither is a bridge — only the lone
        // 1-2 edge is. The previous implementation reported all three, because it excluded
        // the parent *node* instead of the specific edge it had arrived on.
        let bridges = graph.find_bridges_by_types(&["bridge", "road"]);
        let expected_bridges = vec![(
            NodeId::from_index(1),
            NodeId::from_index(2),
            "bridge".to_string(),
        )];

        let bridges_set: HashSet<_> = bridges.into_iter().collect();
        let expected_set: HashSet<_> = expected_bridges.into_iter().collect();
        assert_eq!(bridges_set, expected_set);

        // Ищем мосты для типа "path"
        let bridges = graph.find_bridges_by_types(&["path"]);
        let expected_bridges = vec![(
            NodeId::from_index(0),
            NodeId::from_index(2),
            "path".to_string(),
        )];

        let bridges_set: HashSet<_> = bridges.into_iter().collect();
        let expected_set: HashSet<_> = expected_bridges.into_iter().collect();
        assert_eq!(bridges_set, expected_set);
    }

    #[test]
    fn test_find_bridges_cycle() {
        let mut graph = HeterogeneousGraph::<f64, TestNode, TestEdge>::new(false);
        let n0 = graph.add_node(TestNode("A".to_string()));
        let n1 = graph.add_node(TestNode("B".to_string()));
        let n2 = graph.add_node(TestNode("C".to_string()));

        graph
            .add_edge(n0, n1, 1.0, TestEdge("road".to_string()))
            .unwrap();
        graph
            .add_edge(n1, n2, 2.0, TestEdge("bridge".to_string()))
            .unwrap();
        graph
            .add_edge(n2, n0, 3.0, TestEdge("path".to_string()))
            .unwrap();

        let bridges = graph.find_bridges();
        assert!(bridges.is_empty());
    }

    #[test]
    fn test_find_bridges_multiple_edges() {
        let mut graph = HeterogeneousGraph::<f64, TestNode, TestEdge>::new(false);
        let n0 = graph.add_node(TestNode("A".to_string()));
        let n1 = graph.add_node(TestNode("B".to_string()));

        graph
            .add_edge(n0, n1, 1.0, TestEdge("road".to_string()))
            .unwrap();
        graph
            .add_edge(n0, n1, 2.0, TestEdge("bridge".to_string()))
            .unwrap();

        let bridges = graph.find_bridges();
        assert!(bridges.is_empty());
    }

    #[test]
    fn test_find_bridges_empty() {
        let graph = HeterogeneousGraph::<f64, TestNode, TestEdge>::new(false);
        let bridges = graph.find_bridges();
        assert!(bridges.is_empty());
    }
}