25.1.6. Naive vs. Incremental Computation

If I do it naively then I will write out my vertices in some topological order and now when I come to this vertex and I want to compute its longest path, I will look at in my graph all the incoming edges and they will all be from vertices which appear before. So, I can take the value here, the value here, the value here and then take its maximum and then add here. So, actually we will see that you do not need to do this backward, you can actually do it forward.

In a naive approach to compute the longest path in a directed acyclic graph (DAG), you first need to establish a topological order of the vertices. Once you have this order, for each vertex, you then look backward at all the incoming edges to its prerequisites. The key point here is that as you look at each vertex, you take the maximum value from the lengths of paths leading to it and add one to account for the current vertex.

However, this backward scanning for incoming edges can be inefficient, especially if many vertices have multiple incoming edges. The naive approach requires multiple scans throughout the list of vertices, leading to potentially higher computational time, especially for large graphs.

Imagine tracking your progress in learning subjects where each subject has prerequisites. If you followed a backward route, you'd have to keep looking back to the subjects you learned before, making notes of which were completed to verify how far you can progress in your studies. Instead, if you took a forward approach, you could simply follow your current progression through your studies without constantly looking back, which is more efficient.

So, we can actually incrementally compute the value at i k as you are going forwards. Because, going backward requires you to scan this list and look for all the incoming neighbours. So, we will kind of implicitly do this longest path calculation along with topological sort side by side, as we will see in the next example.

In contrast to the naive method, the incremental approach to compute the longest path is much more efficient. Instead of looking backward, as you process each vertex in the topological order, you can simultaneously update the longest path for its outgoing neighbors.

When you encounter each vertex, you start with the assumption that the longest path to each vertex is zero. As you process the vertices, whenever you reach a new vertex, you can compute its longest path based on the longest paths already calculated for its predecessors. This forward-moving method allows real-time updating and reduces the need for redundant scanning of the graph.

Think of this like building a road map as you drive. Instead of stopping to check each road you passed, you update your GPS in real-time as you drive forward. Each time you reach a new intersection, your GPS updates the best routes based on the new information from the roads you’ve just traveled. This forward-thinking avoids the headache of having to go back and confirm information.

So, here is an example in which we are going to compute the longest path as we are computing the topological order. So, as before the red numbers I given as the vertices are used for topological sort and they denote the indegrees.

In the incremental approach, as we compute the topological order for the vertices of the DAG, we simultaneously calculate the longest path. The indegrees (the number of incoming edges for each vertex) are tracked and updated as we traverse the graph. When we process each vertex, we not only adjust its indegree but also use its longest path to further calculate the paths to its outgoing neighbors. This ability to calculate paths while creating a topological order eliminates extra steps of revisiting vertices.

Imagine planning the steps of a project. As you determine the sequence of tasks (topological order), you're also tracking how long each task will take based on the time it takes to finish the tasks that lead into it. Hence, every time you finish a task, you immediately adjust your overall project timeline without having to go back to reassess previous tasks.

So, this has complexity order n squared for the same reason that we had found that topological short with adjacency matrix or order n squared. Because we have the nested loops in order to scan all the neighbours.

The complexity of incrementally computing the longest path through a DAG in conjunction with the topological sort can be analyzed similarly to that of the topological sort alone. When implementing this method using an adjacency matrix, it requires quadratic time, O(n²), due to the nested loops necessary to visit each vertex and its neighbors.

However, using an adjacency list and more efficient data structures can reduce the complexity to linear time, O(n + m), where n is the number of vertices and m is the number of edges, making the algorithm significantly faster for larger graphs.

Returning to our project example, organizing tasks by complexity is much like simplifying a workflow. If you try to manually update your timeline and dependencies on a whiteboard (analogous to using a nested approach), it takes much longer than using software that automatically adjusts timelines and dependencies based on your inputs, significantly speeding up the entire process.

--