TopologicalSort - Maple Programming Help

Home : Support : Online Help : Programming : Operations : TopologicalSort

TopologicalSort

compute a linear ordering consistent with a given partial ordering

 Calling Sequence TopologicalSort(rel)

Parameters

 rel - partial order specified as a list or set of pairs

Description

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

Examples

 > $\mathrm{TopologicalSort}\left(\left[\left[a,b\right],\left[a,c\right]\right]\right)$
 $\left[{a}{,}{c}{,}{b}\right]$ (1)
 > $\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]$ (2)
 > $\mathrm{TopologicalSort}\left(\left[\left[a,b\right],\left[b,a\right]\right]\right)$

Sort subexpressions of an expression by containment.

 > $e≔F\left(G\left(x,y\right),H\left(G\left(u,v\right),a,b\right)\right)$
 ${e}{≔}{F}{}\left({G}{}\left({x}{,}{y}\right){,}{H}{}\left({G}{}\left({u}{,}{v}\right){,}{a}{,}{b}\right)\right)$ (3)
 > $\mathrm{dom}≔\mathrm{indets}\left(e,'\mathrm{anything}'\right)$
 ${\mathrm{dom}}{≔}\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\}$ (4)
 > $\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}≔\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}≔\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]$ (5)