EF Topological sorting

Section 19.6 Topological sorting

Sometimes we want to turn a partial order into a total order. What makes an order partial instead of total is the presence of pairs of incomparable elements. So to convert our partial order into a total order we just need to impose an order relation on those previously incomparable element pairs. However, for each pair of incomparable elements there is a choice to be made of which will become the smaller and which the larger in the new total order. And we cannot carry out these choices completely arbitrarily, because we risk contradicting the required properties of a partial order (see Example 19.6.1).

🔗

The following definitions apply to a partial order

⪯

on a set

A .

compatible total order: 🔗
a total order $\leq$ on $A$ such that if $a_{1} ⪯ a_{2}$ then $a_{1} \leq a_{2}$
topological sorting: 🔗
a process for determining a compatible total order

🔗

Example 19.6.1. A failed attempt at topological sorting.

🔗

The relation

\subseteq

P (N)

is a partial order but not a total order. Consider what happens when we begin trying to build a total order on

P (N)

out of

\subseteq

by choosing relations between previously incomparable elements arbitrarily.

🔗
Elements ${1}, {2, 3}$ are $\subseteq$ -incomparable; choose ${2, 3} \leq {1} .$
🔗
Elements ${1}, {2}$ are $\subseteq$ -incomparable; choose ${1} \leq {2} .$
🔗
…

🔗

Now,

{2} \subseteq {2, 3}

is already true, so to be compatible we must set

{2} \leq {2, 3}

in the new total order. But now

{1} \leq {2} \leq {2, 3}

would dictate

{1} \leq {2, 3}

to satisfy the transitive property, but this contradicts our first arbitrary choice above.

🔗

Note 19.6.2.

🔗

A

is countable, whether finite or countably infinite, then specifying a total order on

A

amounts to writing the elements of

A

in an ordered list. (See Example 19.4.6 and Remark 19.4.7.) In that case, topological sorting amounts to creating such an ordered list so that if

a ⪯ b

then

a

appears before

b

in the list.

🔗

Algorithm 19.6.3. Topological sorting.

🔗

A

is a finite partially ordered set with respect to

⪯,

we can specify a compatible total order

\leq

A

by writing the elements of

A

in a list

a_{0} \leq a_{1} \leq \dots \leq a_{n - 1}

🔗

as follows, where

n = | A | .

🔗
Initialize $i = 0$ and $A_{0} = A .$
🔗
Choose a minimal element of $A_{i};$ let $a_{i}$ represent the chosen element.
🔗
Set $A_{i + 1} = A_{i} ∖ {a_{i}}$ (i.e. create a smaller partially ordered set by discarding $a_{i}$ ).
🔗
Increment $i$ by $1 .$ If $i < n$ then go back to Step 2. Otherwise, if $i = n$ then $A_{i}$ should now be empty, so stop — the desired compatible order has now been specified.

🔗

Note 19.6.4.

🔗

In Step 2 of the algorithm, if

A_{i}

contains a minimum element, then you must choose that element, since in that case no other minimal element can exist (see the Fact 19.5.13).

🔗

Worked Example 19.6.5.

🔗

Consider

A = P ({0, 1, 2}) = {\emptyset, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}} .

🔗

Apply Algorithm 19.6.3 to determine a total order

\leq

A

that is compatible with

\subseteq .

Solution 1. Algorithm solution

A_{0} = A,

we must choose

a_{0} = \emptyset,

since it is the minimum. Now remove

a_{0}

so that

A_{1} = {{0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}} .

Choose a minimal element from

A_{1} :

let

a_{1} = {2} .

Now remove

a_{1};

set

A_{2} = {{0}, {1}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}} .

Choose a minimal element from

A_{2} :

let

a_{2} = {0} .

Now remove

a_{2};

set

A_{3} = {{1}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}} .

Choose a minimal element from

A_{3} :

let

a_{3} = {0, 2} .

Now remove

a_{3};

set

A_{4} = {{1}, {0, 1}, {1, 2}, {0, 1, 2}} .

We must choose

a_{4} = {1},

since it is the minimum in

A_{4} .

Now remove

a_{4};

set

A_{5} = {{0, 1}, {1, 2}, {0, 1, 2}} .

Choose a minimal element from

A_{5} :

let

a_{5} = {1, 2} .

Now remove

a_{5};

set

A_{6} = {{0, 1}, {0, 1, 2}} .

We must choose

a_{6} = {0, 1},

since it is the minimum in

A_{6} .

There is only one element left; set

A_{7} = {{0, 1, 2}}

and choose

a_{7} = {0, 1, 2} .

So we have

\emptyset \leq {2} \leq {0} \leq {0, 2} \leq {1} \leq {1, 2} \leq {0, 1} \leq {0, 1, 2} .

Notice that the maximum element of

A

ended up at the “top” of the total order and the minimum element was forced to the “bottom.”

Solution 2. Graphical solution

We can perform the algorithm of topological sorting graphically; at each step, choose a vertex that has no adjacent vertices below it in the graph, then cross that vertex and any adjacent edges out of the graph. (See Figure 19.6.6.)

Our end result is a list of our choices, in order: