25.1.2. Topological Sorting

So, recall that the directed acyclic graph is just a directed graph in which there is no directed path from any vertex back to itself, so it is direct and it is acyclic.

A Directed Acyclic Graph (DAG) is a special type of directed graph. In a directed graph, the edges have a direction, meaning they go from one vertex to another. An acyclic graph is one that does not contain cycles, which means there are no paths that start and end at the same vertex. Therefore, in a DAG, you cannot start at a vertex and follow the directed edges to return to that vertex. This property is crucial for many algorithms that operate on DAGs.

Think of a DAG like a flow of tasks in a project. Each task must be completed before certain other tasks can start. If a task has already been completed, it can’t be revisited, reflecting the acyclic nature of the graph.

Any directed acyclic graph can be topologically ordered. If you think of the vertices as being 1 to n, you can write out 1 to n as a sequence in such a way that for every pair j, k which is an edge if j, k is an edge in my graph, then j will appear before k in the sequence.

Topological ordering is a linear arrangement of the vertices in a DAG such that for every directed edge from vertex j to vertex k, vertex j appears before vertex k in the ordering. This is essential for scheduling tasks where certain tasks depend on the completion of others. For example, if you have tasks that require specific prerequisites, a topological sort allows you to arrange those tasks in an order that respects those prerequisites.

Imagine you're planning a party. You have tasks such as sending invitations, preparing food, and decorating the venue. You need to send the invitations first because people should know about the party before they show up. A topological sort will help you figure out the right order to do each task so that they're completed in a way that meets all dependencies.

So, supposing we have this DAG and we imagine that the vertices represent courses and the edges are prerequisites. Now, these are courses that we have to do to complete the degree. Every course requires a semester, but we can do more than one course in a semester.

In this example, each course is represented as a vertex in a DAG, and any directed edge going from one vertex to another indicates that the first course must be completed before the second can be taken. The goal is to find the minimum number of semesters required to complete all courses while respecting the prerequisites. Through analyzing the dependencies represented in the DAG, one can compute how courses can be grouped into semesters.

Think of a student trying to decide when to take courses in college. Some courses need to be taken in a specific order, and some can be taken simultaneously. If the student needs to finish certain introductory courses before taking advanced ones, figuring out the shortest possible path (or minimum semesters) to graduate becomes a critical planning issue.

Now, this problem corresponds to asking for the longest path in the DAG. What we are saying is that it takes 5 semesters to complete 8 because there is a chain of dependencies...

The longest path in a DAG helps to determine the maximum amount of time or the minimum number of divisions needed to complete all tasks or courses. In this case, it highlights the fact that, while there may be numerous available paths between courses, it's the path involving dependencies that dictates the overall schedule and completion timeline. If one course relies on the completion of several others, the time taken to complete all will indeed be greater.

Consider a train station with multiple routes. Some routes require a train to finish its journey before other trains can take off. The longest route the trains take to reach their destinations reflects the time it takes to finish various paths. This perception helps in planning further routes and ensuring smooth connections between destinations.

Therefore in order to compute the longest path to k, I need to compute the longest path to all its incoming neighbours. ...

To calculate the longest path to a vertex k, one needs to consider the paths to all vertices that point to k (its incoming neighbours). If you have already computed these paths before reaching k in the topological sort, you can easily derive the longest path to k by adding one to the length of the longest incoming path. This method efficiently uses previously calculated values to streamline computations.

Think of it as building a pyramid where each layer's blocks depend on the layer below. If you know how many blocks are needed to fill each layer, calculating the total blocks needed to stack onto the next layer becomes straightforward, just as calculating the next longest path builds on previous lengths.

So, we can actually incrementally compute the value at k as you are going forwards. Because, going backwards requires you to scan this list and look for all the incoming neighbours...

By processing the vertices in topological order during the longest path calculation, you ensure that when you reach a vertex, you have already processed all its incoming neighbours. This allows for an ongoing update of the longest paths without needing to backtrack, significantly improving efficiency as the paths can be calculated in a single pass.

Picture crossing a river using stepping stones. Instead of going back to reassess which stones you've already crossed, you only focus on the next available stones as you move forward, thus ensuring you take the most efficient path across.

So, this pseudo code for longest path as we saw is very similar to what we did for the topological sort...

The algorithm for finding the longest path in a DAG closely resembles the one used for topological sorting. It begins with initializing the longest path value for each vertex to zero and proceeds by processing each vertex in a way that updates the longest paths iteratively. This ensures that as each vertex's edges are traversed, the longest path calculations are concurrently made.

Imagine a relay race where each runner hands off a baton at different points. Each runner can pass along the time taken so far to their teammate while maintaining a record of the fastest lap. In this way, the overall completion time accumulates without the need to backtrack, highlighting efficiency in completing multiple segments.

--