24.4. Topological Sorting

So, imagine you are given an arbitrary poset less than equal to relationship. This is not again a numerical less than equal to, this is an arbitrary relation, R, which is reflexive, anti-symmetric and transitive. Then if I take a pair of elements x, y then the element y is called the cover of element x if the following two conditions hold. The element x should be related to the element y and of course x ≠ y, that is why the less than symbol. And there should not exist any intermediate element ∃z, x ≤ z ≤ y.

In a partially ordered set (poset), a 'cover' is a key concept. When we say that y is the cover of x, it means that there's a direct connection (relationship) from x to y without any other elements in between. This is important in understanding the structure of the poset. The two conditions for y being a cover for x are: first, there should be a relation between x and y that implies x comes before y (x ≤ y), and second, there should be no element z that stands between them, meaning z does not fulfill the relationship where x ≤ z ≤ y.

Think of a hierarchy in an organization. If we say that a manager directly supervises an employee, then you can consider that manager as a 'cover' over that employee. There are no direct reports between them; the employee reports directly to the manager without any other layers (like team leads) intervening.

Let us next define what we call as the maximal and minimal element in a poset. A maximal element has no cover, meaning there isn’t any element related to it that is greater. Conversely, a minimal element is one where it covers no other elements. For instance, in a poset, elements 8 and 12 are both maximal because there’s nothing above them.

Maximal elements in a poset are similar to the highest points in a structure where no other elements are above them. Minimal elements, on the other hand, are the lowest points in that structure where no elements are below them. For example, if we have a set defined as {1, 2, 3, 4, 5, 6} where 6 is on top, it is maximal since nothing exceeds it. Meanwhile, if 1 is at the bottom and there are no lower elements connected to it, 1 is minimal.

Imagine a stack of boxes. The box on the bottom that supports the entire stack is like a minimal element, while the box on top that no other boxes are stacked upon is a maximal element.

Now finally let us define what we call as the greatest element and the least element of a poset. The element a is called the greatest element if every other element is related to it. The least element is where it relates to every other element.

The greatest element in a poset is a single element that every other element points to, meaning that every element is less than or equal to this element. The least element is the opposite; it’s the one that all other elements point to, implying that it is less than or equal to them. It’s important to note that while maximal and minimal elements may exist, greatest and least elements may not.

Think about a company with a CEO (greatest element) who is at the top of the hierarchy. Every employee reports to that CEO. Conversely, the intern who has no one below them in reporting order represents the least element since they are at the bottom of the organizational chart.

Using all the concepts that we have discussed now we will now do a very interesting exercise here, which we call as topological sorting. In this topological sorting, you are given a set of tasks denoted by S with a dependency relationship R.

Topological sorting is an ordering of tasks that respects the dependencies defined by the poset. For instance, if task A must be completed before task B can start, topological sorting will ensure that A appears before B in the final list of tasks. The resulting order can help in scheduling tasks effectively.

Consider cooking a meal. Some steps must be done in a specific order, like chopping vegetables before cooking them or marinating meat before grilling. Topological sorting ensures that all required steps are completed in the correct sequence.

The algorithm starts with the minimal element in the set S and removes it from the set while listing it down in the total order. This process continues until all tasks are scheduled.

In a practical sense, to execute the topological sorting, you begin by identifying the tasks that have no prerequisites (minimal elements). You then record these tasks, remove them from the consideration, and repeat this process with the updated set of remaining tasks until all tasks are sorted.

Imagine you want to finish a puzzle but can only add pieces that connect to others. You start by placing corner pieces (minimal elements) first, then edges, and finally the inner pieces based on what fits until the puzzle is complete.

--