23.2.3. Modeling Dependencies with Graphs

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

To motivate this class of graphs, let us look at a problem where we have a bunch of tasks to perform with some constraints.

Directed Acyclic Graphs, or DAGs, are a type of graph used in computer science to represent dependencies among tasks. They are called 'directed' because the edges between vertices have a direction, showing the order in which tasks must be completed. They are 'acyclic' because there are no cycles, meaning a task cannot depend on itself directly or indirectly through a series of dependencies. Understanding DAGs is essential in problems involving scheduling, task management, and many algorithms.

Imagine planning a wedding. You can't order the cake until you finalize the guest list, and you can't send invitations until the venue is booked. Each task is dependent on others being completed first, much like the dependencies in a DAG.

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.

Now, these tasks are dependent on each other in certain ways, without a passport you cannot buy a ticket, not even buy any travel insurance. For the visa, you need both the ticket and the insurance to be available and without a visa, the bank will not give you foreign exchange.

In this chunk, we explore how certain tasks are interdependent. For instance, you first require a passport before you can book a ticket or purchase travel insurance. Similarly, obtaining a visa requires both the ticket and the insurance to be acquired first. This can be represented as a graph where the tasks are the vertices and the edges represent the dependencies. So, for any task, the graph illustrates which tasks must precede it.

Think of a relay race. Each runner depends on the previous runner completing their part of the race before they can start. If the first runner doesn't finish their lap, the second runner cannot begin, just as in our travel preparations.

So, our goal is that given these constraints in what sequence should we perform these operations ... we can see that you need a passport to do anything, so we always need to start with getting a passport.

This chunk discusses how to determine the sequence for task completion based on the dependencies stated in the graph. Starting with the tasks that have no prerequisites, such as getting a passport, we can plan a valid sequence of tasks. After the passport, the next tasks can be either getting a ticket or purchasing insurance, as these two do not depend on each other. This flexibility in task ordering can lead to multiple valid sequences.

Imagine baking a cake. You can't glaze it before it's baked, and you need to mix the ingredients before you bake. However, you can prepare your baking sheets while the oven preheats. Just like sorting our travel tasks, mixing and preheating tasks can happen simultaneously, giving you different valid ways to complete the cake preparation.

This class of graph is an important class and it has two important features, one is of course, it is directed... So, we call such a graph a directed acyclic graph.

DAGs possess two unique characteristics: they are directed and acyclic. The directed feature ensures that there are specific paths to follow for task completion, indicating dependencies. The acyclic feature ensures no circular dependencies exist, allowing tasks to be completed without deadlocks or infinite waiting. This structure is vital for algorithms involving scheduling.

Imagine a one-way road system in a city where you cannot circle back on yourself. You follow a set route to reach your destination (completing tasks) without looping back, which would cause chaos and delays—just as cycles in a DAG would.

So, the problem that we had discussed in our example is that we have given a set of tasks...so for various reasons, this is known as topologically sorting the DAG.

Topological sorting is a method used to arrange the tasks (vertices) of a DAG such that for every directed edge from task A to task B, task A appears before task B in the ordering. This is achievable only in a DAG due to its acyclic property, allowing us to respect all dependencies without contradictions.

Think of a playlist of songs where certain songs must play before others due to their content (like a story). You can’t play a song that references the story’s ending before the song that lays out the background. Just like organizing tasks in topological sorting helps us follow the narrative flow.

Our first claim is that every DAG has at least one vertex with in degree 0...So, therefore, if I have a continuous sequence of vertices all of which are pointing to each the previous one with in degree not equal to 0, then I will end up with a cycle.

In any DAG, there is always at least one task (vertex) that does not depend on any other task (in-degree 0). This indicates a clear starting point for task execution. The absence of this characteristic would imply a cyclical dependency, violating the acyclic nature required for a valid DAG.

Picture a group project where one team member does not rely on others. This member can initiate the project, drawing upon different starting points rather than being hindered by dependencies, just like how the task with in-degree 0 allows the flow of operations.

--