Kahn's Algorithm | Topological Sort | Graph Cycle Detection

A sort that return a specific order of the vertex of a given a graph as long as the graph satisfies certain condition. This is a simple algorithm to learn.

First thing we need to look at is vertex at Isolation.

(A)

Every vertex in isolation has what's known as in-degree factor.

This only applies as long as the vertex is within a directed graph.

This is the key, graph needs to have edges that are directed in order to have this in degree value.

In degree value:

It's represented as how many connections are coming into this vertex. We want to start with vertex that has 0 because we're looking at a vertex in isolation.

So the easiest way to think about it is how many edges are pointing into this vertex

this is whatever the in-degree value for that vertex will be.

Now we understand in-degree, how does this apply to topological sort?

So topological sort is less a sort, but more a way to get this order in a topological sense

What it is is simply, when you get a graph that's directed, you want to figure out what every vertex's in-degree value is

A ----> B < ----- C
        |         |
        V         V  
D-----> E         F

In-degree values:

A : 0

B : 2

C : 0

D : 0

E : 2

F : 1

(A) => (B)
Indegree = 1 for B

The way topological sort works is that you can only take a vertex and it's value as long as its in-degree value is 0. But once you take it , then you want to remove it from the graph.

What that will do is, it will reduce the in-degree value of any nodes that it is directing into and then those nodes become open for us to take as a next value.

But because there may be multiple values where in-degree value is 0,

you can take them in whichever order

Topological sort does-not have very set order.

Topological rule is a graph should be DAG i.e Directed Acyclic Graph and will not be able to help us if a graph is Directed cyclic graph. ACG

(A:0) ----> B:2 < ----- (C:0)
             |         |
             V         V  
(D:0)-----> E:2      F:1

Here, we want to take the initial value of one of the vertex with in-degree of 0

here A, C, and D has in-degree 0
let just take C and put it in the array output, that will hold the order that we want to see for this topological sort.
Decrement 1 from the indegree value of any vertex it C is directing into i.e F & B

(A:0) ----> B:1
             |         
             V          
(D:0)-----> E:2      F:0

here we see that (F) has indegree value of 0, so let's take that

order = [C, F]

(A:0) ----> B:1
             |         
             V          
(D:0)-----> E:2

let's take (D) this time

    order = [C, F, D]

    (A:0) ----> B:1
                |         
                V          
        -----> E:2

now let decrement in-degree value of any node it's directed to

    (A:0) ----> B:1
                |         
                V          
                E:1

Now let's take (A)

order = [C, F, D, A]

         ----> B:1
                |         
                V          
                E:1

Now let's decrement in-degree value of any node it's directing into i.e B

Now let's remove B

    order = [C, F, D, A, B]

                |         
                V          
                E:1

let's decrement indegree value of any node it's directing into i.e E

E:0

Now let's remove E

    order = [C, F, D, A, B, E]

This is one example of the topological order that we can get from that graph.

So when is topological sort not applicable?

It is always applicable in directed graph

There can be no cycle within this graph for us to perform a topological sort

If the graph contains a cycle, then it's impossible for us to get the value

The reason why is we can see this eg:

(A:0) ----> B:2  -----> (C:1)
             ^            |
             |            V  
             | ---------- F:1

When to do topological sort, A is the only value with indegree 0

sort [ A ]
   
         ----> B:2  -----> (C:1)
                ^            |
                |            V  
                | ---------- F:1

now decrementing in-degree value that A is directing to nodes

                B:1  -----> (C:1)
                ^            |
                |            V  
                | ---------- F:1

Now we can't take any of the remaining vertex because the in-degree value for these vertex is 1, and topological sort is only able to take vertex where they're in degree 0

But this also does-not mean that this topological algorithm does not have it's use cases if you have DCG i.e Directed Cyclic Graph

To figure out whether or not our directed graph is acyclic or a cyclic.

Once we finish our topological sort, if we are able to reach every single vertex, then it's a acyclic graph.

If we are not able to then, there must have been a cycle.

this note was taken from

https://www.udemy.com/

Let's solve a course schedule problem in leetcode that utilizes this Topological Sort

course-schedule/description/

 /**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */

var canFinish = function (numCourses, prerequisites) {
    const inDegree = new Array(numCourses).fill(0)
    const graph = new Array(numCourses).fill(1).map(o => [])

    for (let [course, prereq] of prerequisites) {
        inDegree[course]++
        graph[prereq].push(course)
    }

we then start from indegree 0 value

    const queue = []
    for(let i = 0; i < inDegree.length; i++){
        if(inDegree[i] === 0){
            queue.push(i)
        }
    }

we run bfs on that inDegree 0 node

    let course = bfs(queue, inDegree, graph)
    return numCourses === course
};

bfs returns us the number of courses we can take:

function bfs(queue, inDegree, graph){
    let courseCompleted = 0
    while(0 < queue.length){
        const vertex = queue.shift()
        courseCompleted++
        const connections = graph[vertex] || []
        for(let conn of connections){
            inDegree[conn]--
            if(inDegree[conn] === 0){
                queue.push(conn)
            }
        }
    }
    return courseCompleted
}