reduction = truefalse

There are two (potentially) different graphs that this command can generate: the graph where the arrows form the transitive reduction of the ordering of P, and the graph where the arrows form the transitive closure of the ordering. By default, DrawGraph displays the transitive reduction graph (the Hasse diagram). When passed the option reduction = false, it displays the transitive closure graph. Passing the option reduction or reduction = true explicitly selects the default transitive reduction graph.

graded = truefalse

When laying out the vertices of a transitive reduction graph, Maple chooses between two different but similar algorithms; one applicable only to graded posets and a more general algorithm applicable to all posets. Both are described below. By default, Maple determines if the poset is graded if this is not known already, and then chooses the algorithm for graded posets if applicable and the general algorithm otherwise; except if the option prefer = high is used, then the general algorithm is used.

When passing the option graded = false, Maple will bypass this check and always use the algorithm appropriate for all posets.

The option graded = true explicitly selects the algorithm appropriate only for graded posets. If the poset is not graded, this option is ignored.

The graded option is not supported for drawing the transitive closure graph.

prefer = low or high

When using the algorithm appropriate for non-graded posets, the vertices are divided into groups, each group being placed at the same height. Some vertices have a fixed height, whereas for others, there are several possibilities. With the option prefer = low (the default), each vertex gets placed into the lowest group available to it. With the option prefer = high, each vertex gets placed into the highest group available to it.

This option is not supported for drawing the transitive closure graph and it is ignored by the algorithm for drawing graded posets. If the algorithm appropriate for non-graded posets is used to draw a graded poset, this option has no effect.

dgopts (not a literal option name)

If passing any extra options not mentioned before (represented by dgopts in the calling sequence above), they are passed on to the GraphTheory:-DrawGraph command.

The command DrawGraph(P) displays the vertices and edges of the partially ordered set P as the Maple plot of a graph using the command GraphTheory:-DrawGraph  of the package GraphTheory.

In this section, we describe the algorithms for layout out the vertices of transitive reduction graphs. As described in the "Options" section, there are two algorithms: one appropriate for graded posets only, and one applicable more generally. We first describe the algorithm for graded posets:

First, the rank of all elements is determined (that is, their value under a rank function), which also determines the split of the elements into connected components. The rank determines the $y$-coordinate at which a vertex is placed; concretely, the $y$-coordinates of a vertex corresponding to an element of rank $r$, in a poset of rank $n$, is $\frac{2r}{\sqrt{n+1}}$.

To determine the $x$-coordinate, we proceed connected component by connected component (in arbitrary order), as follows.

First, order the elements of minimal rank in this component arbitrarily. If there are k elements of this rank, place them spaced equidistantly between $\frac{1-k}{\sqrt{k}}$ and $\frac{k-1}{\sqrt{k}}$.

Then we iterate over the ranks in ascending order. For each rank, order the elements by the average horizontal position of their immediate predecessors, using the same rule for spacing.

Finally, re-order the minimal rank entries by the average horizontal position of their successors.

If there are fewer than two connected components, we use these $x$-coordinates directly. Otherwise, we shift each connected component horizontally so that the first connected component has 0 as its left hand bound, and the space between each pair of subsequent connected components is one third of the maximal width of one connected component.

Note that Maple's algorithm for computing ranks sets the rank of the lowest-ranked elements of each connected component of the poset to 0. This can be seen if a poset has two connected components, each of which is ranked, but they have different rank: then this algorithm lays out the components so that their lowest-ranked elements align horizontally.

The more general algorithm proceeds as follows.

We compute all maximal chains and group these by the pair of their minimal and maximal elements. Let $S$ be the set that consists of those chains within each such group of maximal cardinality within that group. For now, we consider only the covering relations within $S$; we call these the skeleton of the poset. We will find "ranks" for the elements of the chains in $S$ in a straightforward manner, below. Note that some vertices may not be in any of these chains; we will find appropriate ranks for them later. Note furthermore that the elements of the chains in $S$ in a single connected component, are still connected if we only consider the covering relations in $S$.

