problemreductions/topology/
mixed_graph.rs

1//! Mixed graph implementation.
2//!
3//! This module provides [`MixedGraph`], a graph topology with both directed arcs
4//! and undirected edges. It is intended for models whose instances genuinely
5//! depend on both kinds of adjacency, such as Mixed Chinese Postman.
6
7use serde::{Deserialize, Serialize};
8
9/// A graph with both directed arcs and undirected edges.
10///
11/// Arcs are ordered pairs `(u, v)`. Undirected edges preserve the input order
12/// so higher-level models can use that order as part of their configuration
13/// semantics, but edge-membership queries treat them as unordered pairs.
14#[derive(Debug, Clone, Serialize, Deserialize)]
15#[serde(try_from = "MixedGraphData")]
16pub struct MixedGraph {
17    num_vertices: usize,
18    arcs: Vec<(usize, usize)>,
19    edges: Vec<(usize, usize)>,
20}
21
22#[derive(Deserialize)]
23struct MixedGraphData {
24    num_vertices: usize,
25    arcs: Vec<(usize, usize)>,
26    edges: Vec<(usize, usize)>,
27}
28
29impl TryFrom<MixedGraphData> for MixedGraph {
30    type Error = crate::registry::ConstructionError;
31    fn try_from(data: MixedGraphData) -> Result<Self, Self::Error> {
32        Self::try_new(data.num_vertices, data.arcs, data.edges)
33    }
34}
35
36impl MixedGraph {
37    /// Create a new mixed graph.
38    ///
39    /// # Panics
40    ///
41    /// Panics if any endpoint references a vertex outside `0..num_vertices`.
42    pub fn new(num_vertices: usize, arcs: Vec<(usize, usize)>, edges: Vec<(usize, usize)>) -> Self {
43        Self::try_new(num_vertices, arcs, edges).unwrap_or_else(|error| panic!("{error}"))
44    }
45
46    fn try_new(
47        num_vertices: usize,
48        arcs: Vec<(usize, usize)>,
49        edges: Vec<(usize, usize)>,
50    ) -> Result<Self, crate::registry::ConstructionError> {
51        for &(u, v) in &arcs {
52            if !(u < num_vertices && v < num_vertices) {
53                return Err(format!(
54                    "arc ({}, {}) references vertex >= num_vertices ({})",
55                    u, v, num_vertices
56                )
57                .into());
58            }
59        }
60
61        for &(u, v) in &edges {
62            if !(u < num_vertices && v < num_vertices) {
63                return Err(format!(
64                    "edge ({}, {}) references vertex >= num_vertices ({})",
65                    u, v, num_vertices
66                )
67                .into());
68            }
69        }
70
71        Ok(Self {
72            num_vertices,
73            arcs,
74            edges,
75        })
76    }
77
78    /// Create an empty mixed graph with no arcs or undirected edges.
79    pub fn empty(num_vertices: usize) -> Self {
80        Self::new(num_vertices, vec![], vec![])
81    }
82
83    /// Return the number of vertices.
84    pub fn num_vertices(&self) -> usize {
85        self.num_vertices
86    }
87
88    /// Return the number of directed arcs.
89    pub fn num_arcs(&self) -> usize {
90        self.arcs.len()
91    }
92
93    /// Return the number of undirected edges.
94    pub fn num_edges(&self) -> usize {
95        self.edges.len()
96    }
97
98    /// Return the directed arcs.
99    pub fn arcs(&self) -> Vec<(usize, usize)> {
100        self.arcs.clone()
101    }
102
103    /// Return the undirected edges.
104    pub fn edges(&self) -> Vec<(usize, usize)> {
105        self.edges.clone()
106    }
107
108    /// Return true when the directed arc `(u, v)` is present.
109    pub fn has_arc(&self, u: usize, v: usize) -> bool {
110        self.arcs.iter().any(|&(src, dst)| src == u && dst == v)
111    }
112
113    /// Return true when the undirected edge `{u, v}` is present.
114    pub fn has_edge(&self, u: usize, v: usize) -> bool {
115        let edge = normalize_edge(u, v);
116        self.edges
117            .iter()
118            .any(|&(a, b)| normalize_edge(a, b) == edge)
119    }
120
121    /// Return the outgoing arc count of vertex `v`.
122    pub fn out_degree(&self, v: usize) -> usize {
123        self.arcs.iter().filter(|&&(u, _)| u == v).count()
124    }
125
126    /// Return the incoming arc count of vertex `v`.
127    pub fn in_degree(&self, v: usize) -> usize {
128        self.arcs.iter().filter(|&&(_, w)| w == v).count()
129    }
130
131    /// Return the undirected-edge count incident to vertex `v`.
132    pub fn undirected_degree(&self, v: usize) -> usize {
133        self.edges
134            .iter()
135            .filter(|&&(u, w)| u == v || w == v)
136            .count()
137    }
138
139    /// Return true if the graph has no vertices.
140    pub fn is_empty(&self) -> bool {
141        self.num_vertices == 0
142    }
143}
144
145fn normalize_edge(u: usize, v: usize) -> (usize, usize) {
146    if u <= v {
147        (u, v)
148    } else {
149        (v, u)
150    }
151}
152
153impl PartialEq for MixedGraph {
154    fn eq(&self, other: &Self) -> bool {
155        if self.num_vertices != other.num_vertices {
156            return false;
157        }
158
159        let mut self_arcs = self.arcs.clone();
160        let mut other_arcs = other.arcs.clone();
161        self_arcs.sort();
162        other_arcs.sort();
163        if self_arcs != other_arcs {
164            return false;
165        }
166
167        let mut self_edges = self.edges.clone();
168        let mut other_edges = other.edges.clone();
169        for edge in &mut self_edges {
170            *edge = normalize_edge(edge.0, edge.1);
171        }
172        for edge in &mut other_edges {
173            *edge = normalize_edge(edge.0, edge.1);
174        }
175        self_edges.sort();
176        other_edges.sort();
177        self_edges == other_edges
178    }
179}
180
181impl Eq for MixedGraph {}
182
183use crate::impl_variant_param;
184impl_variant_param!(MixedGraph, "graph");
185
186#[cfg(test)]
187#[path = "../unit_tests/topology/mixed_graph.rs"]
188mod tests;
problemreductions/topology/mixed_graph.rs

problemreductions/topology/
mixed_graph.rs
