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
}
}