Topological sorting of 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 ab, of vertex a to b, a, always comes before b.
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 other), pre-requisite problems (what course or problems should be solved in other to solve a higher problem) — (adapted from geekforgeeks)
In other to sort a graph with topological ordering, such a graph must be:
1. Directed: Edges must have direction
2. Acyclic: This means that there would be no cycle in such a graph.
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, define a Directed Acyclic Graph (DAG) struct, and name it DAG (defines what our graph would like):
Next, we will define a method called new on the DAG struct, the new method will be used to create an instance of a graph using the argument passed into it.
1. The new method accepts an argument graph_info which is a vector of tuples containing u8 values.
2. It 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 its key as graph.
5. and then call the get_topological_order method.
The get_topological_order method stores the order of the graph in a stack (LIFO - last in, first out).
1. Create a stack of u8 values (in this case, we would use Rust’s vector as a stack) called stack
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.
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 vertices that this vertex points to and does the same of all of such vertex 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.
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)]
Going a step forward to test our output:
