23.1. Design and Analysis of Algorithms, Chennai Mathematical Institute

We now turn our attention to a very interesting and important class of graphs called Directed Acyclic Graphs or DAGs.

Directed Acyclic Graphs, or DAGs, are complex graphs that exhibit specific properties. They are 'directed', meaning that edges between vertices (or nodes) have a direction, implying a one-way connection from one vertex to another. Additionally, they are 'acyclic', indicating that there are no cycles within the graph, which means you cannot start at one vertex, traverse the edges, and return to the same vertex.

Think of a flowing river (representing the direction) that never loops back on itself (representing acyclic). Each task depends on its previous tasks, and once a task is completed, it cannot be re-visited in the sequence.

So, to motivate this class of graphs, let us look at a problem where we have a bunch of tasks to perform with some constraints. Suppose, we are going on a foreign trip, then of course, we need a passport, we need to buy a ticket, we require a visa probably, we want to buy some travel insurance, we probably need some foreign exchange as well and perhaps you want to buy some gifts for our hosts.

When planning a trip, there are several tasks that need to be completed, each with its own dependencies. For example, you cannot buy a travel ticket without having a passport, and you cannot obtain a visa without having both the ticket and travel insurance. This creates a dependency structure among the tasks, which can be visualized as a directed graph.

Imagine organizing a dinner party. You need to take tasks like sending invitations, cooking the meal, and setting the table. However, you cannot set the table before you agree on the guest list. This illustrates how tasks can depend on each other in a sequenced manner.

So, as you would expect, we will model this using a graph. In this graph, the vertices will be the tasks and then you will have an edge pointing from T1 to T2, if T1 must come before T2. In other words, T2 depends on T1; you cannot do T2 unless T1 has been completed.

In graph theory, we represent tasks as vertices (points) and the dependencies between those tasks as directed edges (lines with arrows). For example, if getting a passport must occur before buying a ticket, we would draw an arrow from the passport vertex to the ticket vertex, illustrating that the ticket task cannot begin until the passport task is complete.

Consider a family tree where parents create children; you cannot have children before being parents. Here, being a parent represents the task that must happen first, creating a simple directed relationship.

So, our goal is that given these constraints in what sequence should we perform these six operations, getting a passport, buying a ticket, getting insurance, getting a visa, buying foreign exchange and buying gifts for our hosts.

The necessity for a proper task sequence arises from the dependencies among them. To ensure that each task can be executed without any prior dependencies left unmet, we must find an order that respects these constraints. This is effectively a scheduling problem where we need to assess the dependencies and derive an appropriate order or sequence in which to complete the tasks.

Imagine baking a cake. Prior to baking, you need to gather ingredients (eggs, flour, sugar), mix them, and then finally bake the mixture. Each activity must occur in a certain order, analogous to managing dependencies in project scheduling.

So, we can see that you need a passport to do anything, so we always need to start with getting a passport. Now, there is no dependency between buying a ticket and buying insurance as per the constraints we have, so after passport you can either buy a ticket first and then buy insurance or you can buy insurance first and then buy a ticket.

Some tasks are dependent on one another while others are independent. In this scenario, the passport must be obtained first. However, once you have the passport, both buying a ticket and obtaining insurance can happen in any order. This flexibility is key in recognizing multiple valid sequences of operations based on varying dependencies.

Consider getting ready for your day. You must brush your teeth before you can eat breakfast, but you can choose to get dressed before or after breakfast—they are independent of each other. This illustrates the concept of task sequencing based on dependency.

So, this class of graph is an important class and it has two important features: one is of course, it is directed. Because, these dependencies are from one task to another task, it is not a symmetric dependency and there are no cycles.

DAGs have two essential features: they are directed, meaning every relationship between tasks has a defined direction (who comes before whom), and they are acyclic, which implies that there are no circular dependencies. This ensures a clear starting point in the task list and allows for systematic progression through the tasks without potential roadblocks from cyclic references.

Think of a flowchart mapping out a project. You can only move in one direction through the chart (no going backwards), and you can’t loop back to any point without completing prior steps—that's what makes it acyclic.

See, if you had a cycle it would mean that a group of tasks depend on each other, so there is no way to start, because each task depends on something else in the cycle.

If there is a cycle in the graph, it creates a significant issue: you cannot complete any task because every task relies on another task that has not yet been completed. This creates an interdependence that creates a deadlock, preventing any action from being taken. In a DAG, the absence of cycles allows for a clear, pathway-based execution of tasks.

Imagine a group project where everyone waits for one another to start their part; if each segment requires the completion of the next, no one can initiate their work, and the project stalls completely.

So, our goal is to find a sequence of numbers which is a permutation of 1 to n in such a way that whenever there is a constraint of the form j k that is represented as edge j k, then in the numeration that we have performed j must come before k.

The process of 'topological sorting' arranges the tasks (vertices) so that for every directed edge from vertex j to vertex k, j appears before k in the sequence. This means that whenever tasks depend on each other, the one that must be completed first is listed first. Topological sorting is crucial for respecting task dependencies in project planning.

In cooking, if a recipe calls for mixing ingredients (task 1) before heating them (task 2), the 'topological order' ensures that your mix happens before applying heat. Just like respecting the right order of task execution, it is all about following the recipe correctly.

So, our first claim is that every DAG has at least one vertex with indegree 0, which corresponds to a task with no dependencies.

Every directed acyclic graph contains at least one vertex with an indegree of zero, meaning that there is at least one task that does not depend on any other task. This is essential because it acts as a starting point for the topological sorting process. If every task depended on another, it would create a cycle, contradicting the acyclic nature of the graph.

Think of a company hierarchy; at least one person (like the CEO) has no direct supervisor—they are the starting point. Just as tasks need a starting point to begin, organizations need leaders to initiate processes.

So, we pick a vertex with in degree 0, we call that such a vertex has no dependencies, now we enumerated because it now has it is available for enumeration. Once we delete it from the graph, we can find the next vertex with in degree 0 and keep going.

The algorithm for topological sorting starts by choosing a vertex with an indegree of zero (no dependencies). After processing this vertex, it is removed from the graph, which may cause other vertices to have their indegree decremented. You then look for the next vertex with an indegree of zero and repeat the process, systematically reducing the graph until all tasks are attended to.

Imagine a new hire at a company learning the job. They start with simple tasks (no predecessors), complete them, and gradually take on more complex assignments as they become available. Just like in an organization, tasks become manageable through systematic progress based on dependencies.

--