graco/

activities.rs

use crate::petgraph::graph::Graph;
use crate::petgraph::prelude::*;
use std::fmt;

#[derive(Debug, Clone, Copy)]
pub struct Resource {
    /// Name of the resource
    pub id: u32,
    /// Number of times this resource is reusable
    pub reusability: u16,
}

#[derive(Debug, Clone)]
pub struct Activity {
    /// Earliest start (get the latest start by adding the slack time)
    pub earliest_start: u32,
    /// Earliest finish (get the latest finish by adding the slack time)
    pub earliest_finish: u32,
    /// Slack time, i.e. difference between the earliest and latest start or, equally, end
    pub slack: u32,
    /// Vector of resources
    pub resources: Vec<Resource>,
    /// An activity is a dummy activity if it is the very first or very last
    pub dummy: bool,
}

impl fmt::Display for Activity {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        if self.dummy {
            write!(
                f,
                "dur: {}\t#r: {}",
                self.earliest_finish - self.earliest_start,
                self.resources.len()
            )
        } else if self.resources.len() > 1 {
            write!(
                f,
                "dur: {}\t#r: {}\n({} .. {})",
                self.earliest_finish - self.earliest_start,
                self.resources.len(),
                self.resources[0].id,
                self.resources[self.resources.len() - 1].id
            )
        } else {
            write!(
                f,
                "dur: {}\t#r: {}\n({})",
                self.earliest_finish - self.earliest_start,
                self.resources.len(),
                self.resources[0].id
            )
        }
    }
}

impl Activity {
    pub fn start() -> Activity {
        Activity {
            earliest_start: 0,
            earliest_finish: 0,
            slack: 0,
            resources: vec![],
            dummy: true,
        }
    }

    pub fn from_earliest_start(start: u32, duration: u32, resources: Vec<Resource>) -> Activity {
        Activity {
            earliest_start: start,
            earliest_finish: start + duration,
            slack: 0,
            resources: resources.clone(),
            dummy: false,
        }
    }

    pub fn duration(&self) -> u32 {
        self.earliest_finish - self.earliest_start
    }
}

#[derive(Clone, Copy)]
pub enum BuildUntil {
    Exhaustion,
    UntilNActivities(usize),
}

#[derive(Clone, Copy)]
pub enum ResAlloc {
    /// Activities require exactly two resources
    Single,
    /// Activities require exactly one resource
    Dual,
}

fn place_dual_resource_activities<V: Copy, W: Copy, T: fmt::Display>(
    mut activities: &mut Graph<Activity, T, Directed>,
    resources: Vec<Resource>,
    prev_node: NodeIndex<u32>,
    activity_duration: u32,
    edge_weighting: W,
    activity_valid: V,
    condition: BuildUntil,
) where
    V: Fn(Activity, Activity) -> bool,
    W: Fn(Activity, Activity) -> T,
{
    let mut available_resources = resources.clone();

    let get_node_uid = |res_1: Resource, res_2: Resource| {
        if res_1.id > res_2.id {
            (res_1.id, res_2.id)
        } else {
            (res_2.id, res_1.id)
        }
    };

    let mut node_id: Option<(u32, u32)> = None;
    // Use the current node resources
    let prev_activity = activities[prev_node].clone();
    if !prev_activity.dummy {
        // We are using this
        let res_1 = prev_activity.resources[0];
        let res_2 = prev_activity.resources[1];
        for res in &mut available_resources {
            if res.id == res_1.id || res.id == res_2.id {
                res.reusability -= 1;
            }
        }

        node_id = Some(get_node_uid(res_1, res_2));
    }

    let cur_time = prev_activity.earliest_finish;
    let mut added_nodes = Vec::new();

    for i in 0..available_resources.len() {
        if available_resources[i].reusability == 0 {
            continue; // This resource has been exhausted
        }

        for j in 0..available_resources.len() {
            if i == j {
                continue;
            }

            if let BuildUntil::UntilNActivities(max_num) = condition {
                if activities.node_count() >= max_num {
                    break;
                }
            }

            if available_resources[j].reusability == 0 {
                continue; // This resource has been exhausted
            }

            if let Some(prev_id) = node_id {
                // Check that the node we are about to add is not the same as the previous node
                if prev_id == get_node_uid(available_resources[i], available_resources[j]) {
                    continue;
                }
            }

            let new_node_id = get_node_uid(available_resources[i], available_resources[j]);
            if added_nodes.contains(&new_node_id) {
                continue;
            }
            added_nodes.push(new_node_id);

            // New activity looks like it can fit, let's use it
            let new_activity = Activity::from_earliest_start(
                cur_time,
                activity_duration,
                vec![available_resources[i], available_resources[j]],
            );

            // Check that this activity can be placed after the previous one
            if !activity_valid(prev_activity.clone(), new_activity.clone()) {
                continue;
            }

            let new_node = activities.add_node(new_activity.clone());

            activities.add_edge(
                prev_node,
                new_node,
                edge_weighting(prev_activity.clone(), new_activity),
            );

            place_dual_resource_activities(
                &mut activities,
                available_resources.clone(),
                new_node,
                activity_duration,
                edge_weighting,
                activity_valid,
                condition,
            );
        }
    }
}

