combinat::linearExtensions
--
linear extensions (topological sortings) of DAGs or posets
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).
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
.G
,
linear extensions are naturally ordered lexicographically. The
user can provide the total ordering as an optional argument; by
default sysorder
is used.Cat::CombinatorialClass
The MuPAD domain used to represent linear extensions:
DOM_LIST
.
The MuPAD type used to represent directed graphs:
Type::Intersection((
.
Graph
,Type::Predicate
(Graph::isDirected
)))
The MuPAD type used to represent vertex orderings:
Type::Union(
.
DOM_PROC
, DOM_FUNC_ENV
)
isA(list l <, directed graph g>)
l
is a linear extension. If g
is
given, returns whether the list l
is a linear extension of the
directed graph g
.
count(directed graph g)
g
.
generator(directed graph g <, vertex order order>)
g
, in lexicographic order w.r.t. order
.
list(directed graph g <, vertex order order>)
g
, in lexicographic order w.r.t. order
.
first(directed graph g <, vertex order order>)
g
, in
lexicographic order w.r.t. order
, or FAIL
if there is
none.
Next(linear extension l, directed graph g <, vertex order order>)
g
, in lexicographic order w.r.t. order
, or
FAIL
if there is none.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
Counting is done by brute force generation.
Ax::systemRep
combinat::linearExtensions
is a new library
MuPAD Combinat, an open source algebraic combinatorics package