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::{FieldInfo, 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        module_path: module_path!(),
24        description: "Find a PERT event network for a precedence DAG minimizing dummy activities",
25        fields: &[
26            FieldInfo {
27                name: "graph",
28                type_name: "DirectedGraph",
29                description: "The precedence DAG G=(V,A) whose vertices are tasks and arcs encode direct precedence constraints",
30            },
31        ],
32    }
33}
34
35/// Minimum Dummy Activities in PERT Networks.
36///
37/// For each precedence arc `u -> v`, the configuration chooses one of two
38/// encodings:
39/// - `1`: merge `u`'s finish event with `v`'s start event
40/// - `0`: keep a dummy activity from `u`'s finish event to `v`'s start event
41///
42/// A valid configuration must preserve exactly the same reachability relation
43/// between task completions and task starts as the original precedence DAG.
44#[derive(Debug, Clone, Serialize)]
45pub struct MinimumDummyActivitiesPert {
46    graph: DirectedGraph,
47}
48
49impl MinimumDummyActivitiesPert {
50    /// Fallible constructor used by CLI validation and deserialization.
51    pub fn try_new(graph: DirectedGraph) -> Result<Self, String> {
52        if !graph.is_dag() {
53            return Err("MinimumDummyActivitiesPert requires the input graph to be a DAG".into());
54        }
55        Ok(Self { graph })
56    }
57
58    /// Create a new instance.
59    ///
60    /// # Panics
61    ///
62    /// Panics if the input graph is not a DAG.
63    pub fn new(graph: DirectedGraph) -> Self {
64        Self::try_new(graph).unwrap_or_else(|msg| panic!("{msg}"))
65    }
66
67    /// Get the precedence DAG.
68    pub fn graph(&self) -> &DirectedGraph {
69        &self.graph
70    }
71
72    /// Get the number of tasks.
73    pub fn num_vertices(&self) -> usize {
74        self.graph.num_vertices()
75    }
76
77    /// Get the number of direct precedence arcs.
78    pub fn num_arcs(&self) -> usize {
79        self.graph.num_arcs()
80    }
81
82    /// Check whether the merge-selection config encodes a valid PERT network.
83    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
84        self.evaluate(config).is_valid()
85    }
86
87    fn precedence_arcs(&self) -> Vec<(usize, usize)> {
88        self.graph.arcs()
89    }
90
91    fn build_candidate_network(&self, config: &[usize]) -> Option<CandidatePertNetwork> {
92        let num_tasks = self.num_vertices();
93        let arcs = self.precedence_arcs();
94        if config.len() != arcs.len() || config.iter().any(|&bit| bit > 1) {
95            return None;
96        }
97
98        let mut uf = UnionFind::new(2 * num_tasks);
99        for ((u, v), &merge_bit) in arcs.iter().zip(config.iter()) {
100            if merge_bit == 1 {
101                uf.union(finish_endpoint(*u), start_endpoint(*v));
102            }
103        }
104
105        let roots: Vec<usize> = (0..2 * num_tasks)
106            .map(|endpoint| uf.find(endpoint))
107            .collect();
108        let mut root_to_dense = BTreeMap::new();
109        for &root in &roots {
110            let next = root_to_dense.len();
111            root_to_dense.entry(root).or_insert(next);
112        }
113
114        let start_events: Vec<usize> = (0..num_tasks)
115            .map(|task| root_to_dense[&roots[start_endpoint(task)]])
116            .collect();
117        let finish_events: Vec<usize> = (0..num_tasks)
118            .map(|task| root_to_dense[&roots[finish_endpoint(task)]])
119            .collect();
120
121        if start_events
122            .iter()
123            .zip(finish_events.iter())
124            .any(|(start, finish)| start == finish)
125        {
126            return None;
127        }
128
129        let task_arcs: Vec<(usize, usize)> = (0..num_tasks)
130            .map(|task| (start_events[task], finish_events[task]))
131            .collect();
132
133        let dummy_arcs: BTreeSet<(usize, usize)> = arcs
134            .iter()
135            .zip(config.iter())
136            .filter_map(|((u, v), &merge_bit)| {
137                if merge_bit == 1 {
138                    return None;
139                }
140                let source = finish_events[*u];
141                let target = start_events[*v];
142                (source != target).then_some((source, target))
143            })
144            .collect();
145
146        let task_arc_set: BTreeSet<(usize, usize)> = task_arcs.iter().copied().collect();
147        let num_dummy_arcs = dummy_arcs.difference(&task_arc_set).count();
148
149        let mut event_arcs = task_arcs;
150        event_arcs.extend(dummy_arcs.iter().copied());
151        let event_graph = DirectedGraph::new(root_to_dense.len(), event_arcs);
152        if !event_graph.is_dag() {
153            return None;
154        }
155
156        Some(CandidatePertNetwork {
157            event_graph,
158            start_events,
159            finish_events,
160            num_dummy_arcs,
161        })
162    }
163}
164
165impl Problem for MinimumDummyActivitiesPert {
166    const NAME: &'static str = "MinimumDummyActivitiesPert";
167    type Value = Min<i32>;
168
169    fn variant() -> Vec<(&'static str, &'static str)> {
170        crate::variant_params![]
171    }
172
173    fn dims(&self) -> Vec<usize> {
174        vec![2; self.graph.num_arcs()]
175    }
176
177    fn evaluate(&self, config: &[usize]) -> Min<i32> {
178        let Some(candidate) = self.build_candidate_network(config) else {
179            return Min(None);
180        };
181
182        let source_reachability = reachability_matrix(&self.graph);
183        let event_reachability = reachability_matrix(&candidate.event_graph);
184
185        for source in 0..self.num_vertices() {
186            for target in 0..self.num_vertices() {
187                let pert_reachable = candidate.finish_events[source]
188                    == candidate.start_events[target]
189                    || event_reachability[candidate.finish_events[source]]
190                        [candidate.start_events[target]];
191                if source_reachability[source][target] != pert_reachable {
192                    return Min(None);
193                }
194            }
195        }
196
197        Min(Some(
198            i32::try_from(candidate.num_dummy_arcs).expect("dummy activity count must fit in i32"),
199        ))
200    }
201}
202
203crate::declare_variants! {
204    default MinimumDummyActivitiesPert => "2^num_arcs",
205}
206
207#[cfg(feature = "example-db")]
208pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
209    vec![crate::example_db::specs::ModelExampleSpec {
210        id: "minimum_dummy_activities_pert",
211        instance: Box::new(MinimumDummyActivitiesPert::new(DirectedGraph::new(
212            6,
213            vec![(0, 2), (0, 3), (1, 3), (1, 4), (2, 5)],
214        ))),
215        optimal_config: vec![1, 0, 0, 1, 1],
216        optimal_value: serde_json::json!(2),
217    }]
218}
219
220#[derive(Deserialize)]
221struct MinimumDummyActivitiesPertData {
222    graph: DirectedGraph,
223}
224
225impl<'de> Deserialize<'de> for MinimumDummyActivitiesPert {
226    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
227    where
228        D: Deserializer<'de>,
229    {
230        let data = MinimumDummyActivitiesPertData::deserialize(deserializer)?;
231        Self::try_new(data.graph).map_err(serde::de::Error::custom)
232    }
233}
234
235struct CandidatePertNetwork {
236    event_graph: DirectedGraph,
237    start_events: Vec<usize>,
238    finish_events: Vec<usize>,
239    num_dummy_arcs: usize,
240}
241
242#[derive(Debug)]
243struct UnionFind {
244    parent: Vec<usize>,
245}
246
247impl UnionFind {
248    fn new(size: usize) -> Self {
249        Self {
250            parent: (0..size).collect(),
251        }
252    }
253
254    fn find(&mut self, x: usize) -> usize {
255        if self.parent[x] != x {
256            let root = self.find(self.parent[x]);
257            self.parent[x] = root;
258        }
259        self.parent[x]
260    }
261
262    fn union(&mut self, a: usize, b: usize) {
263        let root_a = self.find(a);
264        let root_b = self.find(b);
265        if root_a != root_b {
266            self.parent[root_b] = root_a;
267        }
268    }
269}
270
271fn start_endpoint(task: usize) -> usize {
272    2 * task
273}
274
275fn finish_endpoint(task: usize) -> usize {
276    2 * task + 1
277}
278
279fn reachability_matrix(graph: &DirectedGraph) -> Vec<Vec<bool>> {
280    let num_vertices = graph.num_vertices();
281    let adjacency: Vec<Vec<usize>> = (0..num_vertices)
282        .map(|vertex| graph.successors(vertex))
283        .collect();
284    let mut reachable = vec![vec![false; num_vertices]; num_vertices];
285
286    for source in 0..num_vertices {
287        let mut stack = adjacency[source].clone();
288        while let Some(vertex) = stack.pop() {
289            if reachable[source][vertex] {
290                continue;
291            }
292            reachable[source][vertex] = true;
293            stack.extend(adjacency[vertex].iter().copied());
294        }
295    }
296
297    reachable
298}
299
300#[cfg(test)]
301#[path = "../../unit_tests/models/graph/minimum_dummy_activities_pert.rs"]
302mod tests;
problemreductions/models/graph/minimum_dummy_activities_pert.rs

problemreductions/models/graph/
minimum_dummy_activities_pert.rs
