PQ-Trees¶
This module implements PQ-Trees, a data structure use to represent all permutations of the columns of a matrix which satisfy the consecutive ones property:
A binary matrix satisfies the consecutive ones property if the 1s are contiguous in each of its rows (or equivalently, if no row contains the regexp pattern
).
Alternatively, one can say that a sequence of sets
satisfies the consecutive ones property if for any
the indices of the sets containing
is an interval of
.
This module is used for the recognition of Interval Graphs (see
is_interval()
).
P-tree and Q-tree
A
-tree with children
(which can be
-trees,
-trees, or actual sets of points) indicates that all
permutations of the children are allowed.
Example:
(disjoint sets can be permuted in any way)
A
-tree with children
(which can be
-trees,
-trees, or actual sets of points) indicates that only two permutations of its children are allowed:
or
.
Example:
(only two permutations of these sets have the consecutive ones property).
Computation of all possible orderings
In order to compute all permutations of a sequence of sets
satisfying the consecutive ones property, we initialize
as a
-tree whose children are all the
, thus representing the set of all
permutations of them.
We select some element
and update the data structure
to restrict the permutations it describes to those that keep the occurrences of
on an interval of
. This will result in a new
-tree whose children are:
- all
sets
which do not contain
.
- a new
-tree whose children are the
sets
containing
.
This describes the set of all
permutations of
that keep the sets containing
on an interval.
- all
We take a second element
and update the data structure
to restrict the permutations it describes to those that keep
on an interval of
. The sets
belong to 4 categories:
- The family
of sets which do not contain any of
.
- The family
of sets which contain
but do not contain
.
- The family
of sets which contain
but do not contain
.
- The family
of sets which contain
and
.
With these notations, the permutations of
which keep the occurrences of
and
on an interval are of two forms:
- <some sets
>, <sets from
>, <sets from
>, <sets from
>, <other sets from
>
- <some sets
>, <sets from
>, <sets from
>, <sets from
>, <other sets from
>
These permutations can be modeled with the following
-tree:
- A
-tree whose children are:
- All sets from
- A
-tree whose children are:
- A
-tree with whose children are the sets from
- A
-tree with whose children are the sets from
- A
-tree with whose children are the sets from
- A
- All sets from
- The family
One at a time, we update the data structure with each element until they are all exhausted, or until we reach a proof that no permutation satisfying the consecutive ones property exists.
Using these two types of tree, and exploring the different cases of intersection, it is possible to represent all the possible permutations of our sets satisfying our constraints, or to prove that no such ordering exists. This is the whole purpose of this module, and is explained with more details in many places, for example in the following document from Hajiaghayi [Haj].
REFERENCES:
[Haj] | M. Hajiaghayi http://www-math.mit.edu/~hajiagha/pp11.ps |
Authors:
Nathann Cohen (initial implementation)
Methods and functions¶
-
class
sage.graphs.pq_trees.
P
(seq)¶ Bases:
sage.graphs.pq_trees.PQ
A P-Tree is a PQ-Tree whose children can be permuted in any way.
For more information, see the documentation of
sage.graphs.pq_trees
.-
cardinality
()¶ Return the number of orderings allowed by the structure.
See also
orderings()
– iterate over all admissible orderingsEXAMPLE:
sage: from sage.graphs.pq_trees import P, Q sage: p = P([[0,3], [1,2], [2,3], [2,4], [4,0],[2,8], [2,9]]) sage: p.cardinality() 5040 sage: p.set_contiguous(3) (1, True) sage: p.cardinality() 1440
-
orderings
()¶ Iterate over all orderings of the sets allowed by the structure.
See also
cardinality()
– return the number of orderingsEXAMPLES:
sage: from sage.graphs.pq_trees import P, Q sage: p = P([[2,4], [1,2], [0,8], [0,5]]) sage: for o in p.orderings(): ....: print(o) ({2, 4}, {1, 2}, {0, 8}, {0, 5}) ({2, 4}, {1, 2}, {0, 5}, {0, 8}) ({2, 4}, {0, 8}, {1, 2}, {0, 5}) ({2, 4}, {0, 8}, {0, 5}, {1, 2}) ...
-
set_contiguous
(v)¶ Updates
self
so that the sets containingv
are contiguous for any admissible permutation of its subtrees.INPUT:
v
– an element of the ground set
OUTPUT:
According to the cases :
(EMPTY, ALIGNED)
if no set of the tree contains an occurrence ofv
(FULL, ALIGNED)
if all the sets of the tree containv
(PARTIAL, ALIGNED)
if some (but not all) of the sets containv
, all of which are aligned to the right of the ordering at the end when the function ends(PARTIAL, UNALIGNED)
if some (but not all) of the sets containv
, though it is impossible to align them all to the right
In any case, the sets containing
v
are contiguous when this function ends. If there is no possibility of doing so, the function raises aValueError
exception.EXAMPLE:
Ensuring the sets containing
0
are continuous:sage: from sage.graphs.pq_trees import P, Q sage: p = P([[0,3], [1,2], [2,3], [2,4], [4,0],[2,8], [2,9]]) sage: p.set_contiguous(0) (1, True) sage: print(p) ('P', [{1, 2}, {2, 3}, {2, 4}, {8, 2}, {9, 2}, ('P', [{0, 3}, {0, 4}])])
Impossible situation:
sage: p = P([[0,1], [1,2], [2,3], [3,0]]) sage: p.set_contiguous(0) (1, True) sage: p.set_contiguous(1) (1, True) sage: p.set_contiguous(2) (1, True) sage: p.set_contiguous(3) Traceback (most recent call last): ... ValueError: Impossible
-
-
class
sage.graphs.pq_trees.
PQ
(seq)¶ PQ-Trees
This class should not be instantiated by itself: it is extended by
P
andQ
. See the documentation ofsage.graphs.pq_trees
for more information.AUTHOR : Nathann Cohen
-
flatten
()¶ Returns a flattened copy of
self
If self has only one child, we may as well consider its child’s children, as
self
encodes no information. This method recursively “flattens” trees having only on PQ-tree child, and returns it.EXAMPLE:
sage: from sage.graphs.pq_trees import P, Q sage: p = Q([P([[2,4], [2,8], [2,9]])]) sage: p.flatten() ('P', [{2, 4}, {8, 2}, {9, 2}])
-
number_of_children
()¶ Returns the number of children of
self
EXAMPLE:
sage: from sage.graphs.pq_trees import P, Q sage: p = Q([[1,2], [2,3], P([[2,4], [2,8], [2,9]])]) sage: p.number_of_children() 3
-
ordering
()¶ Returns the current ordering given by listing the leaves from left to right.
EXAMPLE:
sage: from sage.graphs.pq_trees import P, Q sage: p = Q([[1,2], [2,3], P([[2,4], [2,8], [2,9]])]) sage: p.ordering() [{1, 2}, {2, 3}, {2, 4}, {8, 2}, {9, 2}]
-
reverse
()¶ Recursively reverses
self
and its childrenEXAMPLE:
sage: from sage.graphs.pq_trees import P, Q sage: p = Q([[1,2], [2,3], P([[2,4], [2,8], [2,9]])]) sage: p.ordering() [{1, 2}, {2, 3}, {2, 4}, {8, 2}, {9, 2}] sage: p.reverse() sage: p.ordering() [{9, 2}, {8, 2}, {2, 4}, {2, 3}, {1, 2}]
-
simplify
(v, left=False, right=False)¶ Returns a simplified copy of self according to the element
v
If
self
is a partial P-tree forv
, we would like to restrict the permutations of its children to permutations keeping the children containingv
contiguous. This function also “locks” all the elements not containingv
inside a-tree, which is useful when one want to keep the elements containing
v
on one side (which is the case when this method is called).INPUT:
left, right
(boolean) – whetherv
is aligned to the right or to the leftv
– an element of the ground set
OUTPUT:
If
self
is a-Tree, the sequence of its children is returned. If
self
is a-tree, 2
-tree are returned, namely the two
-tree defined above and restricting the permutations, in the order implied by
left, right
(ifright =True
, the second-tree will be the one gathering the elements containing
v
, ifleft=True
, the opposite).Note
This method is assumes that
self
is partial forv
, and aligned to the side indicated byleft, right
.EXAMPLES:
A
-Tree
sage: from sage.graphs.pq_trees import P, Q sage: p = P([[2,4], [1,2], [0,8], [0,5]]) sage: p.simplify(0, right = True) [('P', [{2, 4}, {1, 2}]), ('P', [{0, 8}, {0, 5}])]
A
-Tree
sage: q = Q([[2,4], [1,2], [0,8], [0,5]]) sage: q.simplify(0, right = True) [{2, 4}, {1, 2}, {0, 8}, {0, 5}]
-
-
class
sage.graphs.pq_trees.
Q
(seq)¶ Bases:
sage.graphs.pq_trees.PQ
A Q-Tree is a PQ-Tree whose children are ordered up to reversal
For more information, see the documentation of
sage.graphs.pq_trees
.-
cardinality
()¶ Return the number of orderings allowed by the structure.
See also
orderings()
– iterate over all admissible orderingsEXAMPLE:
sage: from sage.graphs.pq_trees import P, Q sage: q = Q([[0,3], [1,2], [2,3], [2,4], [4,0],[2,8], [2,9]]) sage: q.cardinality() 2
-
orderings
()¶ Iterates over all orderings of the sets allowed by the structure
See also
cardinality()
– return the number of orderingsEXAMPLES:
sage: from sage.graphs.pq_trees import P, Q sage: q = Q([[2,4], [1,2], [0,8], [0,5]]) sage: for o in q.orderings(): ....: print(o) ({2, 4}, {1, 2}, {0, 8}, {0, 5}) ({0, 5}, {0, 8}, {1, 2}, {2, 4})
-
set_contiguous
(v)¶ Updates
self
so that the sets containingv
are contiguous for any admissible permutation of its subtrees.INPUT:
v
– an element of the ground set
OUTPUT:
According to the cases :
(EMPTY, ALIGNED)
if no set of the tree contains an occurrence ofv
(FULL, ALIGNED)
if all the sets of the tree containv
(PARTIAL, ALIGNED)
if some (but not all) of the sets containv
, all of which are aligned to the right of the ordering at the end when the function ends(PARTIAL, UNALIGNED)
if some (but not all) of the sets containv
, though it is impossible to align them all to the right
In any case, the sets containing
v
are contiguous when this function ends. If there is no possibility of doing so, the function raises aValueError
exception.EXAMPLE:
Ensuring the sets containing
0
are continuous:sage: from sage.graphs.pq_trees import P, Q sage: q = Q([[2,3], Q([[3,0],[3,1]]), Q([[4,0],[4,5]])]) sage: q.set_contiguous(0) (1, False) sage: print(q) ('Q', [{2, 3}, {1, 3}, {0, 3}, {0, 4}, {4, 5}])
Impossible situation:
sage: p = Q([[0,1], [1,2], [2,0]]) sage: p.set_contiguous(0) Traceback (most recent call last): ... ValueError: Impossible
-
-
sage.graphs.pq_trees.
flatten
(x)¶
-
sage.graphs.pq_trees.
new_P
(liste)¶
-
sage.graphs.pq_trees.
new_Q
(liste)¶
-
sage.graphs.pq_trees.
reorder_sets
(sets)¶ Reorders a collection of sets such that each element appears on an interval.
Given a collection of sets
on a ground set
, this function attempts to reorder them in such a way that
and
with
, then
for every
if it exists.
INPUT:
sets
- a list of instances oflist, Set
orset
ALGORITHM:
PQ-Trees
EXAMPLE:
There is only one way (up to reversal) to represent contiguously the sequence ofsets
:
sage: from sage.graphs.pq_trees import reorder_sets sage: seq = [Set([i-1,i,i+1]) for i in range(1,15)]
We apply a random permutation:
sage: p = Permutations(len(seq)).random_element() sage: seq = [ seq[p(i+1)-1] for i in range(len(seq)) ] sage: ordered = reorder_sets(seq) sage: if not 0 in ordered[0]: ....: ordered = ordered.reverse() sage: print(ordered) [{0, 1, 2}, {1, 2, 3}, {2, 3, 4}, {3, 4, 5}, {4, 5, 6}, {5, 6, 7}, {8, 6, 7}, {8, 9, 7}, {8, 9, 10}, {9, 10, 11}, {10, 11, 12}, {11, 12, 13}, {12, 13, 14}, {13, 14, 15}]
-
sage.graphs.pq_trees.
set_contiguous
(tree, x)¶