-
Notifications
You must be signed in to change notification settings - Fork 72
Expand file tree
/
Copy pathproblem.py
More file actions
272 lines (237 loc) · 9.88 KB
/
problem.py
File metadata and controls
272 lines (237 loc) · 9.88 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
"""Module containing the code for problem definitions."""
import copy
from operator import itemgetter
from typing import Callable, Optional, Union
from collections.abc import Sequence
from constraint.constraints import Constraint, FunctionConstraint
from constraint.domain import Domain
from constraint.solvers import OptimizedBacktrackingSolver
from constraint.parser import compile_restrictions
class Problem:
"""Class used to define a problem and retrieve solutions."""
def __init__(self, solver=None):
"""Initialization method.
Args:
solver (instance of a :py:class:`Solver`): Problem solver (default :py:class:`OptimizedBacktrackingSolver`)
"""
self._solver = solver or OptimizedBacktrackingSolver()
self._constraints = []
self._str_constraints = []
self._variables = {}
def reset(self):
"""Reset the current problem definition.
Example:
>>> problem = Problem()
>>> problem.addVariable("a", [1, 2])
>>> problem.reset()
>>> problem.getSolution()
>>>
"""
del self._constraints[:]
self._variables.clear()
def setSolver(self, solver):
"""Change the problem solver currently in use.
Example:
>>> solver = OptimizedBacktrackingSolver()
>>> problem = Problem(solver)
>>> problem.getSolver() is solver
True
Args:
solver (instance of a :py:class:`Solver`): New problem
solver
"""
self._solver = solver
def getSolver(self):
"""Obtain the problem solver currently in use.
Example:
>>> solver = OptimizedBacktrackingSolver()
>>> problem = Problem(solver)
>>> problem.getSolver() is solver
True
Returns:
instance of a :py:class:`Solver` subclass: Solver currently in use
"""
return self._solver
def addVariable(self, variable, domain):
"""Add a variable to the problem.
Example:
>>> problem = Problem()
>>> problem.addVariable("a", [1, 2])
>>> problem.getSolution() in ({'a': 1}, {'a': 2})
True
Args:
variable (hashable object): Object representing a problem
variable
domain (list, tuple, or instance of :py:class:`Domain`): Set of items
defining the possible values that the given variable may
assume
"""
if variable in self._variables:
msg = f"Tried to insert duplicated variable {repr(variable)}"
raise ValueError(msg)
if isinstance(domain, Domain):
domain = copy.deepcopy(domain)
elif hasattr(domain, "__getitem__"):
domain = Domain(domain)
else:
msg = "Domains must be instances of subclasses of the Domain class"
raise TypeError(msg)
if not domain:
raise ValueError("Domain is empty")
self._variables[variable] = domain
def addVariables(self, variables: Sequence, domain):
"""Add one or more variables to the problem.
Example:
>>> problem = Problem()
>>> problem.addVariables(["a", "b"], [1, 2, 3])
>>> solutions = problem.getSolutions()
>>> len(solutions)
9
>>> {'a': 3, 'b': 1} in solutions
True
Args:
variables (sequence of hashable objects): Any object
containing a sequence of objects represeting problem
variables
domain (list, tuple, or instance of :py:class:`Domain`): Set of items
defining the possible values that the given variables
may assume
"""
for variable in variables:
self.addVariable(variable, domain)
def addConstraint(self, constraint: Union[Constraint, Callable, str], variables: Optional[Sequence] = None):
"""Add a constraint to the problem.
Example:
>>> problem = Problem()
>>> problem.addVariables(["a", "b"], [1, 2, 3])
>>> problem.addConstraint(lambda a, b: b == a+1, ["a", "b"])
>>> solutions = problem.getSolutions()
>>>
Args:
constraint (instance of :py:class:`Constraint`, function to be wrapped by :py:class:`FunctionConstraint`, or string expression):
Constraint to be included in the problem
variables (set or sequence of variables): :py:class:`Variables` affected
by the constraint (default to all variables). Depending
on the constraint type the order may be important.
""" # noqa: E501
# compile string constraints (variables argument ignored as it is inferred from the string and may be reordered)
if isinstance(constraint, str):
self._str_constraints.append(constraint)
return
elif isinstance(constraint, list):
assert all(isinstance(c, str) for c in constraint), f"Expected constraints to be strings, got {constraint}"
self._str_constraints.extend(constraint)
return
# add regular constraints
if not isinstance(constraint, Constraint):
if callable(constraint):
constraint = FunctionConstraint(constraint)
else:
msg = "Constraints must be instances of subclasses " "of the Constraint class"
raise ValueError(msg)
self._constraints.append((constraint, variables))
def getSolution(self):
"""Find and return a solution to the problem.
Example:
>>> problem = Problem()
>>> problem.getSolution() is None
True
>>> problem.addVariables(["a"], [42])
>>> problem.getSolution()
{'a': 42}
Returns:
dictionary mapping variables to values: Solution for the
problem
"""
domains, constraints, vconstraints = self._getArgs()
if not domains:
return None
return self._solver.getSolution(domains, constraints, vconstraints)
def getSolutions(self):
"""Find and return all solutions to the problem.
Example:
>>> problem = Problem()
>>> problem.getSolutions() == []
True
>>> problem.addVariables(["a"], [42])
>>> problem.getSolutions()
[{'a': 42}]
Returns:
list of dictionaries mapping variables to values: All
solutions for the problem
"""
domains, constraints, vconstraints = self._getArgs()
if not domains:
return []
return self._solver.getSolutions(domains, constraints, vconstraints)
def getSolutionIter(self):
"""Return an iterator to the solutions of the problem.
Example:
>>> problem = Problem()
>>> list(problem.getSolutionIter()) == []
True
>>> problem.addVariables(["a"], [42])
>>> iter = problem.getSolutionIter()
>>> next(iter)
{'a': 42}
>>> next(iter)
Traceback (most recent call last):
...
StopIteration
"""
domains, constraints, vconstraints = self._getArgs()
if not domains:
return iter(())
return self._solver.getSolutionIter(domains, constraints, vconstraints)
def getSolutionsOrderedList(self, order: list[str] = None) -> list[tuple]:
"""Returns the solutions as a list of tuples, with each solution tuple ordered according to `order`."""
solutions: list[dict] = self.getSolutions()
if order is None or len(order) == 1:
return list(tuple(solution.values()) for solution in solutions)
get_in_order = itemgetter(*order)
return list(get_in_order(params) for params in solutions)
def getSolutionsAsListDict(
self, order: list[str] = None, validate: bool = True
) -> tuple[list[tuple], dict[tuple, int], int]: # noqa: E501
"""Returns the searchspace as a list of tuples, a dict of the searchspace for fast lookups and the size."""
solutions_list = self.getSolutionsOrderedList(order)
size_list = len(solutions_list)
solutions_dict: dict = dict(zip(solutions_list, range(size_list)))
if validate:
# check for duplicates
size_dict = len(solutions_dict)
if size_list != size_dict:
raise ValueError(
f"{size_list - size_dict} duplicate parameter configurations in searchspace, should not happen."
)
return (
solutions_list,
solutions_dict,
size_list,
)
def _getArgs(self):
domains = self._variables.copy()
allvariables = domains.keys()
constraints = []
for constraint in self._str_constraints:
parsed = compile_restrictions([constraint], domains)
for c, v, _ in parsed:
self.addConstraint(c, v)
for constraint, variables in self._constraints:
if not variables:
variables = list(allvariables)
constraints.append((constraint, variables))
vconstraints = {}
for variable in domains:
vconstraints[variable] = []
for constraint, variables in constraints:
for variable in variables:
vconstraints[variable].append((constraint, variables))
for constraint, variables in constraints[:]:
constraint.preProcess(variables, domains, constraints, vconstraints)
for domain in domains.values():
domain.resetState()
if not domain:
return None, None, None
# doArc8(getArcs(domains, constraints), domains, {})
return domains, constraints, vconstraints