We now compute "ranks" for all elements of the chains in $S$, as follows. We initially color all these elements black. We pick one arbitrarily and set its "rank" to 0, coloring it gray. We then iteratively pick one gray element, color it white, and color its neighbors (both greater and smaller) gray, assigning their "ranks" as we do so. When we have no more gray elements, we have finished this connected component and we can again pick an arbitrary black element if any are left. After we are done with a connected component, we subtract either its minimal (if the prefer = low option is used) or its maximal (if the prefer = high option is used; the default is prefer = low) "rank" from all "ranks" in that component. As a consequence, with prefer = low, the lowest-ranked elements of each connected component will have the same "rank" (0), and with prefer = high, the highest-ranked elements of each connected component will have the same "rank" (0). During this step, we keep track of which of the elements in the chains in $S$ are in which connected component.

Next, we assign "ranks" to the remaining elements of the poset and add them to the correct connected component.

If the prefer = low option is used, we iterate through these elements in an order that is compatible with the partial ordering. When processing an element $e$, we look at all its immediate predecessors in the partial ordering. There must be some, because otherwise $e$ would be part of a chain in $S$; and its connected component and "rank" will have been assigned, either when assigning ranks for $S$ or earlier in this loop. We put this element in the same connected component as its predecessors and assign it the maximum of the "ranks" of the predecessors, plus one.

If the prefer = high option is used, we do the same, except we iterate through these elements in the reverse of this order, look at the element's immediate successors rather than predecessors, and assign the minimum of the "ranks" of the successors, minus one.

Once these "ranks" have been assigned, we proceed exactly as in the algorithm for graded posets, except using the newly computed "ranks" instead of the actual ranks of the elements.

$\mathrm{with}\left(\mathrm{PartiallyOrderedSets}\right)\:$

$\mathrm{leq}≔\mathrm{`<=`}\&colon;$

$S≔\left\{1\&comma;2\&comma;3\&comma;4\&comma;5\right\}\&colon;$$\mathrm{poset1}≔\mathrm{PartiallyOrderedSet}\left(S\&comma;\mathrm{leq}\right)$

$\mathrm{poset1}≔\mathrm{<\; a\; poset\; with\; 5\; elements\; >}$

$\mathrm{DrawGraph}\left(\mathrm{poset1}\right)$

$\mathrm{lneq}≔\mathrm{`<`}\&colon;$$\mathrm{poset1\_1}≔\mathrm{PartiallyOrderedSet}\left(S\&comma;\mathrm{lneq}\right)$

$\mathrm{poset1\_1}≔\mathrm{<\; a\; poset\; with\; 5\; elements\; >}$

$\mathrm{DrawGraph}\left(\mathrm{poset1\_1}\right)$

$\mathrm{divisibility}≔\left(x\&comma;y\right)\mapsto \mathrm{irem}\left(y\&comma;x\right)=0\&colon;$$T≔\left\{3\&comma;4\&comma;5\&comma;6\&comma;7\&comma;8\&comma;9\right\}\&colon;$

$\mathrm{poset2}≔\mathrm{PartiallyOrderedSet}\left(T\&comma;\mathrm{divisibility}\right)$

$\mathrm{poset2}≔\mathrm{<\; a\; poset\; with\; 7\; elements\; >}$

$\mathrm{DrawGraph}\left(\mathrm{poset2}\right)$

$\mathrm{divisibNE}≔\left(x\&comma;y\right)\mapsto \mathrm{irem}\left(y\&comma;x\right)=0\mathbf{and}y\ne x\&colon;$

$\mathrm{poset2\_1}≔\mathrm{PartiallyOrderedSet}\left(T\&comma;\mathrm{divisibNE}\&comma;\mathrm{reflexive}=\mathrm{checkfalse}\right)$

$\mathrm{poset2\_1}≔\mathrm{<\; a\; poset\; with\; 7\; elements\; >}$

$\mathrm{DrawGraph}\left(\mathrm{poset2\_1}\right)$

$U≔\left\{1\&comma;2\&comma;3\right\}\&colon;$

$\mathrm{poset3}≔\mathrm{PartiallyOrderedSet}\left(U\&comma;\mathrm{leq}\&comma;\mathrm{reflexive}=\mathrm{checktrue}\right)$

