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

  1. 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.

  2. 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.

  3. 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}\)

  4. 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: 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 orderings

EXAMPLES:

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 orderings

EXAMPLES:

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 containing v 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 of v

  • (FULL, ALIGNED) if all the sets of the tree contain v

  • (PARTIAL, ALIGNED) if some (but not all) of the sets contain v, 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 contain v, 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 a ValueError 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 and Q. See the documentation of sage.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 children

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}]
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 for v, we would like to restrict the permutations of its children to permutations keeping the children containing v contiguous. This function also “locks” all the elements not containing v inside a \(P\)-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) – whether v is aligned to the right or to the left

  • v– an element of the ground set

OUTPUT:

If self is a \(Q\)-Tree, the sequence of its children is returned. If self is a \(P\)-tree, 2 \(P\)-tree are returned, namely the two \(P\)-tree defined above and restricting the permutations, in the order implied by left, right (if right =True, the second \(P\)-tree will be the one gathering the elements containing v, if left=True, the opposite).

Note

This method is assumes that self is partial for v, and aligned to the side indicated by left, 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: 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 orderings

EXAMPLES:

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 orderings

EXAMPLES:

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 containing v 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 of v

  • (FULL, ALIGNED) if all the sets of the tree contain v

  • (PARTIAL, ALIGNED) if some (but not all) of the sets contain v, 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 contain v, 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 a ValueError 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.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 \(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 of list, Set or set

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}]
sage.graphs.pq_trees.set_contiguous(tree, x)