Precedence Network Analysis for Rust

Precedence Networks

A Precedence Network (or Precedence diagram method) is a method of constructing connected activivies in a directed graph that specify dependencies. By specifyfing the minmimum, expected and maximum duration of each task the network can be analysed to find activities that sit on the critical path and must be completed on time to avoid delaying the entire network.

Usage

Given the following precedence network

                       ┌──────────┐
     ┌────────────────►│Document:4├─────────────────┐
     │                 └──────────┘                 │
     │                                              ▼
┌────┴───┐       ┌─────────┐     ┌──────┐      ┌────────┐
│Design:5├──────►│Develop:6├────►│Test:4├─────►│Deploy:1│
└────────┘       └──────┬──┘     └──────┘      └────────┘
                        │                           ▲
                        │         ┌───────┐         │
                        └────────►│Train:3├─────────┘
                                  └───────┘

Using precedence-net we can model it with the following code

use precedence_net::{Network, Result};

fn main() -> Result<()> {
  let mut network_builder = Network::builder();

  network_builder.add_activity("Design", 5.0)?;
  network_builder.add_activity("Develop", 6.0)?;
  network_builder.add_activity("Document", 4.0)?;
  network_builder.add_activity("Deploy", 1.0)?;
  network_builder.add_activity("Train", 3.0)?;
  network_builder.add_activity("Test", 4.0)?;

  network_builder.connect("Design", "Develop")?;
  network_builder.connect("Design", "Document")?;
  network_builder.connect("Develop", "Test")?;
  network_builder.connect("Develop", "Train")?;
  network_builder.connect("Test", "Deploy")?;
  network_builder.connect("Train", "Deploy")?;
  network_builder.connect("Document", "Deploy")?;

  let network = Network::try_from(network_builder)?;

  println!("Activity | Earliest Start | Earliest Finish | Latest Start | Latest Finish | Total Float | Free Float | Critical Path");
  println!("---------------------------------------------------------------------------------------------------------------------");
  for activity in network.activities()? {
    println!(
      "{:^8} | {:>14} | {:>15} | {:>12} | {:>13} | {:>11} | {:>10} | {:^14}",
      activity,
      network.earliest_start(activity)?,
      network.earliest_finish(activity)?,
      network.latest_start(activity)?,
      network.latest_finish(activity)?,
      network.total_float(activity)?,
      network.free_float(activity)?,
      network.on_critical_path(activity)?,
    );
  }
  Ok(())
}

will produce the following output

Activity | Earliest Start | Earliest Finish | Latest Start | Latest Finish | Total Float | Free Float | Critical Path
---------------------------------------------------------------------------------------------------------------------
 Design  |              0 |               5 |            0 |             5 |           0 |          0 |      true
Develop  |              5 |              11 |            5 |            11 |           0 |          0 |      true
Document |              5 |               9 |           11 |            15 |           6 |          6 |     false
  Test   |             11 |              15 |           11 |            15 |           0 |          0 |      true
 Train   |             11 |              14 |           12 |            15 |           1 |          1 |     false
 Deploy  |             15 |              16 |           15 |            16 |           0 |          0 |      true

Performance

Using Criterion.rs the following activities were benchmarked for a precedence network of 62 500 activities on an Intel Core i7 with 16GB RAM.

• Adding activities to the network: 78ms
• Creating Network from Network Builder: 239ms
• Creating NetworkBuilder from Network: 44ms
• Retrieving Critical Path: 1.1ms

To Implement

• Cyclic route checking
• Serialize and deserialize
• Update activities

License

Copyright 2022 Farrel Lifson

Released under the MIT License. See LICENSE-MIT for details.