23.2.2. Dependency Problem Description

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.

This chunk introduces the concept of a dependency problem through the lens of preparing for a foreign trip. It lists various tasks associated with a trip (like obtaining a passport and purchasing tickets) that are interdependent, highlighting that some tasks cannot be completed unless others are finished first. Understanding this sequencing is vital to successful trip planning.

Imagine planning a birthday party. You cannot send invitations until you have confirmed the venue. Similarly, you won't know how much cake to order without knowing how many guests to expect. This illustrates the need to understand the order in which tasks must be completed.

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.

This chunk explains the specific dependencies between tasks. It emphasizes that some tasks are prerequisites for others, thereby establishing a clear order of operations. For example, one must obtain a passport before purchasing a ticket, and one cannot get the visa without having both the ticket and the travel insurance.

Think about making a sandwich: you need to gather ingredients (bread, lettuce, etc.) before you can start assembling it. If you don't have the bread, you can't make that sandwich. Similarly, each task in the trip preparation has to be sequenced correctly to ensure everything can be completed successfully.

Our goal is to 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.

This chunk introduces how tasks can be represented as a directed graph, where each task is a vertex, and directed edges indicate dependencies. This visualization helps in understanding which task can be performed next and highlights the relationships between tasks.

Using a family tree analogy, where each person is a node, and connections represent relationships. If you want to know the order of family events, identifying who is born first, and who has children later becomes very much like understanding task dependencies in your trip preparation.

Now our goal is to sequence these six operations, in such a way that whenever we want to perform a task, whatever it depends on has already been done. We can see that you need a passport to do anything, so we always need to start with getting a passport.

This chunk stresses the importance of sequencing the tasks according to their dependencies. It specifies that the process must start with tasks that have no prerequisites, like obtaining a passport. This ensures that as each task is approached, all necessary conditions are already fulfilled.

Consider a game of Jenga where you can only remove blocks from the top. You can't remove a lower block unless all the blocks above it are gone. Similarly, in task management, you must 'remove' tasks in the correct order to ensure success.

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

This chunk explains what makes a Directed Acyclic Graph (DAG) unique. It is directed (meaning each edge indicates a one-way dependency) and acyclic (meaning there are no cycles). Cycles would create situations where you cannot determine the starting point for tasks, which is essential for graph-based models of dependencies.

Imagine a round-robin tournament where each team plays every other team. If winning the tournament depended on beating a specific opponent, it could create a situation where teams cannot start competing due to mutual dependencies, highlighting the necessity of directional and acyclic dependencies in a graph.

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.

This chunk introduces the concept of topological sorting, which involves arranging tasks in a linear order based on their dependencies. It states that for every directed edge from task j to task k, task j must appear before task k in the final arrangement. This highlights the importance of respecting task constraints in task sequencing.

Think of preparing a recipe: you cannot bake a cake until you've mixed the ingredients. You must first sort the steps to ensure that one connects logically to the next, just like ensuring dependencies are respected in task ordering.

If the directed graph had a cycle, then you will not be able to topologically order it. Because, if it had a cycle then for instance supposing j and k are vertices on the cycle, then you will have a path from j to k and a path from k to j.

This chunk illustrates why directed cycles prevent topological sorting. If a cycle exists between two tasks, each task cannot proceed without the other being completed first, creating a paradox that makes it impossible to establish a clear order for executing tasks.

Consider a situation where two friends need to borrow each other's books: Friend A won’t lend their book until they receive the one from Friend B, while Friend B will only give their book after getting A's. This creates a cycle; similar to cycles in the task graph that prevents clear progression.

Every DAG has at least one vertex with in degree 0, in terms of our example a vertex with in degree 0 is something which has no dependencies, nothing pointing into it.

This chunk asserts that within a directed acyclic graph, there is always at least one task that does not depend on any other tasks. This task can be viewed as a starting point, allowing the sequencing of tasks to begin.

Think of a family tree: the ancestors are the starting points because they don't depend on anyone else's lineage to exist. Similarly, in a sequence of tasks, the initial tasks that have no dependencies are crucial for starting the process.

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 and then we deleted from the graph.

This chunk explains the process of selecting a task with no dependencies, completing it, and removing it from the graph to simplify the dependency structure. By doing this iteratively, the DAG gradually becomes empty, ensuring all tasks are completed in adherence to constraints.

Imagine cleaning your room: you start with the items that are not obstructed by anything else (like picking up a free-standing lamp). Once you deal with those items, it becomes easier to clean the rest without interruptions from dependencies.

--