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 \(10^+1\)).
Alternatively, one can say that a sequence of sets \(S_1,...,S_n\) satisfies the consecutive ones property if for any \(x\) the indices of the sets containing \(x\) is an interval of \([1,n]\).
This module is used for the recognition of Interval Graphs (see
is_interval()
).
P-tree and Q-tree
A \(P\)-tree with children \(c_1,...,c_k\) (which can be \(P\)-trees, \(Q\)-trees, or actual sets of points) indicates that all \(k!\) permutations of the children are allowed.
Example: \(\{1,2\},\{3,4\},\{5,6\}\) (disjoint sets can be permuted in any way)
A \(Q\)-tree with children \(c_1,...,c_k\) (which can be \(P\)-trees, \(Q\)-trees, or actual sets of points) indicates that only two permutations of its children are allowed: \(c_1,...,c_k\) or \(c_k,...,c_1\).
Example: \(\{1,2\},\{2,3\},\{3,4\},\{4,5\},\{5,6\}\) (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 \(S_1,...,S_k\) satisfying the consecutive ones property, we initialize \(T\) as a \(P\)-tree whose children are all the \(S_1,...,S_k\), thus representing the set of all \(k!\) permutations of them.
We select some element \(x\) and update the data structure \(T\) to restrict the permutations it describes to those that keep the occurrences of \(x\) on an interval of \([1,...,k]\). This will result in a new \(P\)-tree whose children are:
all \(\bar c_x\) sets \(S_i\) which do not contain \(x\).
a new \(P\)-tree whose children are the \(c_x\) sets \(S_i\) containing \(x\).
This describes the set of all \(c_x!\times \bar c'_x!\) permutations of \(S_1,...,S_k\) that keep the sets containing \(x\) on an interval.
We take a second element \(x'\) and update the data structure \(T\) to restrict the permutations it describes to those that keep \(x'\) on an interval of \([1,...,k]\). The sets \(S_1,...,S_k\) belong to 4 categories:
The family \(S_{00}\) of sets which do not contain any of \(x,x'\).
The family \(S_{01}\) of sets which contain \(x'\) but do not contain \(x\).
The family \(S_{10}\) of sets which contain \(x\) but do not contain \(x'\).
The family \(S_{11}\) of sets which contain \(x'\) and \(x'\).
With these notations, the permutations of \(S_1,...,S_k\) which keep the occurrences of \(x\) and \(x'\) on an interval are of two forms:
<some sets \(S_{00}\)>, <sets from \(S_{10}\)>, <sets from \(S_{11}\)>, <sets from \(S_{01}\)>, <other sets from \(S_{00}\)>
<some sets \(S_{00}\)>, <sets from \(S_{01}\)>, <sets from \(S_{11}\)>, <sets from \(S_{10}\)>, <other sets from \(S_{00}\)>
These permutations can be modeled with the following \(PQ\)-tree:
A \(P\)-tree whose children are:
All sets from \(S_{00}\)
A \(Q\)-tree whose children are:
A \(P\)-tree with whose children are the sets from \(S_{10}\)
A \(P\)-tree with whose children are the sets from \(S_{11}\)
A \(P\)-tree with whose children are the sets from \(S_{01}\)
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 [Haj2000].
Authors:
Nathann Cohen (initial implementation)
Methods and functions#
- class sage.graphs.pq_trees.P(seq)#
Bases:
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 orderingsEXAMPLES:
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.EXAMPLES:
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)#
Bases:
object
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.EXAMPLES:
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
EXAMPLES:
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.
EXAMPLES:
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 childrenEXAMPLES:
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 \(P\)-tree, which is useful when one want to keep the elements containingv
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 \(Q\)-Tree, the sequence of its children is returned. Ifself
is a \(P\)-tree, 2 \(P\)-tree are returned, namely the two \(P\)-tree defined above and restricting the permutations, in the order implied byleft, right
(ifright =True
, the second \(P\)-tree will be the one gathering the elements containingv
, ifleft=True
, the opposite).Note
This method is assumes that
self
is partial forv
, and aligned to the side indicated byleft, right
.EXAMPLES:
A \(P\)-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 \(Q\)-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:
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 orderingsEXAMPLES:
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.EXAMPLES:
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.reorder_sets(sets)#
Reorders a collection of sets such that each element appears on an interval.
Given a collection of sets \(C = S_1,...,S_k\) on a ground set \(X\), this function attempts to reorder them in such a way that \(\forall x \in X\) and \(i<j\) with \(x\in S_i, S_j\), then \(x\in S_l\) for every \(i<l<j\) if it exists.
INPUT:
sets
- a list of instances oflist, Set
orset
ALGORITHM:
PQ-Trees
EXAMPLES:
There is only one way (up to reversal) to represent contiguously the sequence ofsets \(\{i-1, i, i+1\}\):
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}]