# Linear Extensions of Directed Acyclic Graphs.¶

A linear extension of a directed acyclic graph is a total (linear) ordering on the vertices that is compatible with the graph in the following sense: if there is a path from x to y in the graph, the x appears before y in the linear extension.

The algorithm implemented in this module is from “Generating Linear Extensions Fast” by Preusse and Ruskey, which can be found at http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.52.3057 . The algorithm generates the extensions in constant amortized time (CAT) – a constant amount of time per extension generated, or linear in the number of extensions generated.

EXAMPLES:

Here we generate the 5 linear extensions of the following directed acyclic graph:

sage: from sage.graphs.linearextensions import LinearExtensions
sage: D = DiGraph({ 0:[1,2], 1:[3], 2:[3,4] })
sage: D.is_directed_acyclic()
True
sage: LinearExtensions(D).list()
doctest:...: DeprecationWarning: LinearExtensions is deprecated; use FinitePoset.linear_extensions or DiGraph.topological_sort_generator instead
See https://trac.sagemath.org/25864 for details.
[[0, 1, 2, 3, 4],
[0, 1, 2, 4, 3],
[0, 2, 1, 3, 4],
[0, 2, 1, 4, 3],
[0, 2, 4, 1, 3]]


Notice how all of the total orders are compatible with the ordering induced from the graph.

We can also get at the linear extensions directly from the graph. From the graph, the linear extensions are known as topological sorts

sage: list(D.topological_sort_generator())
[[0, 1, 2, 3, 4],
[0, 2, 1, 3, 4],
[0, 2, 1, 4, 3],
[0, 2, 4, 1, 3],
[0, 1, 2, 4, 3]]

sage.graphs.linearextensions.LinearExtensions(dag)

LinearExtensions is deprecated; use sage.combinat.posets.FinitePoset.linear_extensions() or sage.graphs.digraph.DiGraph.topological_sort_generator() instead.

EXAMPLES:

sage: D = DiGraph({ 0:[1,2], 1:[3], 2:[3,4] })
sage: Poset(D).linear_extensions().list()
[[0, 1, 2, 3, 4],
[0, 2, 1, 3, 4],
[0, 2, 1, 4, 3],
[0, 2, 4, 1, 3],
[0, 1, 2, 4, 3]]

sage: D.topological_sort_generator().list()
[[0, 1, 2, 3, 4],
[0, 2, 1, 3, 4],
[0, 2, 1, 4, 3],
[0, 2, 4, 1, 3],
[0, 1, 2, 4, 3]]

sage: D = DiGraph({ "a":["b","c"], "b":["d"], "c":["d","e"] })
sage: Poset(D).linear_extensions().list()
[['a', 'b', 'c', 'd', 'e'],
['a', 'c', 'b', 'd', 'e'],
['a', 'c', 'b', 'e', 'd'],
['a', 'c', 'e', 'b', 'd'],
['a', 'b', 'c', 'e', 'd']]

sage: D.topological_sort_generator().list()
[['a', 'b', 'c', 'd', 'e'],
['a', 'c', 'b', 'd', 'e'],
['a', 'c', 'b', 'e', 'd'],
['a', 'c', 'e', 'b', 'd'],
['a', 'b', 'c', 'e', 'd']]

class sage.graphs.linearextensions.LinearExtensionsOld(dag)

Creates an object representing the class of all linear extensions of the directed acyclic graph code{dag}.

EXAMPLES:

sage: from sage.graphs.linearextensions import LinearExtensions
sage: D = DiGraph({ 0:[1,2], 1:[3], 2:[3,4] })
sage: l = LinearExtensions(D)
doctest:...: DeprecationWarning: LinearExtensions is deprecated; use FinitePoset.linear_extensions or DiGraph.topological_sort_generator instead
See https://trac.sagemath.org/25864 for details.

True

list()

Returns a list of the linear extensions of the directed acyclic graph.

EXAMPLES:

sage: from sage.graphs.linearextensions import LinearExtensions
sage: D = DiGraph({ 0:[1,2], 1:[3], 2:[3,4] })
sage: LinearExtensions(D).list()
doctest:...: DeprecationWarning: LinearExtensions is deprecated; use FinitePoset.linear_extensions or DiGraph.topological_sort_generator instead
See https://trac.sagemath.org/25864 for details.
[[0, 1, 2, 3, 4],
[0, 1, 2, 4, 3],
[0, 2, 1, 3, 4],
[0, 2, 1, 4, 3],
[0, 2, 4, 1, 3]]