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).
Superdomain
Categories
Axioms
Related Domains:
Details:
Let math be a directed graph. A linear extensionmath of math is a total ordering math of the vertices of math such that math for all edges math of math. There exists such a linear extension if, and only if, math is a DAG (directed acyclic graph), that is if math contains no cycle math Linear extensions are also called topological sortings.
A graph math 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.
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).
isA – check for linear extensions
combinat::linearExtensions::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.
count – number of linear extensions
combinat::linearExtensions::count(directed graph g)
Returns the number of linear extensions of the directed graph g.
generator – generator for linear extensions
combinat::linearExtensions::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.
list – list of the linear extensions
combinat::linearExtensions::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.
first – first linear extension
combinat::linearExtensions::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.
Next – next linear extension
combinat::linearExtensions::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.
Let gr be the directed graph whose edges are math and math:
gr := Graph([a, b, c], [[a, c], [b, c]], Directed)
math
gr has math linear extensions:
combinat::linearExtensions::count(gr)
math
Here is the list:
combinat::linearExtensions::list(gr)
math
You can use the function combinat::linearExtensions::first to get the "first" linear extension a graph:
combinat::linearExtensions::first(gr)
math
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)
math
combinat::linearExtensions::Next returns FAIL when the input is the last linear extension:
combinat::linearExtensions::Next([b, a, c], gr)
math
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();
math
math
math
math
math
math
One can check that these are actually linear extensions of gr:
combinat::linearExtensions::isA([a, b, d, c], gr)
math
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)
math
Background:
A partially ordered set, or poset for short, is a set math equipped with a reflexive anti-symmetric and transitive relation denoted by math. A linear extention of a poset is a total order extending math. A poset can be considered as a directed acyclic graph: math if and only if math. Reciprocally, the transitive closure of a directed acyclic graph math is a poset math with same linear extensions.
For efficiency of the algorithm, it is better not to give the full poset math but the smallest DAG math whose transitive closure is math. This DAG is called the Hasse diagram of math.
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.