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

problemreductions/models/graph/
minimum_dummy_activities_pert.rs
