Topological Sorting

How Should I Begin to Complete My To-Do List?

Today’s lesson, number 5 in the Algorithms Unplugged book, shows that you can do some algorithms during your normal day without being known.

Every day you have a list of missions you manage to finish which is known as a to-do list the to-do list can be easy to write but it’s always hard to stick with and complete it.

So how does the algorithm help me in such a case it will not help you of course to finish it because this depends on your efforts and commitment sad news I know but it will help you in sorting it in a way that will help you to finish it properly.

I love to give examples let’s say this is my to-do list for today:

• Do English essay
• washing dishes
• buy soft drink

Well, it’s a simple to-do list and it only consists of 3 things but you still can be lazy enough and not able to finish it at the end of the day. wait a minute, are you lazy? or do you need to have a different technique in writing your to-do list?

I think that you have written it in a bad way because every task has a prerequisite task or even tasks that you have to finish before beginning this task for example to do an English essay you may need to borrow a book from the library and surf the internet, and that’s not the end of it to borrow a book you must go to the centre of the city and visit the library to borrow it. So if we put all the tasks we need to do with put in mind prerequisite tasks that may come up with this bigger to-do list:

• install PC
• go to centre
• borrow book
• surf the internet
• buy washing liquid
• washing dishes
• do English essay
• buy soft drink

Now you will say well done Zakaria from 3 to 7 it gets bigger and more complex how can this even help me to finish it well if you sort it in a proper way you will finish it.

You can see that there are tasks that depend on other tasks so you can’t start them at the beginning of your day until you have finished the tasks they depend on For example I can’t wash dishes unless I buy washing liquid and I can’t buy washing liquid unless I go to the centre.

So putting these priorities in mind you may come up with this list:

• go to centre
• borrow book
• buy washing liquid
• buy soft drink
• install PC
• surf the internet
• do English essay
• washing dishes

What you have done here in logically sorting this list is a thing that every human does every day to manage his daily life tasks is called the topological sorting algorithm.

So if we want to represent this to-do list in a suitable data structure it will be represented as a graph. We will consider every task as a node and every node will be connected by other nodes through edges. the below image will make you more familiar with what I am talking about

The above graph represents our to-do list I have added wake up only I know it seems like a silly task but when you finish any task you will feel deserve enough to finish the following task so why not? let’s deceive our brains.

From the graph, we can see that we only can start with a node that has no node points to it. So I can start only with waking up and after that, I have two choices as a human you will have some priorities maybe you have a slow computer that takes time to start so you will turn it on and go to the centre to finish your shopping so your PC will be ready when you come back home and these priorities are not handled by this algorithm.

The Topological sorting algorithm only ensures that when washing dishes for example we have already woken up, go to the centre and buy washing liquid. but if two choices have the same level (can be executed at the same time) like going to the centre and installing a PC it will depend on how you order the nodes that you pass to algorithms so if we consider nodes as an array and it is equal V = [“wake up”, “go to centre”, “install pc” ….] then it will do something that can’t be done in real life which is going to centre then install PC which is already in your house.

💡 This is a thing that comes in my mind I don’t know if it’s applicable or not but maybe if we put pirioty for each node we can make it more smart to take decision in such case. e.g V = [{task:”wake up”, p:0}, {task:”go to center”, p:1} , {task:”install pc”, p:2}] and then when we iterate throug nodes we can choose to finish all the nodes (children) of the higher pirioty task go to center then return back to the other node install pc and finish all the nodes (children) of it. If i implement a code that do such thing i will share it with you of course.

Topological sorting is implemented in many different ways but I have used the pseudo-code provided by the book to implement it and after searching it’s more similar to Kahn’s algorithm, there are also DFS (depth-first search) and parallel algorithms that you can use to implement the same concept.

At this, the graph G = (V, E) consists of the set of nodes V and a set of edges E of the form (node1,node2), whereas the dependency is directed from node2 to node1 (In other words, node1 is a prerequisite for node2 to occur or be executed) and V must contain both nodes.

function topologicalSort(graph) {
    const V = new Set(graph.nodes); // Make a set contain all nodes
    let E = [...graph.edges]; // Make a copy of the edges array

    while (V.size > 0) { // Loop as long as set has elements

        let cycle = true; // Consider that it's a cycle graph

        for (let v of V) { // loop through nodes inside set

            // check if the node has parent related to it
            const edgeIndex = findEdgeIndex(E, v); 
            // if it has no parent then you can execute it
            if (edgeIndex === -1) {
                // update our set and edges 
                V.delete(v); 
                E = removeEdgesWithNode(E, v);
                //know i have ensured that it's not cycle graph 
                cycle = false;
                console.log(v); // printing out the executed node
            }
        }
        // check if we have cycle 
        if (cycle) {
            // break the loop 
            console.log("I cannot resolve cyclic dependencies!");
            break;
        }
    }
}
// helper function to find if a node has a parent
function findEdgeIndex(edges, node) {
    return edges.findIndex(([X,v])=> node === v)
}
// helper function to delete the edges of the executed node
function removeEdgesWithNode(edges, node) {
    return edges.filter(([v,_])=> v !== node)
}

// Example usage
const graph = {
    nodes: ['Wake up', 'Go to center','Borrow book', 
   'Search internet' , 'Buy Coca Cola' , 'Buy washing liquid' 
  , 'Do English Essay' , 'Washing Dishes' , 'Install pc'],
    edges: [
        ['Wake up', 'Go to center'],
        ['Wake up', 'Install pc'],
        ['Go to center', 'Borrow book'],
        ['Go to center', 'Buy Coca Cola'],
        ['Go to center','Buy washing liquid'],
        ['Buy washing liquid' , 'Washing Dishes'],
        ['Borrow book' , 'Do English Essay' ],
        ['Install pc', 'Search internet' ],
        ['Search internet', 'Do English Essay' ],
        
    ],
};

topologicalSort(graph);

// out put will be: 
/* 
Wake up
Go to center
Borrow book
Buy Coca Cola
Buy washing liquid
Washing Dishes
Install pc
Search internet
Do English Essay
*/

As you can see it works perfectly it even detects if the graph is cycle one which means every node has a parent and no root node therefore we reach a deadlock state where every task depends on another task and no task will be executed so we must break out the loop or we will have an infinite loop.

The book has mentioned that this algorithm can be used in many fields of computer science and the most famous use is to solve deadlock status that happens by cycle graph as we mentioned before and easily detected by TopSort algorithm. In the end, one program has to be aborted and that is what will happen with the help of this algorithm.

I think it’s a very nice topic I have enjoyed reading it and more enjoyed trying to simplify it for you hope it helps you to understand it. Tomorrow we have another lesson explained from Algorithms Unplugged in which we will talk about Searching text in a fast way. very attractive topic so stay tuned💥.