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)]
15pub struct MixedGraph {
16    num_vertices: usize,
17    arcs: Vec<(usize, usize)>,
18    edges: Vec<(usize, usize)>,
19}
20
21impl MixedGraph {
22    /// Create a new mixed graph.
23    ///
24    /// # Panics
25    ///
26    /// Panics if any endpoint references a vertex outside `0..num_vertices`.
27    pub fn new(num_vertices: usize, arcs: Vec<(usize, usize)>, edges: Vec<(usize, usize)>) -> Self {
28        for &(u, v) in &arcs {
29            assert!(
30                u < num_vertices && v < num_vertices,
31                "arc ({}, {}) references vertex >= num_vertices ({})",
32                u,
33                v,
34                num_vertices
35            );
36        }
37
38        for &(u, v) in &edges {
39            assert!(
40                u < num_vertices && v < num_vertices,
41                "edge ({}, {}) references vertex >= num_vertices ({})",
42                u,
43                v,
44                num_vertices
45            );
46        }
47
48        Self {
49            num_vertices,
50            arcs,
51            edges,
52        }
53    }
54
55    /// Create an empty mixed graph with no arcs or undirected edges.
56    pub fn empty(num_vertices: usize) -> Self {
57        Self::new(num_vertices, vec![], vec![])
58    }
59
60    /// Return the number of vertices.
61    pub fn num_vertices(&self) -> usize {
62        self.num_vertices
63    }
64
65    /// Return the number of directed arcs.
66    pub fn num_arcs(&self) -> usize {
67        self.arcs.len()
68    }
69
70    /// Return the number of undirected edges.
71    pub fn num_edges(&self) -> usize {
72        self.edges.len()
73    }
74
75    /// Return the directed arcs.
76    pub fn arcs(&self) -> Vec<(usize, usize)> {
77        self.arcs.clone()
78    }
79
80    /// Return the undirected edges.
81    pub fn edges(&self) -> Vec<(usize, usize)> {
82        self.edges.clone()
83    }
84
85    /// Return true when the directed arc `(u, v)` is present.
86    pub fn has_arc(&self, u: usize, v: usize) -> bool {
87        self.arcs.iter().any(|&(src, dst)| src == u && dst == v)
88    }
89
90    /// Return true when the undirected edge `{u, v}` is present.
91    pub fn has_edge(&self, u: usize, v: usize) -> bool {
92        let edge = normalize_edge(u, v);
93        self.edges
94            .iter()
95            .any(|&(a, b)| normalize_edge(a, b) == edge)
96    }
97
98    /// Return the outgoing arc count of vertex `v`.
99    pub fn out_degree(&self, v: usize) -> usize {
100        self.arcs.iter().filter(|&&(u, _)| u == v).count()
101    }
102
103    /// Return the incoming arc count of vertex `v`.
104    pub fn in_degree(&self, v: usize) -> usize {
105        self.arcs.iter().filter(|&&(_, w)| w == v).count()
106    }
107
108    /// Return the undirected-edge count incident to vertex `v`.
109    pub fn undirected_degree(&self, v: usize) -> usize {
110        self.edges
111            .iter()
112            .filter(|&&(u, w)| u == v || w == v)
113            .count()
114    }
115
116    /// Return true if the graph has no vertices.
117    pub fn is_empty(&self) -> bool {
118        self.num_vertices == 0
119    }
120}
121
122fn normalize_edge(u: usize, v: usize) -> (usize, usize) {
123    if u <= v {
124        (u, v)
125    } else {
126        (v, u)
127    }
128}
129
130impl PartialEq for MixedGraph {
131    fn eq(&self, other: &Self) -> bool {
132        if self.num_vertices != other.num_vertices {
133            return false;
134        }
135
136        let mut self_arcs = self.arcs.clone();
137        let mut other_arcs = other.arcs.clone();
138        self_arcs.sort();
139        other_arcs.sort();
140        if self_arcs != other_arcs {
141            return false;
142        }
143
144        let mut self_edges = self.edges.clone();
145        let mut other_edges = other.edges.clone();
146        for edge in &mut self_edges {
147            *edge = normalize_edge(edge.0, edge.1);
148        }
149        for edge in &mut other_edges {
150            *edge = normalize_edge(edge.0, edge.1);
151        }
152        self_edges.sort();
153        other_edges.sort();
154        self_edges == other_edges
155    }
156}
157
158impl Eq for MixedGraph {}
159
160use crate::impl_variant_param;
161impl_variant_param!(MixedGraph, "graph");
162
163#[cfg(test)]
164#[path = "../unit_tests/topology/mixed_graph.rs"]
165mod tests;
problemreductions/topology/mixed_graph.rs

problemreductions/topology/
mixed_graph.rs
