23.2. Directed Acyclic Graphs (DAGs)

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

Directed Acyclic Graphs (DAGs) are a type of graph that is directed, meaning each edge has a direction, and acyclic, meaning there are no cycles in the diagram. This structure allows us to model situations where tasks depend on the completion of other tasks, ensuring a logical flow without contradictions.

Imagine a recipe where you can't add eggs until you've mixed the flour and sugar. The steps must be followed in a certain order, much like how DAGs represent tasks that depend on previous tasks being completed.

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, various tasks must be completed in a specific order due to dependencies. For example, you cannot buy a ticket without a passport, and you need both a ticket and insurance to get a visa. This is a practical way to understand how tasks are interlinked, and these dependencies can be represented as a directed graph.

Think of preparing for a big party. You can't send invitations until you have a venue booked. Similarly, you can't finalize the guest list until you know how many people can fit in. Each task depends on the previous one being completed.

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.

In this visualization, each task is a vertex (or node), and directed edges show the order in which tasks must be performed. This means if task T1 must be completed before task T2, an arrow will point from T1 to T2, representing this dependency.

Imagine the tasks of a construction project. You can't install windows before the walls are built. If wall construction is T1 and window installation is T2, you'll have an arrow from T1 to T2 showing that wall construction must happen before windows can be installed.

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 key challenge is to determine the correct order to perform tasks given their dependencies. By analyzing which tasks must be completed before others, we can find multiple valid sequences through which all tasks can be accomplished while satisfying the constraints.

Consider a LEGO set. You need to lay the foundation blocks before adding walls and roofs. If you don’t follow the build orders outlined in the instructions, you may complete certain blocks but find that they won’t fit because the foundational blocks aren’t in place.

So, there are two possible ways of reordering ticket and insurance and there are two possible ways of reordering the gifts and the foreign exchange. So, overall there are four different sequences which are compatible with these constraints.

Given the task dependencies, there can be multiple valid sequences to complete these tasks. In this case, after obtaining a passport, you can buy a ticket or insurance first—both sequences are valid since neither depends on the other. Thus, various combinations can yield the same successful outcome.

Imagine organizing a little concert. You can either invite your friends before printing tickets or print tickets and then tell your friends. Both methods lead to getting everyone together, but the order may change based on your initial preparation.

This class of graph is an important class and it has two important features: one is of course, it is directed, and there are no cycles.

DAGs have two defining characteristics: they are directed graphs and they do not have cycles. Each direction in the tasks represents a dependency, and the absence of cycles ensures that tasks can be ordered without contradiction.

Think of a one-way street: you cannot drive back on the same path, similar to how dependencies in DAGs cannot cycle back to an earlier stage. If you were organizing tasks in a loop, you'd never complete them.

So, in general we are given a set of vertices (tasks) and we want to write them out in a sequence with respect to the constraints, using what is known as topological sorting.

Topological sorting is a mathematical process of ordering tasks based on their dependencies in a DAG. By ensuring that each task follows its prerequisites in the output sequence, it allows for a valid execution of a series of interlinked tasks.

Think of how you might pack a suitcase. You start with packing the large items first and only then add smaller items without risking smashing them—following an order based on need and availability, much like topological sorting.

If the directed graph had a cycle, then you will not be able to topologically order it.

In the presence of cycles, tasks would depend on each other circularly, making it impossible to begin execution since no task could start without another being finished first. This emphasizes the importance of DAGs having no cycles for successful task management.

Imagine a situation where you have a group project: if everyone is waiting on someone else to finish their portion before starting, no one can ever begin—this would create a cycle, halting progress entirely.

Our first claim is that every DAG has at least one vertex with in degree 0.

In any directed acyclic graph, there exists at least one vertex with no incoming edges (in degree 0), which means it has no prerequisites. This is crucial for topological sorting since we can start our task sequence from this point.

Consider cooking dinner. You must have groceries before you can cook—if the grocery store has everything you need, it functions as your starting point (vertex with in degree 0) for preparing your meal.

This is a more elaborate version of the algorithm that it described earlier. So, we pick a vertex with in degree 0...

The algorithm involves selecting a vertex with no dependencies (in degree 0), performing its task, and removing it from the graph. This process repeats until no vertices are left, systematically ensuring that tasks are completed in correct order according to constraints.

Picture a class where students must present projects. If you have a student who has completed their project early, they present first, and their absence won't affect others. Each completed project allows the next presenter to go, similar to how DAG processing works.

--