problemreductions/topology/
bipartite_graph.rs

1//! Bipartite graph with explicit left/right partitions.
2
3use super::graph::{Graph, SimpleGraph};
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)]
25pub struct BipartiteGraph {
26    left_size: usize,
27    right_size: usize,
28    /// Edges in bipartite-local coordinates: (left_index, right_index).
29    edges: Vec<(usize, usize)>,
30}
31
32impl BipartiteGraph {
33    /// Create a new bipartite graph.
34    ///
35    /// # Arguments
36    ///
37    /// * `left_size` - Number of vertices in the left partition
38    /// * `right_size` - Number of vertices in the right partition
39    /// * `edges` - Edges as `(left_index, right_index)` pairs in bipartite-local coordinates
40    ///
41    /// # Panics
42    ///
43    /// Panics if any edge references an out-of-bounds left or right vertex index.
44    pub fn new(left_size: usize, right_size: usize, edges: Vec<(usize, usize)>) -> Self {
45        for &(u, v) in &edges {
46            assert!(
47                u < left_size,
48                "left vertex {} out of bounds (left_size={})",
49                u,
50                left_size
51            );
52            assert!(
53                v < right_size,
54                "right vertex {} out of bounds (right_size={})",
55                v,
56                right_size
57            );
58        }
59        Self {
60            left_size,
61            right_size,
62            edges,
63        }
64    }
65
66    /// Returns the number of vertices in the left partition.
67    pub fn left_size(&self) -> usize {
68        self.left_size
69    }
70
71    /// Returns the number of vertices in the right partition.
72    pub fn right_size(&self) -> usize {
73        self.right_size
74    }
75
76    /// Returns the edges in bipartite-local coordinates.
77    pub fn left_edges(&self) -> &[(usize, usize)] {
78        &self.edges
79    }
80}
81
82impl Graph for BipartiteGraph {
83    const NAME: &'static str = "BipartiteGraph";
84
85    fn num_vertices(&self) -> usize {
86        self.left_size + self.right_size
87    }
88
89    fn num_edges(&self) -> usize {
90        self.edges.len()
91    }
92
93    fn edges(&self) -> Vec<(usize, usize)> {
94        self.edges
95            .iter()
96            .map(|&(u, v)| {
97                let a = u;
98                let b = self.left_size + v;
99                if a < b {
100                    (a, b)
101                } else {
102                    (b, a)
103                }
104            })
105            .collect()
106    }
107
108    fn has_edge(&self, u: usize, v: usize) -> bool {
109        let (u, v) = if u < v { (u, v) } else { (v, u) };
110        // u must be a left vertex and v must be a right vertex (in unified space)
111        if u >= self.left_size || v < self.left_size {
112            return false;
113        }
114        let local_v = v - self.left_size;
115        self.edges.contains(&(u, local_v))
116    }
117
118    fn neighbors(&self, v: usize) -> Vec<usize> {
119        if v < self.left_size {
120            // Left vertex: find all right neighbors
121            self.edges
122                .iter()
123                .filter(|(u, _)| *u == v)
124                .map(|(_, rv)| self.left_size + rv)
125                .collect()
126        } else {
127            // Right vertex: find all left neighbors
128            let local_v = v - self.left_size;
129            self.edges
130                .iter()
131                .filter(|(_, rv)| *rv == local_v)
132                .map(|(u, _)| *u)
133                .collect()
134        }
135    }
136}
137
138use crate::impl_variant_param;
139impl_variant_param!(BipartiteGraph, "graph", parent: SimpleGraph,
140    cast: |g| SimpleGraph::new(g.num_vertices(), g.edges()));
141
142#[cfg(test)]
143#[path = "../unit_tests/topology/bipartite_graph.rs"]
144mod tests;
problemreductions/topology/bipartite_graph.rs

problemreductions/topology/
bipartite_graph.rs
