problemreductions/models/graph/
minimum_dummy_activities_pert.rs

1//! Minimum Dummy Activities in PERT Networks.
2//!
3//! Given a precedence DAG whose vertices are tasks, select which direct
4//! precedence constraints can be represented by merging the predecessor's
5//! finish event with the successor's start event. The remaining precedence
6//! constraints require dummy activities. A configuration is valid when the
7//! resulting event network is acyclic and preserves exactly the same
8//! task-to-task reachability relation as the original DAG.
9
10use crate::registry::{CreateSpec, ProblemSchemaEntry};
11use crate::topology::DirectedGraph;
12use crate::traits::Problem;
13use crate::types::Min;
14use serde::{Deserialize, Deserializer, Serialize};
15use std::collections::{BTreeMap, BTreeSet};
16
17inventory::submit! {
18    ProblemSchemaEntry {
19        name: "MinimumDummyActivitiesPert",
20        display_name: "Minimum Dummy Activities in PERT Networks",
21        aliases: &[],
22        dimensions: &[],
23        category: crate::registry::ProblemCategory::Graph,
24        module_path: module_path!(),
25        description: "Find a PERT event network for a precedence DAG minimizing dummy activities",
26        fields: MinimumDummyActivitiesPertCreateSpec::FIELDS,
27    }
28}
29
30/// Minimum Dummy Activities in PERT Networks.
31///
32/// For each precedence arc `u -> v`, the configuration chooses one of two
33/// encodings:
34/// - `1`: merge `u`'s finish event with `v`'s start event
35/// - `0`: keep a dummy activity from `u`'s finish event to `v`'s start event
36///
37/// A valid configuration must preserve exactly the same reachability relation
38/// between task completions and task starts as the original precedence DAG.
39#[derive(Debug, Clone, Serialize)]
40pub struct MinimumDummyActivitiesPert {
41    graph: DirectedGraph,
42}
43
44#[derive(Debug, Deserialize, crate::CreateSpec)]
45struct MinimumDummyActivitiesPertCreateSpec {
46    /// Directed precedence arcs.
47    #[create(codec = "arc-list")]
48    arcs: Vec<(usize, usize)>,
49    /// Vertex count, needed to preserve isolated tasks.
50    num_vertices: Option<usize>,
51}
52impl TryFrom<MinimumDummyActivitiesPertCreateSpec> for MinimumDummyActivitiesPert {
53    type Error = crate::registry::ConstructionError;
54    fn try_from(spec: MinimumDummyActivitiesPertCreateSpec) -> Result<Self, Self::Error> {
55        let inferred = spec
56            .arcs
57            .iter()
58            .flat_map(|&(u, v)| [u, v])
59            .max()
60            .map(|vertex| vertex.checked_add(1).ok_or("vertex count overflows usize"))
61            .transpose()?
62            .unwrap_or(0);
63        let num_vertices = spec.num_vertices.unwrap_or(inferred);
64        if num_vertices < inferred {
65            return Err("num_vertices is too small for the provided arcs".into());
66        }
67        Self::try_new(DirectedGraph::new(num_vertices, spec.arcs))
68    }
69}
70
71impl MinimumDummyActivitiesPert {
72    /// Fallible constructor used by CLI validation and deserialization.
73    pub fn try_new(graph: DirectedGraph) -> Result<Self, crate::registry::ConstructionError> {
74        if !graph.is_dag() {
75            return Err("MinimumDummyActivitiesPert requires the input graph to be a DAG".into());
76        }
77        Ok(Self { graph })
78    }
79
80    /// Create a new instance.
81    ///
82    /// # Panics
83    ///
84    /// Panics if the input graph is not a DAG.
85    pub fn new(graph: DirectedGraph) -> Self {
86        Self::try_new(graph).unwrap_or_else(|msg| panic!("{msg}"))
87    }
88
89    /// Get the precedence DAG.
90    pub fn graph(&self) -> &DirectedGraph {
91        &self.graph
92    }
93
94    /// Get the number of tasks.
95    pub fn num_vertices(&self) -> usize {
96        self.graph.num_vertices()
97    }
98
99    /// Get the number of direct precedence arcs.
100    pub fn num_arcs(&self) -> usize {
101        self.graph.num_arcs()
102    }
103
104    /// Check whether the merge-selection config encodes a valid PERT network.
105    pub fn is_valid_solution(
106        &self,
107        config: &[bool],
108    ) -> Result<bool, crate::traits::EvaluationError> {
109        Ok(self.evaluate_solution(config)?.is_valid())
110    }
111
112    fn evaluate_solution(
113        &self,
114        config: &[bool],
115    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
116        if config.len() != self.precedence_arcs().len() {
117            return Err(crate::traits::EvaluationError::InvalidConfiguration(
118                "arc-selection length does not match the precedence graph".into(),
119            ));
120        }
121        let Some(candidate) = self.build_candidate_network(config) else {
122            return Ok(Min(None));
123        };
124
125        let source_reachability = reachability_matrix(&self.graph);
126        let event_reachability = reachability_matrix(&candidate.event_graph);
127
128        for source in 0..self.num_vertices() {
129            for target in 0..self.num_vertices() {
130                let pert_reachable = candidate.finish_events[source]
131                    == candidate.start_events[target]
132                    || event_reachability[candidate.finish_events[source]]
133                        [candidate.start_events[target]];
134                if source_reachability[source][target] != pert_reachable {
135                    return Ok(Min(None));
136                }
137            }
138        }
139
140        Ok(Min(Some(
141            i64::try_from(candidate.num_dummy_arcs).expect("dummy activity count must fit in i64"),
142        )))
143    }
144
145    fn precedence_arcs(&self) -> Vec<(usize, usize)> {
146        self.graph.arcs()
147    }
148
149    fn build_candidate_network(&self, config: &[bool]) -> Option<CandidatePertNetwork> {
150        let num_tasks = self.num_vertices();
151        let arcs = self.precedence_arcs();
152        if config.len() != arcs.len() {
153            return None;
154        }
155
156        let mut uf = UnionFind::new(2 * num_tasks);
157        for ((u, v), &merge_bit) in arcs.iter().zip(config.iter()) {
158            if merge_bit {
159                uf.union(finish_endpoint(*u), start_endpoint(*v));
160            }
161        }
162
163        let roots: Vec<usize> = (0..2 * num_tasks)
164            .map(|endpoint| uf.find(endpoint))
165            .collect();
166        let mut root_to_dense = BTreeMap::new();
167        for &root in &roots {
168            let next = root_to_dense.len();
169            root_to_dense.entry(root).or_insert(next);
170        }
171
172        let start_events: Vec<usize> = (0..num_tasks)
173            .map(|task| root_to_dense[&roots[start_endpoint(task)]])
174            .collect();
175        let finish_events: Vec<usize> = (0..num_tasks)
176            .map(|task| root_to_dense[&roots[finish_endpoint(task)]])
177            .collect();
178
179        if start_events
180            .iter()
181            .zip(finish_events.iter())
182            .any(|(start, finish)| start == finish)
183        {
184            return None;
185        }
186
187        let task_arcs: Vec<(usize, usize)> = (0..num_tasks)
188            .map(|task| (start_events[task], finish_events[task]))
189            .collect();
190
191        let dummy_arcs: BTreeSet<(usize, usize)> = arcs
192            .iter()
193            .zip(config.iter())
194            .filter_map(|((u, v), &merge_bit)| {
195                if merge_bit {
196                    return None;
197                }
198                let source = finish_events[*u];
199                let target = start_events[*v];
200                (source != target).then_some((source, target))
201            })
202            .collect();
203
204        let task_arc_set: BTreeSet<(usize, usize)> = task_arcs.iter().copied().collect();
205        let num_dummy_arcs = dummy_arcs.difference(&task_arc_set).count();
206
207        let mut event_arcs = task_arcs;
208        event_arcs.extend(dummy_arcs.iter().copied());
209        let event_graph = DirectedGraph::new(root_to_dense.len(), event_arcs);
210        if !event_graph.is_dag() {
211            return None;
212        }
213
214        Some(CandidatePertNetwork {
215            event_graph,
216            start_events,
217            finish_events,
218            num_dummy_arcs,
219        })
220    }
221}
222
223impl Problem for MinimumDummyActivitiesPert {
224    const NAME: &'static str = "MinimumDummyActivitiesPert";
225    type Solution = Vec<bool>;
226    type Value = Min<i64>;
227
228    crate::problem_parameters![("num_vertices", num_vertices), ("num_arcs", num_arcs),];
229
230    fn variant() -> Vec<(&'static str, &'static str)> {
231        crate::variant_params![]
232    }
233
234    fn evaluate(
235        &self,
236        config: &Self::Solution,
237    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
238        self.evaluate_solution(config)
239    }
240}
241
242impl crate::solvers::BruteForceProblem for MinimumDummyActivitiesPert {
243    fn dimensions(&self) -> Vec<usize> {
244        vec![2; self.graph.num_arcs()]
245    }
246}
247
248crate::declare_variants! {
249    default MinimumDummyActivitiesPert => "2^num_arcs" create MinimumDummyActivitiesPertCreateSpec,
250}
251
252crate::register_brute_force! {
253    MinimumDummyActivitiesPert decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
254}
255
256#[cfg(feature = "example-db")]
257pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
258    vec![crate::example_db::specs::ModelExampleSpec {
259        id: "minimum_dummy_activities_pert",
260        instance: Box::new(MinimumDummyActivitiesPert::new(DirectedGraph::new(
261            6,
262            vec![(0, 2), (0, 3), (1, 3), (1, 4), (2, 5)],
263        ))),
264        optimal_config: serde_json::json!(vec![true, false, false, true, true]),
265        optimal_value: serde_json::json!(2),
266    }]
267}
268
269#[derive(Deserialize)]
270struct MinimumDummyActivitiesPertData {
271    graph: DirectedGraph,
272}
273
274impl<'de> Deserialize<'de> for MinimumDummyActivitiesPert {
275    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
276    where
277        D: Deserializer<'de>,
278    {
279        let data = MinimumDummyActivitiesPertData::deserialize(deserializer)?;
280        Self::try_new(data.graph).map_err(serde::de::Error::custom)
281    }
282}
283
284struct CandidatePertNetwork {
285    event_graph: DirectedGraph,
286    start_events: Vec<usize>,
287    finish_events: Vec<usize>,
288    num_dummy_arcs: usize,
289}
290
291#[derive(Debug)]
292struct UnionFind {
293    parent: Vec<usize>,
294}
295
296impl UnionFind {
297    fn new(size: usize) -> Self {
298        Self {
299            parent: (0..size).collect(),
300        }
301    }
302
303    fn find(&mut self, x: usize) -> usize {
304        if self.parent[x] != x {
305            let root = self.find(self.parent[x]);
306            self.parent[x] = root;
307        }
308        self.parent[x]
309    }
310
311    fn union(&mut self, a: usize, b: usize) {
312        let root_a = self.find(a);
313        let root_b = self.find(b);
314        if root_a != root_b {
315            self.parent[root_b] = root_a;
316        }
317    }
318}
319
320fn start_endpoint(task: usize) -> usize {
321    2 * task
322}
323
324fn finish_endpoint(task: usize) -> usize {
325    2 * task + 1
326}
327
328fn reachability_matrix(graph: &DirectedGraph) -> Vec<Vec<bool>> {
329    let num_vertices = graph.num_vertices();
330    let adjacency: Vec<Vec<usize>> = (0..num_vertices)
331        .map(|vertex| graph.successors(vertex))
332        .collect();
333    let mut reachable = vec![vec![false; num_vertices]; num_vertices];
334
335    for source in 0..num_vertices {
336        let mut stack = adjacency[source].clone();
337        while let Some(vertex) = stack.pop() {
338            if reachable[source][vertex] {
339                continue;
340            }
341            reachable[source][vertex] = true;
342            stack.extend(adjacency[vertex].iter().copied());
343        }
344    }
345
346    reachable
347}
348
349#[cfg(test)]
350#[path = "../../unit_tests/models/graph/minimum_dummy_activities_pert.rs"]
351mod tests;
problemreductions/models/graph/minimum_dummy_activities_pert.rs

problemreductions/models/graph/
minimum_dummy_activities_pert.rs
