compute a linear ordering consistent with a given partial ordering - Maple Help

Online Help

All Products    Maple    MapleSim


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

TopologicalSort - compute a linear ordering consistent with a given partial ordering

Calling Sequence

TopologicalSort(rel::{list, set}([anything, anything]))::list

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 a,b, each representing an ordering of the elements of the domain of the relation. A pair a,b 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 a,b,a,c (indicating that a is "less than" b and a is "less than" c has two consistent linear orderings: a,b,c and a,c,b. 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 a,b,b,a, which clearly has no consistent linear order.

Examples

TopologicalSorta,b,a,c

a,c,b

(1)

TopologicalSorta,b,a,c,b,d,c,d

a,c,b,d

(2)

TopologicalSorta,b,b,a

Error, (in TopologicalSort) graph is not acyclic

Sort subexpressions of an expression by containment.

e:=FGx,y,HGu,v,a,b

e:=FGx,y,HGu,v,a,b

(3)

dom:=indetse,'anything'

dom:=a,b,u,v,x,y,FGx,y,HGu,v,a,b,Gu,v,Gx,y,HGu,v,a,b

(4)

fordindomdoreld:=seqd,t,t=selecthas,dom,dend do:rel:=seqreld,d=dom:TopologicalSortrel

v,u,Gu,v,b,a,y,x,HGu,v,a,b,Gx,y,FGx,y,HGu,v,a,b

(5)

See Also

list, seq, sort


Download Help Document

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam