TopologicalSort
compute a linear ordering consistent with a given partial ordering
Calling Sequence
Parameters
Description
Examples
TopologicalSort(rel)
rel

partial order specified as a list or set of pairs
The procedure TopologicalSort attempts to produce a linear ordering of a collection of elements that is consistent with a specified partial ordering of those elements. This means that an element $a$ precedes an element $b$ in the partial order only if $a$ precedes $b$ in the linear order.
The partial order is specified as a "relation" rel, which is a list or set of pairs $\left[a\,b\right]$, each representing an ordering of the elements of the domain of the relation. A pair $\left[a\,b\right]$ belongs to the relation rel if $a$ precedes $b$ in the partial order it represents. The domain of the relation is the set of all expressions that occur as either a first or second entry (or both) in some pair in the relation rel.
Alternatively, you may think of the members of rel as directed edges in a graph whose vertices are the elements of the domain of the relation. In these terms, a topological sort of the vertices is a linear ordering of them such that a vertex $a$ occurs before $b$ in the linear order only if there is a directed path from $a$ to $b$ in the graph. The two characterizations are equivalent.
In general, there may be many linear orderings of the vertices of a graph that are consistent with it. For example, the partial order $\left[\left[a\,b\right]\,\left[a\,c\right]\right]$ (indicating that $a$ is "less than" $b$ and $a$ is "less than" $c$ has two consistent linear orderings: $\left[a\,b\,c\right]$ and $\left[a\,c\,b\right]$. The TopologicalSort procedure produces one of them.
It is also possible that no linear ordering consistent with the given partial order exists. This is the case when the directed graph contains a cycle. If TopologicalSort detects a cycle in the graph, then an exception is raised. The simplest example of this is the relation $\left[\left[a\,b\right]\,\left[b\,a\right]\right]$, which clearly has no consistent linear order.
$\mathrm{TopologicalSort}\left(\left[\left[a\,b\right]\,\left[a\,c\right]\right]\right)$
$\left[{a}{\,}{c}{\,}{b}\right]$
$\mathrm{TopologicalSort}\left(\left[\left[a\,b\right]\,\left[a\,c\right]\,\left[b\,d\right]\,\left[c\,d\right]\right]\right)$
$\left[{a}{\,}{c}{\,}{b}{\,}{d}\right]$
$\mathrm{TopologicalSort}\left(\left[\left[a\,b\right]\,\left[b\,a\right]\right]\right)$
Error, (in TopologicalSort) graph is not acyclic
Sort subexpressions of an expression by containment.
$e\u2254F\left(G\left(x\,y\right)\,H\left(G\left(u\,v\right)\,a\,b\right)\right)$
${e}{\u2254}{F}{}\left({G}{}\left({x}{\,}{y}\right){\,}{H}{}\left({G}{}\left({u}{\,}{v}\right){\,}{a}{\,}{b}\right)\right)$
$\mathrm{dom}\u2254\mathrm{indets}\left(e\,\'\mathrm{anything}\'\right)$
${\mathrm{dom}}{\u2254}\left\{{a}{\,}{b}{\,}{u}{\,}{v}{\,}{x}{\,}{y}{\,}{F}{}\left({G}{}\left({x}{\,}{y}\right){\,}{H}{}\left({G}{}\left({u}{\,}{v}\right){\,}{a}{\,}{b}\right)\right){\,}{G}{}\left({u}{\,}{v}\right){\,}{G}{}\left({x}{\,}{y}\right){\,}{H}{}\left({G}{}\left({u}{\,}{v}\right){\,}{a}{\,}{b}\right)\right\}$
$\mathbf{for}\phantom{\rule[0.0ex]{0.5em}{0.0ex}}d\phantom{\rule[0.0ex]{0.5em}{0.0ex}}\mathbf{in}\phantom{\rule[0.0ex]{0.5em}{0.0ex}}\mathrm{dom}\phantom{\rule[0.0ex]{0.5em}{0.0ex}}\mathbf{do}\phantom{\rule[0.0ex]{0.5em}{0.0ex}}{\mathrm{rel}}_{d}\u2254\mathrm{seq}\left(\left[d\,t\right]\,t\=\mathrm{select}\left(\mathrm{has}\,\mathrm{dom}\,d\right)\right)\phantom{\rule[0.0ex]{0.5em}{0.0ex}}\mathbf{end\; do}\:$$\mathrm{rel}\u2254\left[\mathrm{seq}\left({\mathrm{rel}}_{d}\,d\=\mathrm{dom}\right)\right]\:$$\mathrm{TopologicalSort}\left(\mathrm{rel}\right)$
$\left[{v}{\,}{u}{\,}{G}{}\left({u}{\,}{v}\right){\,}{b}{\,}{a}{\,}{y}{\,}{x}{\,}{H}{}\left({G}{}\left({u}{\,}{v}\right){\,}{a}{\,}{b}\right){\,}{G}{}\left({x}{\,}{y}\right){\,}{F}{}\left({G}{}\left({x}{\,}{y}\right){\,}{H}{}\left({G}{}\left({u}{\,}{v}\right){\,}{a}{\,}{b}\right)\right)\right]$
See Also
list
seq
sort
Download Help Document
What kind of issue would you like to report? (Optional)