1,251 reads
Topological Sorting of a Directed Acyclic Graph in Rust Using DFS
by Tolumide ShopeinOctober 20th, 2020
Too Long; Didn't Read
Topological sorting refers to the linear ordering of vertices in a graph such that for every edge ab, of a to b, a, always comes before b. There are two possible topological sort orders for this graph which would be: 1, 0, 2, 3, 4 or 0, 1, 4. Rust uses the depth-first search to sort the order of a directed acyclic graph. The get_topological_order method basically stores the order in a stack (LIFO)
Topological sorting refers to the linear ordering of vertices in a graph such that for every directed edge ab, of vertex a to b, a, always comes before 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/
Example: 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 .
Typical applications 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 geekforgeeks)
Our approach to solving this problem would involve using the depth-first search. let’s get down to business already 😊
First, we would create a Graph module, import hashMap from rust’s standard library into our module, and define a Directed Acyclic Graph (DAG) struct name it DAG, which defines what our graph would like:
mod Graph {
use std::collections::HashMap; //import hashmap from std lib
pub struct DAG { // define the DAG struct
graph: Option<HashMap<u8, Vec<u8>>,
}
}Next, we will define a method on the DAG struct call it new that will create a graph from the argument passed into it.
1. The new method accepts an argument graph_info which is a vector of tuples containing u8 values.
2. Creates a hashMap (adjacency_map) that would contain the edges and vectors in our graph.
3. Loops through the graph_info argument and populates the adjacency_map with the information on the graph
4. Move the adjacency_map into the Graph struct, wrapping it in theOption type as defined on the struct with it’s key as graph.
5. and then calls the get_topological_order method.
mod Graph {
use std::collections::HashMap;
pub struct DAG {
graph: Option<HashMap<u8, Vec<u8>>,
}
impl DAG {
pub fn new(graph_info: Vec<(u8, u8)>) -> Vec<u8> {
let mut adjacency_map: HashMap<u8, Vec<u8>> = HashMap::new();
for value in graph_info {
let source_vertex = &mut adjacency_list.entry(value.0).or_insert(vec![]);
source_vertex.push(value.1);
}
let the_graph = DAG {
graph: Some(adjacency_map),
};
return the_graph.get_topological_order();
}
}The get_topological_order method basically stores the order of the graph in a stack (LIFO i.e last in, first out).
1. Create a stack (in this case, we would use a vector but only use it as a stack) data-structure called stack, a vector of u8 values.
2. Loop through the graph keys to get the order using the get_order method.
3. Once the order is obtained, we would reverse the stack.
use std::collections::HashMap;
pub struct DAG {
graph: Option<HashMap<u8, Vec<u8>>,
}
impl DAG {
pub fn new(graph_info: Vec<(u8, u8)>) -> Vec<u8> {...}
pub fn get_topological_order(&self) -> Vec<u8> {
let source_nodes = self.graph.as_ref().unwrap().keys();
let mut stack: Vec<u8> = vec![];
for node in source_nodes {
self.get_order(node, &mut stack);
}
stack.reverse();
println!("THE STACK!! {:?}", stack);
return stack;
}
}
The get_order method accepts the node (current key, borrowed u8 value), stack(mutable vector of u8 values) .
Using the node (current key) passed to it, the get_order 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.
mod Graph {
use std::collections::HashMap;
pub struct DAG {
graph: Option<HashMap<u8, Vec<u8>>,
}
impl DAG {
pub fn new(graph_info: Vec<(u8, u8)>) -> Vec<u8> {...}
pub fn get_topological_order(&self)-> Vec<u8> {
...
stack.reverse();
println!("THE STACK!! {:?}", stack);
return stack;
}
pub fn get_order(&self, node: &u8, stack: &mut Vec<u8>) {
let receiving_nodes = self.graph.as_ref().unwrap().get(node);
if receiving_nodes != None {
for value in receiving_nodes.unwrap() {
self.get_order(value, stack);
}
}
if !stack.contains(node) {
stack.push(*node);
}
}
}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)]
pub fn execute() {
use Graphs;
// 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)]);
Graphs::DAG::new(vec![(0, 2), (1, 2), (2, 3), (3, 4)]);
}
mod Graphs {
use std::collections::HashMap;
pub struct DAG {
graph: Option<HashMap<u8, Vec<u8>>>,
}
impl DAG {
pub fn new(graph_info: Vec<(u8, u8)>) -> Vec<u8> {
// DirectedGraph { graph: None }
let mut adjacency_list: HashMap<u8, Vec<u8>> = HashMap::new();
let graph = graph_info.get(0..);
for value in graph.unwrap() {
let source_vertex = &mut adjacency_list.entry(value.0).or_insert(vec![]);
source_vertex.push(value.1);
}
let the_graph = DAG {
graph: Some(adjacency_list),
};
return the_graph.get_topological_order();
}
pub fn get_topological_order(&self) -> Vec<u8> {
let source_nodes = self.graph.as_ref().unwrap().keys();
let mut stack: Vec<u8> = vec![];
// let mut visited: HashMap<u8, bool> = HashMap::new();
for node in source_nodes {
// if visited.get(node) == None {
self.get_order(node, &mut stack);
// }
}
stack.reverse();
println!("THE STACK!! {:?}", stack);
return stack;
}
pub fn get_order(&self, node: &u8, stack: &mut Vec<u8>) {
let receiving_nodes = self.graph.as_ref().unwrap().get(node);
// if visited.get(node) == None {
if receiving_nodes != None {
for value in receiving_nodes.unwrap() {
self.get_order(value, stack);
}
}
if !stack.contains(node) {
stack.push(*node);
}
// }
}
}
}
Going a step forward to test our output:
pub fn execute() {
use Graphs;
// 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 result = Graphs::DAG::new(vec![(0, 2), (1, 2), (2, 3), (3, 4)]);
println!("THE RESULT >>> {:?}", result);
}
mod Graphs {
use std::collections::HashMap;
pub struct DAG {
graph: Option<HashMap<u8, Vec<u8>>>,
}
impl DAG {
pub fn new(graph_info: Vec<(u8, u8)>) -> Vec<u8> {
// DirectedGraph { graph: None }
let mut adjacency_list: HashMap<u8, Vec<u8>> = HashMap::new();
let graph = graph_info.get(0..);
for value in graph.unwrap() {
let source_vertex = &mut adjacency_list.entry(value.0).or_insert(vec![]);
source_vertex.push(value.1);
}
let the_graph = DAG {
graph: Some(adjacency_list),
};
return the_graph.get_topological_order();
}
pub fn get_topological_order(&self) -> Vec<u8> {
let source_nodes = self.graph.as_ref().unwrap().keys();
let mut stack: Vec<u8> = vec![];
// let mut visited: HashMap<u8, bool> = HashMap::new();
for node in source_nodes {
// if visited.get(node) == None {
self.get_order(node, &mut stack);
// }
}
stack.reverse();
println!("THE STACK!! {:?}", stack);
return stack;
}
pub fn get_order(&self, node: &u8, stack: &mut Vec<u8>) {
let receiving_nodes = self.graph.as_ref().unwrap().get(node);
// if visited.get(node) == None {
if receiving_nodes != None {
for value in receiving_nodes.unwrap() {
self.get_order(value, stack);
}
}
if !stack.contains(node) {
stack.push(*node);
}
// }
}
}
}
#[cfg(test)]
mod test {
use super::Graphs;
#[test]
fn test_topological_order() {
let mut result = Graphs::DAG::new(vec![(0, 2), (1, 2), (2, 3), (3, 4)]);
assert_eq!(result.pop(), Some(4));
assert_eq!(result.pop(), Some(3));
assert_eq!(result.pop(), Some(2));
}
}find me on twitter [@tolumide] and github: [tolumide-ng]
L O A D I N G
. . . comments & more!
. . . comments & more!
