1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

use super::*;

#[derive(Debug, PartialEq, Eq, ProvidesStaticType, Allocative, Clone, Deserialize, Serialize)]
pub struct Workflow {
    pub name: String,
    pub version: String,
    pub tasks: HashMap<String, Task>,
}

impl Workflow {
    /// Finds the list of dependencies that the given task depends on.
    ///
    /// # Arguments
    ///
    /// * `task_name` - A string slice that holds the name of the task
    /// * `workflow_index` - A integer that holds the index of the workflow where the given
    ///   task is stored
    ///
    /// # Returns
    ///
    /// * `Option<Vec<String>>` - An option containing a vector of dependencies if the task is
    ///   found, or None if the task have no dependency
    ///
    pub fn get_dependencies(&self, task_name: &str) -> Option<Vec<String>> {
        let mut dependencies = Vec::<String>::new();

        for task in self.tasks.get(task_name).unwrap().depend_on.iter() {
            dependencies.push(task.task_name.clone());
        }

        Some(dependencies)
    }

    /// Performs depth-first search (DFS) in the workflow subgraph.
    /// This method is invoked within the get_flow method to perform `Topological-Sorting`
    /// # Arguments
    ///
    /// * `task_name` - A string slice that holds the name of the task where the DFS should start
    /// * `visited` - A mutable reference to a HashMap that holds the list of task (node) names
    ///   and a boolean indicating whether it has been traversed
    /// * `flow` - A mutable reference to a vector of strings that stores the flow of the DFS
    ///   traversal
    /// * `workflow_index` - An integer that holds the index of the workflow where the given
    ///   task is located
    ///
    fn dfs(&self, task_name: &str, visited: &mut HashMap<String, bool>, flow: &mut Vec<String>) {
        visited.insert(task_name.to_string(), true);

        for depend_task in self.get_dependencies(task_name).unwrap().iter() {
            if !visited[depend_task] {
                self.dfs(depend_task, visited, flow);
            }
        }

        flow.push(task_name.to_string());
    }

    /// Performs topological sort in the workflow graph.
    /// This method is invoked by the parse_module.
    ///
    /// # Arguments
    ///
    /// * `workflow_index` - An integer that holds the index of the workflow for which
    ///   topological sort is to be performed
    ///
    /// # Returns
    ///
    /// * `Vec<String>` - A vector containing the list of task names in the order of the
    ///   topological sort
    ///
    pub fn get_flow(&self) -> Vec<String> {
        let mut visited = HashMap::<String, bool>::new();
        let mut flow = Vec::<String>::new();

        for task in self.tasks.iter() {
            visited.insert(task.0.to_string(), false);
        }

        for task in self.tasks.iter() {
            if !visited[task.0] {
                self.dfs(task.0, &mut visited, &mut flow)
            }
        }

        flow
    }
}