Commit upstream/0.4.0 - logilab-constraint

Imported Upstream version 0.4.0 SVN-Git Migration 8 years ago

38 changed file(s) with 5195 addition(s) and 0 deletion(s). Raw diff Collapse all Expand all

+340

-0

COPYING less more

	0	GNU GENERAL PUBLIC LICENSE
	1	Version 2, June 1991
	2
	3	Copyright (C) 1989, 1991 Free Software Foundation, Inc.
	4	51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
	5	Everyone is permitted to copy and distribute verbatim copies
	6	of this license document, but changing it is not allowed.
	7
	8	Preamble
	9
	10	The licenses for most software are designed to take away your
	11	freedom to share and change it. By contrast, the GNU General Public
	12	License is intended to guarantee your freedom to share and change free
	13	software--to make sure the software is free for all its users. This
	14	General Public License applies to most of the Free Software
	15	Foundation's software and to any other program whose authors commit to
	16	using it. (Some other Free Software Foundation software is covered by
	17	the GNU Library General Public License instead.) You can apply it to
	18	your programs, too.
	19
	20	When we speak of free software, we are referring to freedom, not
	21	price. Our General Public Licenses are designed to make sure that you
	22	have the freedom to distribute copies of free software (and charge for
	23	this service if you wish), that you receive source code or can get it
	24	if you want it, that you can change the software or use pieces of it
	25	in new free programs; and that you know you can do these things.
	26
	27	To protect your rights, we need to make restrictions that forbid
	28	anyone to deny you these rights or to ask you to surrender the rights.
	29	These restrictions translate to certain responsibilities for you if you
	30	distribute copies of the software, or if you modify it.
	31
	32	For example, if you distribute copies of such a program, whether
	33	gratis or for a fee, you must give the recipients all the rights that
	34	you have. You must make sure that they, too, receive or can get the
	35	source code. And you must show them these terms so they know their
	36	rights.
	37
	38	We protect your rights with two steps: (1) copyright the software, and
	39	(2) offer you this license which gives you legal permission to copy,
	40	distribute and/or modify the software.
	41
	42	Also, for each author's protection and ours, we want to make certain
	43	that everyone understands that there is no warranty for this free
	44	software. If the software is modified by someone else and passed on, we
	45	want its recipients to know that what they have is not the original, so
	46	that any problems introduced by others will not reflect on the original
	47	authors' reputations.
	48
	49	Finally, any free program is threatened constantly by software
	50	patents. We wish to avoid the danger that redistributors of a free
	51	program will individually obtain patent licenses, in effect making the
	52	program proprietary. To prevent this, we have made it clear that any
	53	patent must be licensed for everyone's free use or not licensed at all.
	54
	55	The precise terms and conditions for copying, distribution and
	56	modification follow.
	57
	58	GNU GENERAL PUBLIC LICENSE
	59	TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
	60
	61	0. This License applies to any program or other work which contains
	62	a notice placed by the copyright holder saying it may be distributed
	63	under the terms of this General Public License. The "Program", below,
	64	refers to any such program or work, and a "work based on the Program"
	65	means either the Program or any derivative work under copyright law:
	66	that is to say, a work containing the Program or a portion of it,
	67	either verbatim or with modifications and/or translated into another
	68	language. (Hereinafter, translation is included without limitation in
	69	the term "modification".) Each licensee is addressed as "you".
	70
	71	Activities other than copying, distribution and modification are not
	72	covered by this License; they are outside its scope. The act of
	73	running the Program is not restricted, and the output from the Program
	74	is covered only if its contents constitute a work based on the
	75	Program (independent of having been made by running the Program).
	76	Whether that is true depends on what the Program does.
	77
	78	1. You may copy and distribute verbatim copies of the Program's
	79	source code as you receive it, in any medium, provided that you
	80	conspicuously and appropriately publish on each copy an appropriate
	81	copyright notice and disclaimer of warranty; keep intact all the
	82	notices that refer to this License and to the absence of any warranty;
	83	and give any other recipients of the Program a copy of this License
	84	along with the Program.
	85
	86	You may charge a fee for the physical act of transferring a copy, and
	87	you may at your option offer warranty protection in exchange for a fee.
	88
	89	2. You may modify your copy or copies of the Program or any portion
	90	of it, thus forming a work based on the Program, and copy and
	91	distribute such modifications or work under the terms of Section 1
	92	above, provided that you also meet all of these conditions:
	93
	94	a) You must cause the modified files to carry prominent notices
	95	stating that you changed the files and the date of any change.
	96
	97	b) You must cause any work that you distribute or publish, that in
	98	whole or in part contains or is derived from the Program or any
	99	part thereof, to be licensed as a whole at no charge to all third
	100	parties under the terms of this License.
	101
	102	c) If the modified program normally reads commands interactively
	103	when run, you must cause it, when started running for such
	104	interactive use in the most ordinary way, to print or display an
	105	announcement including an appropriate copyright notice and a
	106	notice that there is no warranty (or else, saying that you provide
	107	a warranty) and that users may redistribute the program under
	108	these conditions, and telling the user how to view a copy of this
	109	License. (Exception: if the Program itself is interactive but
	110	does not normally print such an announcement, your work based on
	111	the Program is not required to print an announcement.)
	112
	113	These requirements apply to the modified work as a whole. If
	114	identifiable sections of that work are not derived from the Program,
	115	and can be reasonably considered independent and separate works in
	116	themselves, then this License, and its terms, do not apply to those
	117	sections when you distribute them as separate works. But when you
	118	distribute the same sections as part of a whole which is a work based
	119	on the Program, the distribution of the whole must be on the terms of
	120	this License, whose permissions for other licensees extend to the
	121	entire whole, and thus to each and every part regardless of who wrote it.
	122
	123	Thus, it is not the intent of this section to claim rights or contest
	124	your rights to work written entirely by you; rather, the intent is to
	125	exercise the right to control the distribution of derivative or
	126	collective works based on the Program.
	127
	128	In addition, mere aggregation of another work not based on the Program
	129	with the Program (or with a work based on the Program) on a volume of
	130	a storage or distribution medium does not bring the other work under
	131	the scope of this License.
	132
	133	3. You may copy and distribute the Program (or a work based on it,
	134	under Section 2) in object code or executable form under the terms of
	135	Sections 1 and 2 above provided that you also do one of the following:
	136
	137	a) Accompany it with the complete corresponding machine-readable
	138	source code, which must be distributed under the terms of Sections
	139	1 and 2 above on a medium customarily used for software interchange; or,
	140
	141	b) Accompany it with a written offer, valid for at least three
	142	years, to give any third party, for a charge no more than your
	143	cost of physically performing source distribution, a complete
	144	machine-readable copy of the corresponding source code, to be
	145	distributed under the terms of Sections 1 and 2 above on a medium
	146	customarily used for software interchange; or,
	147
	148	c) Accompany it with the information you received as to the offer
	149	to distribute corresponding source code. (This alternative is
	150	allowed only for noncommercial distribution and only if you
	151	received the program in object code or executable form with such
	152	an offer, in accord with Subsection b above.)
	153
	154	The source code for a work means the preferred form of the work for
	155	making modifications to it. For an executable work, complete source
	156	code means all the source code for all modules it contains, plus any
	157	associated interface definition files, plus the scripts used to
	158	control compilation and installation of the executable. However, as a
	159	special exception, the source code distributed need not include
	160	anything that is normally distributed (in either source or binary
	161	form) with the major components (compiler, kernel, and so on) of the
	162	operating system on which the executable runs, unless that component
	163	itself accompanies the executable.
	164
	165	If distribution of executable or object code is made by offering
	166	access to copy from a designated place, then offering equivalent
	167	access to copy the source code from the same place counts as
	168	distribution of the source code, even though third parties are not
	169	compelled to copy the source along with the object code.
	170
	171	4. You may not copy, modify, sublicense, or distribute the Program
	172	except as expressly provided under this License. Any attempt
	173	otherwise to copy, modify, sublicense or distribute the Program is
	174	void, and will automatically terminate your rights under this License.
	175	However, parties who have received copies, or rights, from you under
	176	this License will not have their licenses terminated so long as such
	177	parties remain in full compliance.
	178
	179	5. You are not required to accept this License, since you have not
	180	signed it. However, nothing else grants you permission to modify or
	181	distribute the Program or its derivative works. These actions are
	182	prohibited by law if you do not accept this License. Therefore, by
	183	modifying or distributing the Program (or any work based on the
	184	Program), you indicate your acceptance of this License to do so, and
	185	all its terms and conditions for copying, distributing or modifying
	186	the Program or works based on it.
	187
	188	6. Each time you redistribute the Program (or any work based on the
	189	Program), the recipient automatically receives a license from the
	190	original licensor to copy, distribute or modify the Program subject to
	191	these terms and conditions. You may not impose any further
	192	restrictions on the recipients' exercise of the rights granted herein.
	193	You are not responsible for enforcing compliance by third parties to
	194	this License.
	195
	196	7. If, as a consequence of a court judgment or allegation of patent
	197	infringement or for any other reason (not limited to patent issues),
	198	conditions are imposed on you (whether by court order, agreement or
	199	otherwise) that contradict the conditions of this License, they do not
	200	excuse you from the conditions of this License. If you cannot
	201	distribute so as to satisfy simultaneously your obligations under this
	202	License and any other pertinent obligations, then as a consequence you
	203	may not distribute the Program at all. For example, if a patent
	204	license would not permit royalty-free redistribution of the Program by
	205	all those who receive copies directly or indirectly through you, then
	206	the only way you could satisfy both it and this License would be to
	207	refrain entirely from distribution of the Program.
	208
	209	If any portion of this section is held invalid or unenforceable under
	210	any particular circumstance, the balance of the section is intended to
	211	apply and the section as a whole is intended to apply in other
	212	circumstances.
	213
	214	It is not the purpose of this section to induce you to infringe any
	215	patents or other property right claims or to contest validity of any
	216	such claims; this section has the sole purpose of protecting the
	217	integrity of the free software distribution system, which is
	218	implemented by public license practices. Many people have made
	219	generous contributions to the wide range of software distributed
	220	through that system in reliance on consistent application of that
	221	system; it is up to the author/donor to decide if he or she is willing
	222	to distribute software through any other system and a licensee cannot
	223	impose that choice.
	224
	225	This section is intended to make thoroughly clear what is believed to
	226	be a consequence of the rest of this License.
	227
	228	8. If the distribution and/or use of the Program is restricted in
	229	certain countries either by patents or by copyrighted interfaces, the
	230	original copyright holder who places the Program under this License
	231	may add an explicit geographical distribution limitation excluding
	232	those countries, so that distribution is permitted only in or among
	233	countries not thus excluded. In such case, this License incorporates
	234	the limitation as if written in the body of this License.
	235
	236	9. The Free Software Foundation may publish revised and/or new versions
	237	of the General Public License from time to time. Such new versions will
	238	be similar in spirit to the present version, but may differ in detail to
	239	address new problems or concerns.
	240
	241	Each version is given a distinguishing version number. If the Program
	242	specifies a version number of this License which applies to it and "any
	243	later version", you have the option of following the terms and conditions
	244	either of that version or of any later version published by the Free
	245	Software Foundation. If the Program does not specify a version number of
	246	this License, you may choose any version ever published by the Free Software
	247	Foundation.
	248
	249	10. If you wish to incorporate parts of the Program into other free
	250	programs whose distribution conditions are different, write to the author
	251	to ask for permission. For software which is copyrighted by the Free
	252	Software Foundation, write to the Free Software Foundation; we sometimes
	253	make exceptions for this. Our decision will be guided by the two goals
	254	of preserving the free status of all derivatives of our free software and
	255	of promoting the sharing and reuse of software generally.
	256
	257	NO WARRANTY
	258
	259	11. BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY
	260	FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN
	261	OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES
	262	PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED
	263	OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
	264	MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS
	265	TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD THE
	266	PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING,
	267	REPAIR OR CORRECTION.
	268
	269	12. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING
	270	WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR
	271	REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES,
	272	INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING
	273	OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED
	274	TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY
	275	YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER
	276	PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE
	277	POSSIBILITY OF SUCH DAMAGES.
	278
	279	END OF TERMS AND CONDITIONS
	280
	281	How to Apply These Terms to Your New Programs
	282
	283	If you develop a new program, and you want it to be of the greatest
	284	possible use to the public, the best way to achieve this is to make it
	285	free software which everyone can redistribute and change under these terms.
	286
	287	To do so, attach the following notices to the program. It is safest
	288	to attach them to the start of each source file to most effectively
	289	convey the exclusion of warranty; and each file should have at least
	290	the "copyright" line and a pointer to where the full notice is found.
	291
	292	<one line to give the program's name and a brief idea of what it does.>
	293	Copyright (C) <year> <name of author>
	294
	295	This program is free software; you can redistribute it and/or modify
	296	it under the terms of the GNU General Public License as published by
	297	the Free Software Foundation; either version 2 of the License, or
	298	(at your option) any later version.
	299
	300	This program is distributed in the hope that it will be useful,
	301	but WITHOUT ANY WARRANTY; without even the implied warranty of
	302	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	303	GNU General Public License for more details.
	304
	305	You should have received a copy of the GNU General Public License
	306	along with this program; if not, write to the Free Software
	307	Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
	308
	309
	310	Also add information on how to contact you by electronic and paper mail.
	311
	312	If the program is interactive, make it output a short notice like this
	313	when it starts in an interactive mode:
	314
	315	Gnomovision version 69, Copyright (C) year name of author
	316	Gnomovision comes with ABSOLUTELY NO WARRANTY; for details type `show w'.
	317	This is free software, and you are welcome to redistribute it
	318	under certain conditions; type `show c' for details.
	319
	320	The hypothetical commands `show w' and `show c' should show the appropriate
	321	parts of the General Public License. Of course, the commands you use may
	322	be called something other than `show w' and `show c'; they could even be
	323	mouse-clicks or menu items--whatever suits your program.
	324
	325	You should also get your employer (if you work as a programmer) or your
	326	school, if any, to sign a "copyright disclaimer" for the program, if
	327	necessary. Here is a sample; alter the names:
	328
	329	Yoyodyne, Inc., hereby disclaims all copyright interest in the program
	330	`Gnomovision' (which makes passes at compilers) written by James Hacker.
	331
	332	<signature of Ty Coon>, 1 April 1989
	333	Ty Coon, President of Vice
	334
	335	This General Public License does not permit incorporating your program into
	336	proprietary programs. If your program is a subroutine library, you may
	337	consider it more useful to permit linking proprietary applications with the
	338	library. If this is what you want to do, use the GNU Library General
	339	Public License instead of this License.

+71

-0

ChangeLog less more

	0	ChangeLog for logilab.constraint
	1	================================
	2
	3	2008-08-07 -- 0.4.0
	4	* allow capture of solver output
	5
	6
	7
	8	2005-09-05 -- 0.3.0
	9	* Added finite interval domains and constraints in module
	10	constraint.fi
	11
	12	* constraint now depends on logilab.common to support a larger number
	13	of python versions
	14
	15	* Optimisation of finite domains by using copy on write
	16
	17	* Better heuristics for constraint queuing
	18
	19
	20
	21	2005-06-17 -- 0.2.7
	22	* Added fd.InSet special constraint that tests for set inclusion
	23
	24	* bumped copyright
	25
	26	* pylint fixes
	27
	28
	29
	30	2004-12-22 -- 0.2.6
	31	* Dropped support for python2.2, added support for python2.4
	32
	33	* Optimized version of Expression and BinaryExpression, as well as
	34	several other optimizations lead to increased performance (money2 runs
	35	almost 40% faster with the new release, queens about 20%)
	36
	37	* Optimizations in the search algorithm leads to important speedups
	38	when only looking for a single solution (instead of performing an
	39	exhaustive search of all solutions)
	40
	41	* Added a warning when psyco cannot be loaded
	42
	43
	44
	45	2004-06-13 -- 0.2.5
	46	* logilab/debian packaging
	47
	48	* New constraint AllDistinct with linear narrowing time
	49
	50	* updated unit tests
	51
	52	* updated send+more=money example
	53
	54	* added RandomizingDistributor
	55
	56
	57
	58	2002-10-16 -- 0.2.3
	59	* New distributors SplitDistributor and EnumeratorDistributor
	60
	61	* fast solution in examples/menza2.py
	62
	63	* Dichotomy distributors can now split domains in more than two parts.
	64
	65	* added timestamps to log messages
	66
	67	* updated queens.py to use the new EnumeratorDistributor (25% speed increase)
	68
	69
	70

+15

-0

PKG-INFO less more

	0	Metadata-Version: 1.0
	1	Name: logilab-constraint
	2	Version: 0.4.0
	3	Summary: constraints satisfaction solver in Python
	4	Home-page: http://www.logilab.org/projects/constraint
	5	Author: Alexandre Fayolle
	6	Author-email: alexandre.fayolle@logilab.fr
	7	License: GPL
	8	Description: Extensible constraint satisfaction problem solver written in pure
	9	Python, using constraint propagation algorithms. The
	10	logilab.constraint module provides finite domains with arbitrary
	11	values, finite interval domains, and constraints which can be applied
	12	to variables linked to these domains.
	13
	14	Platform: UNKNOWN

+21

-0

README less more

	0	This package implements constraint propagation algorithm to solve
	1	constraint satisfaction problem. It requires python 2.3 or later to
	2	work. Having psyco (http://psyco.sf.net) installed will definitely
	3	speed up things, but is not a requirement.
	4
	5	It is released under the GNU Public License.
	6
	7	The documentation is in the doc/ directory. Examples are in the
	8	examples/ directory.
	9
	10	Discussion about constraint should take place on the python-logic
	11	mailing list. Information on subscription and mailing list archives
	12	can be accessed at
	13	http://lists.logilab.org/mailman/listinfo/python-logic/
	14
	15	Your feedback is very valuable to me. Please share tour experience
	16	with other users of the package on the mailing list.
	17
	18	--
	19	Alexandre Fayolle
	20

+22

-0

__init__.py less more

	0	"""
	1	Constraint Satisfaction Problem (CSP) Solver in Python.
	2
	3	:copyright:
	4	2000-2008 `LOGILAB S.A. <http://www.logilab.fr>`_ (Paris, FRANCE),
	5	all rights reserved.
	6
	7	:contact:
	8	http://www.logilab.org/project/logilab-constraint --
	9	mailto:python-projects@logilab.org
	10
	11	:license:
	12	`General Public License version 2
	13	<http://www.gnu.org/licenses/old-licenses/gpl-2.0.html>`_
	14	"""
	15
	16	from logilab.constraint.__pkginfo__ import version as __version__
	17	from logilab.constraint.propagation import Repository, Solver
	18	from logilab.constraint.distributors import DefaultDistributor
	19	from logilab.constraint import fd
	20	from logilab.constraint import fi
	21	__all__ = ['Repository', 'Solver', 'DefaultDistributor', 'fd', 'fi']

+47

-0

__pkginfo__.py less more

	0	# pylint: disable-msg=W0622
	1	# This program is free software; you can redistribute it and/or modify it under
	2	# the terms of the GNU General Public License as published by the Free Software
	3	# Foundation; either version 2 of the License, or (at your option) any later
	4	# version.
	5	#
	6	# This program is distributed in the hope that it will be useful, but WITHOUT
	7	# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
	8	# FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details
	9	#
	10	# You should have received a copy of the GNU General Public License along with
	11	# this program; if not, write to the Free Software Foundation, Inc.,
	12	# 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
	13	"""Copyright (c) 2001-2006 LOGILAB S.A. (Paris, FRANCE).
	14	http://www.logilab.fr/ -- mailto:contact@logilab.fr
	15	"""
	16
	17	modname = 'constraint'
	18	distname = 'logilab-constraint'
	19
	20	numversion = (0, 4, 0)
	21	version = '.'.join(map(str, numversion))
	22	pyversions = ('2.3', '2.4')
	23
	24	license = 'GPL'
	25	copyright = '''Copyright (c) 2001-2006 LOGILAB S.A. (Paris, FRANCE).
	26	http://www.logilab.fr/ -- mailto:contact@logilab.fr'''
	27
	28	short_desc = "constraints satisfaction solver in Python"
	29
	30	long_desc = """Extensible constraint satisfaction problem solver written in pure
	31	Python, using constraint propagation algorithms. The
	32	logilab.constraint module provides finite domains with arbitrary
	33	values, finite interval domains, and constraints which can be applied
	34	to variables linked to these domains.
	35	"""
	36
	37	author = "Alexandre Fayolle"
	38	author_email = "alexandre.fayolle@logilab.fr"
	39
	40	web = "http://www.logilab.org/projects/%s" % modname
	41	ftp = "ftp://ftp.logilab.org/pub/%s/" % modname
	42	mailinglist = "http://lists.logilab.org/mailman/listinfo/python-logic/"
	43
	44	subpackage_of = 'logilab'
	45	debian_name = 'constraint'
	46	debian_maintainer_email = 'afayolle@debian.org'

+175

-0

distributors.py less more

	0	# (c) 2000-2001 LOGILAB S.A. (Paris, FRANCE).
	1	# http://www.logilab.fr/ -- mailto:contact@logilab.fr
	2	#
	3	# This program is free software; you can redistribute it and/or modify it under
	4	# the terms of the GNU General Public License as published by the Free Software
	5	# Foundation; either version 2 of the License, or (at your option) any later
	6	# version.
	7	#
	8	# This program is distributed in the hope that it will be useful, but WITHOUT
	9	# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
	10	# FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
	11	#
	12	# You should have received a copy of the GNU General Public License along with
	13	# this program; if not, write to the Free Software Foundation, Inc.,
	14	# 59 Temple Place - Suite 330, Boston, MA 02111-1307
	15	# USA.
	16
	17	"""
	18	distributors - part of Logilab's constraint satisfaction solver.
	19	"""
	20
	21	from logilab.constraint.psyco_wrapper import Psyobj
	22	from logilab.constraint.interfaces import DistributorInterface
	23	import math, random
	24
	25	def make_new_domains(domains):
	26	"""return a shallow copy of dict of domains passed in argument"""
	27	domain = {}
	28	for key, value in domains.items():
	29	domain[key] = value.copy()
	30	return domain
	31
	32	class AbstractDistributor(Psyobj):
	33	"""Implements DistributorInterface but abstract because
	34	_distribute is left unimplemented."""
	35
	36	__implements__ = DistributorInterface
	37
	38	def __init__(self, nb_subspaces=2):
	39	self.nb_subspaces = nb_subspaces
	40	self.verbose = 0
	41
	42	def findSmallestDomain(self, domains):
	43	"""returns the variable having the smallest domain.
	44	(or one of such varibles if there is a tie)
	45	"""
	46	domlist = [(dom.size(), variable ) for variable, dom in domains.items()
	47	if dom.size() > 1]
	48	domlist.sort()
	49	return domlist[0][1]
	50
	51	def findLargestDomain(self, domains):
	52	"""returns the variable having the largest domain.
	53	(or one of such variables if there is a tie)
	54	"""
	55	domlist = [(dom.size(), variable) for variable, dom in domains.items()
	56	if dom.size() > 1]
	57	domlist.sort()
	58	return domlist[-1][1]
	59
	60	def nb_subdomains(self, domains):
	61	"""return number of sub domains to explore"""
	62	return self.nb_subspaces
	63
	64	def distribute(self, domains, verbose=0):
	65	"""do the minimal job and let concrete class distribute variables
	66	"""
	67	self.verbose = verbose
	68	replicas = []
	69	for i in range(self.nb_subdomains(domains)):
	70	replicas.append(make_new_domains(domains))
	71	modified_domains = self._distribute(*replicas)
	72	for domain in modified_domains:
	73	domain.resetFlags()
	74	return replicas
	75
	76	def _distribute(self, *args):
	77	""" method to implement in concrete class
	78
	79	take self.nb_subspaces copy of the original domains as argument
	80	distribute the domains and return each modified domain
	81	"""
	82	raise NotImplementedError("Use a concrete implementation of "
	83	"the Distributor interface")
	84
	85	class NaiveDistributor(AbstractDistributor):
	86	"""distributes domains by splitting the smallest domain in 2 new domains
	87	The first new domain has a size of one,
	88	and the second has all the other values"""
	89
	90	def __init__(self):
	91	AbstractDistributor.__init__(self)
	92
	93	def _distribute(self, dom1, dom2):
	94	"""See AbstractDistributor"""
	95	variable = self.findSmallestDomain(dom1)
	96	values = dom1[variable].getValues()
	97	if self.verbose:
	98	print 'Distributing domain for variable', variable, \
	99	'at value', values[0]
	100	dom1[variable].removeValues(values[1:])
	101	dom2[variable].removeValue(values[0])
	102	return (dom1[variable], dom2[variable])
	103
	104
	105	class RandomizingDistributor(AbstractDistributor):
	106	"""distributes domains as the NaiveDistrutor, except that the unique
	107	value of the first domain is picked at random."""
	108
	109	def __init__(self):
	110	AbstractDistributor.__init__(self)
	111
	112	def _distribute(self, dom1, dom2):
	113	"""See AbstractDistributor"""
	114	variable = self.findSmallestDomain(dom1)
	115	values = dom1[variable].getValues()
	116	distval = random.choice(values)
	117	values.remove(distval)
	118	if self.verbose:
	119	print 'Distributing domain for variable', variable, \
	120	'at value', distval
	121	dom1[variable].removeValues(values)
	122	dom2[variable].removeValue(distval)
	123	return (dom1[variable], dom2[variable])
	124
	125
	126	class SplitDistributor(AbstractDistributor):
	127	"""distributes domains by splitting the smallest domain in
	128	nb_subspaces equal parts or as equal as possible.
	129	If nb_subspaces is 0, then the smallest domain is split in
	130	domains of size 1"""
	131
	132	def __init__(self, nb_subspaces=3):
	133	AbstractDistributor.__init__(self, nb_subspaces)
	134	self.__to_split = None
	135	def nb_subdomains(self, domains):
	136	"""See AbstractDistributor"""
	137	self.__to_split = self.findSmallestDomain(domains)
	138	if self.nb_subspaces:
	139	return min(self.nb_subspaces, domains[self.__to_split].size())
	140	else:
	141	return domains[self.__to_split].size()
	142
	143	def _distribute(self, *args):
	144	"""See AbstractDistributor"""
	145	variable = self.__to_split
	146	nb_subspaces = len(args)
	147	values = args[0][variable].getValues()
	148	nb_elts = max(1, len(values)*1./nb_subspaces)
	149	slices = [(int(math.floor(index * nb_elts)),
	150	int(math.floor((index + 1) * nb_elts)))
	151	for index in range(nb_subspaces)]
	152	if self.verbose:
	153	print 'Distributing domain for variable', variable
	154	modified = []
	155	for (dom, (end, start)) in zip(args, slices) :
	156	dom[variable].removeValues(values[:end])
	157	dom[variable].removeValues(values[start:])
	158	modified.append(dom[variable])
	159	return modified
	160
	161	class DichotomyDistributor(SplitDistributor):
	162	"""distributes domains by splitting the smallest domain in
	163	two equal parts or as equal as possible"""
	164	def __init__(self):
	165	SplitDistributor.__init__(self, 2)
	166
	167
	168	class EnumeratorDistributor(SplitDistributor):
	169	"""distributes domains by splitting the smallest domain
	170	in domains of size 1."""
	171	def __init__(self):
	172	SplitDistributor.__init__(self, 0)
	173
	174	DefaultDistributor = DichotomyDistributor

-0

doc/CONTRIBUTORS less more

	0	Alexandre Fayolle: core coding
	1	Herb Schilling: documentation proof reading
	2	Terry Reedy: documentation proof reading

+109

-0

doc/documentation.html less more

	0	<html><head><meta content="text/html; charset=ISO-8859-1" http-equiv="Content-Type"><title>Constraint Propagation in Python</title><meta name="generator" content="LOGILAB adaptation of DocBook XSL Stylesheets V1.29"><meta name="language" content="en"><meta name="organization" content="Logilab S.A."></head><body bgcolor="#FFFFFF" text="#000000"><table border="0" width="100%" cellspacing="2" cellpadding="0"><tr><td width="20%"><img src="file:/home/logilab/public/logos/logilab.gif" width="150"></td><td width="80%"><h3 class="template"><center>Constraint Propagation in Python</center></h3><hr noshade="yes" size="5" width="100%"></td></tr></table><table width="100%" cellspacing="0" cellpadding="8"><tr><td width="5%" bgcolor="#FFAA1B" valign="top" align="left"> </td><td width="95%" valign="top" align="left"><div id="constraint-propagation-manual" class="article"><div class="article"><p> </p><h1 class="title0"><center>Constraint Propagation in Python</center></h1><h2 class="subtitle0"><center><i></i></center></h2><p> </p><table border="0" width="100%"><tr><td width="50%"><p align="left"><b>Alexandre Fayolle</b></p></td><td width="50%"></td></tr></table><hr width="100%"><p> </p><h3 class="titlepage-title">Copyright © 2002 by Logilab</h3>This manual presents how to use the constraint package to solve
	1	constraint propagation problems in Python. It also presents the
	2	the extension mechanisms available in the package</div><div class="sect1"><a name="using"></a><div class="sect1"><p> </p><h1 class="title2"><a name="using"></a>1. Using the constraint package<br><hr width="100%"></h1></div><div class="sect2"><a name="id2709498"></a><div class="sect2"><h2 class="title3"><a name="id2709498"></a>1.1. Sample problem</h2></div><p>Let's take a real-life problem to get started. You're organising a
	3	an international Python Programming event, and you have to schedule
	4	conferences. There are 10 different conferences, you have 3 conference
	5	rooms available during 2 days. Each conference is 4 hours long, so you
	6	can organize at most 2 conferences per day in a given room.</p><p>Conferences 3, 4, 5 and 6 have to take place in room C, because
	7	it's the only one with Internet access.</p><p>Some of the speakers are not available on both days, so
	8	conferences 1, 5 and 10 have to take place on day 1, and conferences 2,
	9	3 4 and 9 on day 2.</p><p>You have made a quick poll over the python mailing list, and it
	10	turns out that people attending some of the conferences are likely to be
	11	attending some other conferences too, so you want to make sure that such
	12	conferences are not scheduled at the same time. A careful statistical
	13	study has found 4 groups of potential attendees. The first group want to
	14	attend conferences 1, 2, 3 and 10, the second conferences 2, 6, 8 and 9
	15	the third group conferences 3, 5, 6 and 7, and the last group
	16	conferences 1, 3, 7 and 8.</p><p>You've tried to put this on a whiteboard, but this quickly proved
	17	to be tedious, so you thought about using the constraint solving
	18	package.</p></div><div class="sect2"><a name="id2709551"></a><div class="sect2"><h2 class="title3"><a name="id2709551"></a>1.2. Variables, Domains and Constraints</h2></div><p>The first thing to find out in order to use the constraint package
	19	is what the variables are, what their domains are and what the
	20	constraints between variables are.</p><p>If we look at our problem, the variables are the conferences' room
	21	and time slot, and for each conference, the domain is the cross product
	22	of the set of available rooms with the set of available time slots. We
	23	could say that the conferences which require Internet access have a
	24	different domain, because they need to be in room C. This is perfectly
	25	valid. However, we will model this as a constraint.</p><p>Variables are manipulated as names, stored in character
	26	strings. Domains are instances of the fd.FiniteDomain class, which is
	27	instantiated with a list of values. Domains are manipulated through a
	28	dictionnary mapping a variable to its domain. Do not use the same domain
	29	instance for several variables, because in the current implementation,
	30	this is guaranteed to break. The code looks like this:
	31	<pre class="programlisting">
	32	<font color="#008000"># import Repository class and fd module, </font>
	33	<font color="#C00000">from</font> logilab.constraint <font color="#C00000">import</font> *
	34	variables = (<font color="#004080">'c01'</font>,<font color="#004080">'c02'</font>,<font color="#004080">'c03'</font>,<font color="#004080">'c04'</font>,<font color="#004080">'c05'</font>,<font color="#004080">'c06'</font>,<font color="#004080">'c07'</font>,<font color="#004080">'c08'</font>,<font color="#004080">'c09'</font>,<font color="#004080">'c10'</font>)
	35	values = [(room,slot)
	36	<font color="#C00000">for</font> room <font color="#C00000">in</font> (<font color="#004080">'room A'</font>,<font color="#004080">'room B'</font>,<font color="#004080">'room C'</font>)
	37	<font color="#C00000">for</font> slot <font color="#C00000">in</font> (<font color="#004080">'day 1 AM'</font>,<font color="#004080">'day 1 PM'</font>,<font color="#004080">'day 2 AM'</font>,<font color="#004080">'day 2 PM'</font>)]
	38	domains = {}
	39	<font color="#C00000">for</font> v <font color="#C00000">in</font> variables:
	40	domains[v]=fd.FiniteDomain(values)
	41	</pre>
	42	</p><p>Constraints, like domains are objects. So far the only class that
	43	can be used is fd.Expression and fd.BinaryExpression. We use the
	44	fd.make_expression factory function to build an instance of the right
	45	class, depending on the number of variables that is passed. This
	46	function takes a list of affected variables and a python expression that
	47	evaluates to true if the constraint is satisfied. </p><p>We have several constraints on our variables. First some
	48	conferences need to take place in room C:
	49	<pre class="programlisting">
	50	constraints = []
	51	<font color="#C00000">for</font> conf <font color="#C00000">in</font> (<font color="#004080">'c03'</font>,<font color="#004080">'c04'</font>,<font color="#004080">'c05'</font>,<font color="#004080">'c06'</font>):
	52	constraints.append(fd.make_expression((conf,),
	53	"%s[0] == 'room C'"%conf))
	54	</pre>
	55	</p><p>Availability of the speakers impose some more constraints:
	56	<pre class="programlisting">
	57	<font color="#C00000">for</font> conf <font color="#C00000">in</font> (<font color="#004080">'c01'</font>,<font color="#004080">'c05'</font>,<font color="#004080">'c10'</font>):
	58	constraints.append(fd.make_expression((conf,),
	59	"%s[1].startswith(<font color="#004080">'day 1'</font>)"%conf))
	60	<font color="#C00000">for</font> conf <font color="#C00000">in</font> (<font color="#004080">'c02'</font>,<font color="#004080">'c03'</font>,<font color="#004080">'c04'</font>,<font color="#004080">'c09'</font>):
	61	constraints.append(fd.make_expression((conf,),
	62	"%s[1].startswith(<font color="#004080">'day 2'</font>)"%conf))
	63	</pre>
	64	</p><p>Then we want to say that some of the conferences should not be
	65	scheduled at the same time:
	66	<pre class="programlisting">
	67	groups = ((<font color="#004080">'c01'</font>,<font color="#004080">'c02'</font>,<font color="#004080">'c03'</font>,<font color="#004080">'c10'</font>),
	68	(<font color="#004080">'c02'</font>,<font color="#004080">'c06'</font>,<font color="#004080">'c08'</font>,<font color="#004080">'c09'</font>),
	69	(<font color="#004080">'c03'</font>,<font color="#004080">'c05'</font>,<font color="#004080">'c06'</font>,<font color="#004080">'c07'</font>),
	70	(<font color="#004080">'c01'</font>,<font color="#004080">'c03'</font>,<font color="#004080">'c07'</font>,<font color="#004080">'c08'</font>))
	71	<font color="#C00000">for</font> g <font color="#C00000">in</font> groups:
	72	<font color="#C00000">for</font> conf1 <font color="#C00000">in</font> g:
	73	<font color="#C00000">for</font> conf2 <font color="#C00000">in</font> g:
	74	<font color="#C00000">if</font> conf2 > conf1:
	75	constraints.append(fd.make_expression((conf1,conf2),
	76	<font color="#004080">'%s[1] != %s[1]'</font>%\
	77	(conf1,conf2)))
	78	</pre>
	79	</p><p>Finally, no two conferences can be scheduled in the same room at
	80	the same time:
	81	<pre class="programlisting">
	82	<font color="#C00000">for</font> conf1 <font color="#C00000">in</font> variables:
	83	<font color="#C00000">for</font> conf2 <font color="#C00000">in</font> variables:
	84	<font color="#C00000">if</font> conf2 > conf1:
	85	constraints.append(fd.make_expression((conf1,conf2),
	86	<font color="#004080">'%s != %s'</font>%(conf1,conf2)))
	87	</pre>
	88	</p></div><div class="sect2"><a name="id2706665"></a><div class="sect2"><h2 class="title3"><a name="id2706665"></a>1.3. The Repository class</h2></div><p>Repository objects are used to hold the variables, domains and
	89	constraints describing the problem. A Solver object can solve the
	90	problem described by a Repository.</p><p>Here's the final touch:
	91	<pre class="programlisting">
	92	r = Repository(variables,domains,constraints)
	93	solutions = Solver().solve(r)
	94	<font color="#C00000">print</font> solutions
	95	</pre>
	96	</p></div><p>The code is available in the file conferences.py in the examples
	97	directory of the distribution. It finds 64 possible schedules in a
	98	couple of seconds on my machine.</p><div class="sect2"><a name="id2706710"></a><div class="sect2"><h2 class="title3"><a name="id2706710"></a>1.4. Performance considerations</h2></div><p>There is still a lot of things to be worked on with this
	99	package. Here are a few tips that can help you to use it in its
	100	current state:
	101	<div class="itemizedlist"><ul><li><a name="id2706724"></a><p class="in-li"><a name="id2706724"></a>Try to avoid constraints with a lot of variables. It
	102	is better to have several binary constraints than one big N-ary
	103	constraint with several 'and' conditions</p></li><li><a name="id2706733"></a><p class="in-li"><a name="id2706733"></a>If you cannot avoid constraint with lots of
	104	variable, put the constraints with less variables first in the list,
	105	because they will get evaluated before, will take less time to
	106	process, and will hopefully reduce the domains of the variables
	107	playing a role in your big constraints</p></li></ul></div>
	108	</p></div></div><div class="sect1"><a name="extending"></a><div class="sect1"><p> </p><h1 class="title2"><a name="extending"></a>2. Extending the constraint package<br><hr width="100%"></h1></div><p>WRITE ME!</p></div></div></td></tr></table></body></html>

+206

-0

doc/documentation.xml less more

	0	<?xml version="1.0" encoding="ISO-8859-1"?>
	1
	2	<!DOCTYPE article SYSTEM "/home/logilab/docbook/dtd/docbookx.dtd" >
	3	<article id='constraint-propagation-manual' lang='en'>
	4	<artheader>
	5	<title>Constraint Propagation in Python</title>
	6	<author>
	7	<firstname>Alexandre</firstname>
	8	<surname>Fayolle</surname>
	9	</author>
	10	<abstract>
	11	<simpara>This manual presents how to use the constraint package to solve
	12	constraint propagation problems in Python. It also presents the
	13	the extension mechanisms available in the package</simpara>
	14	</abstract>
	15	<copyright><year>2002-2005</year><holder>Logilab</holder>
	16	</copyright>
	17	<revhistory>
	18	<revision>
	19	<revnumber>$Revision: 1.6 $</revnumber>
	20	<date>$Date: 2005-09-05 15:56:26 $</date>
	21	<authorinitials>$Author: alf $</authorinitials>
	22	</revision>
	23	</revhistory>
	24	</artheader>
	25
	26
	27	<sect1 id='using'><title>Using the constraint package</title>
	28
	29	<sect2><title>Sample problem</title>
	30
	31	<para>Let's take a real-life problem to get started. You're organising a
	32	an international Python Programming event, and you have to schedule
	33	conferences. There are 10 different conferences, you have 3 conference
	34	rooms available during 2 days. Each conference is 4 hours long, so you
	35	can organize at most 2 conferences per day in a given room.</para>
	36
	37	<para>Conferences 3, 4, 5 and 6 have to take place in room C, because
	38	it's the only one with Internet access.</para>
	39
	40	<para>Some of the speakers are not available on both days, so
	41	conferences 1, 5 and 10 have to take place on day 1, and conferences 2,
	42	3 4 and 9 on day 2.</para>
	43
	44	<para>You have made a quick poll over the python mailing list, and it
	45	turns out that people attending some of the conferences are likely to be
	46	attending some other conferences too, so you want to make sure that such
	47	conferences are not scheduled at the same time. A careful statistical
	48	study has found 4 groups of potential attendees. The first group want to
	49	attend conferences 1, 2, 3 and 10, the second conferences 2, 6, 8 and 9
	50	the third group conferences 3, 5, 6 and 7, and the last group
	51	conferences 1, 3, 7 and 8.</para>
	52
	53	<para>You've tried to put this on a whiteboard, but this quickly proved
	54	to be tedious, so you thought about using the constraint solving
	55	package.</para>
	56
	57	</sect2>
	58
	59	<sect2><title>Variables, Domains and Constraints</title>
	60
	61	<para>The first thing to find out in order to use the constraint package
	62	is what the variables are, what their domains are and what the
	63	constraints between variables are.</para>
	64
	65	<para>If we look at our problem, the variables are the conferences' room
	66	and time slot, and for each conference, the domain is the cross product
	67	of the set of available rooms with the set of available time slots. We
	68	could say that the conferences which require Internet access have a
	69	different domain, because they need to be in room C. This is perfectly
	70	valid. However, we will model this as a constraint.</para>
	71
	72	<para>Variables are manipulated as names, stored in character
	73	strings. Domains are instances of the fd.FiniteDomain class, which is
	74	instantiated with a list of values. Domains are manipulated through a
	75	dictionnary mapping a variable to its domain. Do not use the same domain
	76	instance for several variables, because in the current implementation,
	77	this is guaranteed to break. The code looks like this:
	78	<programlisting role='python' >
	79	<emphasis role='comment'># import Repository class and fd module, </emphasis>
	80	<emphasis role='keyword'>from</emphasis> logilab.constraint <emphasis role='keyword'>import</emphasis> *
	81	variables = (<emphasis role='string'>'c01'</emphasis>,<emphasis role='string'>'c02'</emphasis>,<emphasis role='string'>'c03'</emphasis>,<emphasis role='string'>'c04'</emphasis>,<emphasis role='string'>'c05'</emphasis>,<emphasis role='string'>'c06'</emphasis>,<emphasis role='string'>'c07'</emphasis>,<emphasis role='string'>'c08'</emphasis>,<emphasis role='string'>'c09'</emphasis>,<emphasis role='string'>'c10'</emphasis>)
	82	values = [(room,slot)
	83	<emphasis role='keyword'>for</emphasis> room <emphasis role='keyword'>in</emphasis> (<emphasis role='string'>'room A'</emphasis>,<emphasis role='string'>'room B'</emphasis>,<emphasis role='string'>'room C'</emphasis>)
	84	<emphasis role='keyword'>for</emphasis> slot <emphasis role='keyword'>in</emphasis> (<emphasis role='string'>'day 1 AM'</emphasis>,<emphasis role='string'>'day 1 PM'</emphasis>,<emphasis role='string'>'day 2 AM'</emphasis>,<emphasis role='string'>'day 2 PM'</emphasis>)]
	85	domains = {}
	86	<emphasis role='keyword'>for</emphasis> v <emphasis role='keyword'>in</emphasis> variables:
	87	domains[v]=fd.FiniteDomain(values)
	88	</programlisting>
	89	</para>
	90
	91	<para>Constraints, like domains are objects. So far the only class that
	92	can be used is fd.Expression and fd.BinaryExpression. We use the
	93	fd.make_expression factory function to build an instance of the right
	94	class, depending on the number of variables that is passed. This
	95	function takes a list of affected variables and a python expression that
	96	evaluates to true if the constraint is satisfied. </para>
	97
	98	<para>We have several constraints on our variables. First some
	99	conferences need to take place in room C:
	100	<programlisting role='python' >
	101	constraints = []
	102	<emphasis role='keyword'>for</emphasis> conf <emphasis role='keyword'>in</emphasis> (<emphasis role='string'>'c03'</emphasis>,<emphasis role='string'>'c04'</emphasis>,<emphasis role='string'>'c05'</emphasis>,<emphasis role='string'>'c06'</emphasis>):
	103	constraints.append(fd.make_expression((conf,),
	104	"%s[0] == 'room C'"%conf))
	105	</programlisting >
	106	</para>
	107
	108	<para>Availability of the speakers impose some more constraints:
	109	<programlisting role='python' >
	110	<emphasis role='keyword'>for</emphasis> conf <emphasis role='keyword'>in</emphasis> (<emphasis role='string'>'c01'</emphasis>,<emphasis role='string'>'c05'</emphasis>,<emphasis role='string'>'c10'</emphasis>):
	111	constraints.append(fd.make_expression((conf,),
	112	"%s[1].startswith(<emphasis role='string'>'day 1'</emphasis>)"%conf))
	113	<emphasis role='keyword'>for</emphasis> conf <emphasis role='keyword'>in</emphasis> (<emphasis role='string'>'c02'</emphasis>,<emphasis role='string'>'c03'</emphasis>,<emphasis role='string'>'c04'</emphasis>,<emphasis role='string'>'c09'</emphasis>):
	114	constraints.append(fd.make_expression((conf,),
	115	"%s[1].startswith(<emphasis role='string'>'day 2'</emphasis>)"%conf))
	116	</programlisting>
	117	</para>
	118
	119	<para>Then we want to say that some of the conferences should not be
	120	scheduled at the same time:
	121	<programlisting role='python'>
	122	groups = ((<emphasis role='string'>'c01'</emphasis>,<emphasis role='string'>'c02'</emphasis>,<emphasis role='string'>'c03'</emphasis>,<emphasis role='string'>'c10'</emphasis>),
	123	(<emphasis role='string'>'c02'</emphasis>,<emphasis role='string'>'c06'</emphasis>,<emphasis role='string'>'c08'</emphasis>,<emphasis role='string'>'c09'</emphasis>),
	124	(<emphasis role='string'>'c03'</emphasis>,<emphasis role='string'>'c05'</emphasis>,<emphasis role='string'>'c06'</emphasis>,<emphasis role='string'>'c07'</emphasis>),
	125	(<emphasis role='string'>'c01'</emphasis>,<emphasis role='string'>'c03'</emphasis>,<emphasis role='string'>'c07'</emphasis>,<emphasis role='string'>'c08'</emphasis>))
	126	<emphasis role='keyword'>for</emphasis> g <emphasis role='keyword'>in</emphasis> groups:
	127	<emphasis role='keyword'>for</emphasis> conf1 <emphasis role='keyword'>in</emphasis> g:
	128	<emphasis role='keyword'>for</emphasis> conf2 <emphasis role='keyword'>in</emphasis> g:
	129	<emphasis role='keyword'>if</emphasis> conf2 > conf1:
	130	constraints.append(fd.make_expression((conf1,conf2),
	131	<emphasis role='string'>'%s[1] != %s[1]'</emphasis>%\
	132	(conf1,conf2)))
	133	</programlisting>
	134	</para>
	135
	136	<para>Finally, no two conferences can be scheduled in the same room at
	137	the same time:
	138	<programlisting role='python'>
	139	<emphasis role='keyword'>for</emphasis> conf1 <emphasis role='keyword'>in</emphasis> variables:
	140	<emphasis role='keyword'>for</emphasis> conf2 <emphasis role='keyword'>in</emphasis> variables:
	141	<emphasis role='keyword'>if</emphasis> conf2 > conf1:
	142	constraints.append(fd.make_expression((conf1,conf2),
	143	<emphasis role='string'>'%s != %s'</emphasis>%(conf1,conf2)))
	144	</programlisting>
	145	</para>
	146
	147	</sect2>
	148
	149	<sect2><title>The Repository class</title>
	150	<para>Repository objects are used to hold the variables, domains and
	151	constraints describing the problem. A Solver object can solve the
	152	problem described by a Repository.</para>
	153
	154	<para>Here's the final touch:
	155	<programlisting role='python'>
	156	r = Repository(variables,domains,constraints)
	157	solutions = Solver().solve(r)
	158	<emphasis role='keyword'>print</emphasis> solutions
	159	</programlisting>
	160	</para>
	161	</sect2>
	162
	163	<para>The code is available in the file conferences.py in the examples
	164	directory of the distribution. It finds 64 possible schedules in a
	165	couple of seconds on my machine.</para>
	166
	167	<sect2><title>Performance considerations</title>
	168	<para>There is still a lot of things to be worked on with this
	169	package. Here are a few tips that can help you to use it in its
	170	current state:
	171	<itemizedlist>
	172	<listitem><para>Try to avoid constraints with a lot of variables. It
	173	is better to have several binary constraints than one big N-ary
	174	constraint with several 'and' conditions</para></listitem>
	175
	176	<listitem><para>If you cannot avoid constraint with lots of
	177	variable, put the constraints with less variables first in the list,
	178	because they will get evaluated before, will take less time to
	179	process, and will hopefully reduce the domains of the variables
	180	playing a role in your big constraints</para>
	181	</listitem>
	182	</itemizedlist>
	183	</para>
	184	</sect2>
	185
	186	</sect1>
	187	<sect1 id='extending'><title>Extending the constraint package</title>
	188
	189	<para>WRITE ME!</para>
	190	<!--
	191	<sect2><title>The interfaces</title>
	192	<para></para>
	193	</sect2>
	194
	195	<sect2><title>The abstract implementations</title>
	196	<para></para>
	197	</sect2>
	198
	199	<sect2><title>AbstractConstraint Narrowing algorithm</title>
	200	<para></para>
	201	</sect2>
	202	-->
	203
	204	</sect1>
	205	</article>

+62

-0

examples/chess.py less more

	0	"""Chess constraints and domains"""
	1
	2
	3	from logilab.constraint import fd
	4	from logilab.constraint.propagation import AbstractConstraint, ConsistencyFailure
	5
	6	class ChessDomain(fd.FiniteDomain):
	7	def __init__(self, size):
	8	values = [(i,j) for i in range(size) for j in range(size)]
	9	fd.FiniteDomain.__init__(self, values)
	10
	11	def __repr__(self):
	12	vals = self.getValues()
	13	vals.sort()
	14	return '<ChessDomain %s>' % str(vals)
	15
	16	class QueensConstraint(AbstractConstraint):
	17	def __init__(self, variables):
	18	AbstractConstraint.__init__(self, variables)
	19
	20	def __repr__(self):
	21	return '<QueensConstraint %s>' % str(self._variables)
	22
	23	def narrow(self, domains):
	24	maybe_entailed = 1
	25	var1 = self._variables[0]
	26	dom1 = domains[var1]
	27	values1 = dom1.getValues()
	28	var2 = self._variables[1]
	29	dom2 = domains[var2]
	30	values2 = dom2.getValues()
	31
	32	keep1 = {}
	33	keep2 = {}
	34	maybe_entailed = 1
	35	for val1 in values1:
	36	val1_0 = val1[0]
	37	val1_1 = val1[1]
	38	for val2 in values2:
	39	if val1 in keep1 and val2 in keep2 and maybe_entailed == 0:
	40	continue
	41	val2_0 = val2[0]
	42	val2_1 = val2[1]
	43	if val1_0 < val2_0 and \
	44	val1_1 != val2_1 and \
	45	abs(val1_0-val2_0) != abs(val1_1-val2_1):
	46	keep1[val1] = 1
	47	keep2[val2] = 1
	48	else:
	49	maybe_entailed = 0
	50
	51	try:
	52	dom1.removeValues([val for val in values1 if val not in keep1])
	53	dom2.removeValues([val for val in values2 if val not in keep2])
	54	except ConsistencyFailure:
	55	raise ConsistencyFailure('Inconsistency while applying %s' % \
	56	repr(self))
	57	except Exception:
	58	print self, kwargs
	59	raise
	60	return maybe_entailed
	61

+64

-0

examples/conferences.py less more

	0	# (c) 2000-2001 LOGILAB S.A. (Paris, FRANCE).
	1	# http://www.logilab.fr/ -- mailto:contact@logilab.fr
	2	#
	3	# This program is free software; you can redistribute it and/or modify it under
	4	# the terms of the GNU General Public License as published by the Free Software
	5	# Foundation; either version 2 of the License, or (at your option) any later
	6	# version.
	7	#
	8	# This program is distributed in the hope that it will be useful, but WITHOUT
	9	# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
	10	# FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
	11	#
	12	# You should have received a copy of the GNU General Public License along with
	13	# this program; if not, write to the Free Software Foundation, Inc.,
	14	# 59 Temple Place - Suite 330, Boston, MA 02111-1307
	15	# USA.
	16
	17
	18	# import Repository, ListDomain and MathematicConstraint
	19	from logilab.constraint import *
	20	variables = ('c01','c02','c03','c04','c05','c06','c07','c08','c09','c10')
	21	values = [(room,slot)
	22	for room in ('room A','room B','room C')
	23	for slot in ('day 1 AM','day 1 PM','day 2 AM','day 2 PM')]
	24	domains = {}
	25	for v in variables:
	26	domains[v]=fd.FiniteDomain(values)
	27	constraints = []
	28
	29	# Internet access is in room C only
	30	for conf in ('c03','c04','c05','c06'):
	31	constraints.append(fd.make_expression((conf,),
	32	"%s[0] == 'room C'"%conf))
	33
	34	# Speakers only available on day 1
	35	for conf in ('c01','c05','c10'):
	36	constraints.append(fd.make_expression((conf,),
	37	"%s[1].startswith('day 1')"%conf))
	38	# Speakers only available on day 2
	39	for conf in ('c02','c03','c04','c09'):
	40	constraints.append(fd.make_expression((conf,),
	41	"%s[1].startswith('day 2')"%conf))
	42
	43	# try to satisfy people willing to attend several conferences
	44	groups = (('c01','c02','c03','c10'),
	45	('c02','c06','c08','c09'),
	46	('c03','c05','c06','c07'),
	47	('c01','c03','c07','c08'))
	48	for g in groups:
	49	for conf1 in g:
	50	for conf2 in g:
	51	if conf2 > conf1:
	52	print '%s[1] != %s[1]'%(conf1,conf2)
	53	constraints.append(fd.make_expression((conf1,conf2),
	54	'%s[1] != %s[1]'%\
	55	(conf1,conf2)))
	56
	57
	58	constraints.append(fd.AllDistinct(variables))
	59
	60	r = Repository(variables,domains,constraints)
	61	solutions = Solver().solve(r)
	62	print solutions
	63	print len(solutions)

+88

-0

examples/intervals.py less more

	0	#!/usr/bin/python
	1	# -- coding: ISO-8859-1 --
	2	# (c) 2000-2001 LOGILAB S.A. (Paris, FRANCE).
	3	# http://www.logilab.fr/ -- mailto:contact@logilab.fr
	4	#
	5	# This program is free software; you can redistribute it and/or modify it under
	6	# the terms of the GNU General Public License as published by the Free Software
	7	# Foundation; either version 2 of the License, or (at your option) any later
	8	# version.
	9	#
	10	# This program is distributed in the hope that it will be useful, but WITHOUT
	11	# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
	12	# FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
	13	#
	14	# You should have received a copy of the GNU General Public License along with
	15	# this program; if not, write to the Free Software Foundation, Inc.,
	16	# 59 Temple Place - Suite 330, Boston, MA 02111-1307
	17	# USA.
	18
	19
	20	"""
	21	Example problem with intervals
	22	"""
	23
	24	from __future__ import generators
	25
	26	from logilab.constraint import *
	27	from logilab.constraint.distributors import *
	28
	29	def intervals(size=5,verbose=0):
	30	variables = []
	31	domains = {}
	32	constraints = []
	33	for i in range(size):
	34	name = 'v%02d'%i
	35	variables.append(name)
	36	domains[name] = fi.FiniteIntervalDomain(0, size*5, 5)
	37
	38	for i, q1 in enumerate(variables):
	39	if i+1 == len(variables):
	40	continue
	41	q2 = variables[i+1]
	42	c = fi.StartsAfterEnd(q1, q2)
	43	constraints.append(c)
	44
	45	## print domains
	46	## print constraints
	47	r = Repository(variables,domains,constraints)
	48	for sol in Solver(fi.FiniteIntervalDistributor()).solve_all(r,verbose):
	49	yield sol
	50
	51	def main(args = None):
	52	import sys,getopt
	53	if args is None:
	54	args = sys.argv[1:]
	55	opts,args = getopt.getopt(args,'dvf')
	56	display = 0
	57	verbose = 0
	58	first = 0
	59	if args:
	60	size = int(args[0])
	61	else:
	62	size = 8
	63	for o,v in opts:
	64	if o == '-d':
	65	display = 1
	66	elif o == '-v':
	67	verbose += 1
	68	elif o == "-f":
	69	first = 1
	70	count = 0
	71	for sol in intervals(size,verbose):
	72	count += 1
	73	if display:
	74	print sol
	75	print ''80
	76	if first:
	77	break
	78	if not display:
	79	print 'Use -d option to display solutions'
	80	print count,'solutions found.'
	81
	82	if __name__ == '__main__':
	83	## import hotshot
	84	## p = hotshot.Profile('/tmp/queens.prof')
	85	## p.runcall(main)
	86	## p.close()
	87	main()

+112

-0

examples/knights.py less more

	0	#!/usr/bin/env python2.3
	1	# -- coding: ISO-8859-1 --
	2	"""Knight tour problem:
	3	Place n*n values on a checker so
	4	that consecutive values are a knight's
	5	move away from each other"""
	6
	7
	8	# This program is free software; you can redistribute it and/or modify it under
	9	# the terms of the GNU General Public License as published by the Free Software
	10	# Foundation; either version 2 of the License, or (at your option) any later
	11	# version.
	12	#
	13	# This program is distributed in the hope that it will be useful, but WITHOUT
	14	# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
	15	# FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
	16	#
	17	# You should have received a copy of the GNU General Public License along with
	18	# this program; if not, write to the Free Software Foundation, Inc.,
	19	# 59 Temple Place - Suite 330, Boston, MA 02111-1307
	20	# USA.
	21
	22
	23	from logilab.constraint import *
	24	from logilab.constraint.distributors import *
	25
	26	def knight_tour(size=6,verbose=0):
	27	variables = []
	28	domains = {}
	29	constraints = []
	30	black_checker=[]
	31	# the black tiles
	32	white_checker=[]
	33	#the white tiles: one less if n is odd
	34	for row in range(size):
	35	for column in range(size):
	36	if (row+column)%2==0:
	37	black_checker.append((row,column))
	38	else:
	39	white_checker.append((row, column))
	40
	41	# One variable for each step in the tour
	42	for i in range(size*size):
	43	name = 'x%02d'%i
	44	variables.append(name)
	45	# The knight's move jumps from black to white
	46	# and vice versa, so we make all the even steps black
	47	# and all the odd ones white.
	48	if i%2==0:
	49	domains[name] = fd.FiniteDomain(black_checker)
	50	else:
	51	domains[name] = fd.FiniteDomain(white_checker)
	52	if i > 0:
	53	j = i -1
	54	k1 = 'x%02d'%j
	55	k2 = 'x%02d'%i
	56	# the knight's move constraint
	57	c = fd.make_expression((k1,k2),
	58	'abs(%(v1)s[0]-%(v2)s[0]) + abs(%(v1)s[1]-%(v2)s[1]) == 3'%\
	59	{'v1':k1,'v2':k2})
	60	constraints.append(c)
	61	c = fd.make_expression((k1,k2),
	62	'abs(abs(%(v1)s[0]-%(v2)s[0]) - abs(%(v1)s[1]-%(v2)s[1])) == 1'%\
	63	{'v1':k1,'v2':k2})
	64	constraints.append(c)
	65	constraints.append(fd.AllDistinct(variables))
	66	half = size/2
	67	r = Repository(variables,domains,constraints)
	68	sol = Solver(EnumeratorDistributor()).solve_one(r,verbose)
	69	return sol
	70
	71	def draw_solution(sol, size):
	72	# change the keys into elements, elements into keys
	73	# to display the results.
	74	# I'm sure there's a better way to do this, but I'm
	75	# new to python
	76	board = ''
	77	board += '_'(size3+1)+'\n'
	78	squares = {}
	79	for t in sol.items():
	80	squares[(t[1][0]*size)+t[1][1]]=t[0]
	81	for i in range(size):
	82	for j in range(size):
	83	# find the variable whose value is (i,j)
	84	square = squares[i*size+j]
	85	# numbering should start from 1 ,not 0
	86	intsquare = int(square[1:4]) + 1
	87	board+='\|%02s'%intsquare
	88	board+='\|\n'
	89	board += '¯'(size3+1)+'\n'
	90	print board
	91
	92
	93	if __name__ == '__main__':
	94	import sys,getopt
	95	opts,args = getopt.getopt(sys.argv[1:],'dv')
	96	display = 0
	97	verbose = 0
	98	if args:
	99	size = int(args[0])
	100	else:
	101	size = 6
	102	for o,v in opts:
	103	if o == '-d':
	104	display = 1
	105	elif o == '-v':
	106	verbose += 2
	107	count = 0
	108	sol = knight_tour(size,verbose)
	109	if display:
	110	print 'Solution found:'
	111	draw_solution(sol,size)

+76

-0

examples/menza.py less more

	0	"""
	1	Solve a puzzle that got discussed on c.l.p. on october 2002
	2
	3	ABC*DE=FGHIJ with all letters different and in domain [0,9]
	4	"""
	5	from __future__ import generators
	6
	7	from logilab.constraint import *
	8	from logilab.constraint.psyco_wrapper import psyobj
	9	from logilab.constraint.propagation import BasicConstraint, ConsistencyFailure
	10
	11	class DistinctDigits(BasicConstraint,psyobj):
	12	def __init__(self,variable):
	13	BasicConstraint.__init__(self,variable,None,None)
	14
	15	def narrow(self,domains):
	16	domain = domains[self._variable]
	17	for v in domain.getValues():
	18	s = str(v)
	19	for d in ('0','1','2','3','4','5','6','7','8','9'):
	20	if s.count(d) not in (0,1):
	21	domain.removeValue(v)
	22	break
	23	return 1
	24
	25	def __repr__(self):
	26
	27	return '<DistinctDigits on variable %s>'%self._variable
	28
	29
	30	def menza() :
	31	"""
	32	"""
	33
	34	VARS='ab'
	35	variables = list(VARS)
	36	domains = {}
	37	constraints = []
	38
	39	domains['a'] = fd.FiniteDomain(range(0,1000))
	40	domains['b'] = fd.FiniteDomain(range(0,100))
	41
	42	me = fd.make_expression
	43
	44	for v in variables:
	45	constraints.append(DistinctDigits(v))
	46	dist = ['10000 < a*b ']
	47	for digit in range(10):
	48	dist.append('("%%.3d%%.2d%%.5d" %% (a,b,a*b)).count("%d")==1'%digit)
	49	constraints.append(me(('a','b'),' and '.join(dist)))
	50	r = Repository(variables, domains, constraints)
	51	return r
	52
	53	if __name__ == '__main__' :
	54	import sys,getopt
	55	opts,args = getopt.getopt(sys.argv[1:],'dv')
	56	verbose = 0
	57	display = 0
	58	create_problem=menza
	59	for o,v in opts:
	60	if o == '-v':
	61	verbose += 1
	62	elif o == '-d':
	63	display = 1
	64
	65
	66	r = create_problem()
	67	print 'problem created. let us solve it.'
	68	s = []
	69	for sol in Solver().solve_all(r,verbose):
	70	s.append(sol)
	71	if display:
	72	sol['c'] = sol['a']*sol['b']
	73	print "%(a)s x %(b)s = %(c)s" % sol
	74	if not display:
	75	print 'Found %d solutions'%len(s)

+82

-0

examples/menza2.py less more

	0	"""
	1	Solve a puzzle that got discussed on c.l.p. on october 2002
	2
	3	ABC*DE=FGHIJ with all letters different and in domain [0,9]
	4	"""
	5	from __future__ import generators
	6
	7	from logilab.constraint import *
	8	from logilab.constraint.distributors import DichotomyDistributor
	9	from logilab.constraint.propagation import BasicConstraint, ConsistencyFailure
	10
	11	class DistinctDigits(BasicConstraint):
	12	def __init__(self,variable):
	13	BasicConstraint.__init__(self,variable,None,None)
	14
	15	def narrow(self,domains):
	16	domain = domains[self._variable]
	17	try:
	18	for v in domain.getValues():
	19	s = str(v)
	20	for d in ('0','1','2','3','4','5','6','7','8','9'):
	21	if s.count(d) not in (0,1):
	22	domain.removeValue(v)
	23	break
	24	except ConsistencyFailure, e:
	25	raise ConsistencyFailure('inconsistency while applying %s'%repr(self))
	26	return 1
	27
	28	def __repr__(self):
	29	return '<DistinctDigits>'
	30
	31
	32
	33	def mensa() :
	34	"""
	35	ABC*DE=FGHIJ with all letters different and in domain [0,9]
	36	"""
	37
	38	VARS='xy'
	39	variables = list(VARS)
	40	domains = {}
	41	constraints = []
	42
	43	# x = ABC and y = DE, x*y = FGHIJ
	44	domains['x'] = fd.FiniteDomain(range(0,1000))
	45	domains['y'] = fd.FiniteDomain(range(0,100))
	46
	47	# x and y must have distinct digits themselves
	48	# (for example this will remove 232 from x's domain)
	49	for v in variables:
	50	constraints.append(DistinctDigits(v))
	51
	52	# x,y and x*y must have distinct digits
	53	dist = []
	54	for digit in range(10):
	55	dist.append('("%%.3d%%.2d%%.5d" %% (x,y,x*y)).count("%d")==1'%digit)
	56	c = ' and '.join(dist)
	57	constraints.append(fd.make_expression(('x','y'),c))
	58	r = Repository(variables, domains, constraints)
	59	return r
	60
	61	if __name__ == '__main__' :
	62	import sys,getopt
	63	opts,args = getopt.getopt(sys.argv[1:],'dv')
	64	verbose = 0
	65	display = 0
	66	for o,v in opts:
	67	if o == '-v':
	68	verbose += 1
	69	elif o == '-d':
	70	display = 1
	71
	72	r = mensa()
	73	print 'problem created. let us solve it.'
	74	s = []
	75	for sol in Solver().solve_all(r,verbose):
	76	s.append(sol)
	77	if display:
	78	sol['c'] = sol['x']*sol['y']
	79	print "%(x)s x %(y)s = %(c)s" % sol
	80	if not display:
	81	print 'Found %d solutions'%len(s)

+23

-0

examples/menza_brute_force.py less more

	0	try:
	1	import psyco
	2	psyco.full()
	3	except ImportError:
	4	print 'Psyco not available'
	5
	6	def menza():
	7	sol = []
	8	all_digits = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]
	9	for a in range(1000) :
	10	for b in range(100) :
	11	c = a*b
	12	if c > 9999:
	13	digits = list("%.3d%.2d%.5d" % (a, b, c))
	14	digits.sort()
	15	if digits == all_digits :
	16	sol.append({'a': a, 'b': b})
	17	print "%.3d x %.2d = %.5d" % (a, b, c)
	18	return sol
	19
	20	if __name__ == '__main__':
	21	sol = menza()
	22	print len(sol)

+75

-0

examples/money.py less more

	0	#!/usr/bin/env python2.2
	1
	2	# (c) 2000-2001 LOGILAB S.A. (Paris, FRANCE).
	3	# http://www.logilab.fr/ -- mailto:contact@logilab.fr
	4	#
	5	# This program is free software; you can redistribute it and/or modify it under
	6	# the terms of the GNU General Public License as published by the Free Software
	7	# Foundation; either version 2 of the License, or (at your option) any later
	8	# version.
	9	#
	10	# This program is distributed in the hope that it will be useful, but WITHOUT
	11	# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
	12	# FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
	13	#
	14	# You should have received a copy of the GNU General Public License along with
	15	# this program; if not, write to the Free Software Foundation, Inc.,
	16	# 59 Temple Place - Suite 330, Boston, MA 02111-1307
	17	# USA.
	18
	19
	20	from logilab.constraint import *
	21
	22	def money(verbose=0):
	23	""" SEND
	24	+MORE
	25	-------
	26	MONEY
	27	"""
	28	digits = range(10)
	29	variables = list('sendmory')
	30	domains = {}
	31	constraints = []
	32	for v in variables:
	33	domains[v] = fd.FiniteDomain(digits)
	34
	35	constraints.append(fd.AllDistinct(variables))
	36	constraints.append(fd.NotEquals('m', 0))
	37	constraints.append(fd.NotEquals('s', 0))
	38	constraints.append(fd.make_expression(('s', 'm', 'o'),
	39	'(s+m) in (10m+o,10m+o-1)'))
	40	constraints.append(fd.make_expression(('d', 'e', 'y'),
	41	'(d+e)%10 == y'))
	42	constraints.append(fd.make_expression(('n', 'r', 'e'),
	43	'(n+r)%10 in (e,e-1)'))
	44	constraints.append(fd.make_expression(('o', 'e', 'n'),
	45	'(o+e)%10 in (n,n-1)'))
	46	constraints.append(fd.make_expression(variables,
	47	'm10000+(o-m-s)1000+(n-o-e)100+(e-r-n)10+y-e-d == 0'))
	48	r = Repository(variables, domains, constraints)
	49	s = Solver().solve_one(r, verbose)
	50	return s
	51
	52	def display_solution(d):
	53	for s in d:
	54	print ' SEND\t \t',' %(s)d%(e)d%(n)d%(d)d'%s
	55	print '+ MORE\t \t','+ %(m)d%(o)d%(r)d%(e)d'%s
	56	print '------\t-->\t','------'
	57	print ' MONEY\t \t',' %(m)d%(o)d%(n)d%(e)d%(y)d'%s
	58	print
	59
	60	if __name__ == '__main__':
	61	import sys, getopt
	62	opts, args = getopt.getopt(sys.argv[1:], 'dv')
	63	verbose = 0
	64	display = 0
	65	for o,v in opts:
	66	if o == '-v':
	67	verbose += 1
	68	if o == '-d':
	69	display = 1
	70	sol = money(verbose)
	71	if display:
	72	display_solution([sol])
	73	else:
	74	print sol

+74

-0

examples/money2.py less more

	0	#!/usr/bin/env python2.2
	1
	2	# (c) 2000-2001 LOGILAB S.A. (Paris, FRANCE).
	3	# http://www.logilab.fr/ -- mailto:contact@logilab.fr
	4	#
	5	# This program is free software; you can redistribute it and/or modify it under
	6	# the terms of the GNU General Public License as published by the Free Software
	7	# Foundation; either version 2 of the License, or (at your option) any later
	8	# version.
	9	#
	10	# This program is distributed in the hope that it will be useful, but WITHOUT
	11	# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
	12	# FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
	13	#
	14	# You should have received a copy of the GNU General Public License along with
	15	# this program; if not, write to the Free Software Foundation, Inc.,
	16	# 59 Temple Place - Suite 330, Boston, MA 02111-1307
	17	# USA.
	18
	19
	20	from logilab.constraint import *
	21	from logilab.constraint.distributors import SplitDistributor
	22
	23	def money(verbose=0):
	24	""" SEND
	25	+MORE
	26	-------
	27	MONEY
	28	"""
	29	digits = range(10)
	30	variables = list('sendmory')
	31	domains = {}
	32	constraints = []
	33	for v in variables:
	34	domains[v] = fd.FiniteDomain(digits)
	35
	36	constraints.append(fd.AllDistinct(variables))
	37	constraints.append(fd.NotEquals('m', 0))
	38	constraints.append(fd.NotEquals('s', 0))
	39	for v1 in variables:
	40	for v2 in variables:
	41	if v1 < v2:
	42	constraints.append(fd.make_expression((v1, v2),
	43	'%s != %s'%(v1, v2)))
	44	constraints.append(fd.make_expression(variables,
	45	'm10000+(o-m-s)1000+(n-o-e)100+(e-r-n)10+y-e-d == 0'))
	46	r = Repository(variables, domains, constraints)
	47	s = Solver(distributor=SplitDistributor(10)).solve_one(r, verbose)
	48	return s
	49
	50	def display_solution(d):
	51	print ' SEND\t \t',' %(s)d%(e)d%(n)d%(d)d'%d
	52	print '+ MORE\t \t','+ %(m)d%(o)d%(r)d%(e)d'%d
	53	print '------\t-->\t','------'
	54	print ' MONEY\t \t',' %(m)d%(o)d%(n)d%(e)d%(y)d'%d
	55
	56	if __name__ == '__main__':
	57	print 'WARNING!'
	58	print 'This example takes looooooooooooooots of CPU to complete.'
	59	print 'try money.py for a faster version.'
	60	import sys, getopt
	61	opts, args = getopt.getopt(sys.argv[1:], 'dv')
	62	verbose = 0
	63	display = 0
	64	for o,v in opts:
	65	if o == '-v':
	66	verbose += 1
	67	if o == '-d':
	68	display = 1
	69	sol = money(verbose)
	70	if display:
	71	display_solution(sol)
	72	else:
	73	print sol

+126

-0

examples/queens.py less more

	0	#!/usr/bin/env python
	1	# -- coding: ISO-8859-1 --
	2	"""N queens problem
	3	The problem is solved with a EnumeratorDistributor splitting
	4	the smallest domain in at most N subdomains."""
	5
	6	# (c) 2000-2001 LOGILAB S.A. (Paris, FRANCE).
	7	# http://www.logilab.fr/ -- mailto:contact@logilab.fr
	8	#
	9	# This program is free software; you can redistribute it and/or modify it under
	10	# the terms of the GNU General Public License as published by the Free Software
	11	# Foundation; either version 2 of the License, or (at your option) any later
	12	# version.
	13	#
	14	# This program is distributed in the hope that it will be useful, but WITHOUT
	15	# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
	16	# FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
	17	#
	18	# You should have received a copy of the GNU General Public License along with
	19	# this program; if not, write to the Free Software Foundation, Inc.,
	20	# 59 Temple Place - Suite 330, Boston, MA 02111-1307
	21	# USA.
	22
	23	from __future__ import generators
	24
	25	from logilab.constraint import *
	26	from logilab.constraint.distributors import *
	27
	28
	29	distributors = {
	30	"enum" : EnumeratorDistributor,
	31	"dicho" : DichotomyDistributor,
	32	"naive" : NaiveDistributor,
	33	}
	34
	35	def queens(size=8,verbose=0,distrib="enum"):
	36	variables = []
	37	domains = {}
	38	constraints = []
	39	for i in range(size):
	40	name = 'Q%02d'%i
	41	variables.append(name)
	42	domains[name] = fd.FiniteDomain([(i,j) for j in range(size)])
	43
	44	for q1 in variables:
	45	for q2 in variables:
	46	if q1 < q2:
	47	c = fd.make_expression((q1,q2),
	48	'%(q1)s[0] < %(q2)s[0] and '
	49	'%(q1)s[1] != %(q2)s[1] and '
	50	'abs(%(q1)s[0]-%(q2)s[0]) != '
	51	'abs(%(q1)s[1]-%(q2)s[1])'%\
	52	{'q1':q1,'q2':q2})
	53	constraints.append(c)
	54	r = Repository(variables,domains,constraints)
	55	Distrib = distributors[distrib]
	56	for sol in Solver(Distrib()).solve_all(r,verbose):
	57	yield sol
	58
	59
	60
	61	def draw_solution(s):
	62	size = len(s)
	63	queens = {}
	64	board = ''
	65	for q,p in s.items():
	66	queens[p]=q
	67	board += '_'(size2+1)+'\n'
	68	for i in range(size):
	69	#
	70	for j in range(size):
	71	q = queens.get((i,j))
	72	if q is None:
	73	board+='\|'+'·-'[(i+j)%2]
	74	else:
	75	board+='\|Q'
	76	board+='\|\n'
	77	board += '¯'(size2+1)
	78	print board
	79
	80
	81	def main(args = None):
	82	import sys,getopt
	83	if args is None:
	84	args = sys.argv[1:]
	85	opts,args = getopt.getopt(args,'dvfD:')
	86	display = 0
	87	verbose = 0
	88	first = 0
	89	distrib = "enum"
	90	if args:
	91	size = int(args[0])
	92	else:
	93	size = 8
	94	for o,v in opts:
	95	if o == '-d':
	96	display = 1
	97	elif o == '-v':
	98	verbose += 1
	99	elif o == "-f":
	100	first = 1
	101	elif o == "-D":
	102	if v in distributors:
	103	distrib = v
	104	else:
	105	raise RuntimeError("Distributor must be one of %s" % ", ".join(distributors.keys()) )
	106
	107	count = 0
	108	for sol in queens(size,verbose,distrib):
	109	count += 1
	110	if display:
	111	print 'solution #%d'%count
	112	draw_solution(sol)
	113	print ''80
	114	if first:
	115	break
	116	if not display:
	117	print 'Use -d option to display solutions'
	118	print count,'solutions found.'
	119
	120	if __name__ == '__main__':
	121	## import hotshot
	122	## p = hotshot.Profile('/tmp/queens.prof')
	123	## p.runcall(main)
	124	## p.close()
	125	main()

+127

-0

examples/queens2.py less more

	0	#!/usr/bin/env python
	1	# -- coding: ISO-8859-1 --
	2	"""N queens problem
	3	The problem is solved with a EnumeratorDistributor splitting
	4	the smallest domain in at most N subdomains."""
	5
	6	# (c) 2000-2001 LOGILAB S.A. (Paris, FRANCE).
	7	# http://www.logilab.fr/ -- mailto:contact@logilab.fr
	8	#
	9	# This program is free software; you can redistribute it and/or modify it under
	10	# the terms of the GNU General Public License as published by the Free Software
	11	# Foundation; either version 2 of the License, or (at your option) any later
	12	# version.
	13	#
	14	# This program is distributed in the hope that it will be useful, but WITHOUT
	15	# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
	16	# FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
	17	#
	18	# You should have received a copy of the GNU General Public License along with
	19	# this program; if not, write to the Free Software Foundation, Inc.,
	20	# 59 Temple Place - Suite 330, Boston, MA 02111-1307
	21	# USA.
	22
	23
	24	from __future__ import generators
	25
	26	from logilab.constraint import *
	27	from logilab.constraint.distributors import *
	28
	29	distributors = {
	30	"enum" : EnumeratorDistributor,
	31	"dicho" : DichotomyDistributor,
	32	"naive" : NaiveDistributor,
	33	"random" : RandomizingDistributor,
	34	}
	35
	36	def queens(size=8,verbose=0,distrib="enum"):
	37	variables = []
	38	domains = {}
	39	constraints = []
	40	for i in range(size):
	41	name = 'Q%02d'%i
	42	variables.append(name)
	43	domains[name] = fd.FiniteDomain( range(size) )
	44
	45	for r1 in range(size):
	46	q1 = 'Q%02d' % r1
	47	for r2 in range(r1+1, size):
	48	q2 = 'Q%02d' % r2
	49	D = {'q1':q1,'q2':q2, 'diag':(r2-r1) }
	50	c = fd.make_expression((q1,q2),
	51	'%(q1)s != %(q2)s and '
	52	'%(diag)s != abs(%(q1)s-%(q2)s)'% D )
	53	constraints.append(c)
	54
	55	r = Repository(variables,domains,constraints)
	56	Distrib = distributors[distrib]
	57	for sol in Solver(Distrib()).solve_all(r,verbose):
	58	yield sol
	59
	60
	61
	62	def draw_solution(s):
	63	size = len(s)
	64	board = ''
	65	queens = s.items()
	66	queens.sort()
	67	board += '_'(size2+1)+'\n'
	68	for i in range(size):
	69	qj = queens[i][1]
	70	for j in range(size):
	71	if j != qj:
	72	board+='\|'+'·-'[(i+j)%2]
	73	else:
	74	board+='\|Q'
	75	board+='\|\n'
	76	board += '¯'(size2+1)
	77	print board
	78
	79
	80	def main(args = None):
	81	import sys,getopt
	82	if args is None:
	83	args = sys.argv[1:]
	84	opts,args = getopt.getopt(args,'dvfD:')
	85	display = 0
	86	verbose = 0
	87	first = 0
	88	distrib = "enum"
	89	if args:
	90	size = int(args[0])
	91	else:
	92	size = 8
	93	for o,v in opts:
	94	if o == '-d':
	95	display = 1
	96	elif o == '-v':
	97	verbose += 1
	98	elif o == "-f":
	99	first = 1
	100	elif o == "-D":
	101	if v in distributors:
	102	distrib = v
	103	else:
	104	raise RuntimeError("Distributor must be one of %s" % ", ".join(distributors.keys()) )
	105	count = 0
	106	for sol in queens(size,verbose,distrib):
	107	count += 1
	108	if display:
	109	print 'solution #%d'%count
	110	draw_solution(sol)
	111	print ''80
	112	if first:
	113	break
	114	if not display:
	115	print 'Use -d option to display solutions'
	116	print count,'solutions found.'
	117
	118	print "Domains copy:", fd.FiniteDomain._copy_count
	119	print "Domains writes:", fd.FiniteDomain._write_count
	120
	121	if __name__ == '__main__':
	122	## import hotshot
	123	## p = hotshot.Profile('/tmp/queens.prof')
	124	## p.runcall(main)
	125	## p.close()
	126	main()

+108

-0

examples/queens3.py less more

	0	#!/usr/bin/env python
	1	# -- coding: ISO-8859-1 --
	2	"""N queens problem
	3	The problem is solved with a EnumeratorDistributor splitting
	4	the smallest domain in at most N subdomains."""
	5
	6	# (c) 2000-2001 LOGILAB S.A. (Paris, FRANCE).
	7	# http://www.logilab.fr/ -- mailto:contact@logilab.fr
	8	#
	9	# This program is free software; you can redistribute it and/or modify it under
	10	# the terms of the GNU General Public License as published by the Free Software
	11	# Foundation; either version 2 of the License, or (at your option) any later
	12	# version.
	13	#
	14	# This program is distributed in the hope that it will be useful, but WITHOUT
	15	# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
	16	# FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
	17	#
	18	# You should have received a copy of the GNU General Public License along with
	19	# this program; if not, write to the Free Software Foundation, Inc.,
	20	# 59 Temple Place - Suite 330, Boston, MA 02111-1307
	21	# USA.
	22
	23
	24	from __future__ import generators
	25
	26	from logilab.constraint import *
	27	from logilab.constraint.distributors import *
	28	from chess import ChessDomain, QueensConstraint
	29
	30	def queens(size=8,verbose=0):
	31	variables = []
	32	domains = {}
	33	constraints = []
	34	for i in range(size):
	35	name = 'Q%02d'%i
	36	variables.append(name)
	37	domains[name] = ChessDomain(size)
	38
	39	for q1 in variables:
	40	for q2 in variables:
	41	if q1 < q2:
	42	c = QueensConstraint((q1,q2))
	43	constraints.append(c)
	44	r = Repository(variables,domains,constraints)
	45	for sol in Solver(EnumeratorDistributor()).solve_all(r,verbose):
	46	yield sol
	47
	48
	49
	50	def draw_solution(s):
	51	size = len(s)
	52	queens = {}
	53	board = ''
	54	for q,p in s.items():
	55	queens[p]=q
	56	board += '_'(size2+1)+'\n'
	57	for i in range(size):
	58	#
	59	for j in range(size):
	60	q = queens.get((i,j))
	61	if q is None:
	62	board+='\|'+'·-'[(i+j)%2]
	63	else:
	64	board+='\|Q'
	65	board+='\|\n'
	66	board += '¯'(size2+1)
	67	print board
	68
	69
	70	def main(args = None):
	71	import sys,getopt
	72	if args is None:
	73	args = sys.argv[1:]
	74	opts,args = getopt.getopt(args,'dvf')
	75	display = 0
	76	verbose = 0
	77	first = 0
	78	if args:
	79	size = int(args[0])
	80	else:
	81	size = 8
	82	for o,v in opts:
	83	if o == '-d':
	84	display = 1
	85	elif o == '-v':
	86	verbose += 1
	87	elif o == "-f":
	88	first = 1
	89	count = 0
	90	for sol in queens(size,verbose):
	91	count += 1
	92	if display:
	93	print 'solution #%d'%count
	94	draw_solution(sol)
	95	print ''80
	96	if first:
	97	break
	98	if not display:
	99	print 'Use -d option to display solutions'
	100	print count,'solutions found.'
	101
	102	if __name__ == '__main__':
	103	## import hotshot
	104	## p = hotshot.Profile('/tmp/queens.prof')
	105	## p.runcall(main)
	106	## p.close()
	107	main()

+109

-0

examples/rooks.py less more

	0	#!/usr/bin/env python
	1	# -- coding: ISO-8859-1 --
	2	"""N queens problem
	3	The problem is solved with a EnumeratorDistributor splitting
	4	the smallest domain in at most N subdomains."""
	5
	6	# (c) 2000-2001 LOGILAB S.A. (Paris, FRANCE).
	7	# http://www.logilab.fr/ -- mailto:contact@logilab.fr
	8	#
	9	# This program is free software; you can redistribute it and/or modify it under
	10	# the terms of the GNU General Public License as published by the Free Software
	11	# Foundation; either version 2 of the License, or (at your option) any later
	12	# version.
	13	#
	14	# This program is distributed in the hope that it will be useful, but WITHOUT
	15	# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
	16	# FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
	17	#
	18	# You should have received a copy of the GNU General Public License along with
	19	# this program; if not, write to the Free Software Foundation, Inc.,
	20	# 59 Temple Place - Suite 330, Boston, MA 02111-1307
	21	# USA.
	22
	23
	24	from __future__ import generators
	25
	26	from logilab.constraint import *
	27	from logilab.constraint.distributors import *
	28
	29	def rooks(size=8,verbose=0):
	30	variables = []
	31	domains = {}
	32	constraints = []
	33	for i in range(size):
	34	name = 'R%02d'%i
	35	variables.append(name)
	36	domains[name] = fd.FiniteDomain( range(size) )
	37
	38	for r1 in range(size):
	39	for r2 in range(size):
	40	q1 = 'R%02d' % r1
	41	q2 = 'R%02d' % r2
	42	if r1 < r2:
	43	D = {'q1':q1,'q2':q2, 'r1' : r1, 'r2' : r2 }
	44	c = fd.make_expression((q1,q2), '%(q1)s != %(q2)s' % D )
	45	constraints.append(c)
	46
	47	r = Repository(variables,domains,constraints)
	48	for sol in Solver(EnumeratorDistributor()).solve_all(r,verbose):
	49	yield sol
	50
	51
	52
	53	def draw_solution(s):
	54	size = len(s)
	55	board = ''
	56	queens = s.items()
	57	queens.sort()
	58	board += '_'(size2+1)+'\n'
	59	for i in range(size):
	60	qj = queens[i][1]
	61	for j in range(size):
	62	if j != qj:
	63	board+='\|'+'·-'[(i+j)%2]
	64	else:
	65	board+='\|R'
	66	board+='\|\n'
	67	board += '¯'(size2+1)
	68	print board
	69
	70
	71	def main(args = None):
	72	import sys,getopt
	73	if args is None:
	74	args = sys.argv[1:]
	75	opts,args = getopt.getopt(args,'dvf')
	76	display = 0
	77	verbose = 0
	78	first = 0
	79	if args:
	80	size = int(args[0])
	81	else:
	82	size = 8
	83	for o,v in opts:
	84	if o == '-d':
	85	display = 1
	86	elif o == '-v':
	87	verbose += 1
	88	elif o == "-f":
	89	first = 1
	90	count = 0
	91	for sol in rooks(size,verbose):
	92	count += 1
	93	if display:
	94	print 'solution #%d'%count
	95	draw_solution(sol)
	96	print ''80
	97	if first:
	98	break
	99	if not display:
	100	print 'Use -d option to display solutions'
	101	print count,'solutions found.'
	102
	103	if __name__ == '__main__':
	104	## import hotshot
	105	## p = hotshot.Profile('/tmp/queens.prof')
	106	## p.runcall(main)
	107	## p.close()
	108	main()

+115

-0

examples/sudoku.py less more

	0	# (c) 2006 LOGILAB S.A. (Paris, FRANCE).
	1	# http://www.logilab.fr/ -- mailto:contact@logilab.fr
	2	#
	3	# This program is free software; you can redistribute it and/or modify it under
	4	# the terms of the GNU General Public License as published by the Free Software
	5	# Foundation; either version 2 of the License, or (at your option) any later
	6	# version.
	7	#
	8	# This program is distributed in the hope that it will be useful, but WITHOUT
	9	# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
	10	# FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
	11	#
	12	# You should have received a copy of the GNU General Public License along with
	13	# this program; if not, write to the Free Software Foundation, Inc.,
	14	# 59 Temple Place - Suite 330, Boston, MA 02111-1307
	15	# USA.
	16
	17
	18	from logilab.constraint import *
	19
	20
	21	# games found on http://www.websudoku.com/
	22	# I'm not sure how they rate the difficulty of their problems.
	23	easy = [" 5 27 ",
	24	" 4 79 ",
	25	"1 6 8 35",
	26	"4 32 16 9",
	27	" 5 8 ",
	28	"8 76 95 3",
	29	"73 2 1 6",
	30	" 41 2 ",
	31	" 12 8 "]
	32
	33	medium = [" 9 85 ",
	34	" 3 1 5 ",
	35	" 283 1 ",
	36	" 2 4 7",
	37	" 3 5 ",
	38	"4 7 5 ",
	39	" 4 362 ",
	40	" 2 7 1 ",
	41	" 26 3 "]
	42
	43	hard = [" 19 73 4",
	44	" 98 72 ",
	45	" 5",
	46	" 4 6",
	47	"93 72",
	48	"4 6 ",
	49	"8 ",
	50	" 92 36 ",
	51	"5 42 31 "]
	52
	53	evil = [" 1 9 ",
	54	" 5 4 ",
	55	"2 1 365",
	56	" 327 ",
	57	"9 8",
	58	" 821 ",
	59	"473 5 1",
	60	" 6 4 ",
	61	" 3 8 "]
	62
	63	def sudoku(problem, verbose=0):
	64	assert len(problem) == 9 # more sizes later
	65	variables = ['v%02d_%02d'%(i,j) for i in range(9) for j in range(9)]
	66	domains = {}
	67	constraints = []
	68	values = list('123456789')
	69	for v in variables:
	70	domains[v] = fd.FiniteDomain(values)
	71
	72	# line and column constraints
	73	for i in range(9):
	74	constraints.append(fd.AllDistinct(['v%02d_%02d'%(i,j) for j in range(9)]))
	75	constraints.append(fd.AllDistinct(['v%02d_%02d'%(j,i) for j in range(9)]))
	76
	77	# square constraints:
	78	for i in (0, 3, 6):
	79	for j in (0, 3, 6):
	80	constraints.append(fd.AllDistinct(['v%02d_%02d'%(i+ii,j+jj)
	81	for ii in (0, 1, 2)
	82	for jj in (0, 1, 2)]))
	83
	84	# fixed values:
	85	for i, line in enumerate(problem):
	86	for j, value in enumerate(line):
	87	if value != ' ':
	88	constraints.append(fd.Equals('v%02d_%02d'%(i,j), value))
	89
	90	r = Repository(variables, domains, constraints)
	91	s = Solver().solve_one(r, verbose)
	92	return s
	93
	94	def display_solution(d):
	95	for i in range(9):
	96	for j in range(9):
	97	print d['v%02d_%02d'%(i,j)],
	98	print
	99
	100	if __name__ == '__main__':
	101	import sys, getopt
	102	opts, args = getopt.getopt(sys.argv[1:], 'dv')
	103	verbose = 0
	104	display = 0
	105	for o,v in opts:
	106	if o == '-v':
	107	verbose += 1
	108	if o == '-d':
	109	display = 1
	110	sol = sudoku(evil, verbose)
	111	if display:
	112	display_solution(sol)
	113	else:
	114	print sol

+371

-0

fd.py less more

	0	# pylint: disable-msg=W0142
	1	# (c) 2002 LOGILAB S.A. (Paris, FRANCE).
	2	# http://www.logilab.fr/ -- mailto:contact@logilab.fr
	3	#
	4	# This program is free software; you can redistribute it and/or modify it under
	5	# the terms of the GNU General Public License as published by the Free Software
	6	# Foundation; either version 2 of the License, or (at your option) any later
	7	# version.
	8	#
	9	# This program is distributed in the hope that it will be useful, but WITHOUT
	10	# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
	11	# FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
	12	#
	13	# You should have received a copy of the GNU General Public License along with
	14	# this program; if not, write to the Free Software Foundation, Inc.,
	15	# 59 Temple Place - Suite 330, Boston, MA 02111-1307
	16	# USA.
	17	"""Tools to work with finite domain variables and constraints
	18
	19	This module provides the following usable classes:
	20	* FiniteDomain: a class for storing FiniteDomains
	21	* Expression: a constraint represented as an expression
	22	* BinaryExpression: a binary constraint represented as an expression
	23	* various BasicConstraint classes
	24
	25	The Expression and BinaryExpression classes can be constructed using the
	26	make_expression factory function. """
	27
	28	from __future__ import generators
	29
	30	import operator
	31
	32	from logilab.constraint.propagation import AbstractDomain, BasicConstraint, \
	33	ConsistencyFailure, \
	34	AbstractConstraint
	35
	36
	37	class FiniteDomain(AbstractDomain):
	38	"""
	39	Variable Domain with a finite set of possible values
	40	"""
	41
	42	_copy_count = 0
	43	_write_count = 0
	44
	45	def __init__(self, values):
	46	"""values is a list of values in the domain
	47	This class uses a dictionnary to make sure that there are
	48	no duplicate values"""
	49	AbstractDomain.__init__(self)
	50	if isinstance(values, FiniteDomain):
	51	# do a copy on write
	52	self._cow = True
	53	values._cow = True
	54	FiniteDomain._copy_count += 1
	55	self._values = values._values
	56	else:
	57	assert len(values) > 0
	58	self.setValues(values)
	59
	60	##self.getValues = self._values.keys
	61
	62	def setValues(self, values):
	63	self._cow = False
	64	FiniteDomain._write_count += 1
	65	self._values = {}
	66	for val in values:
	67	self._values[val] = 0
	68
	69	def removeValue(self, value):
	70	"""Remove value of domain and check for consistency"""
	71	## print "removing", value, "from", self._values.keys()
	72	if self._cow:
	73	self.setValues(self._values)
	74	del self._values[value]
	75	self._valueRemoved()
	76
	77	def removeValues(self, values):
	78	"""Remove values of domain and check for consistency"""
	79	if self._cow:
	80	self.setValues(self._values)
	81	if values:
	82	## print "removing", values, "from", self._values.keys()
	83	for val in values :
	84	del self._values[val]
	85	self._valueRemoved()
	86	__delitem__ = removeValue
	87
	88	def size(self):
	89	"""computes the size of a finite domain"""
	90	return len(self._values)
	91	__len__ = size
	92
	93	def getValues(self):
	94	"""return all the values in the domain"""
	95	return self._values.keys()
	96
	97	def __iter__(self):
	98	return iter(self._values)
	99
	100	def copy(self):
	101	"""clone the domain"""
	102	return FiniteDomain(self)
	103
	104	def __repr__(self):
	105	return '<FiniteDomain %s>' % str(self.getValues())
	106
	107	##
	108	## Constraints
	109	##
	110	class AllDistinct(AbstractConstraint):
	111	"""Contraint: all values must be distinct"""
	112
	113	def __init__(self, variables):
	114	assert len(variables)>1
	115	AbstractConstraint.__init__(self, variables)
	116	# worst case complexity
	117	self.__cost = len(variables) * (len(variables) - 1) / 2
	118
	119	def __repr__(self):
	120	return '<AllDistinct %s>' % str(self._variables)
	121
	122	def estimateCost(self, domains):
	123	"""return cost"""
	124	return self.__cost
	125
	126	def narrow(self, domains):
	127	"""narrowing algorithm for the constraint"""
	128	variables = [(domains[variable].size(), variable, domains[variable])
	129	for variable in self._variables]
	130
	131	variables.sort()
	132	# if a domain has a size of 1,
	133	# then the value must be removed from the other domains
	134	for size, var, dom in variables:
	135	if dom.size() == 1:
	136	for _siz, _var, _dom in variables:
	137	if _var != var:
	138	try:
	139	_dom.removeValue(dom.getValues()[0])
	140	except KeyError:
	141	# we ignore errors caused by the removal of
	142	# non existing values
	143	pass
	144
	145	# if there are less values than variables, the constraint fails
	146	values = {}
	147	for size, var, dom in variables:
	148	for val in dom:
	149	values[val] = 0
	150	if len(values) < len(variables):
	151	raise ConsistencyFailure()
	152
	153	# the constraint is entailed if all domains have a size of 1
	154	for variable in variables:
	155	if variable[2].size() != 1:
	156	return 0
	157	return 1
	158
	159
	160
	161
	162	class Expression(AbstractConstraint):
	163	"""A constraint represented as a python expression."""
	164	_FILTER_CACHE = {}
	165
	166	def __init__(self, variables, formula, type='fd.Expression'):
	167	"""variables is a list of variables which appear in the formula
	168	formula is a python expression that will be evaluated as a boolean"""
	169	AbstractConstraint.__init__(self, variables)
	170	self.formula = formula
	171	self.type = type
	172	try:
	173	self.filterFunc = Expression._FILTER_CACHE[formula]
	174	except KeyError:
	175	self.filterFunc = eval('lambda %s: %s' % \
	176	(','.join(variables), formula), {}, {})
	177	Expression._FILTER_CACHE[formula] = self.filterFunc
	178
	179	def _init_result_cache(self):
	180	"""key = (variable,value), value = [has_success,has_failure]"""
	181	result_cache = {}
	182	for var_name in self._variables:
	183	result_cache[var_name] = {}
	184	return result_cache
	185
	186
	187	def _assign_values(self, domains):
	188	variables = []
	189	kwargs = {}
	190	for variable in self._variables:
	191	domain = domains[variable]
	192	values = domain.getValues()
	193	variables.append((domain.size(), [variable, values, 0, len(values)]))
	194	kwargs[variable] = values[0]
	195	# sort variables to instanciate those with fewer possible values first
	196	variables.sort()
	197
	198	go_on = 1
	199	while go_on:
	200	yield kwargs
	201	# try to instanciate the next variable
	202	for size, curr in variables:
	203	if (curr[2] + 1) < curr[-1]:
	204	curr[2] += 1
	205	kwargs[curr[0]] = curr[1][curr[2]]
	206	break
	207	else:
	208	curr[2] = 0
	209	kwargs[curr[0]] = curr[1][0]
	210	else:
	211	# it's over
	212	go_on = 0
	213
	214
	215	def narrow(self, domains):
	216	"""generic narrowing algorithm for n-ary expressions"""
	217	maybe_entailed = 1
	218	ffunc = self.filterFunc
	219	result_cache = self._init_result_cache()
	220	for kwargs in self._assign_values(domains):
	221	if maybe_entailed:
	222	for var, val in kwargs.iteritems():
	223	if val not in result_cache[var]:
	224	break
	225	else:
	226	continue
	227	if ffunc(**kwargs):
	228	for var, val in kwargs.items():
	229	result_cache[var][val] = 1
	230	else:
	231	maybe_entailed = 0
	232
	233	try:
	234	for var, keep in result_cache.iteritems():
	235	domain = domains[var]
	236	domain.removeValues([val for val in domain if val not in keep])
	237
	238	except ConsistencyFailure:
	239	raise ConsistencyFailure('Inconsistency while applying %s' % \
	240	repr(self))
	241	except KeyError:
	242	# There are no more value in result_cache
	243	pass
	244
	245	return maybe_entailed
	246
	247	def __repr__(self):
	248	return '<%s "%s">' % (self.type, self.formula)
	249
	250	class BinaryExpression(Expression):
	251	"""A binary constraint represented as a python expression
	252
	253	This implementation uses a narrowing algorithm optimized for
	254	binary constraints."""
	255
	256	def __init__(self, variables, formula, type = 'fd.BinaryExpression'):
	257	assert len(variables) == 2
	258	Expression.__init__(self, variables, formula, type)
	259
	260	def narrow(self, domains):
	261	"""specialized narrowing algorithm for binary expressions
	262	Runs much faster than the generic version"""
	263	maybe_entailed = 1
	264	var1 = self._variables[0]
	265	dom1 = domains[var1]
	266	values1 = dom1.getValues()
	267	var2 = self._variables[1]
	268	dom2 = domains[var2]
	269	values2 = dom2.getValues()
	270	ffunc = self.filterFunc
	271	if dom2.size() < dom1.size():
	272	var1, var2 = var2, var1
	273	dom1, dom2 = dom2, dom1
	274	values1, values2 = values2, values1
	275
	276	kwargs = {}
	277	keep1 = {}
	278	keep2 = {}
	279	maybe_entailed = 1
	280	try:
	281	# iterate for all values
	282	for val1 in values1:
	283	kwargs[var1] = val1
	284	for val2 in values2:
	285	kwargs[var2] = val2
	286	if val1 in keep1 and val2 in keep2 and maybe_entailed == 0:
	287	continue
	288	if ffunc(**kwargs):
	289	keep1[val1] = 1
	290	keep2[val2] = 1
	291	else:
	292	maybe_entailed = 0
	293
	294	dom1.removeValues([val for val in values1 if val not in keep1])
	295	dom2.removeValues([val for val in values2 if val not in keep2])
	296
	297	except ConsistencyFailure:
	298	raise ConsistencyFailure('Inconsistency while applying %s' % \
	299	repr(self))
	300	except Exception:
	301	print self, kwargs
	302	raise
	303	return maybe_entailed
	304
	305
	306	def make_expression(variables, formula, constraint_type=None):
	307	"""create a new constraint of type Expression or BinaryExpression
	308	The chosen class depends on the number of variables in the constraint"""
	309	# encode unicode
	310	vars = []
	311	for var in variables:
	312	if type(var) == type(u''):
	313	vars.append(var.encode())
	314	else:
	315	vars.append(var)
	316	if len(vars) == 2:
	317	if constraint_type is not None:
	318	return BinaryExpression(vars, formula, constraint_type)
	319	else:
	320	return BinaryExpression(vars, formula)
	321
	322	else:
	323	if constraint_type is not None:
	324	return Expression(vars, formula, constraint_type)
	325	else:
	326	return Expression(vars, formula)
	327
	328
	329	class Equals(BasicConstraint):
	330	"""A basic constraint variable == constant value"""
	331	def __init__(self, variable, reference):
	332	BasicConstraint.__init__(self, variable, reference, operator.eq)
	333
	334	class NotEquals(BasicConstraint):
	335	"""A basic constraint variable != constant value"""
	336	def __init__(self, variable, reference):
	337	BasicConstraint.__init__(self, variable, reference, operator.ne)
	338
	339	class LesserThan(BasicConstraint):
	340	"""A basic constraint variable < constant value"""
	341	def __init__(self, variable, reference):
	342	BasicConstraint.__init__(self, variable, reference, operator.lt)
	343
	344	class LesserOrEqual(BasicConstraint):
	345	"""A basic constraint variable <= constant value"""
	346	def __init__(self, variable, reference):
	347	BasicConstraint.__init__(self, variable, reference, operator.le)
	348
	349	class GreaterThan(BasicConstraint):
	350	"""A basic constraint variable > constant value"""
	351	def __init__(self, variable, reference):
	352	BasicConstraint.__init__(self, variable, reference, operator.gt)
	353
	354	class GreaterOrEqual(BasicConstraint):
	355	"""A basic constraint variable >= constant value"""
	356	def __init__(self, variable, reference):
	357	BasicConstraint.__init__(self, variable, reference, operator.ge)
	358
	359	def _in(v, set):
	360	"""test presence of v in set"""
	361	return v in set
	362
	363	class InSet(BasicConstraint):
	364	"""A basic contraint variable in set value"""
	365	def __init__(self, variable, set):
	366	BasicConstraint.__init__(self, variable, set, _in )
	367
	368
	369
	370

+353

-0

fi.py less more

	0	# pylint: disable-msg=W0142
	1	# (c) 2002 LOGILAB S.A. (Paris, FRANCE).
	2	# http://www.logilab.fr/ -- mailto:contact@logilab.fr
	3	#
	4	# This program is free software; you can redistribute it and/or modify it under
	5	# the terms of the GNU General Public License as published by the Free Software
	6	# Foundation; either version 2 of the License, or (at your option) any later
	7	# version.
	8	#
	9	# This program is distributed in the hope that it will be useful, but WITHOUT
	10	# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
	11	# FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
	12	#
	13	# You should have received a copy of the GNU General Public License along with
	14	# this program; if not, write to the Free Software Foundation, Inc.,
	15	# 59 Temple Place - Suite 330, Boston, MA 02111-1307
	16	# USA.
	17	"""Tools to work with finite interval domain interval and constraints
	18
	19	"""
	20
	21	from __future__ import generators, division
	22
	23	from logilab.common.compat import set, sorted
	24
	25	from logilab.constraint.distributors import AbstractDistributor
	26	from logilab.constraint.propagation import (AbstractDomain, ConsistencyFailure,
	27	AbstractConstraint)
	28
	29	class Interval:
	30	"""representation of an interval
	31	This class is used to give back results from a FiniteIntervalDomain
	32	"""
	33	def __init__(self, start, end):
	34	self._start = start
	35	self._end = end
	36
	37	def __repr__(self):
	38	return "<Interval [%.2f %.2f[>" % (self._start, self._end)
	39
	40	def __eq__(self, other):
	41	return self._start == other._start and \
	42	self._end == other._end
	43
	44	class FiniteIntervalDomain(AbstractDomain):
	45	"""
	46	Domain for a variable with interval values.
	47	"""
	48
	49	def __init__(self, lowestMin, highestMax,
	50	min_length, max_length=None, resolution=1):
	51	"""
	52	lowestMin is the lowest value of a low boundary for a variable (inclusive).
	53	highestMax is the highest value of a high boundary for a variable (exclusive).
	54	min_length is the minimum width of the interval.
	55	max_length is the maximum width of the interval.
	56	Use None to have max = min.
	57	resolution is the precision to use for constraint satisfaction. Defaults to 1
	58	"""
	59	assert highestMax >= lowestMin
	60	if max_length is None:
	61	max_length = min_length
	62	assert 0 <= min_length <= max_length
	63	assert min_length <= highestMax - lowestMin
	64	assert resolution > 0
	65	AbstractDomain.__init__(self)
	66	self.lowestMin = lowestMin
	67	self.highestMax = highestMax
	68	self._min_length = min_length
	69	max_length = min(max_length, highestMax - lowestMin)
	70	self._max_length = max_length
	71	self._resolution = resolution
	72
	73	def __eq__(self, other):
	74
	75	return self.lowestMin == other.lowestMin and \
	76	self.highestMax == other.highestMax and \
	77	self._min_length == other._min_length and \
	78	self._max_length == other._max_length and \
	79	self._resolution == other._resolution
	80
	81	def getValues(self):
	82	return list(self.iter_values())
	83
	84	def iter_values(self):
	85	length = self._min_length
	86	while length <= self._max_length:
	87	start = self.lowestMin
	88	while start + length <= self.highestMax:
	89	yield Interval(start, start+length)
	90	start += self._resolution
	91	length += self._resolution
	92
	93
	94	def size(self):
	95	"""computes the size of a finite interval"""
	96	size = 0
	97	length = self._min_length
	98	while length <= self._max_length :
	99	size += ((self.highestMax - length) - self.lowestMin) / self._resolution + 1
	100	length += self._resolution
	101	return size
	102
	103	def _highestMin(self):
	104	return self.highestMax - self._min_length
	105
	106	def _lowestMax(self):
	107	return self.lowestMin + self._min_length
	108
	109	lowestMax = property(_lowestMax, None, None, "")
	110
	111	highestMin = property(_highestMin, None, None, "")
	112
	113	def copy(self):
	114	"""clone the domain"""
	115	return FiniteIntervalDomain(self.lowestMin, self.highestMax,
	116	self._min_length, self._max_length,
	117	self._resolution)
	118
	119	def setLowestMin(self, new_lowestMin):
	120	self.lowestMin = new_lowestMin
	121	self._valueRemoved()
	122
	123	def setHighestMax(self, new_highestMax):
	124	self.highestMax = new_highestMax
	125	self._valueRemoved()
	126
	127	def setMinLength(self, new_min):
	128	self._min_length = new_min
	129	self._valueRemoved()
	130
	131	def setMaxLength(self, new_max):
	132	self._max_length = new_max
	133	self._valueRemoved()
	134
	135	def overlap(self, other):
	136	return other.highestMax > self.lowestMin and \
	137	other.lowestMin < self.highestMax
	138
	139	def no_overlap_impossible(self, other):
	140	return self.lowestMax > other.highestMin and \
	141	other.lowestMax > self.highestMin
	142
	143	def hasSingleLength(self):
	144	return self._max_length == self._min_length
	145
	146	def _valueRemoved(self):
	147	if self.lowestMin >= self.highestMax:
	148	raise ConsistencyFailure("earliest start [%.2f] higher than latest end [%.2f]" %
	149	(self.lowestMin, self.highestMax))
	150	if self._min_length > self._max_length:
	151	raise ConsistencyFailure("min length [%.2f] greater than max length [%.2f]" %
	152	(self._min_length, self._max_length))
	153
	154	self._max_length = min(self._max_length, self.highestMax - self.lowestMin)
	155	AbstractDomain._valueRemoved(self)
	156
	157	def __repr__(self):
	158	return '<FiniteIntervalDomain % 3d from [%.2f, %.2f[ to [%.2f, %.2f[>' % (self.size(),
	159	self.lowestMin,
	160	self.lowestMax,
	161	self.highestMin,
	162	self.highestMax,)
	163
	164	##
	165	## Distributors
	166	##
	167
	168	class FiniteIntervalDistributor(AbstractDistributor):
	169	"""Distributes a set of FiniteIntervalDomain
	170	The distribution strategy is the following:
	171	- the smallest domain of size > 1 is picked
	172	- if its max_length is greater than its min_length, a subdomain if size
	173	min_length is distributed, with the same boundaries
	174	- otherwise, a subdomain [lowestMin, lowestMax[ is distributed
	175	"""
	176	def __init__(self):
	177	AbstractDistributor.__init__(self)
	178
	179	def _split_values(self, copy1, copy2):
	180	lm = copy1.lowestMin
	181	hM = copy1.highestMax
	182	if copy1.hasSingleLength():
	183	r = copy1._resolution
	184	L = copy1._min_length
	185	m = (hM-L+lm)//(2r)r
	186	## copy1.highestMax = copy1.lowestMin + copy1._min_length
	187	## copy2.lowestMin += copy2._resolution
	188	copy1.highestMax = m+L
	189	copy2.lowestMin = m+r
	190	else:
	191	copy1._max_length = copy1._min_length
	192	copy2._min_length += copy2._resolution
	193
	194
	195	def _distribute(self, dom1, dom2):
	196	variable = self.findSmallestDomain(dom1)
	197	if self.verbose:
	198	print 'Distributing domain for variable', variable
	199	splitted = dom1[variable]
	200	cpy1 = splitted.copy()
	201	cpy2 = splitted.copy()
	202
	203	self._split_values(cpy1, cpy2)
	204
	205	dom1[variable] = cpy1
	206	dom2[variable] = cpy2
	207
	208	return cpy1, cpy2
	209
	210
	211
	212	##
	213	## Constraints
	214	##
	215
	216	class AbstractFIConstraint(AbstractConstraint):
	217	def __init__(self, var1, var2):
	218	AbstractConstraint.__init__(self, (var1, var2))
	219
	220	def estimateCost(self, domains):
	221	return 1
	222
	223	def __repr__(self):
	224	return '<%s %s>' % (self.__class__.__name__, str(self._variables))
	225
	226	def __eq__(self, other):
	227	return repr(self) == repr(other)
	228
	229	def __hash__(self):
	230	# FIXME: to be able to add constraints in Sets (and compare them)
	231	# FIXME: improve implementation
	232	variables = tuple(sorted(self._variables))
	233	return hash((self.__class__.__name__, variables))
	234
	235	def narrow(self, domains):
	236	"""narrowing algorithm for the constraint"""
	237	dom1 = domains[self._variables[0]]
	238	dom2 = domains[self._variables[1]]
	239
	240	return self._doNarrow(dom1, dom2)
	241
	242	def _doNarrow(self, dom1, dom2):
	243	"""virtual method which does the real work"""
	244	raise NotImplementedError
	245
	246
	247
	248	# FIXME: deal with more than 2 domains at once ?
	249	class NoOverlap(AbstractFIConstraint):
	250
	251	def __eq__(self, other):
	252	return isinstance(other, NoOverlap) and \
	253	set(self._variables) == set(other._variables)
	254
	255	def _doNarrow(self, dom1, dom2):
	256	if not dom1.overlap(dom2):
	257	return 1
	258	elif dom1.no_overlap_impossible(dom2) :
	259	raise ConsistencyFailure
	260	elif dom1.lowestMax == dom2.highestMin and dom2.lowestMax > dom1.highestMin :
	261	dom1.setHighestMax(dom2.highestMin)
	262	dom2.setLowestMin(dom1.lowestMax)
	263	return 1
	264	elif dom1.lowestMax > dom2.highestMin and dom2.lowestMax == dom1.highestMin :
	265	dom2.setHighestMax(dom1.highestMin)
	266	dom1.setLowestMin(dom2.lowestMax)
	267	return 1
	268	return 0
	269
	270	class StartsBeforeStart(AbstractFIConstraint):
	271
	272	def _doNarrow(self, dom1, dom2):
	273
	274	if dom1.lowestMin > dom2.highestMin:
	275	raise ConsistencyFailure
	276	if dom1.highestMin < dom2.lowestMin:
	277	return 1
	278	return 0
	279
	280	class StartsBeforeEnd(AbstractFIConstraint):
	281
	282	def _doNarrow(self, dom1, dom2):
	283	if dom1.lowestMin > dom2.highestMax:
	284	raise ConsistencyFailure
	285	if dom1.highestMin < dom2.lowestMax:
	286	return 1
	287	return 0
	288
	289	class EndsBeforeStart(AbstractFIConstraint):
	290
	291	def _doNarrow(self, dom1, dom2):
	292	if dom1.lowestMax > dom2.highestMin:
	293	raise ConsistencyFailure
	294	if dom1.highestMax < dom2.lowestMin:
	295	return 1
	296	if dom1.highestMax > dom2.highestMin:
	297	dom1.setHighestMax(dom2.highestMin)
	298	return 0
	299
	300	class EndsBeforeEnd(AbstractFIConstraint):
	301
	302	def _doNarrow(self, dom1, dom2):
	303	if dom1.lowestMax > dom2.highestMax:
	304	raise ConsistencyFailure
	305	if dom1.highestMax < dom2.lowestMax:
	306	return 1
	307	if dom1.highestMax > dom2.highestMax:
	308	dom1.setHighestMax(dom2.highestMax)
	309	return 0
	310
	311	class StartsAfterStart(AbstractFIConstraint):
	312
	313	def _doNarrow(self, dom1, dom2):
	314	if dom1.highestMin < dom2.lowestMin:
	315	raise ConsistencyFailure
	316	if dom1.lowestMin > dom2.highestMin:
	317	return 1
	318	if dom1.lowestMin < dom2.lowestMin:
	319	dom1.setLowestMin(dom2.lowestMin)
	320	return 0
	321
	322	class StartsAfterEnd(AbstractFIConstraint):
	323
	324	def _doNarrow(self, dom1, dom2):
	325	if dom1.highestMin < dom2.lowestMax:
	326	raise ConsistencyFailure
	327	if dom1.lowestMin > dom2.highestMax:
	328	return 1
	329	if dom1.lowestMin < dom2.lowestMax:
	330	dom1.setLowestMin(dom2.lowestMax)
	331	if dom2.highestMax > dom1.highestMin:
	332	dom2.setHighestMax(dom1.highestMin)
	333	return 0
	334
	335	class EndsAfterStart(AbstractFIConstraint):
	336
	337	def _doNarrow(self, dom1, dom2):
	338	if dom1.highestMax < dom2.lowestMin:
	339	raise ConsistencyFailure
	340	if dom1.lowestMax > dom2.highestMin:
	341	return 1
	342	return 0
	343
	344	class EndsAfterEnd(AbstractFIConstraint):
	345
	346	def _doNarrow(self, dom1, dom2):
	347	if dom1.highestMax < dom2.lowestMax:
	348	raise ConsistencyFailure
	349	if dom1.lowestMax > dom2.highestMax:
	350	return 1
	351	return 0
	352

+140

-0

interfaces.py less more

	0	# (c) 2000-2001 LOGILAB S.A. (Paris, FRANCE).
	1	# http://www.logilab.fr/ -- mailto:contact@logilab.fr
	2	#
	3	# This program is free software; you can redistribute it and/or modify it under
	4	# the terms of the GNU General Public License as published by the Free Software
	5	# Foundation; either version 2 of the License, or (at your option) any later
	6	# version.
	7	#
	8	# This program is distributed in the hope that it will be useful, but WITHOUT
	9	# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
	10	# FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
	11	#
	12	# You should have received a copy of the GNU General Public License along with
	13	# this program; if not, write to the Free Software Foundation, Inc.,
	14	# 59 Temple Place - Suite 330, Boston, MA 02111-1307
	15	# USA.
	16	"""Definition of interfaces"""
	17
	18	class ConstraintInterface:
	19	"""The interface that all constraints should implement"""
	20	def isVariableRelevant(self, variable):
	21	"""Returns true if changes in the domaine of the variable
	22	should trigger an evaluation of the constraint"""
	23	raise NotImplementedError
	24
	25	def affectedVariables(self):
	26	""" Return a list of all variables affected by this constraint """
	27	raise NotImplementedError
	28
	29	def estimateCost(self, domains):
	30	""" Return an estimate of the cost of the narrowing of the constraint"""
	31	raise NotImplementedError
	32
	33	def narrow(self, domains):
	34	"""ensures that the domains are consistent with the constraint
	35	Calls domain.removeValue to remove values from a domain
	36	raises ConsistencyFailure if the narrowing fails
	37	Returns 1 if the constraint is entailed, and 0 otherwise"""
	38	raise NotImplementedError
	39
	40
	41	class DomainInterface:
	42	"""The interface that all domains should implement"""
	43
	44	def resetFlags(self):
	45	"""resets the hasChanged flag"""
	46	raise NotImplementedError
	47
	48	def hasChanged(self):
	49	"""returns true if values have been removed from the domain
	50	since the last call to resetFlags"""
	51	raise NotImplementedError
	52
	53	def removeValue(self, value):
	54	"""Removes a value from the domain"""
	55	raise NotImplementedError
	56
	57	def size(self):
	58	"""returns the number of values in the domain"""
	59	raise NotImplementedError
	60
	61	def getValues(self):
	62	"""returns a tuple containing all the values in the domain
	63	These values should not be modified!"""
	64	raise NotImplementedError
	65
	66	class DistributorInterface:
	67	"""The interface that all distributors should implement"""
	68	def distribute(self, domains, verbose=0):
	69	"""domains is a dictionnary of variable -> Domain objects
	70	This method returns a list of dictionnaries similar to the domain argument
	71	This list should be a partition of the initial domains"""
	72	raise NotImplementedError
	73
	74	## class VariableInterface:
	75	## """The interface that all variables should implement"""
	76	## def getDomain(self):
	77	## """returns the domain of the variable"""
	78	## raise NotImplementedError
	79	## def setDomain(self, domain):
	80	## """sets a new domain to the variable"""
	81	## raise NotImplementedError
	82
	83	## # Magic methods for various operations
	84	## def __add__(self, other):
	85	## raise NotImplementedError
	86
	87	## def __sub__(self, other):
	88	## raise NotImplementedError
	89
	90	## def __mul__(self, other):
	91	## raise NotImplementedError
	92
	93	## def __div__(self, other):
	94	## raise NotImplementedError
	95
	96	## def __radd__(self, other):
	97	## raise NotImplementedError
	98
	99	## def __rsub__(self, other):
	100	## raise NotImplementedError
	101
	102	## def __rmul__(self, other):
	103	## raise NotImplementedError
	104
	105	## def __rdiv__(self, other):
	106	## raise NotImplementedError
	107
	108	## def __abs__(self):
	109	## raise NotImplementedError
	110
	111	## def __neg__(self):
	112	## raise NotImplementedError
	113
	114	## def __pos__(self):
	115	## raise NotImplementedError
	116
	117	## def __lt__(self, other):
	118	## raise NotImplementedError
	119
	120	## def __le__(self, other):
	121	## raise NotImplementedError
	122
	123	## def __gt__(self, other):
	124	## raise NotImplementedError
	125
	126	## def __ge__(self, other):
	127	## raise NotImplementedError
	128
	129	## def __eq__(self, other):
	130	## raise NotImplementedError
	131
	132	## def __ne__(self, other):
	133	## raise NotImplementedError
	134
	135	## def __len__(self):
	136	## raise NotImplementedError
	137
	138	## def __getitem__(self, size):
	139	## raise NotImplementedError

+409

-0

propagation.py less more

	0	# (c) 2002 LOGILAB S.A. (Paris, FRANCE).
	1	# http://www.logilab.fr/ -- mailto:contact@logilab.fr
	2	#
	3	# This program is free software; you can redistribute it and/or modify it under
	4	# the terms of the GNU General Public License as published by the Free Software
	5	# Foundation; either version 2 of the License, or (at your option) any later
	6	# version.
	7	#
	8	# This program is distributed in the hope that it will be useful, but WITHOUT
	9	# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
	10	# FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
	11	#
	12	# You should have received a copy of the GNU General Public License along with
	13	# this program; if not, write to the Free Software Foundation, Inc.,
	14	# 59 Temple Place - Suite 330, Boston, MA 02111-1307
	15	# USA.
	16	"""The code of the constraint propagation algorithms"""
	17
	18	from __future__ import generators
	19	from operator import mul as MUL
	20	from time import strftime
	21	from logilab.constraint.interfaces import DomainInterface, ConstraintInterface
	22	from logilab.constraint.psyco_wrapper import Psyobj
	23	from logilab.common.compat import enumerate
	24
	25	def _default_printer(*msgs):
	26	for msg in msgs[:-1]:
	27	print msg,
	28	print msgs[-1]
	29	class ConsistencyFailure(Exception):
	30	"""The repository is not in a consistent state"""
	31	pass
	32
	33	class Repository(Psyobj):
	34	"""Stores variables, domains and constraints
	35	Propagates domain changes to constraints
	36	Manages the constraint evaluation queue"""
	37
	38	def __init__(self, variables, domains, constraints = None, printer=_default_printer):
	39	# encode unicode
	40	self._printer = printer
	41
	42	for i, var in enumerate(variables):
	43	if type(var) == type(u''):
	44	variables[i] = var.encode()
	45
	46	self._variables = variables # list of variable names
	47	self._domains = domains # maps variable name to domain object
	48	self._constraints = [] # list of constraint objects
	49	# self._queue = [] # queue of constraints waiting to be processed
	50	self._variableListeners = {}
	51	for var in self._variables:
	52	self._variableListeners[var] = []
	53	assert self._domains.has_key(var)
	54	for constr in constraints or ():
	55	self.addConstraint(constr)
	56
	57
	58	def display(self):
	59	self._printer( "VARIABLES")
	60	self._printer( "---------")
	61	for v in sorted(self._variables):
	62	self._printer( "%s = %s" % (v, self._domains[v]))
	63	self._printer( "CONSTRAINTS")
	64	self._printer( "-----------")
	65	for c in self._constraints:
	66	self._printer( c)
	67
	68	def display_vars(self):
	69	self._printer( "%d constraints with:" % len(self._constraints))
	70	for v in sorted(self._variables):
	71	self._printer( "%15s = %s" % (v, self._domains[v]))
	72
	73
	74	def __repr__(self):
	75	return '<Repository nb_constraints=%d domains=%s>' % \
	76	(len(self._constraints), self._domains)
	77
	78	def vcg_draw(self, filename, title='Constraints graph'):
	79	""" draw a constraints graph readable by vcg
	80	"""
	81	from logilab.common.vcgutils import VCGPrinter, EDGE_ATTRS
	82	stream = open(filename, 'w')
	83	printer = VCGPrinter(stream)
	84	printer.open_graph(title=title, textcolor='black'
	85	# layoutalgorithm='dfs',
	86	# manhattan_edges='yes'
	87	# port_sharing='no'
	88	# late_edge_labels='yes'
	89	)
	90
	91	for var in self._variables:
	92	printer.node(var, shape='ellipse')
	93
	94	type_colors = {}
	95	color_index = 2
	96	i = 0
	97	for constraint in self._constraints:
	98	key = constraint.type
	99	if not type_colors.has_key(key):
	100	type_colors[key] = color_index
	101	color_index += 1
	102	affected_vars = constraint.affectedVariables()
	103	if len(affected_vars) <= 1:
	104	continue
	105	if len(affected_vars) == 2:
	106	var1 = affected_vars[0]
	107	var2 = affected_vars[1]
	108	printer.edge(var1, var2, arrowstyle='none',
	109	color=EDGE_ATTRS['color'][type_colors[key]])
	110	continue
	111	n_id = 'N_aire%i' % i
	112	i += 1
	113	printer.node(n_id, shape='triangle')
	114	for var1 in affected_vars:
	115	printer.edge(var1, n_id, arrowstyle='none',
	116	color=EDGE_ATTRS['color'][type_colors[key]])
	117	# self._printer( legend)
	118	for node_type, color in type_colors.items():
	119	printer.node(node_type, shape='box',
	120	color=EDGE_ATTRS['color'][color])
	121	printer.close_graph()
	122	stream.close()
	123
	124	def addConstraint(self, constraint):
	125	if isinstance(constraint, BasicConstraint):
	126	# Basic constraints are processed just once
	127	# because they are straight away entailed
	128	var = constraint.getVariable()
	129	constraint.narrow({var: self._domains[var]})
	130	else:
	131	self._constraints.append(constraint)
	132	for var in constraint.affectedVariables():
	133	self._variableListeners[var].append(constraint)
	134
	135	def _removeConstraint(self, constraint):
	136	self._constraints.remove(constraint)
	137	for var in constraint.affectedVariables():
	138	try:
	139	self._variableListeners[var].remove(constraint)
	140	except ValueError:
	141	raise ValueError('Error removing constraint from listener',
	142	var,
	143	self._variableListeners[var],
	144	constraint)
	145
	146	def getDomains(self):
	147	return self._domains
	148
	149	def distribute(self, distributor, verbose=0):
	150	"""Create new repository using the distributor and self """
	151	for domains in distributor.distribute(self._domains, verbose):
	152	yield Repository(self._variables, domains, self._constraints)
	153
	154	# alf 20041216 -- I tried the following to avoid the cost of the
	155	# creation of new Repository objects. It resulted in functional, but
	156	# slightly slower code. If you want to try to improve it, I keep the
	157	# commented out version in the source, but the version above stays
	158	# active as it is both simpler and faster.
	159	## backup_constraints = self._constraints[:]
	160	## for domains in distributor.distribute(self._domains, verbose):
	161	## self._domains = domains
	162	## self._constraints = []
	163	## self._queue = []
	164	## for var in self._variables:
	165	## self._variableListeners[var] = []
	166	## for constraint in backup_constraints:
	167	## self.addConstraint(constraint)
	168	## yield self
	169
	170	def consistency(self, verbose=0, custom_printer=None):
	171	"""Prunes the domains of the variables
	172	This method calls constraint.narrow() and queues constraints
	173	that are affected by recent changes in the domains.
	174	Returns True if a solution was found"""
	175	if custom_printer is None:
	176	printer = self._printer
	177	else:
	178	printer = custom_printer
	179	if verbose:
	180	printer( strftime('%H:%M:%S'), ' Consistency ')
	181
	182	_queue = [ (constr.estimateCost(self._domains),
	183	constr) for constr in self._constraints ]
	184	_queue.sort()
	185	_affected_constraints = {}
	186	while True:
	187	if not _queue:
	188	# refill the queue if some constraints have been affected
	189	_queue = [(constr.estimateCost(self._domains),
	190	constr) for constr in _affected_constraints]
	191	if not _queue:
	192	break
	193	_queue.sort()
	194	_affected_constraints.clear()
	195	if verbose > 2:
	196	printer( strftime('%H:%M:%S'), 'Queue', _queue)
	197	cost, constraint = _queue.pop(0)
	198	if verbose > 1:
	199	printer( strftime('%H:%M:%S'),
	200	'Trying to entail constraint', constraint, '[cost:%d]' % cost)
	201	entailed = constraint.narrow(self._domains)
	202	for var in constraint.affectedVariables():
	203	# affected constraints are listeners of
	204	# affected variables of this constraint
	205	dom = self._domains[var]
	206	if not dom.hasChanged():
	207	continue
	208	if verbose > 1 :
	209	printer( strftime('%H:%M:%S'),
	210	' -> New domain for variable', var, 'is', dom)
	211	for constr in self._variableListeners[var]:
	212	if constr is not constraint:
	213	_affected_constraints[constr] = True
	214	dom.resetFlags()
	215	if entailed:
	216	if verbose:
	217	printer( strftime('%H:%M:%S'),
	218	"--> Entailed constraint", constraint)
	219	self._removeConstraint(constraint)
	220	if constraint in _affected_constraints:
	221	del _affected_constraints[constraint]
	222
	223	for domain in self._domains.itervalues():
	224	if domain.size() != 1:
	225	return 0
	226	return 1
	227
	228	class Solver(Psyobj):
	229	"""Top-level object used to manage the search"""
	230
	231	def __init__(self, distributor=None, printer=_default_printer):
	232	"""if no distributer given, will use the default one"""
	233	self.printer = printer
	234	if distributor is None:
	235	from logilab.constraint.distributors import DefaultDistributor
	236	distributor = DefaultDistributor()
	237	self.verbose = True
	238	self._distributor = distributor
	239	self.max_depth = 0
	240
	241	def solve_one(self, repository, verbose=0):
	242	"""Generates only one solution"""
	243	self.verbose = verbose
	244	self.max_depth = 0
	245	self.distrib_cnt = 0
	246	try:
	247	# XXX FIXME: this is a workaround a bug in psyco-1.4
	248	## return self._solve(repository).next()
	249	return self._solve(repository, 0).next()
	250	except StopIteration:
	251	return
	252
	253	def solve_best(self, repository, cost_func, verbose=0):
	254	"""Generates solution with an improving cost"""
	255	self.verbose = verbose
	256	self.max_depth = 0
	257	self.distrib_cnt = 0
	258	best_cost = None
	259	# XXX FIXME: this is a workaround a bug in psyco-1.4
	260	## for solution in self._solve(repository):
	261	for solution in self._solve(repository, 0):
	262	cost = cost_func(**solution)
	263	if best_cost is None or cost <= best_cost:
	264	best_cost = cost
	265	yield solution, cost
	266
	267	def solve_all(self, repository, verbose=0):
	268	"""Generates all solutions"""
	269	self.verbose = verbose
	270	self.max_depth = 0
	271	self.distrib_cnt = 0
	272	for solution in self._solve(repository):
	273	yield solution
	274
	275	def solve(self, repository, verbose=0):
	276	"""return list of all solutions"""
	277	self.max_depth = 0
	278	self.distrib_cnt = 0
	279	solutions = []
	280	for solution in self.solve_all(repository, verbose):
	281	solutions.append(solution)
	282	return solutions
	283
	284	def _solve(self, repository, recursion_level=0):
	285	"""main generator"""
	286	_solve = self._solve
	287	verbose = self.verbose
	288	if recursion_level > self.max_depth:
	289	self.max_depth = recursion_level
	290	if verbose >= 2:
	291	self.printer( strftime('%H:%M:%S'),)
	292	self.printer( '*** [%d] Solve called with repository' % recursion_level,)
	293	repository.display_vars()
	294	try:
	295	foundSolution = repository.consistency(verbose, custom_printer=self.printer)
	296	except ConsistencyFailure, exc:
	297	if verbose:
	298	self.printer( strftime('%H:%M:%S'), exc)
	299	else:
	300	if foundSolution:
	301	solution = {}
	302	for variable, domain in repository.getDomains().items():
	303	solution[variable] = domain.getValues()[0]
	304	if verbose:
	305	self.printer( strftime('%H:%M:%S'), '### Found Solution', solution)
	306	self.printer( '-'*80)
	307	yield solution
	308	else:
	309	self.distrib_cnt += 1
	310	for repo in repository.distribute(self._distributor,
	311	verbose>=2):
	312	for solution in _solve(repo, recursion_level+1):
	313	if solution is not None:
	314	yield solution
	315
	316	if recursion_level == 0 and self.verbose:
	317	self.printer( strftime('%H:%M:%S'),'Finished search')
	318	self.printer( strftime('%H:%M:%S'), 'Maximum recursion depth = ',
	319	self.max_depth)
	320	self.printer( 'Nb distributions = ', self.distrib_cnt)
	321
	322
	323
	324
	325
	326
	327	class BasicConstraint(Psyobj):
	328	"""A BasicConstraint, which is never queued by the Repository
	329	A BasicConstraint affects only one variable, and will be entailed
	330	on the first call to narrow()"""
	331
	332	__implements__ = ConstraintInterface
	333
	334	def __init__(self, variable, reference, operator):
	335	"""variables is a list of variables on which
	336	the constraint is applied"""
	337	self._variable = variable
	338	self._reference = reference
	339	self._operator = operator
	340
	341	def __repr__(self):
	342	return '<%s %s %s>'% (self.__class__, self._variable, self._reference)
	343
	344	def isVariableRelevant(self, variable):
	345	return variable == self._variable
	346
	347	def estimateCost(self, domains):
	348	return 0 # get in the first place in the queue
	349
	350	def affectedVariables(self):
	351	return [self._variable]
	352
	353	def getVariable(self):
	354	return self._variable
	355
	356	def narrow(self, domains):
	357	domain = domains[self._variable]
	358	operator = self._operator
	359	ref = self._reference
	360	try:
	361	for val in domain.getValues() :
	362	if not operator(val, ref) :
	363	domain.removeValue(val)
	364	except ConsistencyFailure:
	365	raise ConsistencyFailure('inconsistency while applying %s' % \
	366	repr(self))
	367	return 1
	368
	369
	370	class AbstractDomain(Psyobj):
	371	"""Implements the functionnality related to the changed flag.
	372	Can be used as a starting point for concrete domains"""
	373
	374	__implements__ = DomainInterface
	375	def __init__(self):
	376	self.__changed = 0
	377
	378	def resetFlags(self):
	379	self.__changed = 0
	380
	381	def hasChanged(self):
	382	return self.__changed
	383
	384	def _valueRemoved(self):
	385	"""The implementation of removeValue should call this method"""
	386	self.__changed = 1
	387	if self.size() == 0:
	388	raise ConsistencyFailure()
	389
	390	class AbstractConstraint(Psyobj):
	391	__implements__ = ConstraintInterface
	392
	393	def __init__(self, variables):
	394	"""variables is a list of variables which appear in the formula"""
	395	self._variables = variables
	396
	397	def affectedVariables(self):
	398	""" Return a list of all variables affected by this constraint """
	399	return self._variables
	400
	401	def isVariableRelevant(self, variable):
	402	return variable in self._variables
	403
	404	def estimateCost(self, domains):
	405	"""Return an estimate of the cost of the narrowing of the constraint"""
	406	return reduce(MUL, [domains[var].size() for var in self._variables])
	407
	408

+41

-0

psyco_wrapper.py less more

	0	# pylint: disable-msg=W0232
	1	# (c) 2002-2004 LOGILAB S.A. (Paris, FRANCE).
	2	# http://www.logilab.fr/ -- mailto:contact@logilab.fr
	3	#
	4	# This program is free software; you can redistribute it and/or modify it under
	5	# the terms of the GNU General Public License as published by the Free Software
	6	# Foundation; either version 2 of the License, or (at your option) any later
	7	# version.
	8	#
	9	# This program is distributed in the hope that it will be useful, but WITHOUT
	10	# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
	11	# FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
	12	#
	13	# You should have received a copy of the GNU General Public License along with
	14	# this program; if not, write to the Free Software Foundation, Inc.,
	15	# 59 Temple Place - Suite 330, Boston, MA 02111-1307
	16	# USA.
	17
	18	"""Provides an psyobj class regardless of the availability of psyco"""
	19
	20	import os
	21
	22	try:
	23	if "NO_PSYCO" in os.environ:
	24	raise ImportError()
	25	from psyco.classes import psyobj as Psyobj # pylint: disable-msg=W0611
	26	except ImportError:
	27
	28	class Psyobj:
	29	pass
	30
	31	if hasattr(os,'uname') and os.uname()[-1] == 'x86_64':
	32	pass # psyco only available for 32bits platforms
	33	else:
	34	from warnings import warn
	35	warn("Psyco could not be loaded."
	36	" Psyco is a Python just in time compiler available at http://psyco.sf.net"
	37	" Installing it will enhance the performance of logilab.constraint",
	38	stacklevel=2)
	39
	40

+182

-0

setup.py less more

	0	#!/usr/bin/env python
	1	# pylint: disable-msg=W0142, W0403,W0404, W0613,W0622,W0622, W0704, R0904
	2	#
	3	# Copyright (c) 2003 LOGILAB S.A. (Paris, FRANCE).
	4	# http://www.logilab.fr/ -- mailto:contact@logilab.fr
	5	#
	6	# This program is free software; you can redistribute it and/or modify it under
	7	# the terms of the GNU General Public License as published by the Free Software
	8	# Foundation; either version 2 of the License, or (at your option) any later
	9	# version.
	10	#
	11	# This program is distributed in the hope that it will be useful, but WITHOUT
	12	# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
	13	# FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
	14	#
	15	# You should have received a copy of the GNU General Public License along with
	16	# this program; if not, write to the Free Software Foundation, Inc.,
	17	# 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
	18	""" Generic Setup script, takes package info from __pkginfo__.py file """
	19
	20	import os
	21	import sys
	22	import shutil
	23	from distutils.core import setup
	24	from distutils.command import install_lib
	25	from os.path import isdir, exists, join, walk
	26
	27	# import required features
	28	from __pkginfo__ import modname, version, license, short_desc, long_desc, \
	29	web, author, author_email
	30	# import optional features
	31	try:
	32	from __pkginfo__ import distname
	33	except ImportError:
	34	distname = modname
	35	try:
	36	from __pkginfo__ import scripts
	37	except ImportError:
	38	scripts = []
	39	try:
	40	from __pkginfo__ import data_files
	41	except ImportError:
	42	data_files = None
	43	try:
	44	from __pkginfo__ import subpackage_of
	45	except ImportError:
	46	subpackage_of = None
	47	try:
	48	from __pkginfo__ import include_dirs
	49	except ImportError:
	50	include_dirs = []
	51	try:
	52	from __pkginfo__ import ext_modules
	53	except ImportError:
	54	ext_modules = None
	55
	56	BASE_BLACKLIST = ('CVS', 'debian', 'dist', 'build', '__buildlog')
	57	IGNORED_EXTENSIONS = ('.pyc', '.pyo', '.elc')
	58
	59
	60	def ensure_scripts(linux_scripts):
	61	"""
	62	Creates the proper script names required for each platform
	63	(taken from 4Suite)
	64	"""
	65	from distutils import util
	66	if util.get_platform()[:3] == 'win':
	67	scripts_ = [script + '.bat' for script in linux_scripts]
	68	else:
	69	scripts_ = linux_scripts
	70	return scripts_
	71
	72
	73	def get_packages(directory, prefix):
	74	"""return a list of subpackages for the given directory
	75	"""
	76	result = []
	77	for package in os.listdir(directory):
	78	absfile = join(directory, package)
	79	if isdir(absfile):
	80	if exists(join(absfile, '__init__.py')) or \
	81	package in ('test', 'tests'):
	82	if prefix:
	83	result.append('%s.%s' % (prefix, package))
	84	else:
	85	result.append(package)
	86	result += get_packages(absfile, result[-1])
	87	return result
	88
	89	def export(from_dir, to_dir,
	90	blacklist=BASE_BLACKLIST,
	91	ignore_ext=IGNORED_EXTENSIONS):
	92	"""make a mirror of from_dir in to_dir, omitting directories and files
	93	listed in the black list
	94	"""
	95	def make_mirror(arg, directory, fnames):
	96	"""walk handler"""
	97	for norecurs in blacklist:
	98	try:
	99	fnames.remove(norecurs)
	100	except ValueError:
	101	pass
	102	for filename in fnames:
	103	# don't include binary files
	104	if filename[-4:] in ignore_ext:
	105	continue
	106	if filename[-1] == '~':
	107	continue
	108	src = '%s/%s' % (directory, filename)
	109	dest = to_dir + src[len(from_dir):]
	110	print >> sys.stderr, src, '->', dest
	111	if os.path.isdir(src):
	112	if not exists(dest):
	113	os.mkdir(dest)
	114	else:
	115	if exists(dest):
	116	os.remove(dest)
	117	shutil.copy2(src, dest)
	118	try:
	119	os.mkdir(to_dir)
	120	except OSError, ex:
	121	# file exists ?
	122	import errno
	123	if ex.errno != errno.EEXIST:
	124	raise
	125	walk(from_dir, make_mirror, None)
	126
	127
	128	EMPTY_FILE = '"""generated file, don\'t modify or your data will be lost"""\n'
	129
	130	class MyInstallLib(install_lib.install_lib):
	131	"""extend install_lib command to handle package __init__.py and
	132	include_dirs variable if necessary
	133	"""
	134	def run(self):
	135	"""overridden from install_lib class"""
	136	install_lib.install_lib.run(self)
	137	# create Products.__init__.py if needed
	138	if subpackage_of:
	139	product_init = join(self.install_dir, subpackage_of, '__init__.py')
	140	if not exists(product_init):
	141	self.announce('creating %s' % product_init)
	142	stream = open(product_init, 'w')
	143	stream.write(EMPTY_FILE)
	144	stream.close()
	145	# manually install included directories if any
	146	if include_dirs:
	147	if subpackage_of:
	148	base = join(subpackage_of, modname)
	149	else:
	150	base = modname
	151	for directory in include_dirs:
	152	dest = join(self.install_dir, base, directory)
	153	export(directory, dest)
	154
	155	def install(**kwargs):
	156	"""setup entry point"""
	157	if subpackage_of:
	158	package = subpackage_of + '.' + modname
	159	kwargs['package_dir'] = {package : '.'}
	160	packages = [package] + get_packages(os.getcwd(), package)
	161	else:
	162	kwargs['package_dir'] = {modname : '.'}
	163	packages = [modname] + get_packages(os.getcwd(), modname)
	164	kwargs['packages'] = packages
	165	return setup(name = distname,
	166	version = version,
	167	license =license,
	168	description = short_desc,
	169	long_description = long_desc,
	170	author = author,
	171	author_email = author_email,
	172	url = web,
	173	scripts = ensure_scripts(scripts),
	174	data_files=data_files,
	175	ext_modules=ext_modules,
	176	cmdclass={'install_lib': MyInstallLib},
	177	**kwargs
	178	)
	179
	180	if __name__ == '__main__' :
	181	install()

+53

-0

test/__profile__.py less more

	0	# (c) 2000-2001 LOGILAB S.A. (Paris, FRANCE).
	1	# http://www.logilab.fr/ -- mailto:contact@logilab.fr
	2	#
	3	# This program is free software; you can redistribute it and/or modify it under
	4	# the terms of the GNU General Public License as published by the Free Software
	5	# Foundation; either version 2 of the License, or (at your option) any later
	6	# version.
	7	#
	8	# This program is distributed in the hope that it will be useful, but WITHOUT
	9	# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
	10	# FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
	11	#
	12	# You should have received a copy of the GNU General Public License along with
	13	# this program; if not, write to the Free Software Foundation, Inc.,
	14	# 59 Temple Place - Suite 330, Boston, MA 02111-1307
	15	# USA.
	16
	17	from logilab.constraint.propagation import *
	18	from logilab.constraint import fd
	19
	20
	21	def queens(size=8,verbose=0):
	22	possible_positions = [(i,j) for i in range(size) for j in range(size)]
	23	variables = []
	24	domains = {}
	25	constraints = []
	26	for i in range(size):
	27	name = 'Q%d'%i
	28	variables.append(name)
	29	domains[name] = fd.FiniteDomain(possible_positions)
	30	for q1 in variables:
	31	for q2 in variables:
	32	if q1 < q2:
	33	constraints.append(fd.make_expression((q1,q2),
	34	'%(q1)s[0] < %(q2)s[0] and '
	35	'%(q1)s[1] != %(q2)s[1] and '
	36	'abs(%(q1)s[0]-%(q2)s[0]) != '
	37	'abs(%(q1)s[1]-%(q2)s[1])'%\
	38	{'q1':q1,'q2':q2}))
	39	r = Repository(variables,domains,constraints)
	40	s = Solver().solve(r,verbose)
	41	print 'Number of solutions:',len(s)
	42
	43	if __name__ == '__main__':
	44	import profile
	45	profile.run('queens()','csp.prof')
	46	import pstats
	47
	48	p = pstats.Stats('csp.prof')
	49	p.sort_stats('time','calls').print_stats(.25)
	50	p.sort_stats('cum','calls').print_stats(.25)
	51	p.strip_dirs().sort_stats('cum','calls').print_callers(.25)
	52	p.strip_dirs().sort_stats('cum','calls').print_callees()

-0

test/runtests.py less more

	0	from logilab.common.testlib import main
	1
	2	if __name__ == '__main__':
	3	import sys, os
	4	main(os.path.dirname(sys.argv[0]) or '.')

+331

-0

test/test_constraints.py less more

	0	"""Unit testing for constraint propagation module"""
	1
	2	# (c) 2000-2001 LOGILAB S.A. (Paris, FRANCE).
	3	# http://www.logilab.fr/ -- mailto:contact@logilab.fr
	4	#
	5	# This program is free software; you can redistribute it and/or modify it under
	6	# the terms of the GNU General Public License as published by the Free Software
	7	# Foundation; either version 2 of the License, or (at your option) any later
	8	# version.
	9	#
	10	# This program is distributed in the hope that it will be useful, but WITHOUT
	11	# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
	12	# FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
	13	#
	14	# You should have received a copy of the GNU General Public License along with
	15	# this program; if not, write to the Free Software Foundation, Inc.,
	16	# 59 Temple Place - Suite 330, Boston, MA 02111-1307
	17	# USA.
	18
	19	import unittest
	20	from logilab.constraint import fd
	21	from logilab.constraint import propagation
	22	from logilab.constraint import distributors
	23
	24
	25	class AbstractConstraintTC(unittest.TestCase):
	26	"""override the following methods:
	27	* setUp to initialize variables
	28	* narrowingAssertions to check that narrowing was ok
	29	"""
	30	def setUp(self):
	31	self.relevant_variables = []
	32	self.irrelevant_variable = 'tagada'
	33	self.constraint = None #AbstractConstraint(self.relevant_variables)
	34	self.domains = {}
	35	self.entailed_domains = {}
	36	#raise NotImplementedError
	37
	38	def testRelevance(self):
	39	"""tests that relevant variables are relevant"""
	40	for v in self.relevant_variables:
	41	self.assert_(self.constraint.isVariableRelevant(v))
	42	self.failIf(self.constraint.isVariableRelevant(self.irrelevant_variable))
	43
	44
	45	def testNarrowing(self):
	46	"""tests that narrowing is performed correctly"""
	47	entailed = self.constraint.narrow(self.domains)
	48	self.narrowingAssertions()
	49
	50	def testEntailment(self):
	51	"""tests that narrowing is performed correctly"""
	52	entailed = self.constraint.narrow(self.entailed_domains)
	53	self.assert_(entailed)
	54
	55	class AllDistinctTC(AbstractConstraintTC):
	56	def setUp(self):
	57	self.relevant_variables = ['x','y','z']
	58	self.irrelevant_variable = 'tagada'
	59	self.constraint = fd.AllDistinct(self.relevant_variables)
	60	self.domains = {'x':fd.FiniteDomain((1,2)),
	61	'y':fd.FiniteDomain((1,3)),
	62	'z':fd.FiniteDomain((1,4)),}
	63
	64	self.entailed_domains = {'x':fd.FiniteDomain((1,)),
	65	'y':fd.FiniteDomain((1,2)),
	66	'z':fd.FiniteDomain((1,2,3)),}
	67
	68	def narrowingAssertions(self):
	69	vx = self.domains['x'].getValues()
	70	vy = self.domains['y'].getValues()
	71	vz = self.domains['z'].getValues()
	72	self.assert_( 1 in vx and 2 in vx)
	73	self.assert_( 1 in vy and 3 in vy)
	74	self.assert_( 1 in vz and 4 in vz)
	75
	76	def testNarrowing2(self):
	77	domains = {'x':fd.FiniteDomain((1,2)),
	78	'y':fd.FiniteDomain((1,)),
	79	'z':fd.FiniteDomain((1,4)),}
	80	entailed = self.constraint.narrow(domains)
	81	vx = domains['x'].getValues()
	82	vy = domains['y'].getValues()
	83	vz = domains['z'].getValues()
	84	self.assert_(entailed)
	85	self.assert_(2 in vx)
	86	self.assert_(1 in vy)
	87	self.assert_(4 in vz)
	88
	89	def testNarrowing3(self):
	90	domains = {'x':fd.FiniteDomain((1,)),
	91	'y':fd.FiniteDomain((2,)),
	92	'z':fd.FiniteDomain((1,2,3,4)),}
	93	entailed = self.constraint.narrow(domains)
	94	vx = domains['x'].getValues()
	95	vy = domains['y'].getValues()
	96	vz = domains['z'].getValues()
	97	self.assert_(not entailed)
	98	self.assert_(1 in vx, str(vx))
	99	self.assert_(2 in vy, str(vy))
	100	self.assert_(4 in vz and 3 in vz, str(vz))
	101
	102	def testNarrowing4(self):
	103	domains = {'x':fd.FiniteDomain((1,)),
	104	'y':fd.FiniteDomain((2,)),
	105	'z':fd.FiniteDomain((1,3,4)),
	106	't':fd.FiniteDomain((2,5,4)),
	107	'u':fd.FiniteDomain((1,2,4)),
	108	}
	109	constraint = fd.AllDistinct(domains.keys())
	110	entailed = constraint.narrow(domains)
	111	vx = domains['x'].getValues()
	112	vy = domains['y'].getValues()
	113	vz = domains['z'].getValues()
	114	vt = domains['t'].getValues()
	115	vu = domains['u'].getValues()
	116	self.failUnless(entailed)
	117	self.assertEquals([1], vx)
	118	self.assertEquals([2], vy)
	119	self.assertEquals([3], vz)
	120	self.assertEquals([5], vt)
	121	self.assertEquals([4], vu)
	122
	123	def testFailure1(self):
	124	domains = {'x':fd.FiniteDomain((1,2)),
	125	'y':fd.FiniteDomain((2,1)),
	126	'z':fd.FiniteDomain((1,2)),}
	127	exception = 0
	128	try:
	129	entailed = self.constraint.narrow(domains)
	130	except propagation.ConsistencyFailure:
	131	exception = 1
	132	assert exception
	133
	134	def testFailure2(self):
	135	domains = {'x':fd.FiniteDomain((1,)),
	136	'y':fd.FiniteDomain((2,)),
	137	'z':fd.FiniteDomain((1,2)),}
	138	exception = 0
	139	try:
	140	entailed = self.constraint.narrow(domains)
	141	except propagation.ConsistencyFailure:
	142	exception = 1
	143	assert exception
	144
	145	def testFailure3(self):
	146	domains = {'x':fd.FiniteDomain((1,)),
	147	'y':fd.FiniteDomain((1,)),
	148	'z':fd.FiniteDomain((2,3)),}
	149	exception = 0
	150	try:
	151	entailed = self.constraint.narrow(domains)
	152	except propagation.ConsistencyFailure:
	153	exception = 1
	154	assert exception
	155
	156
	157
	158	class UnaryMathConstrTC(AbstractConstraintTC):
	159	def setUp(self):
	160	self.relevant_variables = ['x']
	161	self.irrelevant_variable = 'tagada'
	162	self.constraint = fd.make_expression(self.relevant_variables,
	163	'x==2')
	164	self.domains = {'x':fd.FiniteDomain(range(4))}
	165	self.entailed_domains = {'x':fd.FiniteDomain([2])}
	166	def narrowingAssertions(self):
	167	v = list(self.domains['x'].getValues())
	168	v.sort()
	169	assert v == [2],str(v)
	170
	171	class BinaryMathConstrTC(AbstractConstraintTC):
	172	def setUp(self):
	173	self.relevant_variables = ['x','y']
	174	self.irrelevant_variable = 'tagada'
	175	self.constraint = fd.make_expression(self.relevant_variables,
	176	'x+y==2')
	177	self.domains = {'x':fd.FiniteDomain(range(4)),
	178	'y':fd.FiniteDomain(range(2))}
	179	self.entailed_domains = {'x':fd.FiniteDomain([2]),
	180	'y':fd.FiniteDomain([0])}
	181	def narrowingAssertions(self):
	182	v = list(self.domains['x'].getValues())
	183	v.sort()
	184	assert v == [1,2],str(v)
	185	v = list(self.domains['y'].getValues())
	186	v.sort()
	187	assert v == [0,1],str(v)
	188
	189	class TernaryMathConstrTC(AbstractConstraintTC):
	190	def setUp(self):
	191	self.relevant_variables = ['x','y','z']
	192	self.irrelevant_variable = 'tagada'
	193	self.constraint = fd.make_expression(self.relevant_variables,
	194	'x+y==2 and z>1')
	195	self.domains = {'x':fd.FiniteDomain(range(4)),
	196	'y':fd.FiniteDomain(range(3)),
	197	'z':fd.FiniteDomain(range(4))}
	198	self.entailed_domains = {'x':fd.FiniteDomain([2]),
	199	'y':fd.FiniteDomain([0]),
	200	'z':fd.FiniteDomain([2,3]),}
	201
	202
	203	def narrowingAssertions(self):
	204	v = list(self.domains['x'].getValues())
	205	v.sort()
	206	assert v == [0,1,2],str(v)
	207	v = list(self.domains['y'].getValues())
	208	v.sort()
	209	assert v == [0,1,2],str(v)
	210	v = list(self.domains['z'].getValues())
	211	v.sort()
	212	assert v == [2,3],str(v)
	213
	214	class AbstractBasicConstraintTC(unittest.TestCase):
	215	"""override the following methods:
	216	* setUp to initialize variables
	217	* narrowingAssertions to check that narrowing was ok
	218	"""
	219	def setUp(self):
	220	self.constraint = None #AbstractConstraint(self.relevant_variables)
	221	self.domains = {}
	222	self.entailed_domains = {}
	223	#raise NotImplementedError
	224
	225	def testRelevance(self):
	226	"""tests that relevant variables are relevant"""
	227	assert self.constraint.isVariableRelevant('x')
	228	assert not self.constraint.isVariableRelevant('tagada')
	229
	230	def testGetVariable(self):
	231	"""test that getVariable returns the right variable"""
	232	assert self.constraint.getVariable() == 'x'
	233
	234	def testNarrowing(self):
	235	"""tests that narrowing is performed correctly"""
	236	entailed = self.constraint.narrow(self.domains)
	237	self.narrowingAssertions()
	238
	239	def testEntailment(self):
	240	"""tests that narrowing is performed correctly"""
	241	entailed = self.constraint.narrow(self.domains)
	242	assert entailed
	243
	244
	245	class EqualsConstrTC(AbstractBasicConstraintTC):
	246	def setUp(self):
	247	self.constraint = fd.Equals('x',1)
	248	self.domains = {'x':fd.FiniteDomain(range(3))}
	249
	250	def narrowingAssertions(self):
	251	v = list(self.domains['x'].getValues())
	252	v.sort()
	253	assert v == [1],str(v)
	254
	255	class NotEqualsConstrTC(AbstractBasicConstraintTC):
	256	def setUp(self):
	257	self.constraint = fd.NotEquals('x',1)
	258	self.domains = {'x':fd.FiniteDomain(range(3))}
	259
	260	def narrowingAssertions(self):
	261	v = list(self.domains['x'].getValues())
	262	v.sort()
	263	assert v == [0,2],str(v)
	264
	265	class LesserThanConstrTC(AbstractBasicConstraintTC):
	266	def setUp(self):
	267	self.constraint = fd.LesserThan('x',1)
	268	self.domains = {'x':fd.FiniteDomain(range(3))}
	269
	270	def narrowingAssertions(self):
	271	v = list(self.domains['x'].getValues())
	272	v.sort()
	273	assert v == [0],str(v)
	274
	275	class LesserOrEqualConstrTC(AbstractBasicConstraintTC):
	276	def setUp(self):
	277	self.constraint = fd.LesserOrEqual('x',1)
	278	self.domains = {'x':fd.FiniteDomain(range(3))}
	279
	280	def narrowingAssertions(self):
	281	v = list(self.domains['x'].getValues())
	282	v.sort()
	283	assert v == [0,1],str(v)
	284
	285	class GreaterThanConstrTC(AbstractBasicConstraintTC):
	286	def setUp(self):
	287	self.constraint = fd.GreaterThan('x',1)
	288	self.domains = {'x':fd.FiniteDomain(range(3))}
	289
	290	def narrowingAssertions(self):
	291	v = list(self.domains['x'].getValues())
	292	v.sort()
	293	assert v == [2],str(v)
	294
	295	class GreaterOrEqualConstrTC(AbstractBasicConstraintTC):
	296	def setUp(self):
	297	self.constraint = fd.GreaterOrEqual('x',1)
	298	self.domains = {'x':fd.FiniteDomain(range(3))}
	299
	300	def narrowingAssertions(self):
	301	v = list(self.domains['x'].getValues())
	302	v.sort()
	303	assert v == [1,2],str(v)
	304
	305
	306
	307	def get_all_cases(module):
	308	import types
	309	all_cases = []
	310	for name in dir(module):
	311	obj = getattr(module, name)
	312	if type(obj) in (types.ClassType, types.TypeType) and \
	313	issubclass(obj, unittest.TestCase) and \
	314	not name.startswith('Abstract'):
	315	all_cases.append(obj)
	316	all_cases.sort()
	317	return all_cases
	318
	319	def suite(cases = None):
	320	import test_constraints
	321	cases = cases or get_all_cases(test_constraints)
	322	loader = unittest.defaultTestLoader
	323	loader.testMethodPrefix = 'test'
	324	loader.sortTestMethodsUsing = None # disable sorting
	325	suites = [loader.loadTestsFromTestCase(tc) for tc in cases]
	326	return unittest.TestSuite(suites)
	327
	328
	329	if __name__ == '__main__':
	330	unittest.main(defaultTest="suite")

+149

-0

test/test_distributors.py less more

	0	"""Unit testing for constraint propagation module"""
	1
	2	# (c) 2000-2001 LOGILAB S.A. (Paris, FRANCE).
	3	# http://www.logilab.fr/ -- mailto:contact@logilab.fr
	4	#
	5	# This program is free software; you can redistribute it and/or modify it under
	6	# the terms of the GNU General Public License as published by the Free Software
	7	# Foundation; either version 2 of the License, or (at your option) any later
	8	# version.
	9	#
	10	# This program is distributed in the hope that it will be useful, but WITHOUT
	11	# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
	12	# FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
	13	#
	14	# You should have received a copy of the GNU General Public License along with
	15	# this program; if not, write to the Free Software Foundation, Inc.,
	16	# 59 Temple Place - Suite 330, Boston, MA 02111-1307
	17	# USA.
	18
	19	import unittest
	20	from logilab.constraint import distributors,fd
	21
	22
	23	class AbstractDistributorTC(unittest.TestCase):
	24	"""override the following methods:
	25	* buildDistributor to create the distributor
	26	* distributionAssertions to check that distribution was OK
	27	"""
	28	def setUp(self):
	29	self.variables = ('v1','v2','v3')
	30	self.domains1 = {'v1':fd.FiniteDomain([1]),
	31	'v2':fd.FiniteDomain([2,3]),
	32	'v3':fd.FiniteDomain([4,5,6,7]),
	33	}
	34	self.domains2 = {'v1':fd.FiniteDomain([1]),
	35	'v2':fd.FiniteDomain([2,3,4,5,6]),
	36	'v3':fd.FiniteDomain([7,8,9,10,11,12,13]),
	37	}
	38	self.distributor = self.buildDistributor()
	39
	40	def buildDistributor(self):
	41	"""returns a distributor"""
	42	raise NotImplementedError
	43
	44	def distributionAssertions(self):
	45	"""checks the distribution"""
	46	raise NotImplementedError
	47
	48	def testFindSmallestDomain(self):
	49	"""tests that the smallest domain is indeed the smallest one
	50	with at least 2 values inside"""
	51	dist = self.buildDistributor()
	52	self.assertEquals('v2', dist.findSmallestDomain(self.domains1))
	53	self.assertEquals('v2', dist.findSmallestDomain(self.domains2))
	54
	55	def testFindLargestDomain(self):
	56	"""tests that the largest domain is indeed the largest one"""
	57	dist = self.buildDistributor()
	58	self.assertEquals('v3', dist.findLargestDomain(self.domains1))
	59	self.assertEquals('v3', dist.findLargestDomain(self.domains2))
	60
	61	def testSingleValueDomainNotDistributed(self):
	62	"""tests that a domain of size 1 is not distributed"""
	63	for initial_domain in (self.domains1,self.domains2):
	64	distributed_domains = self.distributor.distribute(self.domains1)
	65	for d in distributed_domains:
	66	assert d['v1'].size() == initial_domain['v1'].size()
	67
	68
	69	def testDistribution(self):
	70	"""tests that the right domain is correctly distributed"""
	71	for initial_domain in (self.domains1,self.domains2):
	72	distributed_domains = self.distributor.distribute(initial_domain)
	73	self.distributionAssertions(initial_domain,distributed_domains)
	74
	75	class NaiveDistributorTC(AbstractDistributorTC):
	76	def buildDistributor(self):
	77	return distributors.NaiveDistributor()
	78	def distributionAssertions(self,initial,distributed):
	79	assert len(distributed) == 2
	80	for d in distributed:
	81	for v in ('v1','v3'):
	82	assert d[v].getValues() == initial[v].getValues()
	83	assert distributed[0]['v2'].size() == 1
	84	assert distributed[1]['v2'].size() == initial['v2'].size()-1
	85
	86	class RandomizingDistributorTC(NaiveDistributorTC):
	87	def buildDistributor(self):
	88	return distributors.RandomizingDistributor()
	89
	90
	91	class DichotomyDistributorTC(AbstractDistributorTC):
	92	def buildDistributor(self):
	93	return distributors.DichotomyDistributor()
	94	def distributionAssertions(self,initial,distributed):
	95	assert len(distributed) == 2
	96	for d in distributed:
	97	for v in ('v1','v3'):
	98	assert d[v].getValues() == initial[v].getValues()
	99	assert distributed[0]['v2'].size() + distributed[1]['v2'].size() == initial['v2'].size()
	100
	101	class SplitDistributorTC(AbstractDistributorTC):
	102	def buildDistributor(self):
	103	return distributors.SplitDistributor(4)
	104	def distributionAssertions(self,initial,distributed):
	105	assert len(distributed) == min(4,initial['v2'].size())
	106	for d in distributed:
	107	for v in ('v1','v3'):
	108	assert d[v].getValues() == initial[v].getValues()
	109	sizes = [d['v2'].size() for d in distributed]
	110	import operator
	111	tot_size = reduce(operator.add,sizes)
	112	assert tot_size == initial['v2'].size()
	113
	114	class EnumeratorDistributorTC(AbstractDistributorTC):
	115	def buildDistributor(self):
	116	return distributors.EnumeratorDistributor()
	117	def distributionAssertions(self,initial,distributed):
	118	assert len(distributed) == initial['v2'].size()
	119	for d in distributed:
	120	for v in ('v1','v3'):
	121	assert d[v].getValues() == initial[v].getValues()
	122	assert d['v2'].size() == 1
	123
	124
	125	def get_all_cases(module):
	126	import types
	127	all_cases = []
	128	for name in dir(module):
	129	obj = getattr(module, name)
	130	if type(obj) in (types.ClassType, types.TypeType) and \
	131	issubclass(obj, unittest.TestCase) and \
	132	not name.startswith('Abstract'):
	133	all_cases.append(obj)
	134	all_cases.sort()
	135	return all_cases
	136
	137	def suite(cases = None):
	138	import test_distributors
	139	cases = cases or get_all_cases(test_distributors)
	140	loader = unittest.defaultTestLoader
	141	loader.testMethodPrefix = 'test'
	142	loader.sortTestMethodsUsing = None # disable sorting
	143	suites = [loader.loadTestsFromTestCase(tc) for tc in cases]
	144	return unittest.TestSuite(suites)
	145
	146
	147	if __name__ == '__main__':
	148	unittest.main(defaultTest="suite")

+95

-0

test/test_domains.py less more

	0	"""Unit testing for constraint propagation module"""
	1
	2	# (c) 2000-2001 LOGILAB S.A. (Paris, FRANCE).
	3	# http://www.logilab.fr/ -- mailto:contact@logilab.fr
	4	#
	5	# This program is free software; you can redistribute it and/or modify it under
	6	# the terms of the GNU General Public License as published by the Free Software
	7	# Foundation; either version 2 of the License, or (at your option) any later
	8	# version.
	9	#
	10	# This program is distributed in the hope that it will be useful, but WITHOUT
	11	# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
	12	# FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
	13	#
	14	# You should have received a copy of the GNU General Public License along with
	15	# this program; if not, write to the Free Software Foundation, Inc.,
	16	# 59 Temple Place - Suite 330, Boston, MA 02111-1307
	17	# USA.
	18
	19	import unittest
	20	from logilab.constraint import fd
	21	from logilab.constraint import propagation
	22	from logilab.constraint import distributors
	23
	24	class AbstractDomainTC(unittest.TestCase):
	25	"""override the following methods:
	26	* setUp to initialize variables
	27	"""
	28	def setUp(self):
	29	self.values = []
	30	self.domain = None
	31	raise NotImplementedError
	32
	33	def testGetValues(self):
	34	"""tests the getValues() method"""
	35	v1 = list(self.domain.getValues())
	36	v1.sort()
	37	v2 = self.values[:]
	38	v2.sort()
	39	assert v1 == v2
	40
	41	def testSize(self):
	42	"""tests the size() method"""
	43	assert self.domain.size() == len(self.values)
	44	self.domain.removeValue(self.values[0])
	45	assert self.domain.size() == len(self.values) - 1
	46
	47	def testRemove(self):
	48	"""tests the removeValue() method"""
	49	self.domain.removeValue(self.values[0])
	50	assert self.values[0] not in self.domain.getValues()
	51
	52	def testEmptyDomain(self):
	53	"""tests that a ConsistencyFailure exception is raised
	54	when the last value of a domain is removed"""
	55	exception = 0
	56	for v in self.values[1:]:
	57	self.domain.removeValue(v)
	58	try:
	59	self.domain.removeValue(self.values[0])
	60	except propagation.ConsistencyFailure:
	61	exception = 1
	62	assert exception
	63
	64	class SuiteDomainTC(AbstractDomainTC):
	65	def setUp(self):
	66	self.values = range(3)
	67	self.domain = fd.FiniteDomain(self.values)
	68
	69
	70
	71	def get_all_cases(module):
	72	import types
	73	all_cases = []
	74	for name in dir(module):
	75	obj = getattr(module, name)
	76	if type(obj) in (types.ClassType, types.TypeType) and \
	77	issubclass(obj, unittest.TestCase) and \
	78	not name.startswith('Abstract'):
	79	all_cases.append(obj)
	80	all_cases.sort()
	81	return all_cases
	82
	83	def suite(cases = None):
	84	import test_domains
	85	cases = cases or get_all_cases(test_domains)
	86	loader = unittest.defaultTestLoader
	87	loader.testMethodPrefix = 'test'
	88	loader.sortTestMethodsUsing = None # disable sorting
	89	suites = [loader.loadTestsFromTestCase(tc) for tc in cases]
	90	return unittest.TestSuite(suites)
	91
	92
	93	if __name__ == '__main__':
	94	unittest.main(defaultTest="suite")

+550

-0

test/test_fi.py less more

	0	"""Unit testing for constraint propagation module"""
	1
	2	# (c) 2005 LOGILAB S.A. (Paris, FRANCE).
	3	# http://www.logilab.fr/ -- mailto:contact@logilab.fr
	4	#
	5	# This program is free software; you can redistribute it and/or modify it under
	6	# the terms of the GNU General Public License as published by the Free Software
	7	# Foundation; either version 2 of the License, or (at your option) any later
	8	# version.
	9	#
	10	# This program is distributed in the hope that it will be useful, but WITHOUT
	11	# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
	12	# FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
	13	#
	14	# You should have received a copy of the GNU General Public License along with
	15	# this program; if not, write to the Free Software Foundation, Inc.,
	16	# 59 Temple Place - Suite 330, Boston, MA 02111-1307
	17	# USA.
	18
	19	import unittest
	20	from logilab.constraint.fi import *
	21	from logilab.constraint import Repository, Solver
	22
	23	class FiniteIntervalTC(unittest.TestCase):
	24
	25	def setUp(self):
	26	self.dom1 = FiniteIntervalDomain(0, 10, 2, 4, 1)
	27	self.dom2 = FiniteIntervalDomain(2, 5, 3)
	28	self.dom3 = FiniteIntervalDomain(2, 6, 2, 3, .5)
	29
	30	def testConstructorExceptions(self):
	31	try:
	32	d = FiniteIntervalDomain(5,1,3)
	33	self.fail("Should have an assertion error here")
	34	except AssertionError:
	35	pass
	36	try:
	37	d = FiniteIntervalDomain(1,5,3,1)
	38	self.fail("Should have an assertion error here")
	39	except AssertionError:
	40	pass
	41	try:
	42	d = FiniteIntervalDomain(1,3,-2)
	43	self.fail("Should have an assertion error here")
	44	except AssertionError:
	45	pass
	46	try:
	47	d = FiniteIntervalDomain(1,3,5)
	48	self.fail("Should have an assertion error here")
	49	except AssertionError:
	50	pass
	51
	52	def test_ConstructorDefaults(self):
	53	d = FiniteIntervalDomain(1,3,2)
	54	self.assertEquals(d._max_length, 2)
	55	self.assertEquals(d._resolution, 1)
	56
	57	def test_ConstructorAjustMaxLength(self):
	58	d = FiniteIntervalDomain(0, 5, 2, 8)
	59	self.assertEquals(d._max_length, 5)
	60
	61	def test_getValues(self):
	62	self.assertEquals(len(self.dom1.getValues()), self.dom1.size())
	63	self.assertEquals(len(self.dom2.getValues()), self.dom2.size())
	64	self.assertEquals(len(self.dom3.getValues()), self.dom3.size())
	65
	66	def test_Size(self):
	67	self.assertEquals(self.dom1.size(), 9 + 8 + 7)
	68	self.assertEquals(self.dom2.size(), 1)
	69	self.assertEquals(self.dom3.size(), 12)
	70
	71	def test_overlap(self):
	72	self.failUnless(self.dom1.overlap(self.dom2))
	73	self.failUnless(self.dom1.overlap(FiniteIntervalDomain(-5, 5, 1)))
	74	self.failUnless(self.dom1.overlap(FiniteIntervalDomain( 5, 15, 1)))
	75	self.failUnless(self.dom1.overlap(FiniteIntervalDomain(-5, 15, 1)))
	76	self.failIf(self.dom1.overlap(FiniteIntervalDomain(-15, 0, 1)))
	77	self.failIf(self.dom1.overlap(FiniteIntervalDomain(10, 25, 1)))
	78
	79	def test_SetLow(self):
	80	self.dom1.setLowestMin(2)
	81	self.assertEquals(self.dom1.lowestMin, 2)
	82	self.assertRaises(ConsistencyFailure, self.dom1.setLowestMin, 10)
	83
	84	def test_SetHigh(self):
	85	self.dom1.setHighestMax(9)
	86	self.assertEquals(self.dom1.highestMax, 9)
	87	self.assertRaises(ConsistencyFailure, self.dom1.setHighestMax, -10)
	88
	89	def test_SetMinLength(self):
	90	self.dom1.setMinLength(3)
	91	self.assertEquals(self.dom1._min_length, 3)
	92	self.dom1.setMinLength(4)
	93	self.assertEquals(self.dom1._min_length, 4)
	94	self.assertRaises(ConsistencyFailure, self.dom2.setMinLength, 5)
	95
	96	def test_SetMaxLength(self):
	97	self.dom1.setMaxLength(3)
	98	self.assertEquals(self.dom1._max_length, 3)
	99	self.dom1.setMaxLength(2)
	100	self.assertEquals(self.dom1._max_length, 2)
	101	self.assertRaises(ConsistencyFailure, self.dom2.setMaxLength, 1)
	102
	103	def test_FailureIfSizeEqualsZero(self):
	104	self.assertRaises(ConsistencyFailure, self.dom2.setHighestMax, 4)
	105
	106	def test_LatestStart(self):
	107	self.assertEquals(self.dom1.highestMin, 8)
	108	self.assertEquals(self.dom2.highestMin, 2)
	109	self.assertEquals(self.dom3.highestMin, 4)
	110
	111	def test_EarliestEnd(self):
	112	self.assertEquals(self.dom1.lowestMax, 2)
	113	self.assertEquals(self.dom2.lowestMax, 5)
	114	self.assertEquals(self.dom3.lowestMax, 4)
	115
	116	# FIXME check all possible cases are handled
	117	class ConstraintOverlapTC(unittest.TestCase):
	118	def setUp(self):
	119	self.d1 = FiniteIntervalDomain(0, 5, 2)
	120	self.d2 = FiniteIntervalDomain(0, 5, 3)
	121	self.d3 = FiniteIntervalDomain(1, 5, 3)
	122	self.d4 = FiniteIntervalDomain(0, 4, 2)
	123	self.d5 = FiniteIntervalDomain(1, 4, 2)
	124	self.d6 = FiniteIntervalDomain(4, 7, 2)
	125	self.d7 = FiniteIntervalDomain(0, 5, 4)
	126	self.d8 = FiniteIntervalDomain(3, 8, 4)
	127	self.d9 = FiniteIntervalDomain(3, 8, 1)
	128	self.d10 = FiniteIntervalDomain(0, 6, 2)
	129	self.d11 = FiniteIntervalDomain(1, 5, 2)
	130	self.d12 = FiniteIntervalDomain(0, 6, 3)
	131	self.d13 = FiniteIntervalDomain(1, 6, 3)
	132	self.d14 = FiniteIntervalDomain(0, 6, 3)
	133	self.d15 = FiniteIntervalDomain(0, 2, 2)
	134	self.d16 = FiniteIntervalDomain(0, 2, 2)
	135	self.domains = {'v1': self.d1,
	136	'v2': self.d2,
	137	'v3': self.d3,
	138	'v4': self.d4,
	139	'v5': self.d5,
	140	'v6': self.d6,
	141	'v7': self.d7,
	142	'v8': self.d8,
	143	'v9': self.d9,
	144	'v10': self.d10,
	145	'v11': self.d11,
	146	'v12': self.d12,
	147	'v13': self.d13,
	148	'v14': self.d14,
	149	'v15': self.d15,
	150	'v16': self.d16,
	151	}
	152
	153	# consistency failure
	154
	155	def test_NoOverlap_ConsistencyFailure(self):
	156	c = NoOverlap('v2', 'v3')
	157	self.assertRaises(ConsistencyFailure, c.narrow, self.domains)
	158	c = NoOverlap('v3', 'v2')
	159	self.assertRaises(ConsistencyFailure, c.narrow, self.domains)
	160
	161	def test_NoOverlap_ConsistencyFailure1(self):
	162	c = NoOverlap('v5', 'v2')
	163	self.assertRaises(ConsistencyFailure, c.narrow, self.domains)
	164	c = NoOverlap('v2', 'v5')
	165	self.assertRaises(ConsistencyFailure, c.narrow, self.domains)
	166
	167	def test_NoOverlap_ConsistencyFailure2(self):
	168	c = NoOverlap('v15', 'v16')
	169	self.assertRaises(ConsistencyFailure, c.narrow, self.domains)
	170	c = NoOverlap('v16', 'v15')
	171	self.assertRaises(ConsistencyFailure, c.narrow, self.domains)
	172
	173	# entailed
	174
	175	def test_NoOverlap_Entailed(self):
	176	c = NoOverlap('v6', 'v4')
	177	self.assertEquals(c.narrow(self.domains), 1)
	178	c = NoOverlap('v4', 'v6')
	179	self.assertEquals(c.narrow(self.domains), 1)
	180
	181	def test_NoOverlap_Entailed1(self):
	182	c = NoOverlap('v1', 'v3')
	183	self.assertEquals(c.narrow(self.domains), 1)
	184	c = NoOverlap('v3', 'v1')
	185	self.assertEquals(c.narrow(self.domains), 1)
	186
	187	def test_NoOverlap_Entailed2(self):
	188	c = NoOverlap('v7', 'v8')
	189	self.assertEquals(c.narrow(self.domains), 1)
	190	self.assertEquals(self.d7, FiniteIntervalDomain(0,4,4))
	191	self.assertEquals(self.d8, FiniteIntervalDomain(4,8,4))
	192
	193	def test_NoOverlap_Entailed2bis(self):
	194	c = NoOverlap('v8', 'v7')
	195	self.assertEquals(c.narrow(self.domains), 1)
	196	self.assertEquals(self.d7, FiniteIntervalDomain(0,4,4))
	197	self.assertEquals(self.d8, FiniteIntervalDomain(4,8,4))
	198
	199	def test_NoOverlap_Entailed3(self):
	200	c = NoOverlap('v7', 'v10')
	201	self.assertEquals(c.narrow(self.domains), 1)
	202	self.assertEquals(self.d7, FiniteIntervalDomain(0,4,4))
	203	self.assertEquals(self.d10, FiniteIntervalDomain(4,6,2))
	204
	205	def test_NoOverlap_Entailed3bis(self):
	206	c = NoOverlap('v10', 'v7')
	207	self.assertEquals(c.narrow(self.domains), 1)
	208	self.assertEquals(self.d7, FiniteIntervalDomain(0,4,4))
	209	self.assertEquals(self.d10, FiniteIntervalDomain(4,6,2))
	210
	211	def test_NoOverlap_Entailed4(self):
	212	c = NoOverlap('v12', 'v13')
	213	self.assertEquals(c.narrow(self.domains), 1)
	214	self.assertEquals(self.d12, FiniteIntervalDomain(0,3,3))
	215	self.assertEquals(self.d13, FiniteIntervalDomain(3,6,3))
	216
	217	def test_NoOverlap_Entailed4bis(self):
	218	c = NoOverlap('v13', 'v12')
	219	self.assertEquals(c.narrow(self.domains), 1)
	220	self.assertEquals(self.d12, FiniteIntervalDomain(0,3,3))
	221	self.assertEquals(self.d13, FiniteIntervalDomain(3,6,3))
	222
	223	# not entailed
	224
	225	def test_NoOverlap_NotEntailed(self):
	226	c = NoOverlap('v4', 'v1')
	227	self.assertEquals(c.narrow(self.domains), 0)
	228
	229	def test_NoOverlap_NotEntailed2(self):
	230	c = NoOverlap('v8', 'v9')
	231	self.assertEquals(c.narrow(self.domains), 0)
	232	c = NoOverlap('v9', 'v8')
	233	self.assertEquals(c.narrow(self.domains), 0)
	234
	235	def test_NoOverlap_NotEntailed3(self):
	236	c = NoOverlap('v11', 'v12')
	237	self.assertEquals(c.narrow(self.domains), 0)
	238	c = NoOverlap('v12', 'v11')
	239	self.assertEquals(c.narrow(self.domains), 0)
	240
	241	def test_NoOverlap_NotEntailed4(self):
	242	c = NoOverlap('v12', 'v14')
	243	self.assertEquals(c.narrow(self.domains), 0)
	244	c = NoOverlap('v14', 'v12')
	245	self.assertEquals(c.narrow(self.domains), 0)
	246
	247
	248	def test_equality(self):
	249	c1 = NoOverlap('v12', 'v14')
	250	c2 = NoOverlap('v14', 'v12')
	251	c3 = NoOverlap('v15', 'v12')
	252	self.assertEquals(c1, c2)
	253	self.assertNotEquals(c1, c3)
	254	self.assertNotEquals(c2, c3)
	255	self.assertEquals(c3, c3)
	256
	257	def test_hash(self):
	258	c1 = NoOverlap('v12', 'v14')
	259	c2 = NoOverlap('v14', 'v12')
	260	c3 = NoOverlap('v15', 'v12')
	261	d = {c1 : 'hello', c2 : 'hello', c3 : 'hello'}
	262	self.assertEquals(len(d), 2)
	263
	264
	265	class ConstraintTC(unittest.TestCase):
	266	def setUp(self):
	267	self.d1 = FiniteIntervalDomain(5, 10, 1, 1)
	268	self.d2 = FiniteIntervalDomain(2, 7, 1, 1)
	269	self.d3 = FiniteIntervalDomain(8, 10, 1, 1)
	270	self.d4 = FiniteIntervalDomain(3, 10, 5, 6)
	271	self.d5 = FiniteIntervalDomain(4, 10, 5)
	272	self.d6 = FiniteIntervalDomain(0, 3, 2)
	273	self.d7 = FiniteIntervalDomain(0, 5, 4)
	274	self.d8 = FiniteIntervalDomain(3, 8, 4)
	275	self.d9 = FiniteIntervalDomain(3, 8, 1)
	276	self.d10 = FiniteIntervalDomain(0, 6, 2)
	277	self.domains = {'v1': self.d1,
	278	'v2': self.d2,
	279	'v3': self.d3,
	280	'v4': self.d4,
	281	'v5': self.d5,
	282	'v6': self.d6,
	283	'v7': self.d7,
	284	'v8': self.d8,
	285	'v9': self.d9,
	286	'v10': self.d10,
	287	}
	288	##
	289	## StartsBeforeStart
	290	##
	291	def test_StartsBeforeStart_NotEntailed(self):
	292	c = StartsBeforeStart('v2','v1')
	293	ret = c.narrow(self.domains)
	294	self.assertEquals(ret, 0)
	295
	296	def test_StartsBeforeStart_ConsistencyFailure(self):
	297	c = StartsBeforeStart('v3','v2')
	298	self.assertRaises(ConsistencyFailure, c.narrow, self.domains)
	299
	300	def test_StartsBeforeStart_Entailed(self):
	301	c = StartsBeforeStart('v2','v3')
	302	ret = c.narrow(self.domains)
	303	self.assertEquals(ret, 1)
	304
	305	##
	306	## StartsBeforeEnd
	307	##
	308	def test_StartsBeforeEnd_NotEntailed(self):
	309	c = StartsBeforeEnd('v2','v1')
	310	ret = c.narrow(self.domains)
	311	self.assertEquals(ret, 0)
	312
	313	def test_StartsBeforeEnd_ConsistencyFailure(self):
	314	c = StartsBeforeEnd('v3','v2')
	315	self.assertRaises(ConsistencyFailure, c.narrow, self.domains)
	316
	317	def test_StartsBeforeEnd_Entailed(self):
	318	c = StartsBeforeEnd('v4', 'v1')
	319	ret = c.narrow(self.domains)
	320	self.assertEquals(ret, 1)
	321
	322	##
	323	## EndsBeforeStart
	324	##
	325	def test_EndsBeforeStart_Entailed(self):
	326	c = EndsBeforeStart('v2','v3')
	327	ret = c.narrow(self.domains)
	328	self.assertEquals(ret, 1)
	329
	330	def test_EndsBeforeStart_NotEntailed(self):
	331	c = EndsBeforeStart('v3','v1')
	332	ret = c.narrow(self.domains)
	333	self.assertEquals(ret, 0)
	334
	335	def test_EndsBeforeStart_NotEntailed_withRemoval(self):
	336	c = EndsBeforeStart('v1','v3')
	337	ret = c.narrow(self.domains)
	338	self.assertEquals(ret, 0)
	339	self.assertEquals(self.d1.highestMax, self.d3.highestMin)
	340
	341	def test_EndsBeforeStart_ConsistencyFailure(self):
	342	c = EndsBeforeStart('v3','v2')
	343	self.assertRaises(ConsistencyFailure, c.narrow, self.domains)
	344
	345	##
	346	## EndsBeforeEnd
	347	##
	348	def test_EndsBeforeEnd_Entailed(self):
	349	c = EndsBeforeEnd('v2','v3')
	350	ret = c.narrow(self.domains)
	351	self.assertEquals(ret, 1)
	352
	353	def test_EndsBeforeEnd_NotEntailed(self):
	354	c = EndsBeforeEnd('v2','v1')
	355	ret = c.narrow(self.domains)
	356	self.assertEquals(ret, 0)
	357	self.assertEquals(self.d2.highestMax, 7)
	358
	359	def test_EndsBeforeEnd_NotEntailed_withRemoval(self):
	360	c = EndsBeforeEnd('v1','v2')
	361	ret = c.narrow(self.domains)
	362	self.assertEquals(ret, 0)
	363	self.assertEquals(self.d1.highestMax, self.d2.highestMax)
	364
	365	def test_EndsBeforeEnd_ConsistencyFailure(self):
	366	c = EndsBeforeEnd('v3','v2')
	367	self.assertRaises(ConsistencyFailure, c.narrow, self.domains)
	368
	369	##
	370	## StartsAfterStart
	371	##
	372	def test_StartsAfterStart_Entailed(self):
	373	c = StartsAfterStart('v3','v2')
	374	ret = c.narrow(self.domains)
	375	self.assertEquals(ret, 1)
	376
	377	def test_StartsAfterStart_NotEntailed(self):
	378	c = StartsAfterStart('v1','v2')
	379	ret = c.narrow(self.domains)
	380	self.assertEquals(ret, 0)
	381	self.assertEquals(self.d1.lowestMin, 5)
	382
	383	def test_StartsAfterStart_NotEntailed_withRemoval(self):
	384	c = StartsAfterStart('v2','v1')
	385	ret = c.narrow(self.domains)
	386	self.assertEquals(ret, 0)
	387	self.assertEquals(self.d2.lowestMin, self.d1.lowestMin)
	388
	389	def test_StartsAfterStart_ConsistencyFailure(self):
	390	c = StartsAfterStart('v2','v3')
	391	self.assertRaises(ConsistencyFailure, c.narrow, self.domains)
	392
	393	##
	394	## StartsAfterEnd
	395	##
	396	def test_StartsAfterEnd_Entailed(self):
	397	c = StartsAfterEnd('v3','v2')
	398	ret = c.narrow(self.domains)
	399	self.assertEquals(ret, 1)
	400
	401	def test_StartsAfterEnd_NotEntailed_withRemoval(self):
	402	c = StartsAfterEnd('v1','v4')
	403	ret = c.narrow(self.domains)
	404	self.assertEquals(ret, 0)
	405	self.assertEquals(self.d1.lowestMin, self.d4.lowestMax)
	406
	407	def test_StartsAfterEnd_ConsistencyFailure(self):
	408	c = StartsAfterEnd('v2','v3')
	409	self.assertRaises(ConsistencyFailure, c.narrow, self.domains)
	410
	411	##
	412	## EndsAfterStart
	413	##
	414	def test_EndsAfterStart_Entailed(self):
	415	c = EndsAfterStart('v4','v2')
	416	ret = c.narrow(self.domains)
	417	self.assertEquals(ret, 1)
	418
	419	def test_EndsAfterStart_NotEntailed(self):
	420	c = EndsAfterStart('v4','v3')
	421	ret = c.narrow(self.domains)
	422	self.assertEquals(ret, 0)
	423
	424	def test_EndsAfterStart_ConsistencyFailure(self):
	425	c = EndsAfterStart('v2','v3')
	426	self.assertRaises(ConsistencyFailure, c.narrow, self.domains)
	427
	428
	429	##
	430	## EndsAfterEnd
	431	##
	432	def test_EndsAfterEnd_Entailed(self):
	433	c = EndsAfterEnd('v4','v2')
	434	ret = c.narrow(self.domains)
	435	self.assertEquals(ret, 1)
	436
	437	def test_EndsAfterEnd_NotEntailed(self):
	438	c = EndsAfterEnd('v4','v3')
	439	ret = c.narrow(self.domains)
	440	self.assertEquals(ret, 0)
	441
	442	def test_EndsAfterEnd_ConsistencyFailure(self):
	443	c = EndsAfterEnd('v2','v3')
	444	self.assertRaises(ConsistencyFailure, c.narrow, self.domains)
	445
	446
	447	class DistributorTC(unittest.TestCase):
	448	def setUp(self):
	449	self.d = FiniteIntervalDistributor()
	450
	451	def test_DistributeDifferentLengths(self):
	452	d1 = FiniteIntervalDomain(0, 5, 3, 5)
	453	d2 = FiniteIntervalDomain(0, 20, 1)
	454	domains = {'v1': d1,
	455	'v2': d2,
	456	}
	457	dom1, dom2 = self.d.distribute(domains)
	458	self.failUnless(dom1['v2'] == dom2['v2'])
	459	self.failUnless(dom1['v2'] == d2)
	460	self.failIf(dom1['v1'] == d1)
	461	self.failIf(dom2['v1'] == d1)
	462	self.assertEquals(dom1['v1']._max_length, d1._min_length)
	463	self.assertEquals(dom2["v1"]._min_length, d1._min_length+d1._resolution)
	464	self.assertEquals(d1.size(), dom1['v1'].size() + dom2['v1'].size())
	465
	466	def test_DistributeSameLengths(self):
	467	d1 = FiniteIntervalDomain(lowestMin=0, highestMax=5, min_length=4)
	468	d2 = FiniteIntervalDomain(lowestMin=0, highestMax=20, min_length=1)
	469	domains = {'v1': d1,
	470	'v2': d2,
	471	}
	472	dom1, dom2 = self.d.distribute(domains)
	473	self.failUnless(dom1['v2'] == dom2['v2'])
	474	self.failUnless(dom1['v2'] == d2)
	475	self.failIf(dom1['v1'] == d1)
	476	self.failIf(dom2['v1'] == d1)
	477	self.assertEquals(dom1['v1'].size(), 1)
	478	self.assertEquals(dom1["v1"].highestMax, d1._min_length + d1.lowestMin)
	479	self.assertEquals(dom2["v1"].lowestMin, d1._resolution + d1.lowestMin)
	480	self.assertEquals(d1.size(), dom1['v1'].size() + dom2['v1'].size())
	481
	482
	483	class PlannerTC(unittest.TestCase):
	484	def setUp(self):
	485	self.d = FiniteIntervalDistributor()
	486	self.verbose = 1
	487
	488	def solve_repo1(self, constraints):
	489	dom1 = FiniteIntervalDomain(0, 15, 5)
	490	dom2 = FiniteIntervalDomain(0, 15, 5)
	491	dom3 = FiniteIntervalDomain(0, 15, 5)
	492	repo = Repository( ['A','B','C'], { 'A': dom1,
	493	'B': dom2,
	494	'C': dom3 },
	495	constraints )
	496	s = Solver( self.d )
	497	answers = list(s.solve_all(repo,verbose=self.verbose))
	498	self.assertEquals(len(answers), 2)
	499	import pprint
	500	pprint.pprint( list(answers) )
	501
	502	def test_pb1(self):
	503	constraints = [ StartsAfterEnd('B','A'),
	504	StartsAfterEnd('C','A'),
	505	NoOverlap('B','C' ) ]
	506	self.solve_repo1( constraints )
	507
	508	def test_pb2(self):
	509	constraints = [ EndsBeforeStart('A','B'),
	510	EndsBeforeStart('A','C'),
	511	NoOverlap('B','C' ) ]
	512	self.solve_repo1( constraints )
	513
	514
	515	def solve_repo2(self, constraints):
	516	dom1 = FiniteIntervalDomain(0, 20, 5)
	517	dom2 = FiniteIntervalDomain(0, 20, 5)
	518	dom3 = FiniteIntervalDomain(0, 20, 10)
	519	dom4 = FiniteIntervalDomain(0, 20, 5)
	520	repo = Repository( ['A','B','C', 'D'], { 'A': dom1,
	521	'B': dom2,
	522	'C': dom3,
	523	'D': dom4 },
	524	constraints )
	525	s = Solver( self.d )
	526	answers = list(s.solve_all(repo,verbose=1))
	527	import pprint
	528	pprint.pprint( list(answers) )
	529
	530	def test_pb3(self):
	531	constraints = [ StartsAfterEnd('B','A'),
	532	StartsAfterEnd('C','A'),
	533	StartsAfterEnd('D','B'),
	534	StartsAfterEnd('D','C'),
	535	]
	536	self.solve_repo2( constraints )
	537
	538	def test_pb4(self):
	539	constraints = [ StartsAfterEnd('B','A'),
	540	StartsAfterEnd('C','A'),
	541	StartsAfterEnd('D','B'),
	542	StartsAfterEnd('D','C'),
	543	StartsAfterEnd('D','A'),
	544	]
	545	self.solve_repo2( constraints )
	546
	547
	548	if __name__ == '__main__':
	549	unittest.main()

+166

-0

test/test_propagation.py less more

	0	"""Unit testing for constraint propagation module"""
	1
	2	# (c) 2000-2001 LOGILAB S.A. (Paris, FRANCE).
	3	# http://www.logilab.fr/ -- mailto:contact@logilab.fr
	4	#
	5	# This program is free software; you can redistribute it and/or modify it under
	6	# the terms of the GNU General Public License as published by the Free Software
	7	# Foundation; either version 2 of the License, or (at your option) any later
	8	# version.
	9	#
	10	# This program is distributed in the hope that it will be useful, but WITHOUT
	11	# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
	12	# FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
	13	#
	14	# You should have received a copy of the GNU General Public License along with
	15	# this program; if not, write to the Free Software Foundation, Inc.,
	16	# 59 Temple Place - Suite 330, Boston, MA 02111-1307
	17	# USA.
	18
	19	import unittest
	20	import os
	21	from logilab.constraint.propagation import *
	22	from logilab.constraint import fd
	23	from logilab.constraint.distributors import DefaultDistributor
	24
	25	class Repository_TC(unittest.TestCase):
	26	def setUp(self):
	27	self.domains = {}
	28	self.variables = list('abcdef')
	29	for v in self.variables:
	30	self.domains[v] = fd.FiniteDomain(range(6))
	31
	32	self.repo = Repository(self.variables, self.domains)
	33
	34	def testVCGDraw(self):
	35	for v1 in self.variables:
	36	for v2 in self.variables:
	37	if v1 < v2:
	38	self.repo.addConstraint(fd.make_expression((v1, v2),
	39	'%s < %s'%(v1, v2)))
	40	try:
	41	try:
	42	self.repo.vcg_draw('toto.vcg')
	43	except IOError, exc:
	44	self.fail('This test cannot run in the testing environment'
	45	'because I cannot write the file.\n'
	46	'The error message was: \n%s' % exc)
	47	finally:
	48	os.unlink('toto.vcg')
	49
	50
	51
	52	def testGetDomains(self):
	53	doms = self.repo.getDomains()
	54	self.assertEqual(doms, self.domains)
	55
	56	def testDistribute(self):
	57	d = []
	58	for distributed in self.repo.distribute(DefaultDistributor()):
	59	d.append(distributed)
	60	self.assertEqual(len(d),2)
	61
	62	def testConsistencyNoConstraint(self):
	63	self.repo.consistency()
	64	for v, dom in self.repo.getDomains().items():
	65	self.assertEqual(dom.size(),6)
	66
	67	def testConsistency(self):
	68	for v1 in self.variables:
	69	for v2 in self.variables:
	70	if v1 < v2:
	71	self.repo.addConstraint(fd.make_expression((v1, v2),
	72	'%s < %s'%(v1, v2)))
	73
	74	self.repo.consistency()
	75	for v, dom in self.repo.getDomains().items():
	76	self.assertEqual(dom.size(),1)
	77
	78	def testInconsistency(self):
	79	self.repo.addConstraint(fd.make_expression(('a', 'b'),
	80	'a < b'))
	81	self.repo.addConstraint(fd.make_expression(('a', 'b'),
	82	'a > b'))
	83
	84	try:
	85	self.repo.consistency()
	86	self.fail('No ConsistencyFailure raised')
	87	except ConsistencyFailure:
	88	pass
	89
	90
	91	class Sover_TC(unittest.TestCase):
	92	def setUp(self):
	93	self.solver = Solver()
	94	self.domains = {}
	95	self.variables = list('abcdef')
	96	for v in self.variables:
	97	self.domains[v] = fd.FiniteDomain(range(6))
	98
	99	self.repo = Repository(self.variables, self.domains)
	100	for v1 in self.variables:
	101	for v2 in self.variables:
	102	if v1 < v2:
	103	self.repo.addConstraint(fd.make_expression((v1, v2),
	104	'%s < %s'%(v1, v2)))
	105
	106
	107	def testSolveOne(self):
	108	solution = self.solver.solve_one(self.repo)
	109	self.assertEqual(solution,{'a':0, 'b':1, 'c':2, 'd':3, 'e':4, 'f':5})
	110
	111	def testSolve(self):
	112	solutions = self.solver.solve(self.repo)
	113	self.assertEqual(solutions,
	114	[{'a':0, 'b':1, 'c':2, 'd':3, 'e':4, 'f':5}])
	115
	116	def testSolveAll(self):
	117	solutions = []
	118	for s in self.solver.solve_all(self.repo):
	119	solutions.append(s)
	120	self.assertEqual(solutions,
	121	[{'a':0, 'b':1, 'c':2, 'd':3, 'e':4, 'f':5}])
	122
	123	def testNolutionSolve(self):
	124	self.repo.addConstraint(fd.make_expression(('a', 'b'),
	125	'b < a'))
	126
	127	solutions = self.solver.solve(self.repo)
	128	self.assertEqual(solutions,
	129	[])
	130
	131
	132	class SolverBest_TC(unittest.TestCase):
	133	def setUp(self):
	134	self.solver = Solver()
	135	self.domains = {}
	136	self.variables = list('abc')
	137	for v in self.variables:
	138	self.domains[v] = fd.FiniteDomain(range(6))
	139
	140	self.repo = Repository(self.variables, self.domains)
	141	for v1 in self.variables:
	142	for v2 in self.variables:
	143	if v1 < v2:
	144	self.repo.addConstraint(fd.make_expression((v1, v2),
	145	'%s < %s'%(v1, v2)))
	146
	147	def costFunc(self, a,b,c):
	148	return -(aa+bb+c*c)
	149
	150	def testSolveBest(self):
	151	solutions = []
	152	for s in self.solver.solve_best(self.repo, self.costFunc):
	153	solutions.append(s)
	154
	155	costs = [self.costFunc(**sol[0]) for sol in solutions]
	156	sorted_costs = costs[:]
	157	sorted_costs.sort()
	158	sorted_costs.reverse()
	159	self.assertEquals(costs, sorted_costs)
	160	self.assertEquals(costs, [s[1] for s in solutions])
	161
	162
	163
	164	if __name__ == '__main__':
	165	unittest.main()

+100

-0

test/test_validation.py less more

	0	"""Validation testing for constraint propagation module"""
	1
	2	# (c) 2000-2001 LOGILAB S.A. (Paris, FRANCE).
	3	# http://www.logilab.fr/ -- mailto:contact@logilab.fr
	4	#
	5	# This program is free software; you can redistribute it and/or modify it under
	6	# the terms of the GNU General Public License as published by the Free Software
	7	# Foundation; either version 2 of the License, or (at your option) any later
	8	# version.
	9	#
	10	# This program is distributed in the hope that it will be useful, but WITHOUT
	11	# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
	12	# FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
	13	#
	14	# You should have received a copy of the GNU General Public License along with
	15	# this program; if not, write to the Free Software Foundation, Inc.,
	16	# 59 Temple Place - Suite 330, Boston, MA 02111-1307
	17	# USA.
	18
	19	from logilab.common.testlib import TestCase
	20
	21	from logilab.constraint import *
	22	from logilab.constraint.distributors import EnumeratorDistributor
	23
	24	import os, sys
	25	from cStringIO import StringIO
	26
	27	class Queens8_TC(TestCase):
	28	size = 8
	29	nb_sols = 92
	30	verbose=0
	31	def setUp(self):
	32	variables = []
	33	domains = {}
	34	constraints = []
	35	for i in range(self.size):
	36	name = 'Q%d'%i
	37	variables.append(name)
	38	domains[name] = fd.FiniteDomain([(i,j) for j in range(self.size)])
	39
	40	for q1 in variables:
	41	for q2 in variables:
	42	if q1 < q2:
	43	c = fd.make_expression((q1,q2),
	44	'%(q1)s[0] < %(q2)s[0] and '
	45	'%(q1)s[1] != %(q2)s[1] and '
	46	'abs(%(q1)s[0]-%(q2)s[0]) != '
	47	'abs(%(q1)s[1]-%(q2)s[1])'%\
	48	{'q1':q1,'q2':q2})
	49	constraints.append(c)
	50	self.repo = Repository(variables,domains,constraints)
	51	sys.stdout = StringIO()
	52
	53	def tearDown(self):
	54	sys.stdout = sys.__stdout__
	55
	56	def testQueensWithEnumerator(self):
	57	self.skip("to long")
	58	solver = Solver(EnumeratorDistributor())
	59	solutions = solver.solve(self.repo, verbose=self.verbose)
	60	self.assertEqual(len(solutions), self.nb_sols)
	61
	62	def testQueensWithDefaultDistributor(self):
	63	self.skip("to long")
	64	solver = Solver()
	65	solutions = solver.solve(self.repo, verbose=self.verbose)
	66	self.assertEqual(len(solutions), self.nb_sols)
	67
	68
	69
	70	class Queens4_TC(Queens8_TC):
	71	size=4
	72	nb_sols=2
	73
	74	class Queens5_TC(Queens8_TC):
	75	size=5
	76	nb_sols=10
	77
	78	class Queens6_TC(Queens8_TC):
	79	size=6
	80	nb_sols=4
	81
	82	class Queens7_TC(Queens8_TC):
	83	size=7
	84	nb_sols=40
	85
	86	class Queens6Verbose_TC(Queens6_TC):
	87	verbose = 3
	88
	89
	90	# remove if we are running with pylint, 'cos this gets too long without psyco
	91	if os.environ.get('PYLINT_IMPORT') != '1':
	92	class Queens9_TC(Queens8_TC):
	93	size=9
	94	nb_sols=352
	95
	96	class Queens10_TC(Queens8_TC):
	97	size=10
	98	nb_sols=724
	99