Topological Sorting of a Directed Acyclic Graph in Rust Using DFS

Topological sorting refers to the linear ordering of vertices in a graph such that for every directed edge , of vertex to , always comes before . ab a b a, b Above is an image showing a directed acyclic graph (edge 0 and edge 1 are directed at edge 2, edge 2 is directed at edge 3 and edge 3 is directed at edge 4). from: https://generalducky.github.io/DAG/ : For the image above, there are two possible topological sort orders for this graph which would be: 1, 0, 2, 3, 4 or 0, 1, 2, 3, 4 . Example of topological sorting would be: task scheduling (what task should proceed before the order), pre-requisite problems (what course or problems should be solved in order to solve an higher problem) — (adapted from ) Typical applications geekforgeeks Our approach to solving this problem would involve using the . let’s get down to business already 😊 depth-first search First, we would create a module, import from rust’s standard library into our module, and define a ( ) struct name it , which defines what our graph would like: Graph hashMap Directed Acyclic Graph DAG DAG Graph { std::collections::HashMap; { graph: >, } } mod use //import hashmap from std lib pub struct DAG // define the DAG struct Option u8 Vec u8 Next, we will define a method on the struct call it that will create a graph from the argument passed into it. 1. The method accepts an argument which is a vector of tuples containing values. 2. Creates a hashMap ( ) that would contain the edges and vectors in our graph. 3. Loops through the argument and populates the with the information on the graph 4. Move the into the struct, wrapping it in theOption type as defined on the struct with it’s key as . 5. and then calls the method. DAG new new graph_info u8 adjacency_map graph_info adjacency_map adjacency_map Graph graph get_topological_order Graph { std::collections::HashMap; { graph: >, } DAG { (graph_info: ) -> { adjacency_map: HashMap > = HashMap::new(); value graph_info { source_vertex = & adjacency_list.entry(value. ).or_insert( []); source_vertex.push(value. ); } the_graph = DAG { graph: (adjacency_map), }; the_graph.get_topological_order(); } } mod use pub struct DAG Option u8 Vec u8 impl pub fn new Vec u8 u8 Vec u8 let mut u8 Vec u8 for in let mut 0 vec! 1 let Some return The method basically stores the order of the graph in a stack ( 1. Create a stack (in this case, we would use a vector but only use it as a stack) data-structure called , a vector of values. 2. Loop through the keys to get the order using the method. 3. Once the order is obtained, we would reverse the stack. get_topological_order LIFO i.e last in, first out). stack u8 graph get_order std::collections::HashMap; { graph: >, } DAG { (graph_info: ) -> {...} (& ) -> { source_nodes = .graph.as_ref().unwrap().keys(); stack: = []; node source_nodes { .get_order(node, & stack); } stack.reverse(); ( , stack); stack; } } use pub struct DAG Option u8 Vec u8 impl pub fn new Vec u8 u8 Vec u8 pub fn get_topological_order self Vec u8 let self let mut Vec u8 vec! for in self mut println! "THE STACK!! {:?}" return The method accepts the Using the node (current key) passed to it, the method gets all the values of such key, which are edges that this edge points to and does the same of all of such edges points to. Adding them to the stack. if such node does not point anywhere and has not been visited, i.e. it is not on the stack., it is pushed into the stack. get_order node (current key, borrowed u8 value), stack(mutable vector of u8 values) . get_order Graph { std::collections::HashMap; { graph: >, } DAG { (graph_info: ) -> {...} (& )-> { ... stack.reverse(); ( , stack); stack; } (& , node: & , stack: & ) { receiving_nodes = .graph.as_ref().unwrap().get(node); receiving_nodes != { value receiving_nodes.unwrap() { .get_order(value, stack); } } !stack.contains(node) { stack.push(*node); } } } mod use pub struct DAG Option u8 Vec u8 impl pub fn new Vec u8 u8 Vec u8 pub fn get_topological_order self Vec u8 println! "THE STACK!! {:?}" return pub fn get_order self u8 mut Vec u8 let self if None for in self if The result of our function should be one of the two vectors here: [1, 0, 2, 3, 4] or [0, 1, 2, 3, 4] . If we passed the argument as: vec![(0, 2), (1, 2), (2, 3), (3, 4)] () { Graphs; Graphs::DAG::new( [( , ), ( , ), ( , ), ( , )]); } Graphs { std::collections::HashMap; { graph: >>, } DAG { (graph_info: ) -> { adjacency_list: HashMap > = HashMap::new(); graph = graph_info.get( ..); value graph.unwrap() { source_vertex = & adjacency_list.entry(value. ).or_insert( []); source_vertex.push(value. ); } the_graph = DAG { graph: (adjacency_list), }; the_graph.get_topological_order(); } (& ) -> { source_nodes = .graph.as_ref().unwrap().keys(); stack: = []; node source_nodes { .get_order(node, & stack); } stack.reverse(); ( , stack); stack; } (& , node: & , stack: & ) { receiving_nodes = .graph.as_ref().unwrap().get(node); receiving_nodes != { value receiving_nodes.unwrap() { .get_order(value, stack); } } !stack.contains(node) { stack.push(*node); } } } } pub fn execute use // Graphs::DAG::new(vec![(4, 3), (1, 2), (4, 1), (3, 1)]); // Graphs::DAG::new(vec![(1, 2), (1, 4), (2, 3), (2, 4), (4, 3), (4, 5)]); vec! 0 2 1 2 2 3 3 4 mod use pub struct DAG Option u8 Vec u8 impl pub fn new Vec u8 u8 Vec u8 // DirectedGraph { graph: None } let mut u8 Vec u8 let 0 for in let mut 0 vec! 1 let Some return pub fn get_topological_order self Vec u8 let self let mut Vec u8 vec! // let mut visited: HashMap = HashMap::new(); for in // if visited.get(node) == None { self mut // } println! "THE STACK!! {:?}" return pub fn get_order self u8 mut Vec u8 let self // if visited.get(node) == None { if None for in self if // } Going a step forward to test our output: () { Graphs; result = Graphs::DAG::new( [( , ), ( , ), ( , ), ( , )]); ( , result); } Graphs { std::collections::HashMap; { graph: >>, } DAG { (graph_info: ) -> { adjacency_list: HashMap > = HashMap::new(); graph = graph_info.get( ..); value graph.unwrap() { source_vertex = & adjacency_list.entry(value. ).or_insert( []); source_vertex.push(value. ); } the_graph = DAG { graph: (adjacency_list), }; the_graph.get_topological_order(); } (& ) -> { source_nodes = .graph.as_ref().unwrap().keys(); stack: = []; node source_nodes { .get_order(node, & stack); } stack.reverse(); ( , stack); stack; } (& , node: & , stack: & ) { receiving_nodes = .graph.as_ref().unwrap().get(node); receiving_nodes != { value receiving_nodes.unwrap() { .get_order(value, stack); } } !stack.contains(node) { stack.push(*node); } } } } test { super::Graphs; () { result = Graphs::DAG::new( [( , ), ( , ), ( , ), ( , )]); (result.pop(), ( )); (result.pop(), ( )); (result.pop(), ( )); } } pub fn execute use // Graphs::DAG::new(vec![(4, 3), (1, 2), (4, 1), (3, 1)]); // Graphs::DAG::new(vec![(1, 2), (1, 4), (2, 3), (2, 4), (4, 3), (4, 5)]); let vec! 0 2 1 2 2 3 3 4 println! "THE RESULT >>> {:?}" mod use pub struct DAG Option u8 Vec u8 impl pub fn new Vec u8 u8 Vec u8 // DirectedGraph { graph: None } let mut u8 Vec u8 let 0 for in let mut 0 vec! 1 let Some return pub fn get_topological_order self Vec u8 let self let mut Vec u8 vec! // let mut visited: HashMap = HashMap::new(); for in // if visited.get(node) == None { self mut // } println! "THE STACK!! {:?}" return pub fn get_order self u8 mut Vec u8 let self // if visited.get(node) == None { if None for in self if // } #[cfg(test)] mod use #[test] fn test_topological_order let mut vec! 0 2 1 2 2 3 3 4 assert_eq! Some 4 assert_eq! Some 3 assert_eq! Some 2 find me on twitter [ @tolumide ] and github: [ tolumide-ng ]