TopologicallySortable

ascii_dag::layout::generic

Trait TopologicallySortable 

Source 
pub trait TopologicallySortable {
    type Id: Clone + Eq + Hash + Ord;

    // Required methods
    fn get_all_ids(&self) -> Vec<Self::Id>;
    fn get_dependencies(&self, id: &Self::Id) -> Vec<Self::Id>;

    // Provided methods
    fn topological_sort(&self) -> Result<Vec<Self::Id>, Vec<Self::Id>> { ... }
    fn has_valid_ordering(&self) -> bool { ... }
}
Expand description

Trait for types that support topological sorting.

Implement this trait to get convenient topological_sort() methods.

§Examples

use ascii_dag::layout::generic::TopologicallySortable;
use std::collections::HashMap;

struct TaskGraph {
    tasks: Vec<String>,
    dependencies: HashMap<String, Vec<String>>,
}

impl TopologicallySortable for TaskGraph {
    type Id = String;

    fn get_all_ids(&self) -> Vec<String> {
        self.tasks.clone()
    }

    fn get_dependencies(&self, id: &String) -> Vec<String> {
        self.dependencies.get(id).cloned().unwrap_or_default()
    }
}

// Now you can call:
// let sorted = task_graph.topological_sort().unwrap();

Required Associated Types§

Source

type Id: Clone + Eq + Hash + Ord

The type of identifiers in the graph.

Required Methods§

Source

fn get_all_ids(&self) -> Vec<Self::Id>

Get all item IDs in the collection.

Source

fn get_dependencies(&self, id: &Self::Id) -> Vec<Self::Id>

Get the dependencies for a given item.

Provided Methods§

Source

fn topological_sort(&self) -> Result<Vec<Self::Id>, Vec<Self::Id>>

Perform topological sorting on this collection.

§Returns
  • Ok(Vec<Id>) - Items in dependency order
  • Err(Vec<Id>) - A cycle was detected
Examples found in repository?
examples/topological_sort.rs (line 109)
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}
Source

fn has_valid_ordering(&self) -> bool

Check if a valid topological ordering exists (i.e., no cycles).

Implementors§