Coverage for local/lib/python2.7/site-packages/sage/graphs/pq_trees.py : 89%

r""" 

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 

:meth:`~sage.graphs.generic_graph.GenericGraph.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 

[Haj]_. 

REFERENCES: 

.. [Haj] \M. Hajiaghayi 

http://www-math.mit.edu/~hajiagha/pp11.ps 

Authors: 

Nathann Cohen (initial implementation) 

Methods and functions 

--------------------- 

""" 

################################################################################ 

# Copyright (C) 2012 Nathann Cohen <nathann.cohen@gail.com> # 

# # 

# Distributed under the terms of the GNU General Public License (GPL) # 

# http://www.gnu.org/licenses/ # 

################################################################################ 

from __future__ import print_function 

from six import iteritems 

# Constants, to make the code more readable 

FULL = 2 

PARTIAL = 1 

EMPTY = 0 

ALIGNED = True 

UNALIGNED = False 

########################################################################## 

# Some Lambda Functions # 

# # 

# As the elements of a PQ-Tree can be either P-Trees, Q-Trees, or the # 

# sets themselves (the leaves), the following lambda function are # 

# meant to be applied both on PQ-Trees and Sets, and mimic for the # 

# latter the behaviour we expect from the corresponding methods # 

# defined in class PQ # 

########################################################################## 

set_contiguous = lambda tree, x : ( 

tree.set_contiguous(x) if isinstance(tree, PQ) else 

((FULL, ALIGNED) if x in tree 

else (EMPTY, ALIGNED))) 

new_P = lambda liste : P(liste) if len(liste) > 1 else liste[0] 

new_Q = lambda liste : Q(liste) if len(liste) > 1 else liste[0] 

flatten = lambda x : x.flatten() if isinstance(x, PQ) else x 

impossible_msg = "Impossible" 

def reorder_sets(sets): 

r""" 

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}] 

""" 

if len(sets) <= 2: 

return sets 

s = set().union(*sets) # union of the sets 

tree = P(sets) 

for i in s: 

tree.set_contiguous(i) 

tree = flatten(tree) 

return tree.ordering() 

class PQ: 

r""" 

PQ-Trees 

This class should not be instantiated by itself: it is extended by 

:class:`P` and :class:`Q`. See the documentation of 

:mod:`sage.graphs.pq_trees` for more information. 

AUTHOR : Nathann Cohen 

""" 

def __init__(self, seq): 

r""" 

Construction of a PQ-Tree 

EXAMPLES:: 

sage: from sage.graphs.pq_trees import P, Q 

sage: p = Q([[1,2], [2,3], P([[2,4], [2,8], [2,9]])]) 

:trac:`17787`:: 

sage: Graph('GvGNp?').is_interval() 

False 

""" 

from sage.sets.set import Set 

self._children = [] 

for e in seq: 

if isinstance(e, list): 

e = Set(e) 

if not e in self._children: 

self._children.append(e) 

def reverse(self): 

r""" 

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}] 

""" 

for i in self._children: 

if isinstance(i, PQ): 

i.reverse() 

self._children.reverse() 

def __contains__(self, v): 

r""" 

Tests whether there exists an element of ``self`` containing 

an element ``v`` 

INPUT: 

- ``v`` -- an element of the ground set 

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: 5 in p 

False 

sage: 9 in p 

True 

""" 

return any(v in i for i in self) 

def __iter__(self): 

r""" 

Iterates over the 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: for i in p: 

....: print(i) 

{1, 2} 

{2, 3} 

('P', [{2, 4}, {8, 2}, {9, 2}]) 

""" 

for i in self._children: 

yield i 

def number_of_children(self): 

r""" 

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 

""" 

return len(self._children) 

def ordering(self): 

r""" 

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}] 

""" 

value = [] 

for i in self: 

if isinstance(i, PQ): 

value.extend(i.ordering()) 

else: 

value.append(i) 

return value 

def __repr__(self): 

r""" 

Succintly represents ``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: print(p) 

('Q', [{1, 2}, {2, 3}, ('P', [{2, 4}, {8, 2}, {9, 2}])]) 

""" 

return str((("P" if isinstance(self,P) else "Q"),self._children)) 

def simplify(self, v, left = False, right = False): 

r""" 

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}] 

""" 

if sum([left, right]) !=1: 

raise ValueError("Exactly one of left or right must be specified") 

if isinstance(self,Q): 

l = [] 

for c in self._children: 

if (isinstance(c,PQ) and # Is c partial? 

v in c and # (does c contain sets with 

any(v not in cc for cc in c)): # and without v ?) 