$\mathrm{poset3}≔\mathrm{<\; a\; poset\; with\; 3\; elements\; >}$

$\mathrm{DrawGraph}\left(\mathrm{poset3}\right)$

$\mathrm{poset3\_1}≔\mathrm{PartiallyOrderedSet}\left(U\&comma;\mathrm{lneq}\&comma;\mathrm{reflexive}=\mathrm{useclosure}\right)$

$\mathrm{poset3\_1}≔\mathrm{<\; a\; poset\; with\; 3\; elements\; >}$

$\mathrm{DrawGraph}\left(\mathrm{poset3\_1}\right)$

$X≔\left\{4\&comma;5\&comma;6\right\}\&colon;$$\mathrm{poset3\_2}≔\mathrm{PartiallyOrderedSet}\left(X\&comma;\mathrm{leq}\&comma;\mathrm{reflexive}=\mathrm{checktrue}\right)$

$\mathrm{poset3\_2}≔\mathrm{<\; a\; poset\; with\; 3\; elements\; >}$

$\mathrm{DrawGraph}\left(\mathrm{poset3\_2}\right)$

$\mathrm{adjMatrix4}≔\mathrm{Matrix}\left(\left[\left[1\&comma;1\&comma;1\&comma;1\&comma;1\right]\&comma;\left[0\&comma;1\&comma;1\&comma;1\&comma;1\right]\&comma;\left[0\&comma;0\&comma;1\&comma;1\&comma;1\right]\&comma;\left[0\&comma;0\&comma;0\&comma;1\&comma;1\right]\&comma;\left[0\&comma;0\&comma;0\&comma;0\&comma;1\right]\right]\right)$

$\mathrm{adjMatrix4}≔\left[\begin{array}{ccccc}1& 1& 1& 1& 1\\ 0& 1& 1& 1& 1\\ 0& 0& 1& 1& 1\\ 0& 0& 0& 1& 1\\ 0& 0& 0& 0& 1\end{array}\right]$

$\mathrm{poset4}≔\mathrm{PartiallyOrderedSet}\left(\mathrm{convert}\left(S\&comma;'\mathrm{list}'\right)\&comma;\mathrm{adjMatrix4}\right)$

$\mathrm{poset4}≔\mathrm{<\; a\; poset\; with\; 5\; elements\; >}$

$\mathrm{DrawGraph}\left(\mathrm{poset4}\right)$

$\mathrm{adjList5}≔\mathrm{map2}\left(\mathrm{map}\&comma;\mathrm{`+`}\&comma;\mathrm{Array}\left(\left[\left\{1\&comma;4\&comma;7\right\}\&comma;\left\{2\&comma;6\right\}\&comma;\left\{3\right\}\&comma;\left\{4\right\}\&comma;\left\{5\right\}\&comma;\left\{6\right\}\&comma;\left\{7\right\}\right]\right)\&comma;2\right)$

$\mathrm{adjList5}≔\left[\begin{array}{ccccccc}\left\{3\&comma;6\&comma;9\right\}& \left\{4\&comma;8\right\}& \left\{5\right\}& \left\{6\right\}& \left\{7\right\}& \left\{8\right\}& \left\{9\right\}\end{array}\right]$

$\mathrm{poset5}≔\mathrm{PartiallyOrderedSet}\left(\mathrm{convert}\left(T\&comma;'\mathrm{list}'\right)\&comma;\mathrm{adjList5}\right)$

$\mathrm{poset5}≔\mathrm{<\; a\; poset\; with\; 7\; elements\; >}$

$\mathrm{DrawGraph}\left(\mathrm{poset5}\right)$

