[Previous] [Next] [Contents]

[ImplState=stable,TestState=stable,DocState=stable]

## `combinat::linearExtensions` -- linear extensions (topological sortings) of DAGs or posets

#### Introduction

The library `combinat::linearExtensions` provides functions for counting, generating, and manipulating linear extensions of directed acyclic graphs (DAGs) and in particular partially ordered sets (posets).

#### Details

- Let G be a directed graph. A linear extension L of G is a total ordering <L of the vertices of G such that a<Lb for all edges a→b of G. There exists such a linear extension if, and only if, G is a DAG (directed acyclic graph), that is if G contains no cycle a→b →...→z →a. Linear extensions are also called topological sortings.

- A graph G is stored as an element of the domain `Graph`. Linear extensions are stored as lists of vertices. The definition above rewrites as: the list `L` is a linear extension of `G` if for any edge `[a,b]` of `G` the vertex `a` appears before `b` in `L`.

- Given a total ordering on the vertices of the graph `G`, linear extensions are naturally ordered lexicographically. The user can provide the total ordering as an optional argument; by default `sysorder` is used.

- See the background section below for details about DAGs and posets.

#### Categories

`Cat::CombinatorialClass`

#### Related Domains

`Graph`

#### Entries

domtype

The MuPAD domain used to represent linear extensions: `DOM_LIST`.

typeGraph

The MuPAD type used to represent directed graphs: `Type::Intersection((`Graph`,`Type::Predicate` (`Graph::isDirected`)))`.

typeOrder

The MuPAD type used to represent vertex orderings: `Type::Union(`DOM_PROC`, `DOM_FUNC_ENV`)`.

#### Method isA: check for linear extensions

- `isA(list l <, directed graph g>)`

- Returns whether the list `l` is a linear extension. If `g` is given, returns whether the list `l` is a linear extension of the directed graph `g`.

#### Method count: number of linear extensions

- `count(directed graph g)`

- Returns the number of linear extensions of the directed graph `g`.

#### Method generator: generator for linear extensions

- `generator(directed graph g <, vertex order order>)`

- Returns a generator for the linear extensions of the directed graph `g`, in lexicographic order w.r.t. `order`.

#### Method list: list of the linear extensions

- `list(directed graph g <, vertex order order>)`

- Returns the list of the linear extensions of the directed graph `g`, in lexicographic order w.r.t. `order`.

#### Method first: first linear extension

- `first(directed graph g <, vertex order order>)`

- Returns the first linear extension of `g`, in lexicographic order w.r.t. `order`, or `FAIL` if there is none.

#### Method Next: next linear extension

- `Next(linear extension l, directed graph g <, vertex order order>)`

- Returns the next linear extension of the directed graph `g`, in lexicographic order w.r.t. `order`, or `FAIL` if there is none.

#### Example 1

Let `gr` be the directed graph whose edges are (a→c) and (b→c):

    >> gr := Graph([a, b, c], [[a, c], [b, c]], Directed)

                                    Graph(...)

`gr` has 2 linear extensions:

    >> combinat::linearExtensions::count(gr)

                                         2

Here is the list:

    >> combinat::linearExtensions::list(gr)

                              [[a, b, c], [b, a, c]]

You can use the function `combinat::linearExtensions::first` to get the ``first'' linear extension a graph:

    >> combinat::linearExtensions::first(gr)

                                     [a, b, c]

Using `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:

    >> combinat::linearExtensions::Next([a, b, c], gr)

                                     [b, a, c]

`combinat::linearExtensions::Next` returns `FAIL` when the input is the last linear extension:

    >> combinat::linearExtensions::Next([b, a, c], gr)

                                       FAIL

When you want to run through the linear extensions of a graph, you can generate them one by one to save memory:

    >> gr := Graph([a, b, c, d], [[a, c], [b, c], [b, d]], Directed):
       g := combinat::linearExtensions::generator(gr):
       g(); g(); g(); g(); g(); g();

                                   [a, b, c, d]

                                   [a, b, d, c]

                                   [b, a, c, d]

                                   [b, a, d, c]

                                   [b, d, a, c]

                                       FAIL

One can check that these are actually linear extensions of gr:

    >> combinat::linearExtensions::isA([a, b, d, c], gr)

                                       TRUE

But `[c, a, b, d]` is not because there is an arrow `[a, c]` whereas `a` is after `c`:

    >> combinat::linearExtensions::isA([c, a, b, d], gr)

                                       FALSE

#### Background

- A partially ordered set, or poset for short, is a set P equipped with a reflexive anti-symmetric and transitive relation denoted by ≤P. A linear extention of a poset is a total order extending ≤P. A poset can be considered as a directed acyclic graph: (a→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.

- 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 Hasse diagram of P.

- The amortized complexity of the generation algorithm is linear in the maximal out degree, for each linear extension generated.

- Counting is done by brute force generation.

#### Super-Domain

`Dom::BaseDomain`

#### Axioms

`Ax::systemRep`

#### Changes

- `combinat::linearExtensions` is a new library

[Previous] [Next] [Contents]

MuPAD Combinat, an open source algebraic combinatorics package