problemreductions/models/graph/
acyclic_partition.rs

1//! Acyclic Partition problem implementation.
2//!
3//! Given a directed graph with vertex weights, arc costs, and bounds, determine
4//! whether the vertices can be partitioned into groups whose quotient graph is a
5//! DAG, each group's total vertex weight is bounded, and the total
6//! inter-partition arc cost is bounded.
7
8use crate::registry::{FieldInfo, ProblemSchemaEntry, ProblemSizeFieldEntry, VariantDimension};
9use crate::topology::DirectedGraph;
10use crate::traits::Problem;
11use crate::types::WeightElement;
12use num_traits::Zero;
13use serde::{Deserialize, Serialize};
14use std::collections::BTreeSet;
15
16inventory::submit! {
17    ProblemSchemaEntry {
18        name: "AcyclicPartition",
19        display_name: "Acyclic Partition",
20        aliases: &[],
21        dimensions: &[
22            VariantDimension::new("weight", "i32", &["i32"]),
23        ],
24        module_path: module_path!(),
25        description: "Partition a directed graph into bounded-weight groups with an acyclic quotient graph and bounded inter-partition cost",
26        fields: &[
27            FieldInfo { name: "graph", type_name: "DirectedGraph", description: "The directed graph G=(V,A)" },
28            FieldInfo { name: "vertex_weights", type_name: "Vec<W>", description: "Vertex weights w(v) for each vertex v in V" },
29            FieldInfo { name: "arc_costs", type_name: "Vec<W>", description: "Arc costs c(a) for each arc a in A, matching graph.arcs() order" },
30            FieldInfo { name: "weight_bound", type_name: "W::Sum", description: "Maximum total vertex weight B for each partition" },
31            FieldInfo { name: "cost_bound", type_name: "W::Sum", description: "Maximum total inter-partition arc cost K" },
32        ],
33    }
34}
35
36inventory::submit! {
37    ProblemSizeFieldEntry {
38        name: "AcyclicPartition",
39        fields: &["num_vertices", "num_arcs"],
40    }
41}
42
43/// Acyclic Partition (Garey & Johnson ND15).
44#[derive(Debug, Clone, Serialize, Deserialize)]
45pub struct AcyclicPartition<W: WeightElement> {
46    graph: DirectedGraph,
47    vertex_weights: Vec<W>,
48    arc_costs: Vec<W>,
49    weight_bound: W::Sum,
50    cost_bound: W::Sum,
51}
52
53impl<W: WeightElement> AcyclicPartition<W> {
54    /// Create a new Acyclic Partition instance.
55    pub fn new(
56        graph: DirectedGraph,
57        vertex_weights: Vec<W>,
58        arc_costs: Vec<W>,
59        weight_bound: W::Sum,
60        cost_bound: W::Sum,
61    ) -> Self {
62        assert_eq!(
63            vertex_weights.len(),
64            graph.num_vertices(),
65            "vertex_weights length must match graph num_vertices"
66        );
67        assert_eq!(
68            arc_costs.len(),
69            graph.num_arcs(),
70            "arc_costs length must match graph num_arcs"
71        );
72        Self {
73            graph,
74            vertex_weights,
75            arc_costs,
76            weight_bound,
77            cost_bound,
78        }
79    }
80
81    /// Get the underlying graph.
82    pub fn graph(&self) -> &DirectedGraph {
83        &self.graph
84    }
85
86    /// Get the vertex weights.
87    pub fn vertex_weights(&self) -> &[W] {
88        &self.vertex_weights
89    }
90
91    /// Get the arc costs.
92    pub fn arc_costs(&self) -> &[W] {
93        &self.arc_costs
94    }
95
96    /// Replace the vertex weights.
97    pub fn set_vertex_weights(&mut self, vertex_weights: Vec<W>) {
98        assert_eq!(
99            vertex_weights.len(),
100            self.graph.num_vertices(),
101            "vertex_weights length must match graph num_vertices"
102        );
103        self.vertex_weights = vertex_weights;
104    }
105
106    /// Replace the arc costs.
107    pub fn set_arc_costs(&mut self, arc_costs: Vec<W>) {
108        assert_eq!(
109            arc_costs.len(),
110            self.graph.num_arcs(),
111            "arc_costs length must match graph num_arcs"
112        );
113        self.arc_costs = arc_costs;
114    }
115
116    /// Get the per-part weight bound.
117    pub fn weight_bound(&self) -> &W::Sum {
118        &self.weight_bound
119    }
120
121    /// Get the inter-partition cost bound.
122    pub fn cost_bound(&self) -> &W::Sum {
123        &self.cost_bound
124    }
125
126    /// Check whether this instance uses non-unit weights.
127    pub fn is_weighted(&self) -> bool {
128        !W::IS_UNIT
129    }
130
131    /// Get the number of vertices.
132    pub fn num_vertices(&self) -> usize {
133        self.graph.num_vertices()
134    }
135
136    /// Get the number of arcs.
137    pub fn num_arcs(&self) -> usize {
138        self.graph.num_arcs()
139    }
140
141    /// Check whether a configuration is a valid solution.
142    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
143        is_valid_acyclic_partition(
144            &self.graph,
145            &self.vertex_weights,
146            &self.arc_costs,
147            &self.weight_bound,
148            &self.cost_bound,
149            config,
150        )
151    }
152}
153
154impl<W> Problem for AcyclicPartition<W>
155where
156    W: WeightElement + crate::variant::VariantParam,
157{
158    const NAME: &'static str = "AcyclicPartition";
159    type Value = crate::types::Or;
160
161    fn variant() -> Vec<(&'static str, &'static str)> {
162        crate::variant_params![W]
163    }
164
165    fn dims(&self) -> Vec<usize> {
166        vec![self.graph.num_vertices(); self.graph.num_vertices()]
167    }
168
169    fn evaluate(&self, config: &[usize]) -> crate::types::Or {
170        crate::types::Or({
171            is_valid_acyclic_partition(
172                &self.graph,
173                &self.vertex_weights,
174                &self.arc_costs,
175                &self.weight_bound,
176                &self.cost_bound,
177                config,
178            )
179        })
180    }
181}
182
183fn is_valid_acyclic_partition<W: WeightElement>(
184    graph: &DirectedGraph,
185    vertex_weights: &[W],
186    arc_costs: &[W],
187    weight_bound: &W::Sum,
188    cost_bound: &W::Sum,
189    config: &[usize],
190) -> bool {
191    let num_vertices = graph.num_vertices();
192    if config.len() != num_vertices {
193        return false;
194    }
195    if vertex_weights.len() != num_vertices || arc_costs.len() != graph.num_arcs() {
196        return false;
197    }
198    if config.iter().any(|&label| label >= num_vertices) {
199        return false;
200    }
201
202    let mut partition_weights = vec![W::Sum::zero(); num_vertices];
203    let mut used_labels = vec![false; num_vertices];
204    for (vertex, &label) in config.iter().enumerate() {
205        used_labels[label] = true;
206        partition_weights[label] += vertex_weights[vertex].to_sum();
207        if partition_weights[label] > *weight_bound {
208            return false;
209        }
210    }
211
212    let mut dense_label = vec![usize::MAX; num_vertices];
213    let mut next_dense = 0usize;
214    for (label, used) in used_labels.iter().enumerate() {
215        if *used {
216            dense_label[label] = next_dense;
217            next_dense += 1;
218        }
219    }
220
221    let mut total_cost = W::Sum::zero();
222    let mut quotient_arcs = BTreeSet::new();
223    for ((source, target), cost) in graph.arcs().iter().zip(arc_costs.iter()) {
224        let source_label = config[*source];
225        let target_label = config[*target];
226        if source_label == target_label {
227            continue;
228        }
229        total_cost += cost.to_sum();
230        if total_cost > *cost_bound {
231            return false;
232        }
233        quotient_arcs.insert((dense_label[source_label], dense_label[target_label]));
234    }
235
236    DirectedGraph::new(next_dense, quotient_arcs.into_iter().collect()).is_dag()
237}
238
239crate::declare_variants! {
240    default AcyclicPartition<i32> => "num_vertices^num_vertices",
241}
242
243#[cfg(feature = "example-db")]
244pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
245    vec![crate::example_db::specs::ModelExampleSpec {
246        id: "acyclic_partition_i32",
247        instance: Box::new(AcyclicPartition::new(
248            DirectedGraph::new(
249                6,
250                vec![
251                    (0, 1),
252                    (0, 2),
253                    (1, 3),
254                    (1, 4),
255                    (2, 4),
256                    (2, 5),
257                    (3, 5),
258                    (4, 5),
259                ],
260            ),
261            vec![2, 3, 2, 1, 3, 1],
262            vec![1; 8],
263            5,
264            5,
265        )),
266        optimal_config: vec![0, 1, 0, 2, 2, 2],
267        optimal_value: serde_json::json!(true),
268    }]
269}
270
271#[cfg(test)]
272#[path = "../../unit_tests/models/graph/acyclic_partition.rs"]
273mod tests;
problemreductions/models/graph/acyclic_partition.rs

problemreductions/models/graph/
acyclic_partition.rs