$G≔\mathrm{GraphTheory}:-\mathrm{Graph}\left(\mathrm{directed}\&comma;\left[1\&comma;2\&comma;3\&comma;4\&comma;5\&comma;6\right]\&comma;\left\{\left[1\&comma;1\right]\&comma;\left[1\&comma;2\right]\&comma;\left[1\&comma;3\right]\&comma;\left[1\&comma;4\right]\&comma;\left[1\&comma;5\right]\&comma;\left[1\&comma;6\right]\&comma;\left[2\&comma;2\right]\&comma;\left[2\&comma;4\right]\&comma;\left[2\&comma;6\right]\&comma;\left[3\&comma;3\right]\&comma;\left[3\&comma;5\right]\&comma;\left[3\&comma;6\right]\&comma;\left[4\&comma;4\right]\&comma;\left[4\&comma;6\right]\&comma;\left[5\&comma;5\right]\&comma;\left[5\&comma;6\right]\&comma;\left[6\&comma;6\right]\right\}\right)$

$G≔\mathrm{Graph\; 1:\; a\; directed\; graph\; with\; 6\; vertices,\; 11\; arcs,\; and\; 6\; self-loops}$

$\mathrm{poset6}≔\mathrm{PartiallyOrderedSet}\left(G\right)$

$\mathrm{poset6}≔\mathrm{<\; a\; poset\; with\; 6\; elements\; >}$

$\mathrm{DrawGraph}\left(\mathrm{poset6}\right)$

$\mathrm{poset7}≔\mathrm{PartiallyOrderedSet}\left(\mathrm{convert}\left(U\&comma;'\mathrm{list}'\right)\&comma;⟨⟨1\left|1\right|0⟩\&comma;⟨0\left|1\right|1⟩\&comma;⟨0\left|0\right|1⟩⟩\&comma;\mathrm{input}=\mathrm{transitivereduction}\right)$

$\mathrm{poset7}≔\mathrm{<\; a\; poset\; with\; 3\; elements\; >}$

$\mathrm{DrawGraph}\left(\mathrm{poset7}\right)$

$\mathrm{poset8}≔\mathrm{PartiallyOrderedSet}\left(\left[1\&comma;2\&comma;3\&comma;4\&comma;5\&comma;6\right]\&comma;\mathrm{Array}\left(\left[\left\{1\&comma;2\&comma;3\right\}\&comma;\left\{2\&comma;4\right\}\&comma;\left\{3\&comma;5\right\}\&comma;\left\{4\&comma;6\right\}\&comma;\left\{5\&comma;6\right\}\&comma;\left\{6\right\}\right]\right)\&comma;\mathrm{input}=\mathrm{transitivereduction}\right)$

$\mathrm{poset8}≔\mathrm{<\; a\; poset\; with\; 6\; elements\; >}$

$\mathrm{DrawGraph}\left(\mathrm{poset8}\right)$

$t≔\mathrm{PolyhedralSets}:-\mathrm{ExampleSets}:-\mathrm{Octahedron}\left(\right)$

$t≔\&lcub;\begin{array}{lll}\mathrm{Coordinates}& \&colon;& \left[x_1\&comma;x_2\&comma;x_3\right]\\ \mathrm{Relations}& \&colon;& \left[-x_1-x_2-x_3\le 1\&comma;-x_1-x_2+x_3\le 1\&comma;-x_1+x_2-x_3\le 1\&comma;-x_1+x_2+x_3\le 1\&comma;x_1-x_2-x_3\le 1\&comma;x_1-x_2+x_3\le 1\&comma;x_1+x_2-x_3\le 1\&comma;x_1+x_2+x_3\le 1\right]\end{array}$

$d≔\mathrm{PolyhedralSets}:-\mathrm{Dimension}\left(t\right)$

$d≔3$

$\mathrm{t\_faces}≔\left\{\mathrm{seq}\left(\mathrm{op}\left(\mathrm{PolyhedralSets}:-\mathrm{Faces}\left(t\&comma;\mathrm{dimension}=i\right)\right)\&comma;i=-0..d\right)\right\}\&colon;$

$\mathrm{t\_faces}≔\mathrm{t\_faces}\mathbf{union}\left\{\mathrm{PolyhedralSets}:-\mathrm{ExampleSets}:-\mathrm{EmptySet}\left(d\right)\right\}\&colon;$

$\mathrm{FL}≔\mathrm{convert}\left(\mathrm{t\_faces}\&comma;\mathrm{list}\right)\&colon;$

