uni_algo/algo/algorithms/
bipartite_check.rs

1// SPDX-License-Identifier: Apache-2.0
2// Copyright 2024-2026 Dragonscale Team
3
4//! Bipartite Check Algorithm.
5//!
6//! Checks if a graph is bipartite (2-colorable) using BFS.
7//! Returns `true` if bipartite, and the partition (0 or 1) for each node.
8
9use crate::algo::GraphProjection;
10use crate::algo::algorithms::Algorithm;
11use uni_common::core::id::Vid;
12
13pub struct BipartiteCheck;
14
15#[derive(Debug, Clone, Default)]
16pub struct BipartiteCheckConfig {}
17
18pub struct BipartiteCheckResult {
19    pub is_bipartite: bool,
20    pub partition: Vec<(Vid, u8)>, // (node, color: 0 or 1)
21}
22
23impl Algorithm for BipartiteCheck {
24    type Config = BipartiteCheckConfig;
25    type Result = BipartiteCheckResult;
26
27    fn name() -> &'static str {
28        "bipartite_check"
29    }
30
31    fn run(graph: &GraphProjection, _config: Self::Config) -> Self::Result {
32        let n = graph.vertex_count();
33        if n == 0 {
34            return BipartiteCheckResult {
35                is_bipartite: true,
36                partition: Vec::new(),
37            };
38        }
39
40        // 0: uncolored, 1: color A, 2: color B
41        let mut colors = vec![0u8; n];
42        let mut is_bipartite = true;
43
44        for start_node in 0..n {
45            if colors[start_node] != 0 {
46                continue;
47            }
48
49            let mut queue = std::collections::VecDeque::new();
50            queue.push_back(start_node as u32);
51            colors[start_node] = 1;
52
53            while let Some(u) = queue.pop_front() {
54                let current_color = colors[u as usize];
55                let next_color = if current_color == 1 { 2 } else { 1 };
56
57                // Check out-neighbors (treat as undirected for bipartite check typically,
58                // but if strictly directed, we only check forward edges?
59                // Bipartite usually implies underlying undirected graph structure.
60                // If strictly directed, a cycle might not matter if directions align.
61                // Standard definition: "vertices can be divided into two disjoint and independent sets"
62                // This usually applies to undirected edges.
63                // Let's assume undirected semantics by checking both directions if possible,
64                // or just outgoing if directed graph semantics.
65                // Uni graphs are directed. But bipartite check usually implies structure.
66                // Let's check outgoing edges. If graph represents undirected, user should have added reverse edges.
67                // Actually, `GraphProjection` can have reverse edges if requested.
68                // If `include_reverse` is false, we only check outgoing.
69
70                for &v in graph.out_neighbors(u) {
71                    if colors[v as usize] == 0 {
72                        colors[v as usize] = next_color;
73                        queue.push_back(v);
74                    } else if colors[v as usize] == current_color {
75                        is_bipartite = false;
76                        // Don't break immediately if we want to color the rest of the component?
77                        // But result is invalid.
78                        // We can stop or continue. Let's continue to fill partition map best-effort or stop?
79                        // The result says "is_bipartite: false". Partition might be partial/invalid.
80                        // Let's continue to process this component to finish coloring for debug, but mark false.
81                    }
82                }
83
84                // If we had reverse edges (undirected check), we would check in_neighbors too.
85                if graph.has_reverse() {
86                    for &v in graph.in_neighbors(u) {
87                        if colors[v as usize] == 0 {
88                            colors[v as usize] = next_color;
89                            queue.push_back(v);
90                        } else if colors[v as usize] == current_color {
91                            is_bipartite = false;
92                        }
93                    }
94                }
95            }
96        }
97
98        let partition = if is_bipartite {
99            colors
100                .into_iter()
101                .enumerate()
102                .filter(|(_, c)| *c != 0)
103                .map(|(i, c)| (graph.to_vid(i as u32), c - 1))
104                .collect()
105        } else {
106            Vec::new() // Or return partial partition?
107        };
108
109        BipartiteCheckResult {
110            is_bipartite,
111            partition,
112        }
113    }
114}
115
116#[cfg(test)]
117mod tests {
118    use super::*;
119    use crate::algo::test_utils::build_test_graph;
120
121    #[test]
122    fn test_bipartite_check_true() {
123        // 0 -> 1, 1 -> 2 (0 and 2 are color A, 1 is color B)
124        let vids = vec![Vid::from(0), Vid::from(1), Vid::from(2)];
125        let edges = vec![(Vid::from(0), Vid::from(1)), (Vid::from(1), Vid::from(2))];
126        let graph = build_test_graph(vids, edges);
127
128        let result = BipartiteCheck::run(&graph, BipartiteCheckConfig::default());
129        assert!(result.is_bipartite);
130        assert_eq!(result.partition.len(), 3);
131    }
132
133    #[test]
134    fn test_bipartite_check_false_triangle() {
135        // 0 -> 1 -> 2 -> 0
136        let vids = vec![Vid::from(0), Vid::from(1), Vid::from(2)];
137        let edges = vec![
138            (Vid::from(0), Vid::from(1)),
139            (Vid::from(1), Vid::from(2)),
140            (Vid::from(2), Vid::from(0)),
141        ];
142        let graph = build_test_graph(vids, edges);
143
144        let result = BipartiteCheck::run(&graph, BipartiteCheckConfig::default());
145        assert!(!result.is_bipartite);
146    }
147}
uni_algo/algo/algorithms/bipartite_check.rs

uni_algo/algo/algorithms/
bipartite_check.rs
