23.2.1. Introduction to DAGs

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 task 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.

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. And finally, you would not like to buy gifts for your hosts, unless the trip is confirmed. So, unless you have all these things including the visa in hand, you do not want to invest in the gift.

This chunk introduces Directed Acyclic Graphs (DAGs) by illustrating task dependencies in the context of planning a foreign trip. The tasks (passport, ticket, visa, insurance, foreign exchange, and gifts) demonstrate how certain tasks cannot begin until prerequisite tasks have been completed. This sets the stage for understanding how graph theory can model these dependencies using a directed graph where tasks are the vertices and edges represent the dependencies.

Think of planning a wedding. Before sending out invitations, you need to finalize the venue and the date. You can't have your cake if you haven't decided on the bakery, and you can’t consider the honeymoon plans until the wedding is officially booked. Each step depends on the prior steps not just being completed but confirmed, much like DAGs where some tasks cannot commence until their prerequisites are addressed.

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. What sequence should we do it, so that whenever we want to approach a task, the constraints that are required for the task are satisfied.

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. So, as an example getting a passport must come before buying a ticket, so T1 is getting a passport, T2 could be getting a ticket.

In this chunk, the focus is on how to represent the task dependencies as a directed graph. Each task is represented as a vertex, and directed edges illustrate the dependence between tasks. For instance, the edge from 'getting a passport' to 'buying a ticket' signifies that one cannot buy a ticket before obtaining a passport. This graph serves as a visual and mathematical representation of task execution given constraints.

Consider following a recipe for making a cake. You can’t bake the cake until you have mixed the ingredients, and you can't mix the ingredients without having all of them prepped. The dependencies shown in the recipe can be represented in a directed graph where each step is a vertex connected by arrows indicating the sequence in which they must be completed.

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. See, if you had a cycle it would been that group of tasks depend on each other, so there is no way to start, because each task is depends on something else in the cycle.

This chunk explains the essential characteristics of DAGs: directedness and acyclicity. A directed graph means that the edges have a direction, indicating the order of task completion. Acyclicity implies that no task can circle back and depend on itself directly or indirectly, which would create a deadlock situation. This characteristic is crucial for task scheduling and process management.

Imagine a chain of likes on social media: if user A likes user B's post, they may not simultaneously like back unless a new post prompts them. If we describe this as a directed graph, if A can't like B’s post without first having its own post liked, this creates a direct path with no returns or cycles, allowing clear progression of connections.

So, the problem that we had discussed in our example is that we have given a set of tasks and we want to write them out in a sequence with respect to the constraints, the constraints are nothing but, the edges.

So, in general we are given a set of vertices these are our tasks abstractly 1 to n and we want to read, write our 1 to n in such a way that the constraints are respected. What this means is, that we will write out 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 represents edge j k, then in the numeration that we have perform j must come before k. So, it cannot be that we have to do j before k according to our constraint, but in the sequence that we produced k happens before j.

This chunk addresses the concept of topological sorting, which is a way of ordering vertices (tasks) in a DAG according to their dependencies. The order must respect the directed edges: if task j must precede task k, then in the sorted sequence j must come before k. This sorting is essential for scheduling tasks correctly while adhering to constraints.

Think of organizing a play where certain actors must be on stage before others can join. You cannot have the actors who need props enter the scene before those who bring the props. Topological sorting helps ensure that the order of entrance respects these dependencies, creating a smooth and logical flow for the production.

--