problemreductions/topology/
bipartite_graph.rs

1//! Bipartite graph with explicit left/right partitions.
2
3use super::graph::Graph;
4use serde::{Deserialize, Serialize};
5
6/// Bipartite graph with explicit left/right partitions.
7///
8/// Vertices are split into left (indices `0..left_size`) and right (`0..right_size`).
9/// Edges connect left vertices to right vertices using bipartite-local coordinates.
10/// The [`Graph`] trait maps to a unified vertex space where right vertices are offset
11/// by `left_size`.
12///
13/// # Example
14///
15/// ```
16/// use problemreductions::topology::{BipartiteGraph, Graph};
17///
18/// // K_{2,2}: complete bipartite graph
19/// let g = BipartiteGraph::new(2, 2, vec![(0, 0), (0, 1), (1, 0), (1, 1)]);
20/// assert_eq!(g.num_vertices(), 4);
21/// assert_eq!(g.num_edges(), 4);
22/// assert!(g.has_edge(0, 2)); // left 0 -> right 0 (unified index 2)
23/// ```
24#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
25#[serde(try_from = "BipartiteGraphData")]
26pub struct BipartiteGraph {
27    left_size: usize,
28    right_size: usize,
29    /// Edges in bipartite-local coordinates: (left_index, right_index).
30    edges: Vec<(usize, usize)>,
31}
32
33#[derive(Deserialize)]
34struct BipartiteGraphData {
35    left_size: usize,
36    right_size: usize,
37    edges: Vec<(usize, usize)>,
38}
39
40impl TryFrom<BipartiteGraphData> for BipartiteGraph {
41    type Error = crate::registry::ConstructionError;
42    fn try_from(data: BipartiteGraphData) -> Result<Self, Self::Error> {
43        Self::try_new(data.left_size, data.right_size, data.edges)
44    }
45}
46
47impl BipartiteGraph {
48    /// Create a new bipartite graph.
49    ///
50    /// # Arguments
51    ///
52    /// * `left_size` - Number of vertices in the left partition
53    /// * `right_size` - Number of vertices in the right partition
54    /// * `edges` - Edges as `(left_index, right_index)` pairs in bipartite-local coordinates
55    ///
56    /// # Panics
57    ///
58    /// Panics if any edge references an out-of-bounds left or right vertex index,
59    /// or if the combined vertex count overflows `usize`.
60    pub fn new(left_size: usize, right_size: usize, edges: Vec<(usize, usize)>) -> Self {
61        Self::try_new(left_size, right_size, edges).unwrap_or_else(|error| panic!("{error}"))
62    }
63
64    fn try_new(
65        left_size: usize,
66        right_size: usize,
67        edges: Vec<(usize, usize)>,
68    ) -> Result<Self, crate::registry::ConstructionError> {
69        left_size
70            .checked_add(right_size)
71            .ok_or("bipartite vertex count overflows usize")?;
72        for &(u, v) in &edges {
73            if u >= left_size {
74                return Err(
75                    format!("left vertex {} out of bounds (left_size={})", u, left_size).into(),
76                );
77            }
78            if v >= right_size {
79                return Err(format!(
80                    "right vertex {} out of bounds (right_size={})",
81                    v, right_size
82                )
83                .into());
84            }
85        }
86        Ok(Self {
87            left_size,
88            right_size,
89            edges,
90        })
91    }
92
93    /// Returns the number of vertices in the left partition.
94    pub fn left_size(&self) -> usize {
95        self.left_size
96    }
97
98    /// Returns the number of vertices in the right partition.
99    pub fn right_size(&self) -> usize {
100        self.right_size
101    }
102
103    /// Returns the edges in bipartite-local coordinates.
104    pub fn left_edges(&self) -> &[(usize, usize)] {
105        &self.edges
106    }
107}
108
109impl Graph for BipartiteGraph {
110    const NAME: &'static str = "BipartiteGraph";
111
112    fn num_vertices(&self) -> usize {
113        self.left_size + self.right_size
114    }
115
116    fn num_edges(&self) -> usize {
117        self.edges.len()
118    }
119
120    fn edges(&self) -> Vec<(usize, usize)> {
121        self.edges
122            .iter()
123            .map(|&(u, v)| {
124                let a = u;
125                let b = self.left_size + v;
126                if a < b {
127                    (a, b)
128                } else {
129                    (b, a)
130                }
131            })
132            .collect()
133    }
134
135    fn has_edge(&self, u: usize, v: usize) -> bool {
136        let (u, v) = if u < v { (u, v) } else { (v, u) };
137        // u must be a left vertex and v must be a right vertex (in unified space)
138        if u >= self.left_size || v < self.left_size {
139            return false;
140        }
141        let local_v = v - self.left_size;
142        self.edges.contains(&(u, local_v))
143    }
144
145    fn neighbors(&self, v: usize) -> Vec<usize> {
146        if v < self.left_size {
147            // Left vertex: find all right neighbors
148            self.edges
149                .iter()
150                .filter(|(u, _)| *u == v)
151                .map(|(_, rv)| self.left_size + rv)
152                .collect()
153        } else {
154            // Right vertex: find all left neighbors
155            let local_v = v - self.left_size;
156            self.edges
157                .iter()
158                .filter(|(_, rv)| *rv == local_v)
159                .map(|(u, _)| *u)
160                .collect()
161        }
162    }
163}
164
165use crate::impl_variant_param;
166impl_variant_param!(BipartiteGraph, "graph");
167
168#[cfg(test)]
169#[path = "../unit_tests/topology/bipartite_graph.rs"]
170mod tests;
problemreductions/topology/bipartite_graph.rs

problemreductions/topology/
bipartite_graph.rs
