[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

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

Method count: number of linear extensions

Method generator: generator for linear extensions

Method list: list of the linear extensions

Method first: first linear extension

Method Next: next linear extension

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

Super-Domain

Dom::BaseDomain

Axioms

Ax::systemRep

Changes

[Previous] [Next] [Contents]


MuPAD Combinat, an open source algebraic combinatorics package