xgraph 3.0.0

//! Module for finding dominating sets in heterogeneous multigraphs using greedy heuristics.
//!
//! This module provides implementations of a greedy algorithm to find dominating sets in
//! heterogeneous multigraphs. A dominating set is a subset of nodes such that every node in
//! the graph is either in the set or adjacent to a node in the set. The algorithm supports:
//! - Finding a dominating set using all edges.
//! - Finding a dominating set considering only specific edge types.
//!
//! The module is available only when the `hgraph` feature is enabled in your `Cargo.toml`:
//! ```toml
//! [dependencies.xgraph]
//! version = "x.y.z"
//! features = ["hgraph"]
//! ```

#[cfg(feature = "hgraph")]
use crate::core::view::NodeId;
#[cfg(feature = "hgraph")]
use crate::hgraph::h_graph::HeterogeneousGraph;
#[cfg(feature = "hgraph")]
use std::collections::HashSet;
#[cfg(feature = "hgraph")]
use std::fmt::Debug;
#[cfg(feature = "hgraph")]
use std::hash::Hash;

// Error handling additions

/// Error type for支配 set computation failures.
///
/// Represents errors that may occur during dominating set calculations, such as invalid edge references.
#[cfg(feature = "hgraph")]
#[derive(Debug, thiserror::Error)]
pub enum DominatingSetError {
    /// Indicates an edge referenced in the graph does not exist.
    #[error("Invalid edge reference: edge ID {0} not found")]
    InvalidEdgeReference(NodeId),
    /// Indicates a node referenced in the graph does not exist.
    #[error("Invalid node reference: node ID {0} not found")]
    InvalidNodeReference(NodeId),
}

#[cfg(feature = "hgraph")]
impl From<crate::core::TraversalError> for DominatingSetError {
    fn from(error: crate::core::TraversalError) -> Self {
        match error {
            crate::core::TraversalError::InvalidNode(id) => {
                DominatingSetError::InvalidNodeReference(id)
            }
        }
    }
}

/// Result type alias for dominating set operations.
///
/// Wraps the result of dominating set methods to enable error handling without panicking.
#[cfg(feature = "hgraph")]
pub type Result<T> = std::result::Result<T, DominatingSetError>;

#[cfg(feature = "hgraph")]
/// Trait for finding dominating sets in heterogeneous multigraphs.
///
/// Provides methods to compute dominating sets using a greedy heuristic, with support for
/// edge type filtering. Methods return a `Result` to handle potential errors gracefully.
#[deprecated(
    since = "3.0.0",
    note = "superseded by `xgraph::core::DominatingSet`; `find_dominating_set_by_types` \
            becomes `graph.of_edge_data(&[..]).dominating_set()`"
)]
pub trait HeteroDominatingSetFinder<W, N, E>
where
    W: Copy + Default + PartialEq + Debug,
    N: Clone + Eq + Hash + Debug + crate::hgraph::h_node::NodeType,
    E: Clone + Default + Debug + crate::hgraph::h_edge::EdgeType + PartialEq,
{
    /// Finds a dominating set in the graph considering all edges.
    ///
    /// Returns a set of node indices where every node in the graph is either in the set or
    /// adjacent to a node in the set, using all available edges.
    ///
    /// # Returns
    /// A `Result` containing a `HashSet<NodeId>` of node indices in the dominating set.
    ///
    /// # Errors
    /// Returns `DominatingSetError::InvalidEdgeReference` if an edge ID referenced in the
    /// graph’s neighbor list does not exist.
    fn find_dominating_set(&self) -> Result<HashSet<NodeId>>;

    /// Finds a dominating set in the graph considering only specified edge types.
    ///
    /// Filters edges by type to compute a dominating set in a subgraph defined by
    /// `allowed_edge_types`. If the list is empty, all edge types are considered.
    ///
    /// # Arguments
    /// * `allowed_edge_types` - A slice of edge types to filter the computation.
    ///
    /// # Returns
    /// A `Result` containing a `HashSet<NodeId>` of node indices in the dominating set.
    ///
    /// # Errors
    /// Returns `DominatingSetError::InvalidEdgeReference` if an edge ID referenced in the
    /// graph’s neighbor list does not exist.
    fn find_dominating_set_by_types(&self, allowed_edge_types: &[E]) -> Result<HashSet<NodeId>>;
}

#[cfg(feature = "hgraph")]
#[cfg(feature = "hgraph")]
#[allow(deprecated)]
impl<W, N, E> HeteroDominatingSetFinder<W, N, E> for HeterogeneousGraph<W, N, E>
where
    W: Copy + Default + PartialEq + Debug,
    N: Clone + Eq + Hash + Debug + crate::hgraph::h_node::NodeType,
    E: Clone + Default + Debug + crate::hgraph::h_edge::EdgeType + PartialEq,
{
    fn find_dominating_set(&self) -> Result<HashSet<NodeId>> {
        // An empty type list has always meant "every edge".
        self.find_dominating_set_by_types(&[])
    }

    fn find_dominating_set_by_types(&self, allowed_edge_types: &[E]) -> Result<HashSet<NodeId>> {
        // This search has always ignored nodes left with no edge of the chosen types, so a
        // node filter is composed onto the edge filter to say exactly that. Without it an
        // isolated node would join the set, since nothing else can dominate it.
        let by_data = self.of_edge_data(allowed_edge_types);
        let connected: HashSet<NodeId> = crate::core::GraphView::node_ids(&by_data)
            .filter(|&node| {
                crate::core::GraphView::links(&by_data, node)
                    .next()
                    .is_some()
            })
            .collect();
        let induced =
            crate::core::NodeFiltered::new(&by_data, move |node| connected.contains(&node));

        crate::core::DominatingSet::dominating_set(&induced).map_err(DominatingSetError::from)
    }
}