l.extend(c.simplify(v,right=right,left=left)) 

else: 

l.append(c) 

return l 

else: 

empty = [] 

full = [] 

partial = [] 

for c in self._children: 

if v in c: 

if (isinstance(c,PQ) and # Is c partial? (does c contain 

any(v not in cc for cc in c)): # sets with and without v ?) 

partial = c.simplify(v,right=right,left=left) 

else: 

full.append(c) 

else: 

empty.append(c) 

if empty: 

empty = [new_P(empty)] 

if full: 

full = [new_P(full)] 

if right: 

return empty+partial+full 

else: 

return full+partial+empty 

def flatten(self): 

r""" 

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}]) 

""" 

if self.number_of_children() == 1: 

return flatten(self._children[0]) 

else: 

self._children = [flatten(x) for x in self._children] 

return self 

class P(PQ): 

r""" 

A P-Tree is a PQ-Tree whose children can be permuted in any way. 

For more information, see the documentation of :mod:`sage.graphs.pq_trees`. 

""" 

def set_contiguous(self, v): 

r""" 

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 

""" 

############################################################### 

# Defining Variables : # 

# # 

# Collecting the information of which children are FULL of v, # 

# which ones are EMPTY, PARTIAL_ALIGNED and PARTIAL_UNALIGNED # 

# # 

# Defining variables for their cardinals, just to make the # 

# code slightly more readable :-) # 

############################################################### 

seq = [set_contiguous(x, v) for x in self] 

self.flatten() 

seq = [set_contiguous(x, v) for x in self] 

f_seq = dict(zip(self, seq)) 

set_FULL = [] 

set_EMPTY = [] 

set_PARTIAL_ALIGNED = [] 

set_PARTIAL_UNALIGNED = [] 

sorting = { 

(FULL, ALIGNED) : set_FULL, 

(EMPTY, ALIGNED) : set_EMPTY, 

(PARTIAL, ALIGNED) : set_PARTIAL_ALIGNED, 

(PARTIAL, UNALIGNED) : set_PARTIAL_UNALIGNED 

} 

for i in self: 

sorting[f_seq[i]].append(i) 

n_FULL = len(set_FULL) 

n_EMPTY = len(set_EMPTY) 

n_PARTIAL_ALIGNED = len(set_PARTIAL_ALIGNED) 

n_PARTIAL_UNALIGNED = len(set_PARTIAL_UNALIGNED) 

counts = {x: len(y) for x, y in iteritems(sorting)} 

# Excludes the situation where there is no solution. 

# read next comment for more explanations 

if (n_PARTIAL_ALIGNED > 2 or 

(n_PARTIAL_UNALIGNED >= 1 and n_EMPTY != self.number_of_children() -1)): 

raise ValueError(impossible_msg) 

# From now on, there are at most two pq-trees which are partially filled 

# If there is one which is not aligned to the right, all the others are empty 

######################################################### 

# 1/2 # 

# # 

# Several easy cases where we can decide without paying # 

# attention # 

######################################################### 

# All the children are FULL 

elif n_FULL == self.number_of_children(): 

return FULL, True 

# All the children are empty 

elif n_EMPTY == self.number_of_children(): 

return EMPTY, True 

# There is a PARTIAL UNALIGNED element (and all the others are 

# empty as we checked before 

elif n_PARTIAL_UNALIGNED == 1: 

return (PARTIAL, UNALIGNED) 

# If there is just one partial element and all the others are 

# empty, we just reorder the set to put it at the right end 

elif (n_PARTIAL_ALIGNED == 1 and 

n_EMPTY == self.number_of_children()-1): 

self._children = set_EMPTY + set_PARTIAL_ALIGNED 

return (PARTIAL, ALIGNED) 

################################################################ 

# 2/2 # 

# # 

# From now on, there are at most two partial pq-trees and all # 

# of them have v aligned to their right # 

# # 

# We now want to order them in such a way that all the # 

# elements containing v are located on the right # 

################################################################ 

else: 

self._children = [] 

# We first move the empty elements to the left, if any 

if n_EMPTY > 0: 

self._children.extend(set_EMPTY) 

# If there is one partial element we but have to add it to 

# the sequence, then add all the full elements 

# We must also make sure these elements will not be 

# reordered in such a way that the elements containing v 

# are not contiguous 

# ==> We create a Q-tree 

if n_PARTIAL_ALIGNED < 2: 

new = [] 

# add the partial element, if any 

if n_PARTIAL_ALIGNED == 1: 

subtree = set_PARTIAL_ALIGNED[0] 

new.extend(subtree.simplify(v, right = ALIGNED)) 