fn place_sgl_resource_activities<V: Copy, W: Copy, T: fmt::Display>(
    mut activities: &mut Graph<Activity, T, Directed>,
    resources: Vec<Resource>,
    prev_node: NodeIndex<u32>,
    activity_duration: u32,
    edge_weighting: W,
    activity_valid: V,
    condition: BuildUntil,
) where
    V: Fn(Activity, Activity) -> bool,
    W: Fn(Activity, Activity) -> T,
{
    let mut available_resources = resources.clone();

    let mut node_id: Option<u32> = None;
    // Use the current node resources
    let prev_activity = activities[prev_node].clone();
    if !prev_activity.dummy {
        // We are using this
        let res_1 = prev_activity.resources[0];
        for res in &mut available_resources {
            if res.id == res_1.id {
                res.reusability -= 1;
                break;
            }
        }

        node_id = Some(res_1.id);
    }

    let cur_time = prev_activity.earliest_finish;
    let mut added_nodes = Vec::new();

    for resource in available_resources.clone() {
        if resource.reusability == 0 {
            continue; // This resource has been exhausted
        }

        if let BuildUntil::UntilNActivities(max_num) = condition {
            if activities.node_count() >= max_num {
                break;
            }
        }

        if let Some(prev_id) = node_id {
            // Check that the node we are about to add is not the same as the previous node
            if prev_id == resource.id {
                continue;
            }
        }

        let new_node_id = resource.id;
        if added_nodes.contains(&new_node_id) {
            continue;
        }
        added_nodes.push(new_node_id);

        // New activity looks like it can fit, let's use it
        let new_activity =
            Activity::from_earliest_start(cur_time, activity_duration, vec![resource]);

        // Check that this activity can be placed after the previous one
        if !activity_valid(prev_activity.clone(), new_activity.clone()) {
            continue;
        }

        let new_node = activities.add_node(new_activity.clone());

        activities.add_edge(
            prev_node,
            new_node,
            edge_weighting(prev_activity.clone(), new_activity),
        );

        place_sgl_resource_activities(
            &mut activities,
            available_resources.clone(),
            new_node,
            activity_duration,
            edge_weighting,
            activity_valid,
            condition,
        );
    }
}

pub fn build_equal_activities<V: Copy, W: Copy, T: fmt::Display>(
    resources: Vec<Resource>,
    activity_duration: u32,
    edge_weighting: W,
    activity_valid: V,
    condition: BuildUntil,
    alloc: ResAlloc,
) -> Graph<Activity, T, Directed>
where
    V: Fn(Activity, Activity) -> bool,
    W: Fn(Activity, Activity) -> T,
{
    let mut activities: Graph<Activity, T, Directed> = Graph::new();
    let start_node = activities.add_node(Activity::start());

    match alloc {
        ResAlloc::Dual => place_dual_resource_activities(
            &mut activities,
            resources,
            start_node,
            activity_duration,
            edge_weighting,
            activity_valid,
            condition,
        ),
        ResAlloc::Single => place_sgl_resource_activities(
            &mut activities,
            resources,
            start_node,
            activity_duration,
            edge_weighting,
            activity_valid,
            condition,
        ),
    };

    activities
}

#[test]
fn test_builder_dual_resource() {
    use crate::io::export_dot;
    let sc1 = Resource {
        id: 1,
        reusability: 5,
    };
    let sc2 = Resource {
        id: 2,
        reusability: 5,
    };
    let sc3 = Resource {
        id: 3,
        reusability: 5,
    };

    let always_true = |_, _| true;

    let activities = build_equal_activities(
        vec![sc1, sc2, sc3],
        60,
        always_true,
        always_true,
        BuildUntil::Exhaustion,
        ResAlloc::Dual,
    );
    assert_eq!(activities.node_count(), 298);
    assert_eq!(activities.edge_count(), 297);
    export_dot(&activities, "dotgraphs/test_builder_exhaustion_dual.dot");

    // Test max nodes
    let activities = build_equal_activities(
        vec![sc1, sc2, sc3],
        60,
        always_true,
        always_true,
        BuildUntil::UntilNActivities(100),
        ResAlloc::Dual,
    );
    assert_eq!(activities.node_count(), 100);
    assert_eq!(activities.edge_count(), 99);
    export_dot(&activities, "dotgraphs/test_builder_untilN_dual.dot");
}

#[test]
fn test_builder_sgl_resource() {
    use crate::io::export_dot;
    let sc1 = Resource {
        id: 1,
        reusability: 1,
    };
    let sc2 = Resource {
        id: 2,
        reusability: 1,
    };
    let sc3 = Resource {
        id: 3,
        reusability: 1,
    };

    let always_true = |_, _| true;

    let activities = build_equal_activities(
        vec![sc1, sc2, sc3],
        60,
        always_true,
        always_true,
        BuildUntil::Exhaustion,
        ResAlloc::Single,
    );
    export_dot(&activities, "dotgraphs/test_builder_exhaustion_single.dot");

    let activities = build_equal_activities(
        vec![sc1, sc2, sc3],
        60,
        always_true,
        always_true,
        BuildUntil::UntilNActivities(25),
        ResAlloc::Single,
    );
    export_dot(&activities, "dotgraphs/test_builder_untilN_single.dot");
}