inclusion := proc(x,y) PolyhedralSets:-`subset`(FL[x],FL[y]) end proc:

$\mathrm{polyhedral\_poset}≔\mathrm{PartiallyOrderedSet}\left(\left\{\mathrm{seq}\left(i\&comma;i=1..\mathrm{nops}\left(\mathrm{FL}\right)\right)\right\}\&comma;\mathrm{inclusion}\right)$

$\mathrm{polyhedral\_poset}≔\mathrm{<\; a\; poset\; with\; 28\; elements\; >}$

$\mathrm{DrawGraph}\left(\mathrm{polyhedral\_poset}\right)$

$M≔\mathrm{Matrix}\left(\left[\left[1\&comma;1\&comma;1\&comma;1\&comma;1\right]\&comma;\left[0\&comma;1\&comma;1\&comma;0\&comma;1\right]\&comma;\left[0\&comma;0\&comma;1\&comma;0\&comma;1\right]\&comma;\left[0\&comma;0\&comma;0\&comma;1\&comma;1\right]\&comma;\left[0\&comma;0\&comma;0\&comma;0\&comma;1\right]\right]\right)\&colon;$

$\mathrm{poset9}≔\mathrm{PartiallyOrderedSet}\left(\left[\mathrm{seq}\left(1..5\right)\right]\&comma;M\right)$

$\mathrm{poset9}≔\mathrm{<\; a\; poset\; with\; 5\; elements\; >}$

$\mathrm{DrawGraph}\left(\mathrm{poset9}\right)$

$Z≔\left\{1\&comma;2\&comma;3\&comma;4\&comma;5\&comma;6\&comma;10\&comma;12\&comma;15\&comma;20\&comma;30\&comma;60\right\}$

$Z≔\left\{1\&comma;2\&comma;3\&comma;4\&comma;5\&comma;6\&comma;10\&comma;12\&comma;15\&comma;20\&comma;30\&comma;60\right\}$

$\mathrm{poset10}≔\mathrm{PartiallyOrderedSet}\left(Z\&comma;\mathrm{divisibility}\right)$

$\mathrm{poset10}≔\mathrm{<\; a\; poset\; with\; 12\; elements\; >}$

$\mathrm{DrawGraph}\left(\mathrm{poset10}\&comma;\mathrm{reduction}=\mathrm{true}\right)$

$\mathrm{DrawGraph}\left(\mathrm{poset10}\&comma;\mathrm{reduction}=\mathrm{false}\right)$

$\mathrm{DrawGraph}\left(\mathrm{poset10}\&comma;\mathrm{reduction}=\mathrm{false}\&comma;\mathrm{showlabels}=\mathrm{false}\right)$

$\mathrm{ZZ}≔\left\{1\&comma;2\&comma;3\&comma;4\&comma;5\&comma;6\&comma;12\&comma;15\&comma;60\right\}$

$\mathrm{ZZ}≔\left\{1\&comma;2\&comma;3\&comma;4\&comma;5\&comma;6\&comma;12\&comma;15\&comma;60\right\}$

$\mathrm{poset11}≔\mathrm{PartiallyOrderedSet}\left(\mathrm{ZZ}\&comma;\mathrm{divisibility}\right)$

$\mathrm{poset11}≔\mathrm{<\; a\; poset\; with\; 9\; elements\; >}$

$\mathrm{DrawGraph}\left(\mathrm{poset11}\&comma;\mathrm{prefer}=\mathrm{low}\right)$

$\mathrm{DrawGraph}\left(\mathrm{poset11}\&comma;\mathrm{prefer}=\mathrm{high}\right)$

$\mathrm{DrawGraph}\left(\mathrm{poset11}\&comma;\mathrm{caption}=\mathrm{Poset11}\&comma;\mathrm{size}=\left[200\&comma;200\right]\right)$

Richard P. Stanley: Enumerative Combinatorics 1. 1997, Cambridge Studies in Advanced Mathematics. Vol. 49. Cambridge University Press.

The PartiallyOrderedSets[DrawGraph] command was introduced in Maple 2025.

For more information on Maple 2025 changes, see Updates in Maple 2025.