# Then the full elements, if any, in a P-tree (we can 

# permute any two of them while keeping all the 

# elements containing v on an interval 

if n_FULL > 0: 

new.append(new_P(set_FULL)) 

# We lock all of them in a Q-tree 

self._children.append(new_Q(new)) 

return PARTIAL, True 

# If there are 2 partial elements, we take care of both 

# ends. We also know it will not be possible to align the 

# interval of sets containing v to the right 

else: 

new = [] 

# The second partial element is aligned to the right 

# while, as we want to put it at the end of the 

# interval, it should be aligned to the left 

set_PARTIAL_ALIGNED[1].reverse() 

# 1/3 

# Left partial subtree 

subtree = set_PARTIAL_ALIGNED[0] 

new.extend(subtree.simplify(v, right = ALIGNED)) 

# 2/3 

# Center (Full elements, in a P-tree, as they can be 

# permuted) 

if n_FULL > 0: 

new.append(new_P(set_FULL)) 

# 3/3 

# Right partial subtree 

subtree = set_PARTIAL_ALIGNED[1] 

new.extend(subtree.simplify(v, left= ALIGNED)) 

# We add all of it, locked in a Q-Tree 

self._children.append(new_Q(new)) 

return PARTIAL, False 

def cardinality(self): 

r""" 

Return the number of orderings allowed by the structure. 

.. SEEALSO:: 

:meth:`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 

""" 

from math import factorial 

n = factorial(self.number_of_children()) 

for c in self._children: 

if isinstance(c,PQ): 

n = n*c.cardinality() 

return n 

def orderings(self): 

r""" 

Iterate over all orderings of the sets allowed by the structure. 

.. SEEALSO:: 

:meth:`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}) 

... 

""" 

from itertools import permutations, product 

for p in permutations(self._children): 

for o in product(*[x.orderings() if isinstance(x,PQ) else [x] 

for x in p]): 

yield o 

class Q(PQ): 

r""" 

A Q-Tree is a PQ-Tree whose children are ordered up to reversal 

For more information, see the documentation of :mod:`sage.graphs.pq_trees`. 

""" 

def set_contiguous(self, v): 

r""" 

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 

""" 

################################################################# 

# Guidelines : # 

# # 

# As the tree is a Q-Tree, we can but reverse the order in # 

# which the elements appear. It means that we can but check # 

# the elements containing v are already contiguous (even # 

# though we have to take special care of partial elements -- # 

# the endpoints of the interval), and answer accordingly # 

# (partial, full, empty, aligned..). We also want to align the # 

# elements containing v to the right if possible. # 

################################################################ 

############################################################### 

# Defining Variables : # 

# # 

# Collecting the information of which children are FULL of v, # 

# which ones are EMPTY, PARTIAL_ALIGNED and PARTIAL_UNALIGNED # 

# # 

# Defining variables for their cardinals, just to make the # 

# code slightly more readable :-) # 

############################################################### 

seq = [set_contiguous(x, v) for x in self] 

self.flatten() 

seq = [set_contiguous(x, v) for x in self] 

f_seq = dict(zip(self, seq)) 

set_FULL = [] 

set_EMPTY = [] 

set_PARTIAL_ALIGNED = [] 

set_PARTIAL_UNALIGNED = [] 

sorting = { 

(FULL, ALIGNED) : set_FULL, 

(EMPTY, ALIGNED) : set_EMPTY, 

(PARTIAL, ALIGNED) : set_PARTIAL_ALIGNED, 

(PARTIAL, UNALIGNED) : set_PARTIAL_UNALIGNED 

} 

for i in self: 

sorting[f_seq[i]].append(i) 

n_FULL = len(set_FULL) 

n_EMPTY = len(set_EMPTY) 

n_PARTIAL_ALIGNED = len(set_PARTIAL_ALIGNED) 

n_PARTIAL_UNALIGNED = len(set_PARTIAL_UNALIGNED) 

counts = {x: len(y) for x, y in iteritems(sorting)} 

################################################################### 

# # 

# Picking the good ordering for the children : # 

# # 

# # 

# There is a possibility of aligning to the right iif # 

# the vector can assume the form (as a regular expression) : # 

# # 

# (EMPTY *) PARTIAL (FULL *) Of course, each of these three # 

# members could be empty # 

# # 

# Hence, in the following case we reverse the vector : # 

# # 

# * if the last element is empty (as we checked the whole # 

# vector is not empty # 

# # 

# * if the last element is partial, aligned, and all the # 

# others are full # 

################################################################### 

