% $Id: linearExtensions.tex,v 1.1.1.5 2004/10/04 17:25:16 nthiery Exp $
\begin{Mhelppage}{linearExtensions}{F.~Hivert and N.~Thiéry}
  [ImplState=stable,TestState=stable,DocState=stable]
\Mproofread{Nicolas M. Thiéry}{20/10/2002}{}

\begin{MInfo}
  \eng{linear extensions (topological sortings) of DAGs or posets}
\end{MInfo}

\begin{MIntro}
  \eng{The library \Mthis{} provides functions for counting,
    generating, and manipulating linear extensions of directed acyclic
    graphs (DAGs) and in particular partially ordered sets (posets).}
\end{MIntro}

\MKeywords{combinatorics, poset, acyclic graph, topological sortings,
  linear extensions}

\begin{MDetails}
  \eng{Let $G$ be a directed graph. A \emph{linear extension} $L$ of
    $G$ is a total ordering $<_L$ of the vertices of $G$ such that
    $a<_Lb$ for all edges $a\to b$ of $G$. There exists such a linear
    extension if, and only if, $G$ is a DAG (\emph{directed acyclic
      graph}), that is if $G$ contains no cycle $a\to b \to \dots \to
    z \to a$. Linear extensions are also called \emph{topological
      sortings}.}
  
  \eng{A graph $G$ is stored as an element of the domain
    \Mup[Graph,firstpage]{Graph}.  Linear extensions are stored as lists of
    vertices. The definition above rewrites as: the list \Mex{L} is a
    linear extension of \Mex{G} if for any edge \Mex{[a,b]} of \Mex{G}
    the vertex \Mex{a} appears before \Mex{b} in \Mex{L}.}
  
  \eng{Given a total ordering on the vertices of the graph \Mex{G},
    linear extensions are naturally ordered lexicographically. The
    user can provide the total ordering as an optional argument; by
    default \Mup{sysorder} is used.}
  
  \eng{See the background section below for details about DAGs and
    posets.}
\end{MDetails}

\begin{MCategories}
\Mup{Cat::CombinatorialClass}
\end{MCategories}

\MRelatedDomains{Graph}

\begin{MDomEntries}
  \MDomEntry{domtype}
       \eng{The \mupad\ domain used to represent linear extensions:
       \Mup{DOM_LIST}.}
  \MDomEntry{typeGraph}
     \eng{\begin{sloppypar}
       The \mupad\ type used to represent directed graphs:
       \Mupc{Type::Intersection}%
       {(\Mup[Graph,firstpage]{Graph},\Mup{Type::Predicate}%
       (\Mup{Graph::isDirected}))}.
       \end{sloppypar}}
  \MDomEntry{typeOrder}
     \eng{\begin{sloppypar}
       The \mupad\ type used to represent vertex orderings:
       \Mupc{Type::Union}{\Mup{DOM_PROC}, \Mup{DOM_FUNC_ENV}}.
          \end{sloppypar}}
\end{MDomEntries}

\begin{MMethodDetails}{isA}
  \infoEng{check for linear extensions}
  \call{\Mtype{list} l\Mopt{, \Mtype{directed graph} g}} %
  \eng{Returns whether the list \Mpar{l} is a linear extension. If \Mex{g} is
    given, returns whether the list \Mpar{l} is a linear extension of the
    directed graph \Mpar{g}.}
\end{MMethodDetails}

\begin{MMethodDetails}{count}
  \infoEng{number of linear extensions}
  \call{\Mtype{directed graph} g}%
  \eng{Returns the number of linear extensions of the directed
    graph \Mpar{g}.}
\end{MMethodDetails}

\begin{MMethodDetails}{generator}
  \infoEng{generator for linear extensions}
  \call{\Mtype{directed graph} g\Mopt{, \Mtype{vertex order} order}}%
  \eng{Returns a generator for the linear extensions of the directed
    graph \Mpar{g}, in lexicographic order w.r.t. \Mpar{order}.}
\end{MMethodDetails}

\begin{MMethodDetails}{list}
  \infoEng{list of the linear extensions}
  \call{\Mtype{directed graph} g\Mopt{, \Mtype{vertex order} order}}%
  \eng{Returns the list of the linear extensions of the directed graph
    \Mpar{g}, in lexicographic order w.r.t. \Mpar{order}.}
\end{MMethodDetails}

\begin{MMethodDetails}{first}
  \infoEng{first linear extension}
  \call{\Mtype{directed graph} g\Mopt{, \Mtype{vertex order} order}}%
  \eng{Returns the first linear extension of \Mpar{g}, in
    lexicographic order w.r.t. \Mpar{order}, or \Mex{FAIL} if there is
    none.}
\end{MMethodDetails}
    
