topological_sort/
topological_sort.rs

1use ascii_dag::layout::generic::{TopologicallySortable, topological_sort_fn};
2use std::collections::HashMap;
3
4fn main() {
5    println!("=== Generic Topological Sorting Examples ===\n");
6
7    // Example 1: Build system tasks
8    example_build_tasks();
9
10    // Example 2: Package dependencies
11    example_packages();
12
13    // Example 3: Trait-based API
14    example_trait_based();
15
16    // Example 4: Cycle detection
17    example_cycle_detection();
18}
19
20fn example_build_tasks() {
21    println!("1. Build System Tasks:");
22    println!("   Dependencies: deploy→test→build→compile\n");
23
24    let get_deps = |task: &&str| match *task {
25        "deploy" => vec!["test", "build"],
26        "test" => vec!["build"],
27        "build" => vec!["compile"],
28        "compile" => vec![],
29        _ => vec![],
30    };
31
32    let tasks = ["deploy", "test", "build", "compile"];
33
34    match topological_sort_fn(&tasks, get_deps) {
35        Ok(sorted) => {
36            println!("   Execution order:");
37            for (i, task) in sorted.iter().enumerate() {
38                println!("   {}. {}", i + 1, task);
39            }
40        }
41        Err(cycle) => println!("   ERROR: Cycle detected: {:?}", cycle),
42    }
43    println!();
44}
45
46fn example_packages() {
47    println!("2. Package Dependencies:");
48    println!("   app depends on lib-a and lib-b");
49    println!("   both libs depend on lib-core\n");
50
51    let get_deps = |pkg: &&str| match *pkg {
52        "app" => vec!["lib-a", "lib-b"],
53        "lib-a" => vec!["lib-core"],
54        "lib-b" => vec!["lib-core"],
55        "lib-core" => vec![],
56        _ => vec![],
57    };
58
59    let packages = ["app", "lib-b", "lib-a", "lib-core"]; // Unsorted
60
61    match topological_sort_fn(&packages, get_deps) {
62        Ok(sorted) => {
63            println!("   Build order:");
64            for (i, pkg) in sorted.iter().enumerate() {
65                println!("   {}. {}", i + 1, pkg);
66            }
67        }
68        Err(cycle) => println!("   ERROR: Cycle detected: {:?}", cycle),
69    }
70    println!();
71}
72
73fn example_trait_based() {
74    println!("3. Trait-Based API (Course Prerequisites):");
75
76    struct CourseSchedule {
77        courses: Vec<String>,
78        prerequisites: HashMap<String, Vec<String>>,
79    }
80
81    impl TopologicallySortable for CourseSchedule {
82        type Id = String;
83
84        fn get_all_ids(&self) -> Vec<String> {
85            self.courses.clone()
86        }
87
88        fn get_dependencies(&self, id: &String) -> Vec<String> {
89            self.prerequisites.get(id).cloned().unwrap_or_default()
90        }
91    }
92
93    let mut prereqs = HashMap::new();
94    prereqs.insert("CS301".to_string(), vec!["CS201".to_string()]);
95    prereqs.insert("CS201".to_string(), vec!["CS101".to_string()]);
96    prereqs.insert("CS101".to_string(), vec![]);
97
98    let schedule = CourseSchedule {
99        courses: vec![
100            "CS301".to_string(),
101            "CS101".to_string(),
102            "CS201".to_string(),
103        ],
104        prerequisites: prereqs,
105    };
106
107    println!("   CS301 requires CS201, which requires CS101\n");
108
109    match schedule.topological_sort() {
110        Ok(sorted) => {
111            println!("   Semester order:");
112            for (i, course) in sorted.iter().enumerate() {
113                println!("   Semester {}: {}", i + 1, course);
114            }
115        }
116        Err(cycle) => println!("   ERROR: Circular prerequisites: {:?}", cycle),
117    }
118    println!();
119}
120
121fn example_cycle_detection() {
122    println!("4. Cycle Detection:");
123    println!("   Task A depends on B, B on C, C on A (circular!)\n");
124
125    let get_deps = |task: &&str| match *task {
126        "A" => vec!["B"],
127        "B" => vec!["C"],
128        "C" => vec!["A"], // Creates cycle!
129        _ => vec![],
130    };
131
132    let tasks = ["A", "B", "C"];
133
134    match topological_sort_fn(&tasks, get_deps) {
135        Ok(_) => println!("   ✓ No cycles detected"),
136        Err(cycle) => {
137            println!("   ✗ Cycle detected!");
138            println!("   Circular dependency: {:?}", cycle);
139        }
140    }
141    println!();
142}
topological_sort/topological_sort.rs

topological_sort/
topological_sort.rs