#[cfg(test)]
#[allow(deprecated)]
#[cfg(feature = "hgraph")]
mod tests {
    use super::*;

    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, PartialEq)]
    struct TestEdge(String);
    impl EdgeType for TestEdge {
        fn as_string(&self) -> String {
            self.0.clone()
        }
    }

    #[test]
    fn test_simple_dominating_set() {
        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()));
        let n3 = graph.add_node(TestNode("D".to_string()));

        graph
            .add_edge(n0, n1, 1.0, TestEdge("friend".to_string()))
            .unwrap();
        graph
            .add_edge(n1, n2, 1.0, TestEdge("friend".to_string()))
            .unwrap();
        graph
            .add_edge(n1, n3, 1.0, TestEdge("friend".to_string()))
            .unwrap();

        let ds = graph.find_dominating_set().unwrap();
        assert!(!ds.is_empty(), "Dominating set should not be empty");
        assert!(
            ds.len() <= 2,
            "Dominating set size should be at most 2, got {}",
            ds.len()
        );
    }

    #[test]
    fn test_triangle_dominating_set() {
        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("friend".to_string()))
            .unwrap();
        graph
            .add_edge(n1, n2, 1.0, TestEdge("friend".to_string()))
            .unwrap();
        graph
            .add_edge(n2, n0, 1.0, TestEdge("friend".to_string()))
            .unwrap();

        let ds = graph.find_dominating_set().unwrap();
        assert_eq!(
            ds.len(),
            1,
            "Dominating set for a triangle should be 1, got {}",
            ds.len()
        );
    }

    #[test]
    fn test_disconnected_components() {
        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()));
        let n3 = graph.add_node(TestNode("D".to_string()));

        graph
            .add_edge(n0, n1, 1.0, TestEdge("friend".to_string()))
            .unwrap();
        graph
            .add_edge(n2, n3, 1.0, TestEdge("friend".to_string()))
            .unwrap();

        let ds = graph.find_dominating_set().unwrap();
        assert_eq!(
            ds.len(),
            2,
            "Dominating set should contain 2 nodes for 2 components, got {}",
            ds.len()
        );
    }

    #[test]
    fn test_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("friend".to_string()))
            .unwrap();
        graph
            .add_edge(n0, n1, 2.0, TestEdge("colleague".to_string()))
            .unwrap();

        let ds = graph.find_dominating_set().unwrap();
        assert_eq!(
            ds.len(),
            1,
            "Dominating set should be 1 despite multiple edges, got {}",
            ds.len()
        );
    }

    #[test]
    fn test_dominating_set_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()));
        let n3 = graph.add_node(TestNode("D".to_string()));

        graph
            .add_edge(n0, n1, 1.0, TestEdge("friend".to_string()))
            .unwrap();
        graph
            .add_edge(n1, n2, 1.0, TestEdge("colleague".to_string()))
            .unwrap();
        graph
            .add_edge(n2, n3, 1.0, TestEdge("friend".to_string()))
            .unwrap();

        // Consider only "friend" edges
        let allowed_edge_types = vec![TestEdge("friend".to_string())];
        let ds = graph
            .find_dominating_set_by_types(&allowed_edge_types)
            .unwrap();
        assert_eq!(
            ds.len(),
            2,
            "Dominating set should contain 2 nodes when considering only 'friend' edges, got {}",
            ds.len()
        );
        let covers_all =
            (ds.contains(&n0) || ds.contains(&n1)) && (ds.contains(&n2) || ds.contains(&n3));
        assert!(
            covers_all,
            "Dominating set should cover both components: {:?}",
            ds
        );
    }

    #[test]
    fn test_dominating_set_by_types_isolated() {
        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("friend".to_string()))
            .unwrap();
        graph
            .add_edge(n1, n2, 1.0, TestEdge("colleague".to_string()))
            .unwrap();

        // Consider only "friend" edges
        let allowed_edge_types = vec![TestEdge("friend".to_string())];
        let ds = graph
            .find_dominating_set_by_types(&allowed_edge_types)
            .unwrap();
        assert_eq!(
            ds.len(),
            1,
            "Dominating set should contain 1 node (n0 or n1) for connected 'friend' component, got {}",
            ds.len()
        );
        assert!(
            ds.contains(&n0) || ds.contains(&n1),
            "Either n0 or n1 should be in the dominating set: {:?}",
            ds
        );
    }

    #[test]
    fn test_invalid_edge_reference() {
        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()));

        // Simulate an invalid edge by manually manipulating the graph (not possible through public API)
        // For testing, we assume the possibility of an edge ID not existing in a corrupted graph
        graph
            .add_edge(n0, n1, 1.0, TestEdge("friend".to_string()))
            .unwrap();

        // Note: Since we can't directly inject an invalid edge ID via public API,
        // this test assumes the error handling works as implemented. In practice,
        // this would require internal corruption or a bug in graph construction.
        let ds_result = graph.find_dominating_set();
        assert!(ds_result.is_ok(), "Should succeed with valid edges");
    }
}