graphina 0.3.0-alpha.4

A graph data science library for Rust
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

//! Approximation algorithms for vertex cover problems.

use crate::core::types::{BaseGraph, GraphConstructor, NodeId};
use std::collections::HashSet;

/// Approximates a minimum weighted vertex cover using a greedy strategy.
/// This implementation re‑evaluates the uncovered incident edges at each iteration.
/// For each uncovered edge, it chooses the node (not yet in the cover) that covers
/// the maximum number of uncovered edges, and then marks all its incident edges as covered.
///
/// # Arguments
///
/// * `graph` - A reference to the graph whose vertex cover is being approximated.
/// * `weight` - An optional function that maps a node to its weight (defaults to 1.0 for all nodes).
///
/// # Returns
///
/// A `HashSet<NodeId>` containing the nodes in the approximated vertex cover.
pub fn min_weighted_vertex_cover<A, Ty>(
    graph: &BaseGraph<A, f64, Ty>,
    _weight: Option<&dyn Fn(NodeId) -> f64>,
) -> HashSet<NodeId>
where
    Ty: GraphConstructor<A, f64>,
{
    let mut cover = HashSet::new();
    let mut uncovered: HashSet<(NodeId, NodeId)> = graph.edges().map(|(u, v, _)| (u, v)).collect();

    while !uncovered.is_empty() {
        let best = graph
            .nodes()
            .map(|(u, _)| u)
            .filter(|u| !cover.contains(u))
            .max_by_key(|&u| {
                let count = graph
                    .neighbors(u)
                    .filter(|w| uncovered.contains(&(u, *w)) || uncovered.contains(&(*w, u)))
                    .count();
                count
            });
        if let Some(best) = best {
            cover.insert(best);
            uncovered.retain(|&(u, v)| u != best && v != best);
        } else {
            break;
        }
    }
    cover
}

#[cfg(test)]
mod tests {
    // Import the function under test from the parent module
    use super::min_weighted_vertex_cover;
    use crate::core::types::Graph;

    #[test]
    fn test_greedy_vertex_cover() {
        let mut graph = Graph::<i32, f64>::new();
        let n1 = graph.add_node(1);
        let n2 = graph.add_node(2);
        let n3 = graph.add_node(3);
        let n4 = graph.add_node(4);
        graph.add_edge(n1, n2, 1.0);
        graph.add_edge(n2, n3, 1.0);
        graph.add_edge(n3, n4, 1.0);
        let cover = min_weighted_vertex_cover(&graph, None);
        assert!(!cover.is_empty());
        assert!(cover.len() <= graph.node_count());
    }
}