\begin{MMethodDetails}{Next}
  \infoEng{next linear extension}
  \call{\Mtype{linear extension} l, \Mtype{directed graph} g\Mopt{, \Mtype{vertex order} order}}%
  \eng{Returns the next linear extension of the directed graph
    \Mpar{g}, in lexicographic order w.r.t. \Mpar{order}, or
    \Mex{FAIL} if there is none.}
\end{MMethodDetails}

\begin{MExample}{ex-basic}
  \eng{Let \Mex{gr} be the directed graph whose edges are $(a\to c)$
    and $(b\to c)$:}
  \begin{Mexin}
gr := Graph([a, b, c], [[a, c], [b, c]], Directed)
  \end{Mexin}
  \begin{Mexout}
                          Graph(...)
  \end{Mexout}

  \eng{\Mex{gr} has $2$ linear extensions:}
  \begin{Mexin}
combinat::linearExtensions::count(gr)
  \end{Mexin}
  \begin{Mexout}
                               2
  \end{Mexout}
  \eng{Here is the list:}
  \begin{Mexin}
combinat::linearExtensions::list(gr)
  \end{Mexin}
  \begin{Mexout}
                    [[a, b, c], [b, a, c]]
  \end{Mexout}
  
  \eng{You can use the function
    \Mex{combinat::linearExtensions::first} to get the ``first''
    linear extension a graph:}
  \begin{Mexin}
combinat::linearExtensions::first(gr)
  \end{Mexin}
  \begin{Mexout}
                           [a, b, c]
  \end{Mexout}
  
  \eng{Using \Mex{combinat::linearExtensions::Next}, you can calculate
    the ``next'' next linear extension.  This function takes as
    argument the linear extension relative to which you want the next
    one:}
  \begin{Mexin}
combinat::linearExtensions::Next([a, b, c], gr)
  \end{Mexin}
  \begin{Mexout}
                           [b, a, c]
  \end{Mexout}
  
  \eng{\Mex{combinat::linearExtensions::Next} returns \Mup{FAIL} when
    the input is the last linear extension:}
  \begin{Mexin}
combinat::linearExtensions::Next([b, a, c], gr)
  \end{Mexin}
  \begin{Mexout}
                             FAIL
  \end{Mexout}
  
  \eng{When you want to run through the linear extensions of a graph,
    you can generate them one by one to save memory:}
  \begin{Mexin}
gr := Graph([a, b, c, d], [[a, c], [b, c], [b, d]], Directed):
g := combinat::linearExtensions::generator(gr):
g(); g(); g(); g(); g(); g();
  \end{Mexin}
  \begin{Mexout}
                         [a, b, c, d]

                         [a, b, d, c]

                         [b, a, c, d]

                         [b, a, d, c]

                         [b, d, a, c]

                             FAIL
\end{Mexout}

\eng{One can check that these are actually linear extensions of gr:}
  \begin{Mexin}
combinat::linearExtensions::isA([a, b, d, c], gr)
  \end{Mexin}
  \begin{Mexout}
                             TRUE
  \end{Mexout}
  
  \eng{But \Mex{[c, a, b, d]} is not because there is an arrow
    \Mex{[a, c]} whereas \Mex{a} is after \Mex{c}:}
  \begin{Mexin}
combinat::linearExtensions::isA([c, a, b, d], gr)
  \end{Mexin}
  \begin{Mexout}
                             FALSE
  \end{Mexout}
\end{MExample}

\begin{MBackground}
  \eng{A \emph{partially ordered set}, or \emph{poset} for short, is a
    set $P$ equipped with a reflexive anti-symmetric and transitive
    relation denoted by $\leq_P$. A linear extention of a poset is a
    total order extending $\leq_P$. A poset can be considered as a
    directed acyclic graph: $(a\to b)$ if and only if $(a <_P b)$.
    Reciprocally, the transitive closure of a directed acyclic graph
    $g$ is a poset $P$ with same linear extensions.}
    
  \eng{For efficiency of the algorithm, it is better not to give the
    full poset $P$ but the smallest DAG $g$ whose transitive closure
    is $P$. This DAG is called the \emph{Hasse diagram of $P$}.}
  
  \eng{The amortized complexity of the generation algorithm is linear
    in the maximal out degree, for each linear extension generated.}
  
  \eng{\Mwarn{Counting is done by brute force generation.}}
\end{MBackground}

\MSuperDomain{Dom::BaseDomain}
 
\begin{MAxioms}
  \Mup{Ax::systemRep}
\end{MAxioms}

\begin{MChanges}
  \version{3.0}%
  \eng[New library]{\Mthis{} is a new library}
\end{MChanges}

\end{Mhelppage}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: main
%%% End: 
