xgraph 3.0.0

Graph algorithms for Rust: shortest paths, centrality, connectivity, spanning trees and community detection, over directed, undirected and heterogeneous multigraphs
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179

//! Module for finding dominating sets in graphs using greedy heuristics
//!
//! This module provides functionality to compute minimum dominating sets in graphs—subsets of vertices
//! where every vertex in the graph is either in the set or adjacent to at least one vertex in the set.
//! It uses a greedy heuristic approach for efficiency, suitable for both directed and undirected graphs.
//!
//! # Features
//! - Greedy algorithm for finding dominating sets
//! - Support for graphs with varying node and edge types
//! - Comprehensive error handling for invalid graph states
//!
//! # Examples
//!
//! Basic usage with a simple triangle graph:
//! ```rust
//! use xgraph::graph::graph::Graph;
//! use xgraph::core::DominatingSet;
//!
//! let adjacency_matrix = vec![
//!     vec![0, 1, 1],
//!     vec![1, 0, 1],
//!     vec![1, 1, 0],
//! ];
//! let graph = Graph::from_adjacency_matrix(&adjacency_matrix, false, (), ()).unwrap();
//! let dominating_set = graph.dominating_set().unwrap();
//! assert!(dominating_set.len() == 1); // Any single node dominates a complete graph of 3
//! ```
//!
//! Real-world scenario with disconnected components:
//! ```rust
//! use xgraph::graph::graph::Graph;
//! use xgraph::core::DominatingSet;
//!
//! let adjacency_matrix = vec![
//!     vec![0, 1, 1, 0, 0, 0],
//!     vec![1, 0, 1, 0, 0, 0],
//!     vec![1, 1, 0, 0, 0, 0],
//!     vec![0, 0, 0, 0, 1, 1],
//!     vec![0, 0, 0, 1, 0, 1],
//!     vec![0, 0, 0, 1, 1, 0],
//! ];
//! let graph = Graph::from_adjacency_matrix(&adjacency_matrix, false, (), ()).unwrap();
//! let ds = graph.dominating_set().unwrap();
//! assert_eq!(ds.len(), 2); // One node from each triangle is needed
//! ```

use crate::core::view::NodeId;
use crate::graph::graph::Graph;
use std::collections::HashSet;
use std::fmt::Debug;
use std::hash::Hash;

/// Error type for dominating set computation failures.
///
/// Represents errors that may occur during the computation of a dominating set.
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, thiserror::Error)]
pub enum DominatingSetError {
    /// Indicates that a neighbor node referenced in the graph does not exist.
    #[error("Invalid neighbor node: node ID {0} not found")]
    InvalidNeighborNode(NodeId),
}

impl From<crate::core::TraversalError> for DominatingSetError {
    fn from(error: crate::core::TraversalError) -> Self {
        match error {
            crate::core::TraversalError::InvalidNode(id) => {
                DominatingSetError::InvalidNeighborNode(id)
            }
        }
    }
}

/// Trait for finding dominating sets in graphs.
///
/// Defines a method to compute a dominating set, ensuring every vertex is either in the set
/// or adjacent to a member of the set.
///
/// # Examples
/// Finding a dominating set in a star graph:
/// ```rust
/// use xgraph::core::{DominatingSet, NodeId};
/// use xgraph::graph::graph::Graph;
///
/// let adjacency_matrix = vec![
///     vec![0, 1, 1, 1],
///     vec![1, 0, 0, 0],
///     vec![1, 0, 0, 0],
///     vec![1, 0, 0, 0],
/// ];
/// let graph = Graph::from_adjacency_matrix(&adjacency_matrix, false, (), ()).unwrap();
/// let dominating_set = graph.dominating_set().unwrap();
/// assert!(dominating_set.len() == 1 && dominating_set.contains(&NodeId::from_index(0))); // Center node dominates all
/// ```
#[deprecated(
    since = "3.0.0",
    note = "superseded by `xgraph::core::DominatingSet`, which is implemented for every \
            graph view and can also verify a candidate set with `is_dominating_set`"
)]
pub trait DominatingSetFinder {
    /// Finds a dominating set in the graph.
    ///
    /// Returns a set of node indices such that every node in the graph is either in the set
    /// or adjacent to at least one node in the set.
    ///
    /// # Returns
    /// - `Ok(HashSet<NodeId>)`: A set of node indices forming a dominating set.
    /// - `Err(DominatingSetError)`: If an invalid neighbor node is encountered during computation.
    ///
    /// # Examples
    /// ```rust
    /// use xgraph::graph::graph::Graph;
    /// use xgraph::core::DominatingSet;
    ///
    /// let adjacency_matrix = vec![
    ///     vec![0, 0, 1, 1],
    ///     vec![0, 0, 1, 1],
    ///     vec![1, 1, 0, 0],
    ///     vec![1, 1, 0, 0],
    /// ];
    /// let graph = Graph::from_adjacency_matrix(&adjacency_matrix, false, (), ()).unwrap();
    /// let dominating_set = graph.dominating_set().unwrap();
    /// assert!(dominating_set.len() == 2); // Needs nodes from both partitions
    /// ```
    fn find_dominating_set(&self) -> Result<HashSet<NodeId>, DominatingSetError>;
}

#[allow(deprecated)]
impl<W, N, E> DominatingSetFinder for Graph<W, N, E>
where
    W: Copy + Default + PartialEq,
    N: Clone + Eq + Hash + Debug,
    E: Clone + Default + Debug,
{
    fn find_dominating_set(&self) -> Result<HashSet<NodeId>, DominatingSetError> {
        crate::core::DominatingSet::dominating_set(self).map_err(DominatingSetError::from)
    }
}

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

    /// Helper function to create a graph from an adjacency matrix for testing.
    fn create_test_graph(matrix: Vec<Vec<u32>>) -> Graph<u32, (), ()> {
        Graph::from_adjacency_matrix(&matrix, false, (), ()).expect("Failed to create test graph")
    }

    /// Test the dominating set computation on a simple graph.
    #[test]
    fn test_simple_dominating_set() {
        let matrix = vec![
            vec![0, 1, 1, 0],
            vec![1, 0, 1, 1],
            vec![1, 1, 0, 0],
            vec![0, 1, 0, 0],
        ];
        let graph = create_test_graph(matrix);
        let ds = crate::core::DominatingSet::dominating_set(&graph).unwrap();
        assert!(!ds.is_empty(), "Dominating set should not be empty");
        assert!(ds.len() <= 2, "Dominating set size should be at most 2");
    }

    /// Test the dominating set computation on a more complex graph.
    #[test]
    fn test_complex_dominating_set() {
        let matrix = vec![
            vec![0, 1, 0, 1, 0],
            vec![1, 0, 1, 0, 0],
            vec![0, 1, 0, 1, 1],
            vec![1, 0, 1, 0, 0],
            vec![0, 0, 1, 0, 0],
        ];
        let graph = create_test_graph(matrix);
        let ds = crate::core::DominatingSet::dominating_set(&graph).unwrap();
        assert!(!ds.is_empty(), "Dominating set should not be empty");
        assert!(ds.len() <= 3, "Dominating set size should be at most 3");
    }
}