if (f_seq[self._children[-1]] == (EMPTY, ALIGNED) or 

(f_seq[self._children[-1]] == (PARTIAL, ALIGNED) and n_FULL == self.number_of_children() - 1)): 

# We reverse the order of the elements in the SET only. Which means that they are still aligned to the right ! 

self._children.reverse() 

######################################################### 

# 1/2 # 

# # 

# Several easy cases where we can decide without paying # 

# attention # 

######################################################### 

# Excludes the situation where there is no solution. 

# read next comment for more explanations 

if (n_PARTIAL_ALIGNED > 2 or 

(n_PARTIAL_UNALIGNED >= 1 and n_EMPTY != self.number_of_children() -1)): 

raise ValueError(impossible_msg) 

# From now on, there are at most two pq-trees which are partially filled 

# If there is one which is not aligned to the right, all the others are empty 

# First trivial case, no checking neded 

elif n_FULL == self.number_of_children(): 

return FULL, True 

# Second trivial case, no checking needed 

elif n_EMPTY == self.number_of_children(): 

return EMPTY, True 

# Third trivial case, no checking needed 

elif n_PARTIAL_UNALIGNED == 1: 

return (PARTIAL, UNALIGNED) 

# If there is just one partial element 

# and all the others are empty, we just reorder 

# the set to put it at the right end 

elif (n_PARTIAL_ALIGNED == 1 and 

n_EMPTY == self.number_of_children()-1): 

if set_PARTIAL_ALIGNED[0] == self._children[-1]: 

return (PARTIAL, ALIGNED) 

else: 

return (PARTIAL, UNALIGNED) 

############################################################## 

# 2/2 # 

# # 

# We iteratively consider all the children, and check # 

# that the elements containing v are indeed # 

# located on an interval. # 

# # 

# We are also interested in knowing whether this interval is # 

# aligned to the right # 

# # 

# Because of the previous tests, we can assume there are at # 

# most two partial pq-trees and all of them are aligned to # 

# their right # 

############################################################## 

else: 

new_children = [] 

# Two variables to remember where we are 

# according to the interval 

seen_nonempty = False 

seen_right_end = False 

for i in self: 

type, aligned = f_seq[i] 

# We met an empty element 

if type == EMPTY: 

# 2 possibilities : 

# 

# * we have NOT met a non-empty element before 

# and it just means we are looking at the 

# leading empty elements 

# 

# * we have met a non-empty element before and it 

# means we will never met another non-empty 

# element again => we have seen the right end 

# of the interval 

new_children.append(i) 

if seen_nonempty: 

seen_right_end = True 

# We met a non-empty element 

else: 

if seen_right_end: 

raise ValueError(impossible_msg) 

if type == PARTIAL: 

# if we see an ALIGNED partial tree after 

# having seen a nonempty element then the 

# partial tree must be aligned to the left and 

# so we have seen the right end 

if seen_nonempty and aligned: 

i.reverse() 

seen_right_end = True 

# right partial subtree 

subtree = i 

new_children.extend(subtree.simplify(v, left = True)) 

# If we see an UNALIGNED partial element after 

# having met a nonempty element, there is no 

# solution to the alignment problem 

elif seen_nonempty and not aligned: 

raise ValueError(impossible_msg) 

# If we see an unaligned element but no non-empty 

# element since the beginning, we are witnessing both the 

# left and right end 

elif not seen_nonempty and not aligned: 

raise ValueError("Bon, ben ca arrive O_o") 

seen_right_end = True 

elif not seen_nonempty and aligned: 

# left partial subtree 

subtree = i 

new_children.extend(subtree.simplify(v, right = True)) 

else: 

new_children.append(i) 

seen_nonempty = True 

# Setting the updated sequence of children 

self._children = new_children 

# Whether we achieved an alignment to the right is the 

# complement of whether we have seen the right end 

return (PARTIAL, not seen_right_end) 

def cardinality(self): 

r""" 

Return the number of orderings allowed by the structure. 

.. SEEALSO:: 

:meth:`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 

""" 

n = 1 

for c in self._children: 

if isinstance(c,PQ): 

n = n*c.cardinality() 

return n if (self.number_of_children() == 1) else 2*n 

def orderings(self): 

r""" 

Iterates over all orderings of the sets allowed by the structure 

.. SEEALSO:: 

:meth:`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}) 

""" 

if len(self._children) == 1: 

c = self._children[0] 

for o in (c.orderings() if isinstance(c,PQ) else [o]): 

yield o 

else: 

from itertools import product 

for o in product(*[x.orderings() if isinstance(x,PQ) else [x] 

for x in self._children]): 

yield o 

yield o[::-1]