[hltdi-l3] push by onlysk...@gmail.com - L3Lite: progress on constraints needed for groups; see example in lite... on 2014-04-16 06:00 GMT
0 views
Skip to first unread message
hltd...@googlecode.com
Apr 16, 2014, 2:00:35 AM4/16/14
to hltdi-...@googlegroups.com
Revision: e90acb5b5513
Branch: default
Author: Michael Gasser <gas...@cs.indiana.edu>
Date: Wed Apr 16 06:00:17 2014 UTC
Log: L3Lite: progress on constraints needed for groups; see example in
lite.py
http://code.google.com/p/hltdi-l3/source/detail?r=e90acb5b5513
Modified:
/l3lite/constraint.py
/l3lite/variable.py
/lite.py
=======================================
--- /l3lite/constraint.py Fri Apr 4 06:26:55 2014 UTC
+++ /l3lite/constraint.py Wed Apr 16 06:00:17 2014 UTC
@@ -30,6 +30,8 @@
# -- Fixed cant_precede() so it works with IVars (determined and not).
# 2014.04.03
# -- Created ComplexSetConvexity
+# 2014.04.05
+# -- Created ComplexUnionSelection
from .variable import *
import itertools
@@ -431,8 +433,8 @@
self.name = '{0} <>'.format(self.var)
def fails(self, dstore=None):
- """If the variable's upper does not include all values between
- min and max of lower bound, or if the determined value has gaps,
fail."""
+ """Four ways to fail."""
+ # If the variable is determined and has holes...
if self.var.determined(dstore=dstore, constraint=self) is not
False:
val = self.var.get_value(dstore=dstore)
# There can't be any holes
@@ -440,15 +442,45 @@
val_range = set(range(min(val), max(val)+1))
if val_range - val:
return True
+ lower_card = self.var.get_lower_card(dstore=dstore)
lower = self.var.get_lower(dstore=dstore)
- if not lower:
- return False
upper = self.var.get_upper(dstore=dstore)
- neces_range = set(range(min(lower), max(lower)+1))
- if neces_range - upper:
- # There is some value in necessary range not in upper bound
- return True
- return False
+ if lower:
+ # Necessary range includes all values between the minimum and
the maximum (inclusive)
+ # of the lower bound
+ neces_range = set(range(min(lower), max(lower)+1))
+ if neces_range - upper:
+ # If there's some value in necessary range not in upper
bound...
+ return True
+ # Possible values that are not in necessary range
+ possible = upper - neces_range
+ # If there's a gap separating max necessary and min possible
and too many possible
+ # values would need to be discarded...
+ if possible and neces_range:
+ min_poss = min(possible)
+ max_neces = max(neces_range)
+ if min_poss - max_neces > 1:
+ if len(upper) - len(possible) < lower_card:
+ return True
+ # If there is continuous sequence of integers as long as the lower
cardinality...
+ if lower_card <= 1:
+ return False
+ upper_ordered = list(upper)
+ upper_ordered.sort()
+ last = upper_ordered[0]
+ count = 1
+ for pos in upper_ordered[1:]:
+ if count >= lower_card:
+ return False
+ if pos - last > 1:
+ count = 1
+ last = pos
+ else:
+ count += 1
+ last = pos
+ if count >= lower_card:
+ return False
+ return True
def is_entailed(self, dstore=None):
"""If the variable is determined, or if the lower bound is convex,
@@ -584,8 +616,7 @@
def __init__(self, variables, problem=None, propagate=True,
weight=1):
- Constraint.__init__(self, variables, problem=problem,
propagate=propagate,
- weight=weight)
+ Constraint.__init__(self, variables, problem=problem,
weight=weight)
self.name = '{0} c= {1} U {2}'.format(self.variables[0],
self.variables[1], self.variables[2])
def fails(self, dstore=None):
@@ -612,7 +643,7 @@
return True
return False
- def infer(self, dstore=None, verbosity=0, tracevar=None):
+ def infer(self, dstore=None, verbosity=0, tracevar=[]):
changed = set()
# S1 must be a subset of the union of the upper bounds of S2 and S3
s1 = self.variables[0]
@@ -1294,7 +1325,8 @@
sel_infer = Selection.infer(self, dstore=dstore,
verbosity=verbosity, tracevar=tracevar)
if sel_infer:
return sel_infer
-
+ ## Some variable(s) determined
+ # Selection variable
if selvar.determined(dstore=dstore, verbosity=verbosity,
constraint=self) is not False:
# If the selection var is determined, check whether the
indexed sequence vars
# are also
@@ -1375,7 +1407,7 @@
changed.add(mainvar)
return state, changed
- ## OK, so selvar is not determined; try changing mainvar if it's
not determined
+ # Main variable determined
if mainvar.determined(dstore=dstore, verbosity=verbosity,
constraint=self) is False:
# The main variable must be a subset of the union of the upper
bounds of all
# sequence variables indexed by the upper bound of the
selection variable.
@@ -1397,6 +1429,7 @@
constraint=(verbosity>1 or mainvar
in tracevar) and self):
changed.add(mainvar)
return state, changed
+ ## Neither selection variable nor main variable determined
# If the lower bound of some seqvar is not a subset of mainvar's
upperbound,
# then exclude its index from selection var (remove it from the
selection var's
# upper bound)
@@ -1488,10 +1521,66 @@
# self.selvar = selvar
# self.seqvars = seqvars
-class ComplexUnionSelection(Selection):
+class ComplexUnionSelection(Constraint):
"""Each value of selection variable (potentially) selects a union
selection constraint, with each of the
selection variables (selvars) as the selection variable for one of
these."""
+ def __init__(self, selvar=None, mainvars=None, seqvars=None,
selvars=None,
+ problem=None, weight=1):
+ Constraint.__init__(self, [selvar] + selvars + seqvars + mainvars,
+ problem=problem, weight=weight)
+ self.selvar = selvar
+ self.selvars = selvars
+ self.seqvars = seqvars
+ self.mainvars = mainvars
+ self.name = '{} = U{} [{}]
[[{}]]'.format(Selection.format_seq(mainvars),
+
Selection.format_seq(seqvars),
+
Selection.format_seq(selvars),
+ selvar)
+ self.constraints = []
+ for sel, main in zip(selvars, mainvars):
+ self.constraints.append(UnionSelection(main, sel, seqvars,
weight=1, maxset=None))
+
+ def fails(self, dstore=None):
+ """Fail if any of the UnionSelection constraints over the selvars
and mainvars indexed by the
+ lower bound of selvar fail."""
+ for index in self.selvar.get_lower(dstore=dstore):
+ constraint = self.constraints[index]
+ if constraint.fails(dstore=dstore):
+ return True
+ return False
+
+ def is_entailed(self, dstore=None):
+ """Is entailed if all of the constraints indexed by the upper
bound of selvar are entailed."""
+ for index in self.selvar.get_upper(dstore=dstore):
+ constraint = self.constraints[index]
+ if not constraint.is_entailed(dstore=dstore):
+ return False
+ return True
+
+ def infer(self, dstore=None, verbosity=0, tracevar=[]):
+ """Run infer() on all constraints indexed in the lower bound of
selvar,
+ and remove indices from the upper bound of selvar if the indexed
constraint
+ fails."""
+ selvar = self.selvar
+ selupper = selvar.get_upper(dstore=dstore)
+ sellower = selvar.get_lower(dstore=dstore)
+ for index, constraint in enumerate(self.constraints):
+ if index in sellower:
+ state, changed = constraint.infer(dstore=dstore)
+ # If any variable changed as a result this, return it
+ if changed:
+ return state, changed
+ elif index in selupper:
+ # A constraint indexed by a value in the upper bound of
selvar failed
+ if constraint.fails(dstore=dstore):
+ # Try to remove this index from the upper bound of
selvar
+ if selvar.discard_upper(index, dstore=dstore,
+ constraint=(verbosity>1 or
selvar in tracevar) and self):
+ return Constraint.sleeping, {selvar}
+
+ return Constraint.sleeping, set()
+
class ComplexSetConvexity(Constraint):
"""Each value of selection variable (potentially) selects a set
convexity constraint over one of
the seqvars."""
@@ -1523,13 +1612,25 @@
return True
def infer(self, dstore=None, verbosity=0, tracevar=[]):
- # Try infer() over each of the constraints indexed in the lower
bound of selvar
- for index in self.selvar.get_upper(dstore=dstore):
- constraint = self.constraints[index]
- state, changed = constraint.infer(dstore=dstore)
- # If any variable changed as a result this
- if changed:
- return state, changed
+ """Run infer() on all constraints indexed in the lower bound of
selvar,
+ and remove indices from the upper bound of selvar if the indexed
constraint
+ fails."""
+ selvar = self.selvar
+ selupper = selvar.get_upper(dstore=dstore)
+ sellower = selvar.get_lower(dstore=dstore)
+ for index, constraint in enumerate(self.constraints):
+ if index in sellower:
+ state, changed = constraint.infer(dstore=dstore)
+ # If any variable changed as a result this
+ if changed:
+ return state, changed
+ elif index in selupper:
+ if constraint.fails(dstore=dstore):
+ # Try to remove this index from the upper bound of
selvar
+ if selvar.discard_upper(index, dstore=dstore,
+ constraint=(verbosity>1 or
selvar in tracevar) and self):
+ return Constraint.sleeping, {selvar}
+
return Constraint.sleeping, set()
class IntersectionSelection(Selection):
@@ -2135,11 +2236,10 @@
"""Abstract class for
constraints that are equivalent to a conjunction of primitive or
derived constraints."""
- def __init__(self, variables, problem=None, propagate=True, weight=1):
+ def __init__(self, variables, problem=None, weight=1):
self.variables = variables
self.problem = problem
self.weight = weight
- self.propagate = propagate
self.init_constraints()
def init_constraints(self):
@@ -2167,7 +2267,7 @@
def init_constraints(self):
sv3 = EMPTY
- self.constraints = [SubsetUnion(self.variables + [sv3],
problem=self.problem, propagate=self.propagate,
+ self.constraints = [SubsetUnion(self.variables + [sv3],
problem=self.problem,
weight=self.weight)]
class Equality(DerivedConstraint):
@@ -2191,8 +2291,12 @@
def init_constraints(self):
sv3 = EMPTY
self.constraints = []
- for i, sv1 in enumerate(self.variables):
+ for i, sv1 in enumerate(self.variables[:-1]):
+ if sv1 == EMPTY:
+ continue
for sv2 in self.variables[i+1:]:
+ if sv2 == EMPTY:
+ continue
self.constraints.append(SupersetIntersection([sv3, sv1,
sv2], problem=self.problem,
weight=self.weight))
=======================================
--- /l3lite/variable.py Fri Apr 4 06:26:55 2014 UTC
+++ /l3lite/variable.py Wed Apr 16 06:00:17 2014 UTC
@@ -359,14 +359,20 @@
value = value if isinstance(value, set) else {value}
if value & upper:
new_upper = upper - value
+ new_upper_card = len(new_upper)
lower = self.get_lower(dstore=dstore)
- if len(new_upper) < len(lower) and constraint:
+ if new_upper_card < len(lower) and constraint:
s = 'Warning: attempting to discard {} from upper bound {}
of {}, making it smaller than lower bound {}'
print(s.format(value, upper, self, lower))
+ lower_card = self.get_lower_card(dstore=dstore)
+ if new_upper_card < lower_card:
+ s = 'Warning: attempting to discard {} from upper bound {}
of {}, making cardinality smaller than {}'
+ print(s.format(value, upper, self, lower_card))
# If value and upper overlap
if constraint:
print(' {} discarding {} from {}'.format(constraint,
value, self))
self.set_upper(new_upper, dstore=dstore)
+ self.set_upper_card(new_upper_card, dstore=dstore)
return True
return False
@@ -611,3 +617,5 @@
def __str__(self):
return repr(self.value)
+# Constant variables, determined in all DStores
+EMPTY = Determined("empty", set())
=======================================
--- /lite.py Fri Apr 4 06:26:55 2014 UTC
+++ /lite.py Wed Apr 16 06:00:17 2014 UTC
@@ -109,7 +109,7 @@
e, s = l3lite.Language("English", 'eng'),
l3lite.Language("español", 'spa')
return u, e, s
-def gtest():
+def t1():
# broke the window
g0_nodes = {0, 1, 2}
# the boy
@@ -125,12 +125,12 @@
# the boy broke the window .
w = {0, 1, 2, 3, 4, 5}
g = {0, 1, 2, 3, 4, 5}
- wvars = [l3lite.IVar('the0', {1, 3, 5, 9}), # {3}
- l3lite.IVar('boy', {4}),
- l3lite.IVar('broke', {0, 7, 11}), # {0, 7}
- l3lite.IVar('the3', {1, 3, 5, 9}), # {1, 5}
- l3lite.IVar('window', {2, 6, 10}), # {2, 6}
- l3lite.IVar('.', {8})]
+ w2gnodes = [l3lite.IVar('the0', {1, 3, 5, 9}), # {3}
+ l3lite.DetIVar('boy', 4),
+ l3lite.IVar('broke', {0, 7, 11}), # {0, 7}
+ l3lite.IVar('the3', {1, 3, 5, 9}), # {1, 5}
+ l3lite.IVar('window', {2, 6, 10}), # {2, 6}
+ l3lite.DetIVar('.', 8)]
groups = l3lite.Var('groups', set(), g, 2, 6)
gdetvars = [l3lite.Determined('g0', {0, 1, 2}),
l3lite.Determined('g1', {3, 4}),
@@ -143,7 +143,7 @@
# Union of all group nodes used
gnodeU = l3lite.Var('gnodeU', set(),
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}, 6, 6)
- w_usel = l3lite.UnionSelection(gnodeU, nodes, wvars)
+ w_usel = l3lite.UnionSelection(gnodeU, nodes, w2gnodes)
## Union selection on the gnodes of all groups
g_usel = l3lite.UnionSelection(gnodeU, groups, gdetvars)
## Position constraints
@@ -207,28 +207,282 @@
### setcon5 = l3lite.SetConvexity(g5snode)
setconv = l3lite.ComplexSetConvexity(groups, [g0snode, g1snode,
g2snode,
g3snode, g4snode,
g5snode])
-### return nodes, groups, wvars, gdetvars, usel
- ## Union selection on individual groups: snodes -> gnodes
- ## The union of possible gnodes associated with the snodes of a group
is a *superset*
- ## of the known gnodes for that group
- s2g_sup0 = l3lite.Var('s2g_sup0', {0, 1, 2}, {0, 1, 2, 3, 4, 5, 6, 7,
8, 9, 10, 11})
- s2g_sup1 = l3lite.Var('s2g_sup1', {3, 4}, {0, 1, 2, 3, 4, 5, 6, 7, 8,
9, 10, 11})
- s2g_sup2 = l3lite.Var('s2g_sup2', {5, 6}, {0, 1, 2, 3, 4, 5, 6, 7, 8,
9, 10, 11})
-# s2g_sup5 =
- s2gU0 = l3lite.UnionSelection(s2g_sup0, g0snode, wvars)
- s2gU1 = l3lite.UnionSelection(s2g_sup1, g1snode, wvars)
- s2gU2 = l3lite.UnionSelection(s2g_sup2, g2snode, wvars)
-# s2gU5 = l3lite.UnionSelection(gdetvars[5], g5snode, wvars)
- return w_usel, g_usel, precsel, gp_usel, setconv, s2gU0, s2gU1 #, s2gU2
-# setcon0, setcon1, setcon2, \
-# gsnodeU0, gsnodeU1, gsnodeU2, s2gU0, s2gU1, s2gU2
-#, s2gU5, setcon5, gsnodeU5
+ ## ComplexUnionSelection
+ ## mainvars: [{0, 1, 2}, {3, 4}, ...]
+ ## selvars: [g0snode, g1snode, ...]
+ ## seqvars: w2gnodes
+ ## selvar: groups
+ # mainvars
+# gnodes0 = l3lite.Determined('gnodes0', {0, 1, 2})
+# gnodes1 = l3lite.Determined('gnodes1', {3, 4})
+# gnodes2 = l3lite.Determined('gnodes2', {5, 6})
+# gnodes3 = l3lite.DetIVar('gnodes3', 7)
+# gnodes4 = l3lite.DetIVar('gnodes4', 8)
+# gnodes5 = l3lite.Determined('gnodes5', {9, 10, 11})
+ complexU = l3lite.ComplexUnionSelection(selvar=groups,
+ selvars=[g0snode, g1snode,
g2snode, g3snode,
+ g4snode, g5snode],
+ seqvars=w2gnodes,
+ mainvars=gdetvars)
+ return w_usel, g_usel, precsel, gp_usel, setconv, complexU
+
+def t2():
+ constraints = []
+ ## Groups
+ # 0: read(0) %sbd(1) the(2) riot(3) act(4)
+ # 1: read(5) %sth(6)
+ # 2: the(7) boy(8)
+ # 3: us(9)
+ # 4: the(10) act(11)
+ # 5: the(12) riot(13)
+ # 6: .(14)
+ groups = l3lite.Var('groups', set(), {0, 1, 2, 3, 4, 5, 6}, 2, 7)
+ ## Group node indices
+ gdetvars = [l3lite.Determined('g0', {0, 1, 2, 3, 4}), # 1 is
abstract
+ l3lite.Determined('g1', {5, 6}), # 6 is
abstract
+ l3lite.Determined('g2', {7, 8}),
+ l3lite.Determined('g3', {9}),
+ l3lite.Determined('g4', {10, 11}),
+ l3lite.Determined('g5', {12, 13}),
+ l3lite.Determined('g6', {14})]
+ ## Concrete group node indices
+ gc_detvars = [l3lite.Determined('g0', {0, 2, 3, 4}), # 1 is abstract
+ l3lite.Determined('g1', {5}), # 6 is abstract
+ l3lite.Determined('g2', {7, 8}),
+ l3lite.Determined('g3', {9}),
+ l3lite.Determined('g4', {10, 11}),
+ l3lite.Determined('g5', {12, 13}),
+ l3lite.Determined('g6', {14})]
+ ## Words
+ sentence = ['the', 'boy', 'read', 'us', 'the', 'riot', 'act']
+ ## Word positions associated with group nodes (what about unused
gnodes?)
+ gn0w = l3lite.DetIVar('gn0w', 2)
+ gn1w = l3lite.IVar('gn1w', {1, 3}) # abstract
+ gn2w = l3lite.IVar('gn2w', {0, 4})
+ gn3w = l3lite.DetIVar('gn3w', 5)
+ gn4w = l3lite.DetIVar('gn4w', 6)
+ gn5w = l3lite.DetIVar('gn5w', 2)
+ gn6w = l3lite.IVar('gn6w', {5, 6}) # abstract
+ gn7w = l3lite.IVar('gn7w', {0, 4})
+ gn8w = l3lite.DetIVar('gn8w', 1)
+ gn9w = l3lite.DetIVar('gn9w', 3)
+ gn10w = l3lite.IVar('gn10w', {0, 4})
+ gn11w = l3lite.DetIVar('gn11w', 6)
+ gn12w = l3lite.IVar('gn12w', {0, 4})
+ gn13w = l3lite.DetIVar('gn13w', 5)
+ gn14w = l3lite.DetIVar('gn14w', 7)
+ gn_w = [gn0w, gn1w, gn2w, gn3w, gn4w, gn5w, gn6w, gn7w, gn8w, gn9w,
gn10w, gn11w, gn12w, gn13w, gn14w]
+ ## Group nodes associated with words
+ w0gn = l3lite.IVar('w0gn', {2, 7, 10, 12}) # the
+ w1gn = l3lite.Var('w1gn', set(), {1, 8}, 1, 2) # boy
+ w2gn = l3lite.IVar('w2gn', {0, 5}) # read
+ w3gn = l3lite.Var('w3gn', set(), {1, 9}, 1, 2) # us
+ w4gn = l3lite.IVar('w4gn', {2, 7, 10, 12}) # the
+ w5gn = l3lite.Var('w5gn', set(), {3, 6, 13}, 1, 2) # riot
+ w6gn = l3lite.Var('w6gn', set(), {4, 6, 11}, 1, 2) # act
+ w7gn = l3lite.DetIVar('w7gn', 14)
+ w2gnodes = [w0gn, w1gn, w2gn, w3gn, w4gn, w5gn, w6gn, w7gn]
+ ## Concrete group nodes associated with words
+ w0cgn = w0gn
+ w1cgn = l3lite.DetIVar('w1cgn', 8)
+ w2cgn = w2gn
+ w3cgn = l3lite.DetIVar('w3cgn', 9)
+ w4cgn = w4gn
+ w5cgn = l3lite.IVar('w5cgn', {3, 13})
+ w6cgn = l3lite.IVar('w6cgn', {4, 11})
+ w7cgn = w7gn
+ w2cgnodes = [w0cgn, w1cgn, w2cgn, w3cgn, w4cgn, w5cgn, w6cgn, w7cgn]
+ ## w->m Merged concrete group nodes associated with words
+ w1gnm = l3lite.Var('w1gnm', set(), {8}, 0, 1) # boy (merged
with sbd)
+ w3gnm = l3lite.Var('w3gnm', set(), {9}, 0, 1) # us (merged
with sbd)
+ w5gnm = l3lite.Var('w5gnm', set(), {13}, 0, 1) # riot (merged
with sth)
+ w6gnm = l3lite.Var('w6gnm', set(), {11}, 0, 1) # act (merged
with sth)
+ w2gnm_nodes = [l3lite.EMPTY, w1gnm, l3lite.EMPTY, w3gnm, l3lite.EMPTY,
w5gnm, w6gnm, l3lite.EMPTY]
+ ## w->a Abstract group nodes associated with words
+ w1ga = l3lite.Var('w1ga', set(), {1}, 0, 1)
+ w3ga = l3lite.Var('w3ga', set(), {1}, 0, 1)
+ w5ga = l3lite.Var('w5ga', set(), {6}, 0, 1)
+ w6ga = l3lite.Var('w6ga', set(), {6}, 0, 1)
+ w2ga_nodes = [l3lite.EMPTY, w1ga, l3lite.EMPTY, w3ga, l3lite.EMPTY,
w5ga, w6ga, l3lite.EMPTY]
+ ## All word nodes
+ nodes = l3lite.Determined('nodes', {0, 1, 2, 3, 4, 5, 6, 7})
+ ## Union selection on the gnodes of all words
+ # Words 1 (boy), 3 (us), 5 (riot), 6 (act) can have abstract nodes
+ constraints.extend(l3lite.Union([w1gn, w1cgn, w1ga]).constraints)
+ constraints.extend(l3lite.Union([w3gn, w3cgn, w3ga]).constraints)
+ constraints.extend(l3lite.Union([w5gn, w5cgn, w5ga]).constraints)
+ constraints.extend(l3lite.Union([w6gn, w6cgn, w6ga]).constraints)
+ # Union of all group nodes used
+ gnodeU = l3lite.Var('gnodeU', set(),
+ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
14}, 7, 9)
+ constraints.append(l3lite.UnionSelection(gnodeU, nodes, w2gnodes))
+ ## Union selection on the gnodes of all groups
+ constraints.append(l3lite.UnionSelection(gnodeU, groups, gdetvars))
+ ## Union selection on the words associated with each group node
+ constraints.append(l3lite.UnionSelection(nodes, gnodeU, gn_w))
+ # Positions of gnodes in each group
+ g0snode = l3lite.Var('g0snode', set(), {0, 1, 2, 3, 4, 5, 6}, 5, 5) #
read sbd the riot act
+ g1snode = l3lite.Var('g1snode', set(), {2, 5, 6}, 2, 2) #
read sth
+ g2snode = l3lite.Var('g2snode', set(), {0, 1, 4}, 2, 2) #
the boy
+ g3snode = l3lite.DetIVar('g3snode', 3) #
us
+ g4snode = l3lite.Var('g4snode', set(), {0, 4, 6}, 2, 2) #
the act
+ g5snode = l3lite.Var('g5snode', set(), {0, 4, 5}, 2, 2) #
the riot
+ g6snode = l3lite.DetIVar('g6snode', 7)
# .
+ gsnodes = [g0snode, g1snode, g2snode, g3snode, g4snode, g5snode,
g6snode]
+ # Positions of concrete gnodes in each group
+ g0cw = l3lite.Var('g0cw', set(), {0, 1, 2, 3, 4, 5, 6}, 4, 4)
+ g1cw = l3lite.Determined('g1cw', {2})
+ g2cw = g2snode
+ g3cw = g3snode
+ g4cw = g4snode
+ g5cw = g5snode
+ g6cw = g6snode
+ g_cwords = [g0cw, g1cw, g2cw, g3cw, g4cw, g5cw, g6cw]
+ ## Abstract group node mergers (empty set possible if not selected)
+ # Merge %sbd with boy or us
+ gan1m = l3lite.Var('gan1m', set(), {8, 9}, 0, 1)
+ # Merge %sth with riot or act
+ gan6m = l3lite.Var('gan6m', set(), {11, 13}, 0, 1)
+ gan_m = [l3lite.EMPTY, gan1m, l3lite.EMPTY, l3lite.EMPTY, l3lite.EMPTY,
+ l3lite.EMPTY, gan6m, l3lite.EMPTY, l3lite.EMPTY, l3lite.EMPTY,
+ l3lite.EMPTY, l3lite.EMPTY, l3lite.EMPTY, l3lite.EMPTY,
l3lite.EMPTY]
+ constraints.extend(l3lite.Inclusion([gan1m, gnodeU]).constraints)
+ constraints.extend(l3lite.Inclusion([gan6m, gnodeU]).constraints)
+ # m-> a; Abstract nodes associated with concrete gnodes
+ gm8ga = l3lite.Var('gm8ga', set(), {1}, 0, 1)
+ gm9ga = l3lite.Var('gm9ga', set(), {1}, 0, 1)
+ gm11ga = l3lite.Var('gm11ga', set(), {6}, 0, 1)
+ gm13ga = l3lite.Var('gm13ga', set(), {6}, 0, 1)
+ gm_ga = [l3lite.EMPTY, l3lite.EMPTY, l3lite.EMPTY, l3lite.EMPTY,
l3lite.EMPTY,
+ l3lite.EMPTY, l3lite.EMPTY, l3lite.EMPTY, gm8ga, gm9ga,
l3lite.EMPTY,
+ gm11ga, l3lite.EMPTY, gm13ga,l3lite.EMPTY]
+ ## a->w Words associated with abstract group nodes
+ ga1w = l3lite.Var('ga1w', set(), {1, 3}, 0, 1)
+ ga6w = l3lite.Var('ga6w', set(), {5, 6}, 0, 1)
+ ga_w = [l3lite.EMPTY, ga1w, l3lite.EMPTY, l3lite.EMPTY, l3lite.EMPTY,
l3lite.EMPTY,
+ ga6w, l3lite.EMPTY, l3lite.EMPTY, l3lite.EMPTY, l3lite.EMPTY,
l3lite.EMPTY,
+ l3lite.EMPTY, l3lite.EMPTY, l3lite.EMPTY]
+ ## m->w Words associated with merged group nodes
+ gnm8w = l3lite.Var('gnm8w', set(), {1}, 0, 1)
+ gnm9w = l3lite.Var('gnm9w', set(), {3}, 0, 1)
+ gnm11w = l3lite.Var('gnm11w', set(), {6}, 0, 1)
+ gnm13w = l3lite.Var('gnm13w', set(), {5}, 0, 1)
+ gnm_w = [l3lite.EMPTY, l3lite.EMPTY, l3lite.EMPTY, l3lite.EMPTY,
l3lite.EMPTY,
+ l3lite.EMPTY, l3lite.EMPTY, l3lite.EMPTY,
+ gnm8w, gnm9w, l3lite.EMPTY, gnm11w, l3lite.EMPTY,
+ gnm13w, l3lite.EMPTY]
+ # Merging means the gnodes have the same sentence position
+ # gn1w = gn8w | gn9w ; gn6w = gn11w | gn13w
+ # Abstract nodes in used groups
+ anodes = l3lite.Var('anodes', set(), {1, 6})
+ constraints.append(l3lite.UnionSelection(anodes, groups,
[l3lite.Determined('g0a', {1}),
+
l3lite.Determined('g1a', {6}),
+
l3lite.EMPTY, l3lite.EMPTY,
+
l3lite.EMPTY, l3lite.EMPTY,
+
l3lite.EMPTY]))
+ # Word nodes that involve a merging of two gnodes
+ mwords = l3lite.Var('mwords', set(), {1, 3, 5, 6}, 0, 2)
+ # Set of all concrete gnodes that are merged with abstract nodes
+ merged_gnodes = l3lite.Var('merged_gnodes', set(), {0, 2, 3, 4, 5, 7,
8, 9, 10, 11, 12, 13, 14},
+ 0, 2)
+ ## UnionSelection constraints relating words, abstract nodes, and
merged gnodes
+ # Set of merged nodes is the union of the merged nodes for the set of
selected abstract nodes
+ constraints.append(l3lite.UnionSelection(merged_gnodes, anodes, gan_m))
+ # Set of merged nodes is the union of the merged nodes of all merge
words
+ constraints.append(l3lite.UnionSelection(merged_gnodes, mwords,
w2gnm_nodes))
+ # Set of abstract nodes is the union of the abstract nodes of all
merge words
+ constraints.append(l3lite.UnionSelection(anodes, mwords, w2ga_nodes))
+ # Set of abstract nodes is the union of the abstract nodes of all
gnodes
+ constraints.append(l3lite.UnionSelection(anodes, merged_gnodes, gm_ga))
+ # Set of merge words is the union of the words associated with all
selected abstract nodes
+ constraints.append(l3lite.UnionSelection(mwords, anodes, ga_w))
+ # Set of merge words is the union of the words associated with all
merge group nodes
+ constraints.append(l3lite.UnionSelection(mwords, merged_gnodes, gnm_w))
+ ## Constraints on merged and abstract nodes
+ # Set of merged nodes must be a subset of all used gnodes
+ constraints.append(l3lite.Inclusion([merged_gnodes,
gnodeU]).constraints[0])
+ # All words must have different abstract nodes
+ constraints.extend(l3lite.Disjoint(w2ga_nodes).constraints)
+ # All concrete nodes must nodes have different abstract nodes
+ constraints.extend(l3lite.Disjoint(gm_ga).constraints)
+ ## Relations between w->cgnode, w->gnode, w->agnode
+ ## Groups merged with groups, including the group itself
+ g0gm = l3lite.Var('g0gm', {0}, {0, 2, 3}, 1, 2)
+ g1gm = l3lite.Var('g1gm', {1}, {1, 4, 5}, 1, 2)
+ g2gm = l3lite.Determined('g2gm', {2})
+ g3gm = l3lite.Determined('g3gm', {3})
+ g4gm = l3lite.Determined('g4gm', {4})
+ g5gm = l3lite.Determined('g5gm', {5})
+ g6gm = l3lite.Determined('g6gm', {6})
+ ## Trees under gnode heads
+ g0tree = l3lite.Var('g0tree', set(), {0, 1, 2, 3, 4, 5, 6}, 5)
+ g1tree = l3lite.Var('g1tree', set(), {0, 1, 2, 3, 4, 5, 6}, 2)
+ g2tree = g2snode
+ g3tree = g3snode
+ g4tree = g4snode
+ g5tree = g5snode
+ g6tree = g6snode
+ gtrees = [g0tree, g1tree, g2snode, g3snode, g4snode, g5snode, g6snode]
+ # g1 tree is the union of g0snode and the tree under whatever group
+ # merges with gnode 1 (sbd)
+ constraints.append(l3lite.UnionSelection(g0tree, g0gm, gtrees))
+ constraints.append(l3lite.UnionSelection(g1tree, g1gm, gtrees))
+ # Relate gnode merger with group merger
+ # If gnode 1 merges with gnode 8, then group 0 merges with group 2;
+ # if gnode 1 merges with gnode 9, then group 0 merges with group 3
+ # Select one or the other
+ # UnionSelection(choice, IVar('chooser', {0, 1}), [choice1, choice2])
+ g0merge_sel = l3lite.IVar('g0m_sel', {0, 1, 2})
+ constraints.append(l3lite.UnionSelection(g0gm, g0merge_sel,
[l3lite.Determined('g0g2', {0, 2}),
+
l3lite.Determined('g0g3', {0, 3}),
+
l3lite.Determined('g0_', {0})]))
+ constraints.append(l3lite.UnionSelection(gan1m, g0merge_sel,
+ [l3lite.Determined('gan1g8',
{8}),
+ l3lite.Determined('gan1g9',
{9}),
+ l3lite.EMPTY]))
+ g1merge_sel = l3lite.IVar('g1m_sel', {0, 1, 2})
+ constraints.append(l3lite.UnionSelection(g1gm, g1merge_sel,
[l3lite.Determined('g1g4', {1, 4}),
+
l3lite.Determined('g1g5', {1, 5}),
+
l3lite.Determined('g1_', {1})]))
+ constraints.append(l3lite.UnionSelection(gan6m, g1merge_sel,
+ [l3lite.Determined('gan6g11',
{11}),
+ l3lite.Determined('gan6g13',
{13}),
+ l3lite.EMPTY]))
+ # Position pair constraints
+ gposcons = l3lite.Var('gposcons', set(),
+ {(0, 1), (1, 2), (2, 3), (3, 4), (0, 2), (1, 3),
(2, 4), (0, 3), (1, 4),
+ (5, 6), (7, 8), (10, 11), (12, 13)})
+ # Union selection on position pair constraints
+ gp0 = l3lite.Determined('gp0', {(0, 1), (1, 2), (2, 3), (3, 4), (0,
2), (1, 3), (2, 4), (0, 3), (1, 4)})
+ gp1 = l3lite.Determined('gp1', {(5, 6)})
+ gp2 = l3lite.Determined('gp2', {(7, 8)})
+ gp3 = l3lite.Determined('gp3', set())
+ gp4 = l3lite.Determined('gp4', {(10, 11)})
+ gp5 = l3lite.Determined('gp5', {(12, 13)})
+ gp6 = l3lite.Determined('gp6', set())
+ gpos = [gp0, gp1, gp2, gp3, gp4, gp5, gp6]
+ constraints.append(l3lite.PrecedenceSelection(gposcons,
+ [gn0w, gn1w, gn2w, gn3w,
gn4w, gn5w,
+ gn6w, gn7w, gn8w, gn9w,
gn10w, gn11w, gn12w, gn13w, gn14w]))
+ # Union selection on position pair constraints
+ constraints.append(l3lite.UnionSelection(gposcons, groups, gpos))
+ # Complex union selection on positions of all concrete nodes in each
selected group
+ constraints.append(l3lite.ComplexUnionSelection(selvar=groups,
+ selvars=g_cwords,
+ seqvars=w2cgnodes,
+ mainvars=gc_detvars))
+ # Complex set convexity
+ constraints.append(l3lite.ComplexSetConvexity(groups, gtrees))
+ return constraints
def run_constraints(constraints, times=10):
for t in range(times):
print("\nITERATION {}".format(t))
for c in constraints:
state, changed = c.run()
+ if state == 0:
+ print('FAILED: constraint {}'.format(c))
+ return
if changed:
print("Running {}".format(c))
print(" Changed:
{}".format(list(changed)[0].pretty_string()))
Branch: default
Author: Michael Gasser <gas...@cs.indiana.edu>
Date: Wed Apr 16 06:00:17 2014 UTC
Log: L3Lite: progress on constraints needed for groups; see example in
lite.py
http://code.google.com/p/hltdi-l3/source/detail?r=e90acb5b5513
Modified:
/l3lite/constraint.py
/l3lite/variable.py
/lite.py
=======================================
--- /l3lite/constraint.py Fri Apr 4 06:26:55 2014 UTC
+++ /l3lite/constraint.py Wed Apr 16 06:00:17 2014 UTC
@@ -30,6 +30,8 @@
# -- Fixed cant_precede() so it works with IVars (determined and not).
# 2014.04.03
# -- Created ComplexSetConvexity
+# 2014.04.05
+# -- Created ComplexUnionSelection
from .variable import *
import itertools
@@ -431,8 +433,8 @@
self.name = '{0} <>'.format(self.var)
def fails(self, dstore=None):
- """If the variable's upper does not include all values between
- min and max of lower bound, or if the determined value has gaps,
fail."""
+ """Four ways to fail."""
+ # If the variable is determined and has holes...
if self.var.determined(dstore=dstore, constraint=self) is not
False:
val = self.var.get_value(dstore=dstore)
# There can't be any holes
@@ -440,15 +442,45 @@
val_range = set(range(min(val), max(val)+1))
if val_range - val:
return True
+ lower_card = self.var.get_lower_card(dstore=dstore)
lower = self.var.get_lower(dstore=dstore)
- if not lower:
- return False
upper = self.var.get_upper(dstore=dstore)
- neces_range = set(range(min(lower), max(lower)+1))
- if neces_range - upper:
- # There is some value in necessary range not in upper bound
- return True
- return False
+ if lower:
+ # Necessary range includes all values between the minimum and
the maximum (inclusive)
+ # of the lower bound
+ neces_range = set(range(min(lower), max(lower)+1))
+ if neces_range - upper:
+ # If there's some value in necessary range not in upper
bound...
+ return True
+ # Possible values that are not in necessary range
+ possible = upper - neces_range
+ # If there's a gap separating max necessary and min possible
and too many possible
+ # values would need to be discarded...
+ if possible and neces_range:
+ min_poss = min(possible)
+ max_neces = max(neces_range)
+ if min_poss - max_neces > 1:
+ if len(upper) - len(possible) < lower_card:
+ return True
+ # If there is continuous sequence of integers as long as the lower
cardinality...
+ if lower_card <= 1:
+ return False
+ upper_ordered = list(upper)
+ upper_ordered.sort()
+ last = upper_ordered[0]
+ count = 1
+ for pos in upper_ordered[1:]:
+ if count >= lower_card:
+ return False
+ if pos - last > 1:
+ count = 1
+ last = pos
+ else:
+ count += 1
+ last = pos
+ if count >= lower_card:
+ return False
+ return True
def is_entailed(self, dstore=None):
"""If the variable is determined, or if the lower bound is convex,
@@ -584,8 +616,7 @@
def __init__(self, variables, problem=None, propagate=True,
weight=1):
- Constraint.__init__(self, variables, problem=problem,
propagate=propagate,
- weight=weight)
+ Constraint.__init__(self, variables, problem=problem,
weight=weight)
self.name = '{0} c= {1} U {2}'.format(self.variables[0],
self.variables[1], self.variables[2])
def fails(self, dstore=None):
@@ -612,7 +643,7 @@
return True
return False
- def infer(self, dstore=None, verbosity=0, tracevar=None):
+ def infer(self, dstore=None, verbosity=0, tracevar=[]):
changed = set()
# S1 must be a subset of the union of the upper bounds of S2 and S3
s1 = self.variables[0]
@@ -1294,7 +1325,8 @@
sel_infer = Selection.infer(self, dstore=dstore,
verbosity=verbosity, tracevar=tracevar)
if sel_infer:
return sel_infer
-
+ ## Some variable(s) determined
+ # Selection variable
if selvar.determined(dstore=dstore, verbosity=verbosity,
constraint=self) is not False:
# If the selection var is determined, check whether the
indexed sequence vars
# are also
@@ -1375,7 +1407,7 @@
changed.add(mainvar)
return state, changed
- ## OK, so selvar is not determined; try changing mainvar if it's
not determined
+ # Main variable determined
if mainvar.determined(dstore=dstore, verbosity=verbosity,
constraint=self) is False:
# The main variable must be a subset of the union of the upper
bounds of all
# sequence variables indexed by the upper bound of the
selection variable.
@@ -1397,6 +1429,7 @@
constraint=(verbosity>1 or mainvar
in tracevar) and self):
changed.add(mainvar)
return state, changed
+ ## Neither selection variable nor main variable determined
# If the lower bound of some seqvar is not a subset of mainvar's
upperbound,
# then exclude its index from selection var (remove it from the
selection var's
# upper bound)
@@ -1488,10 +1521,66 @@
# self.selvar = selvar
# self.seqvars = seqvars
-class ComplexUnionSelection(Selection):
+class ComplexUnionSelection(Constraint):
"""Each value of selection variable (potentially) selects a union
selection constraint, with each of the
selection variables (selvars) as the selection variable for one of
these."""
+ def __init__(self, selvar=None, mainvars=None, seqvars=None,
selvars=None,
+ problem=None, weight=1):
+ Constraint.__init__(self, [selvar] + selvars + seqvars + mainvars,
+ problem=problem, weight=weight)
+ self.selvar = selvar
+ self.selvars = selvars
+ self.seqvars = seqvars
+ self.mainvars = mainvars
+ self.name = '{} = U{} [{}]
[[{}]]'.format(Selection.format_seq(mainvars),
+
Selection.format_seq(seqvars),
+
Selection.format_seq(selvars),
+ selvar)
+ self.constraints = []
+ for sel, main in zip(selvars, mainvars):
+ self.constraints.append(UnionSelection(main, sel, seqvars,
weight=1, maxset=None))
+
+ def fails(self, dstore=None):
+ """Fail if any of the UnionSelection constraints over the selvars
and mainvars indexed by the
+ lower bound of selvar fail."""
+ for index in self.selvar.get_lower(dstore=dstore):
+ constraint = self.constraints[index]
+ if constraint.fails(dstore=dstore):
+ return True
+ return False
+
+ def is_entailed(self, dstore=None):
+ """Is entailed if all of the constraints indexed by the upper
bound of selvar are entailed."""
+ for index in self.selvar.get_upper(dstore=dstore):
+ constraint = self.constraints[index]
+ if not constraint.is_entailed(dstore=dstore):
+ return False
+ return True
+
+ def infer(self, dstore=None, verbosity=0, tracevar=[]):
+ """Run infer() on all constraints indexed in the lower bound of
selvar,
+ and remove indices from the upper bound of selvar if the indexed
constraint
+ fails."""
+ selvar = self.selvar
+ selupper = selvar.get_upper(dstore=dstore)
+ sellower = selvar.get_lower(dstore=dstore)
+ for index, constraint in enumerate(self.constraints):
+ if index in sellower:
+ state, changed = constraint.infer(dstore=dstore)
+ # If any variable changed as a result this, return it
+ if changed:
+ return state, changed
+ elif index in selupper:
+ # A constraint indexed by a value in the upper bound of
selvar failed
+ if constraint.fails(dstore=dstore):
+ # Try to remove this index from the upper bound of
selvar
+ if selvar.discard_upper(index, dstore=dstore,
+ constraint=(verbosity>1 or
selvar in tracevar) and self):
+ return Constraint.sleeping, {selvar}
+
+ return Constraint.sleeping, set()
+
class ComplexSetConvexity(Constraint):
"""Each value of selection variable (potentially) selects a set
convexity constraint over one of
the seqvars."""
@@ -1523,13 +1612,25 @@
return True
def infer(self, dstore=None, verbosity=0, tracevar=[]):
- # Try infer() over each of the constraints indexed in the lower
bound of selvar
- for index in self.selvar.get_upper(dstore=dstore):
- constraint = self.constraints[index]
- state, changed = constraint.infer(dstore=dstore)
- # If any variable changed as a result this
- if changed:
- return state, changed
+ """Run infer() on all constraints indexed in the lower bound of
selvar,
+ and remove indices from the upper bound of selvar if the indexed
constraint
+ fails."""
+ selvar = self.selvar
+ selupper = selvar.get_upper(dstore=dstore)
+ sellower = selvar.get_lower(dstore=dstore)
+ for index, constraint in enumerate(self.constraints):
+ if index in sellower:
+ state, changed = constraint.infer(dstore=dstore)
+ # If any variable changed as a result this
+ if changed:
+ return state, changed
+ elif index in selupper:
+ if constraint.fails(dstore=dstore):
+ # Try to remove this index from the upper bound of
selvar
+ if selvar.discard_upper(index, dstore=dstore,
+ constraint=(verbosity>1 or
selvar in tracevar) and self):
+ return Constraint.sleeping, {selvar}
+
return Constraint.sleeping, set()
class IntersectionSelection(Selection):
@@ -2135,11 +2236,10 @@
"""Abstract class for
constraints that are equivalent to a conjunction of primitive or
derived constraints."""
- def __init__(self, variables, problem=None, propagate=True, weight=1):
+ def __init__(self, variables, problem=None, weight=1):
self.variables = variables
self.problem = problem
self.weight = weight
- self.propagate = propagate
self.init_constraints()
def init_constraints(self):
@@ -2167,7 +2267,7 @@
def init_constraints(self):
sv3 = EMPTY
- self.constraints = [SubsetUnion(self.variables + [sv3],
problem=self.problem, propagate=self.propagate,
+ self.constraints = [SubsetUnion(self.variables + [sv3],
problem=self.problem,
weight=self.weight)]
class Equality(DerivedConstraint):
@@ -2191,8 +2291,12 @@
def init_constraints(self):
sv3 = EMPTY
self.constraints = []
- for i, sv1 in enumerate(self.variables):
+ for i, sv1 in enumerate(self.variables[:-1]):
+ if sv1 == EMPTY:
+ continue
for sv2 in self.variables[i+1:]:
+ if sv2 == EMPTY:
+ continue
self.constraints.append(SupersetIntersection([sv3, sv1,
sv2], problem=self.problem,
weight=self.weight))
=======================================
--- /l3lite/variable.py Fri Apr 4 06:26:55 2014 UTC
+++ /l3lite/variable.py Wed Apr 16 06:00:17 2014 UTC
@@ -359,14 +359,20 @@
value = value if isinstance(value, set) else {value}
if value & upper:
new_upper = upper - value
+ new_upper_card = len(new_upper)
lower = self.get_lower(dstore=dstore)
- if len(new_upper) < len(lower) and constraint:
+ if new_upper_card < len(lower) and constraint:
s = 'Warning: attempting to discard {} from upper bound {}
of {}, making it smaller than lower bound {}'
print(s.format(value, upper, self, lower))
+ lower_card = self.get_lower_card(dstore=dstore)
+ if new_upper_card < lower_card:
+ s = 'Warning: attempting to discard {} from upper bound {}
of {}, making cardinality smaller than {}'
+ print(s.format(value, upper, self, lower_card))
# If value and upper overlap
if constraint:
print(' {} discarding {} from {}'.format(constraint,
value, self))
self.set_upper(new_upper, dstore=dstore)
+ self.set_upper_card(new_upper_card, dstore=dstore)
return True
return False
@@ -611,3 +617,5 @@
def __str__(self):
return repr(self.value)
+# Constant variables, determined in all DStores
+EMPTY = Determined("empty", set())
=======================================
--- /lite.py Fri Apr 4 06:26:55 2014 UTC
+++ /lite.py Wed Apr 16 06:00:17 2014 UTC
@@ -109,7 +109,7 @@
e, s = l3lite.Language("English", 'eng'),
l3lite.Language("español", 'spa')
return u, e, s
-def gtest():
+def t1():
# broke the window
g0_nodes = {0, 1, 2}
# the boy
@@ -125,12 +125,12 @@
# the boy broke the window .
w = {0, 1, 2, 3, 4, 5}
g = {0, 1, 2, 3, 4, 5}
- wvars = [l3lite.IVar('the0', {1, 3, 5, 9}), # {3}
- l3lite.IVar('boy', {4}),
- l3lite.IVar('broke', {0, 7, 11}), # {0, 7}
- l3lite.IVar('the3', {1, 3, 5, 9}), # {1, 5}
- l3lite.IVar('window', {2, 6, 10}), # {2, 6}
- l3lite.IVar('.', {8})]
+ w2gnodes = [l3lite.IVar('the0', {1, 3, 5, 9}), # {3}
+ l3lite.DetIVar('boy', 4),
+ l3lite.IVar('broke', {0, 7, 11}), # {0, 7}
+ l3lite.IVar('the3', {1, 3, 5, 9}), # {1, 5}
+ l3lite.IVar('window', {2, 6, 10}), # {2, 6}
+ l3lite.DetIVar('.', 8)]
groups = l3lite.Var('groups', set(), g, 2, 6)
gdetvars = [l3lite.Determined('g0', {0, 1, 2}),
l3lite.Determined('g1', {3, 4}),
@@ -143,7 +143,7 @@
# Union of all group nodes used
gnodeU = l3lite.Var('gnodeU', set(),
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}, 6, 6)
- w_usel = l3lite.UnionSelection(gnodeU, nodes, wvars)
+ w_usel = l3lite.UnionSelection(gnodeU, nodes, w2gnodes)
## Union selection on the gnodes of all groups
g_usel = l3lite.UnionSelection(gnodeU, groups, gdetvars)
## Position constraints
@@ -207,28 +207,282 @@
### setcon5 = l3lite.SetConvexity(g5snode)
setconv = l3lite.ComplexSetConvexity(groups, [g0snode, g1snode,
g2snode,
g3snode, g4snode,
g5snode])
-### return nodes, groups, wvars, gdetvars, usel
- ## Union selection on individual groups: snodes -> gnodes
- ## The union of possible gnodes associated with the snodes of a group
is a *superset*
- ## of the known gnodes for that group
- s2g_sup0 = l3lite.Var('s2g_sup0', {0, 1, 2}, {0, 1, 2, 3, 4, 5, 6, 7,
8, 9, 10, 11})
- s2g_sup1 = l3lite.Var('s2g_sup1', {3, 4}, {0, 1, 2, 3, 4, 5, 6, 7, 8,
9, 10, 11})
- s2g_sup2 = l3lite.Var('s2g_sup2', {5, 6}, {0, 1, 2, 3, 4, 5, 6, 7, 8,
9, 10, 11})
-# s2g_sup5 =
- s2gU0 = l3lite.UnionSelection(s2g_sup0, g0snode, wvars)
- s2gU1 = l3lite.UnionSelection(s2g_sup1, g1snode, wvars)
- s2gU2 = l3lite.UnionSelection(s2g_sup2, g2snode, wvars)
-# s2gU5 = l3lite.UnionSelection(gdetvars[5], g5snode, wvars)
- return w_usel, g_usel, precsel, gp_usel, setconv, s2gU0, s2gU1 #, s2gU2
-# setcon0, setcon1, setcon2, \
-# gsnodeU0, gsnodeU1, gsnodeU2, s2gU0, s2gU1, s2gU2
-#, s2gU5, setcon5, gsnodeU5
+ ## ComplexUnionSelection
+ ## mainvars: [{0, 1, 2}, {3, 4}, ...]
+ ## selvars: [g0snode, g1snode, ...]
+ ## seqvars: w2gnodes
+ ## selvar: groups
+ # mainvars
+# gnodes0 = l3lite.Determined('gnodes0', {0, 1, 2})
+# gnodes1 = l3lite.Determined('gnodes1', {3, 4})
+# gnodes2 = l3lite.Determined('gnodes2', {5, 6})
+# gnodes3 = l3lite.DetIVar('gnodes3', 7)
+# gnodes4 = l3lite.DetIVar('gnodes4', 8)
+# gnodes5 = l3lite.Determined('gnodes5', {9, 10, 11})
+ complexU = l3lite.ComplexUnionSelection(selvar=groups,
+ selvars=[g0snode, g1snode,
g2snode, g3snode,
+ g4snode, g5snode],
+ seqvars=w2gnodes,
+ mainvars=gdetvars)
+ return w_usel, g_usel, precsel, gp_usel, setconv, complexU
+
+def t2():
+ constraints = []
+ ## Groups
+ # 0: read(0) %sbd(1) the(2) riot(3) act(4)
+ # 1: read(5) %sth(6)
+ # 2: the(7) boy(8)
+ # 3: us(9)
+ # 4: the(10) act(11)
+ # 5: the(12) riot(13)
+ # 6: .(14)
+ groups = l3lite.Var('groups', set(), {0, 1, 2, 3, 4, 5, 6}, 2, 7)
+ ## Group node indices
+ gdetvars = [l3lite.Determined('g0', {0, 1, 2, 3, 4}), # 1 is
abstract
+ l3lite.Determined('g1', {5, 6}), # 6 is
abstract
+ l3lite.Determined('g2', {7, 8}),
+ l3lite.Determined('g3', {9}),
+ l3lite.Determined('g4', {10, 11}),
+ l3lite.Determined('g5', {12, 13}),
+ l3lite.Determined('g6', {14})]
+ ## Concrete group node indices
+ gc_detvars = [l3lite.Determined('g0', {0, 2, 3, 4}), # 1 is abstract
+ l3lite.Determined('g1', {5}), # 6 is abstract
+ l3lite.Determined('g2', {7, 8}),
+ l3lite.Determined('g3', {9}),
+ l3lite.Determined('g4', {10, 11}),
+ l3lite.Determined('g5', {12, 13}),
+ l3lite.Determined('g6', {14})]
+ ## Words
+ sentence = ['the', 'boy', 'read', 'us', 'the', 'riot', 'act']
+ ## Word positions associated with group nodes (what about unused
gnodes?)
+ gn0w = l3lite.DetIVar('gn0w', 2)
+ gn1w = l3lite.IVar('gn1w', {1, 3}) # abstract
+ gn2w = l3lite.IVar('gn2w', {0, 4})
+ gn3w = l3lite.DetIVar('gn3w', 5)
+ gn4w = l3lite.DetIVar('gn4w', 6)
+ gn5w = l3lite.DetIVar('gn5w', 2)
+ gn6w = l3lite.IVar('gn6w', {5, 6}) # abstract
+ gn7w = l3lite.IVar('gn7w', {0, 4})
+ gn8w = l3lite.DetIVar('gn8w', 1)
+ gn9w = l3lite.DetIVar('gn9w', 3)
+ gn10w = l3lite.IVar('gn10w', {0, 4})
+ gn11w = l3lite.DetIVar('gn11w', 6)
+ gn12w = l3lite.IVar('gn12w', {0, 4})
+ gn13w = l3lite.DetIVar('gn13w', 5)
+ gn14w = l3lite.DetIVar('gn14w', 7)
+ gn_w = [gn0w, gn1w, gn2w, gn3w, gn4w, gn5w, gn6w, gn7w, gn8w, gn9w,
gn10w, gn11w, gn12w, gn13w, gn14w]
+ ## Group nodes associated with words
+ w0gn = l3lite.IVar('w0gn', {2, 7, 10, 12}) # the
+ w1gn = l3lite.Var('w1gn', set(), {1, 8}, 1, 2) # boy
+ w2gn = l3lite.IVar('w2gn', {0, 5}) # read
+ w3gn = l3lite.Var('w3gn', set(), {1, 9}, 1, 2) # us
+ w4gn = l3lite.IVar('w4gn', {2, 7, 10, 12}) # the
+ w5gn = l3lite.Var('w5gn', set(), {3, 6, 13}, 1, 2) # riot
+ w6gn = l3lite.Var('w6gn', set(), {4, 6, 11}, 1, 2) # act
+ w7gn = l3lite.DetIVar('w7gn', 14)
+ w2gnodes = [w0gn, w1gn, w2gn, w3gn, w4gn, w5gn, w6gn, w7gn]
+ ## Concrete group nodes associated with words
+ w0cgn = w0gn
+ w1cgn = l3lite.DetIVar('w1cgn', 8)
+ w2cgn = w2gn
+ w3cgn = l3lite.DetIVar('w3cgn', 9)
+ w4cgn = w4gn
+ w5cgn = l3lite.IVar('w5cgn', {3, 13})
+ w6cgn = l3lite.IVar('w6cgn', {4, 11})
+ w7cgn = w7gn
+ w2cgnodes = [w0cgn, w1cgn, w2cgn, w3cgn, w4cgn, w5cgn, w6cgn, w7cgn]
+ ## w->m Merged concrete group nodes associated with words
+ w1gnm = l3lite.Var('w1gnm', set(), {8}, 0, 1) # boy (merged
with sbd)
+ w3gnm = l3lite.Var('w3gnm', set(), {9}, 0, 1) # us (merged
with sbd)
+ w5gnm = l3lite.Var('w5gnm', set(), {13}, 0, 1) # riot (merged
with sth)
+ w6gnm = l3lite.Var('w6gnm', set(), {11}, 0, 1) # act (merged
with sth)
+ w2gnm_nodes = [l3lite.EMPTY, w1gnm, l3lite.EMPTY, w3gnm, l3lite.EMPTY,
w5gnm, w6gnm, l3lite.EMPTY]
+ ## w->a Abstract group nodes associated with words
+ w1ga = l3lite.Var('w1ga', set(), {1}, 0, 1)
+ w3ga = l3lite.Var('w3ga', set(), {1}, 0, 1)
+ w5ga = l3lite.Var('w5ga', set(), {6}, 0, 1)
+ w6ga = l3lite.Var('w6ga', set(), {6}, 0, 1)
+ w2ga_nodes = [l3lite.EMPTY, w1ga, l3lite.EMPTY, w3ga, l3lite.EMPTY,
w5ga, w6ga, l3lite.EMPTY]
+ ## All word nodes
+ nodes = l3lite.Determined('nodes', {0, 1, 2, 3, 4, 5, 6, 7})
+ ## Union selection on the gnodes of all words
+ # Words 1 (boy), 3 (us), 5 (riot), 6 (act) can have abstract nodes
+ constraints.extend(l3lite.Union([w1gn, w1cgn, w1ga]).constraints)
+ constraints.extend(l3lite.Union([w3gn, w3cgn, w3ga]).constraints)
+ constraints.extend(l3lite.Union([w5gn, w5cgn, w5ga]).constraints)
+ constraints.extend(l3lite.Union([w6gn, w6cgn, w6ga]).constraints)
+ # Union of all group nodes used
+ gnodeU = l3lite.Var('gnodeU', set(),
+ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
14}, 7, 9)
+ constraints.append(l3lite.UnionSelection(gnodeU, nodes, w2gnodes))
+ ## Union selection on the gnodes of all groups
+ constraints.append(l3lite.UnionSelection(gnodeU, groups, gdetvars))
+ ## Union selection on the words associated with each group node
+ constraints.append(l3lite.UnionSelection(nodes, gnodeU, gn_w))
+ # Positions of gnodes in each group
+ g0snode = l3lite.Var('g0snode', set(), {0, 1, 2, 3, 4, 5, 6}, 5, 5) #
read sbd the riot act
+ g1snode = l3lite.Var('g1snode', set(), {2, 5, 6}, 2, 2) #
read sth
+ g2snode = l3lite.Var('g2snode', set(), {0, 1, 4}, 2, 2) #
the boy
+ g3snode = l3lite.DetIVar('g3snode', 3) #
us
+ g4snode = l3lite.Var('g4snode', set(), {0, 4, 6}, 2, 2) #
the act
+ g5snode = l3lite.Var('g5snode', set(), {0, 4, 5}, 2, 2) #
the riot
+ g6snode = l3lite.DetIVar('g6snode', 7)
# .
+ gsnodes = [g0snode, g1snode, g2snode, g3snode, g4snode, g5snode,
g6snode]
+ # Positions of concrete gnodes in each group
+ g0cw = l3lite.Var('g0cw', set(), {0, 1, 2, 3, 4, 5, 6}, 4, 4)
+ g1cw = l3lite.Determined('g1cw', {2})
+ g2cw = g2snode
+ g3cw = g3snode
+ g4cw = g4snode
+ g5cw = g5snode
+ g6cw = g6snode
+ g_cwords = [g0cw, g1cw, g2cw, g3cw, g4cw, g5cw, g6cw]
+ ## Abstract group node mergers (empty set possible if not selected)
+ # Merge %sbd with boy or us
+ gan1m = l3lite.Var('gan1m', set(), {8, 9}, 0, 1)
+ # Merge %sth with riot or act
+ gan6m = l3lite.Var('gan6m', set(), {11, 13}, 0, 1)
+ gan_m = [l3lite.EMPTY, gan1m, l3lite.EMPTY, l3lite.EMPTY, l3lite.EMPTY,
+ l3lite.EMPTY, gan6m, l3lite.EMPTY, l3lite.EMPTY, l3lite.EMPTY,
+ l3lite.EMPTY, l3lite.EMPTY, l3lite.EMPTY, l3lite.EMPTY,
l3lite.EMPTY]
+ constraints.extend(l3lite.Inclusion([gan1m, gnodeU]).constraints)
+ constraints.extend(l3lite.Inclusion([gan6m, gnodeU]).constraints)
+ # m-> a; Abstract nodes associated with concrete gnodes
+ gm8ga = l3lite.Var('gm8ga', set(), {1}, 0, 1)
+ gm9ga = l3lite.Var('gm9ga', set(), {1}, 0, 1)
+ gm11ga = l3lite.Var('gm11ga', set(), {6}, 0, 1)
+ gm13ga = l3lite.Var('gm13ga', set(), {6}, 0, 1)
+ gm_ga = [l3lite.EMPTY, l3lite.EMPTY, l3lite.EMPTY, l3lite.EMPTY,
l3lite.EMPTY,
+ l3lite.EMPTY, l3lite.EMPTY, l3lite.EMPTY, gm8ga, gm9ga,
l3lite.EMPTY,
+ gm11ga, l3lite.EMPTY, gm13ga,l3lite.EMPTY]
+ ## a->w Words associated with abstract group nodes
+ ga1w = l3lite.Var('ga1w', set(), {1, 3}, 0, 1)
+ ga6w = l3lite.Var('ga6w', set(), {5, 6}, 0, 1)
+ ga_w = [l3lite.EMPTY, ga1w, l3lite.EMPTY, l3lite.EMPTY, l3lite.EMPTY,
l3lite.EMPTY,
+ ga6w, l3lite.EMPTY, l3lite.EMPTY, l3lite.EMPTY, l3lite.EMPTY,
l3lite.EMPTY,
+ l3lite.EMPTY, l3lite.EMPTY, l3lite.EMPTY]
+ ## m->w Words associated with merged group nodes
+ gnm8w = l3lite.Var('gnm8w', set(), {1}, 0, 1)
+ gnm9w = l3lite.Var('gnm9w', set(), {3}, 0, 1)
+ gnm11w = l3lite.Var('gnm11w', set(), {6}, 0, 1)
+ gnm13w = l3lite.Var('gnm13w', set(), {5}, 0, 1)
+ gnm_w = [l3lite.EMPTY, l3lite.EMPTY, l3lite.EMPTY, l3lite.EMPTY,
l3lite.EMPTY,
+ l3lite.EMPTY, l3lite.EMPTY, l3lite.EMPTY,
+ gnm8w, gnm9w, l3lite.EMPTY, gnm11w, l3lite.EMPTY,
+ gnm13w, l3lite.EMPTY]
+ # Merging means the gnodes have the same sentence position
+ # gn1w = gn8w | gn9w ; gn6w = gn11w | gn13w
+ # Abstract nodes in used groups
+ anodes = l3lite.Var('anodes', set(), {1, 6})
+ constraints.append(l3lite.UnionSelection(anodes, groups,
[l3lite.Determined('g0a', {1}),
+
l3lite.Determined('g1a', {6}),
+
l3lite.EMPTY, l3lite.EMPTY,
+
l3lite.EMPTY, l3lite.EMPTY,
+
l3lite.EMPTY]))
+ # Word nodes that involve a merging of two gnodes
+ mwords = l3lite.Var('mwords', set(), {1, 3, 5, 6}, 0, 2)
+ # Set of all concrete gnodes that are merged with abstract nodes
+ merged_gnodes = l3lite.Var('merged_gnodes', set(), {0, 2, 3, 4, 5, 7,
8, 9, 10, 11, 12, 13, 14},
+ 0, 2)
+ ## UnionSelection constraints relating words, abstract nodes, and
merged gnodes
+ # Set of merged nodes is the union of the merged nodes for the set of
selected abstract nodes
+ constraints.append(l3lite.UnionSelection(merged_gnodes, anodes, gan_m))
+ # Set of merged nodes is the union of the merged nodes of all merge
words
+ constraints.append(l3lite.UnionSelection(merged_gnodes, mwords,
w2gnm_nodes))
+ # Set of abstract nodes is the union of the abstract nodes of all
merge words
+ constraints.append(l3lite.UnionSelection(anodes, mwords, w2ga_nodes))
+ # Set of abstract nodes is the union of the abstract nodes of all
gnodes
+ constraints.append(l3lite.UnionSelection(anodes, merged_gnodes, gm_ga))
+ # Set of merge words is the union of the words associated with all
selected abstract nodes
+ constraints.append(l3lite.UnionSelection(mwords, anodes, ga_w))
+ # Set of merge words is the union of the words associated with all
merge group nodes
+ constraints.append(l3lite.UnionSelection(mwords, merged_gnodes, gnm_w))
+ ## Constraints on merged and abstract nodes
+ # Set of merged nodes must be a subset of all used gnodes
+ constraints.append(l3lite.Inclusion([merged_gnodes,
gnodeU]).constraints[0])
+ # All words must have different abstract nodes
+ constraints.extend(l3lite.Disjoint(w2ga_nodes).constraints)
+ # All concrete nodes must nodes have different abstract nodes
+ constraints.extend(l3lite.Disjoint(gm_ga).constraints)
+ ## Relations between w->cgnode, w->gnode, w->agnode
+ ## Groups merged with groups, including the group itself
+ g0gm = l3lite.Var('g0gm', {0}, {0, 2, 3}, 1, 2)
+ g1gm = l3lite.Var('g1gm', {1}, {1, 4, 5}, 1, 2)
+ g2gm = l3lite.Determined('g2gm', {2})
+ g3gm = l3lite.Determined('g3gm', {3})
+ g4gm = l3lite.Determined('g4gm', {4})
+ g5gm = l3lite.Determined('g5gm', {5})
+ g6gm = l3lite.Determined('g6gm', {6})
+ ## Trees under gnode heads
+ g0tree = l3lite.Var('g0tree', set(), {0, 1, 2, 3, 4, 5, 6}, 5)
+ g1tree = l3lite.Var('g1tree', set(), {0, 1, 2, 3, 4, 5, 6}, 2)
+ g2tree = g2snode
+ g3tree = g3snode
+ g4tree = g4snode
+ g5tree = g5snode
+ g6tree = g6snode
+ gtrees = [g0tree, g1tree, g2snode, g3snode, g4snode, g5snode, g6snode]
+ # g1 tree is the union of g0snode and the tree under whatever group
+ # merges with gnode 1 (sbd)
+ constraints.append(l3lite.UnionSelection(g0tree, g0gm, gtrees))
+ constraints.append(l3lite.UnionSelection(g1tree, g1gm, gtrees))
+ # Relate gnode merger with group merger
+ # If gnode 1 merges with gnode 8, then group 0 merges with group 2;
+ # if gnode 1 merges with gnode 9, then group 0 merges with group 3
+ # Select one or the other
+ # UnionSelection(choice, IVar('chooser', {0, 1}), [choice1, choice2])
+ g0merge_sel = l3lite.IVar('g0m_sel', {0, 1, 2})
+ constraints.append(l3lite.UnionSelection(g0gm, g0merge_sel,
[l3lite.Determined('g0g2', {0, 2}),
+
l3lite.Determined('g0g3', {0, 3}),
+
l3lite.Determined('g0_', {0})]))
+ constraints.append(l3lite.UnionSelection(gan1m, g0merge_sel,
+ [l3lite.Determined('gan1g8',
{8}),
+ l3lite.Determined('gan1g9',
{9}),
+ l3lite.EMPTY]))
+ g1merge_sel = l3lite.IVar('g1m_sel', {0, 1, 2})
+ constraints.append(l3lite.UnionSelection(g1gm, g1merge_sel,
[l3lite.Determined('g1g4', {1, 4}),
+
l3lite.Determined('g1g5', {1, 5}),
+
l3lite.Determined('g1_', {1})]))
+ constraints.append(l3lite.UnionSelection(gan6m, g1merge_sel,
+ [l3lite.Determined('gan6g11',
{11}),
+ l3lite.Determined('gan6g13',
{13}),
+ l3lite.EMPTY]))
+ # Position pair constraints
+ gposcons = l3lite.Var('gposcons', set(),
+ {(0, 1), (1, 2), (2, 3), (3, 4), (0, 2), (1, 3),
(2, 4), (0, 3), (1, 4),
+ (5, 6), (7, 8), (10, 11), (12, 13)})
+ # Union selection on position pair constraints
+ gp0 = l3lite.Determined('gp0', {(0, 1), (1, 2), (2, 3), (3, 4), (0,
2), (1, 3), (2, 4), (0, 3), (1, 4)})
+ gp1 = l3lite.Determined('gp1', {(5, 6)})
+ gp2 = l3lite.Determined('gp2', {(7, 8)})
+ gp3 = l3lite.Determined('gp3', set())
+ gp4 = l3lite.Determined('gp4', {(10, 11)})
+ gp5 = l3lite.Determined('gp5', {(12, 13)})
+ gp6 = l3lite.Determined('gp6', set())
+ gpos = [gp0, gp1, gp2, gp3, gp4, gp5, gp6]
+ constraints.append(l3lite.PrecedenceSelection(gposcons,
+ [gn0w, gn1w, gn2w, gn3w,
gn4w, gn5w,
+ gn6w, gn7w, gn8w, gn9w,
gn10w, gn11w, gn12w, gn13w, gn14w]))
+ # Union selection on position pair constraints
+ constraints.append(l3lite.UnionSelection(gposcons, groups, gpos))
+ # Complex union selection on positions of all concrete nodes in each
selected group
+ constraints.append(l3lite.ComplexUnionSelection(selvar=groups,
+ selvars=g_cwords,
+ seqvars=w2cgnodes,
+ mainvars=gc_detvars))
+ # Complex set convexity
+ constraints.append(l3lite.ComplexSetConvexity(groups, gtrees))
+ return constraints
def run_constraints(constraints, times=10):
for t in range(times):
print("\nITERATION {}".format(t))
for c in constraints:
state, changed = c.run()
+ if state == 0:
+ print('FAILED: constraint {}'.format(c))
+ return
if changed:
print("Running {}".format(c))
print(" Changed:
{}".format(list(changed)[0].pretty_string()))
Reply all
Reply to author
Forward
0 new messages