File: distributors.py

package info (click to toggle)
constraint 0.3.0-5
  • links: PTS
  • area: main
  • in suites: etch, etch-m68k
  • size: 312 kB
  • ctags: 501
  • sloc: python: 2,736; xml: 165; makefile: 43; sh: 1
file content (177 lines) | stat: -rw-r--r-- 6,674 bytes parent folder | download | duplicates (2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
# (c) 2000-2001 LOGILAB S.A. (Paris, FRANCE).
# http://www.logilab.fr/ -- mailto:contact@logilab.fr
#
# This program is free software; you can redistribute it and/or modify it under
# the terms of the GNU General Public License as published by the Free Software
# Foundation; either version 2 of the License, or (at your option) any later
# version.
#
# This program is distributed in the hope that it will be useful, but WITHOUT
# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
# FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License along with
# this program; if not, write to the Free Software Foundation, Inc.,
# 59 Temple Place - Suite 330, Boston, MA  02111-1307
# USA.

"""
distributors - part of Logilab's constraint satisfaction solver.
"""

__revision__ = '$Id: distributors.py,v 1.25 2005/01/14 15:16:21 alf Exp $'

from logilab.constraint.psyco_wrapper import Psyobj
from logilab.constraint.interfaces import DistributorInterface
import math, random

def make_new_domains(domains):
    """return a shallow copy of dict of domains passed in argument"""
    domain = {}
    for key, value in domains.items():
        domain[key] = value.copy()
    return domain

class AbstractDistributor(Psyobj):
    """Implements DistributorInterface but abstract because
    _distribute is left unimplemented."""

    __implements__ = DistributorInterface

    def __init__(self, nb_subspaces=2):
        self.nb_subspaces = nb_subspaces
        self.verbose = 0
        
    def findSmallestDomain(self, domains):
        """returns the variable having the smallest domain.
        (or one of such varibles if there is a tie)
        """
        domlist = [(dom.size(), variable ) for variable, dom in domains.items()
                                           if dom.size() > 1]
        domlist.sort()
        return domlist[0][1]

    def findLargestDomain(self, domains):
        """returns the variable having the largest domain.
        (or one of such variables if there is a tie)
        """
        domlist = [(dom.size(), variable) for variable, dom in domains.items()
                                          if dom.size() > 1]
        domlist.sort()
        return domlist[-1][1]

    def nb_subdomains(self, domains):
        """return number of sub domains to explore"""
        return self.nb_subspaces

    def distribute(self, domains, verbose=0):
        """do the minimal job and let concrete class distribute variables
        """
        self.verbose = verbose
        replicas = []
        for i in range(self.nb_subdomains(domains)):
            replicas.append(make_new_domains(domains))
        modified_domains = self._distribute(*replicas)
        for domain in modified_domains:
            domain.resetFlags()
        return replicas

    def _distribute(self, *args):
        """ method to implement in concrete class

        take self.nb_subspaces copy of the original domains as argument
        distribute the domains and return each modified domain
        """
        raise NotImplementedError("Use a concrete implementation of "
                                  "the Distributor interface")
        
class NaiveDistributor(AbstractDistributor):
    """distributes domains by splitting the smallest domain in 2 new domains
    The first new domain has a size of one,
    and the second has all the other values"""

    def __init__(self):
        AbstractDistributor.__init__(self)
        
    def _distribute(self, dom1, dom2):
        """See AbstractDistributor"""
        variable = self.findSmallestDomain(dom1)
        values = dom1[variable].getValues()
        if self.verbose:
            print 'Distributing domain for variable', variable, \
                  'at value', values[0]
        dom1[variable].removeValues(values[1:])
        dom2[variable].removeValue(values[0])
        return (dom1[variable], dom2[variable])


class RandomizingDistributor(AbstractDistributor):
    """distributes domains as the NaiveDistrutor, except that the unique
    value of the first domain is picked at random."""

    def __init__(self):
        AbstractDistributor.__init__(self)
        
    def _distribute(self, dom1, dom2):
        """See AbstractDistributor"""
        variable = self.findSmallestDomain(dom1)
        values = dom1[variable].getValues()
        distval = random.choice(values)
        values.remove(distval)
        if self.verbose:
            print 'Distributing domain for variable', variable, \
                  'at value', distval
        dom1[variable].removeValues(values)
        dom2[variable].removeValue(distval)
        return (dom1[variable], dom2[variable])
    

class SplitDistributor(AbstractDistributor):
    """distributes domains by splitting the smallest domain in
    nb_subspaces equal parts or as equal as possible.
    If nb_subspaces is 0, then the smallest domain is split in
    domains of size 1"""
    
    def __init__(self, nb_subspaces=3):
        AbstractDistributor.__init__(self, nb_subspaces)
        self.__to_split = None
    def nb_subdomains(self, domains):
        """See AbstractDistributor"""
        self.__to_split = self.findSmallestDomain(domains)
        if self.nb_subspaces:
            return min(self.nb_subspaces, domains[self.__to_split].size())
        else:
            return domains[self.__to_split].size()
    
    def _distribute(self, *args):
        """See AbstractDistributor"""
        variable = self.__to_split
        nb_subspaces = len(args)
        values = args[0][variable].getValues()
        nb_elts = max(1, len(values)*1./nb_subspaces)
        slices = [(int(math.floor(index * nb_elts)),
                   int(math.floor((index + 1) * nb_elts)))
                  for index in range(nb_subspaces)]
        if self.verbose:
            print 'Distributing domain for variable', variable
        modified = []
        for (dom, (end, start)) in zip(args, slices) :
            dom[variable].removeValues(values[:end])
            dom[variable].removeValues(values[start:])
            modified.append(dom[variable])
        return modified

class DichotomyDistributor(SplitDistributor):
    """distributes domains by splitting the smallest domain in
    two equal parts or as equal as possible"""
    def __init__(self):
        SplitDistributor.__init__(self, 2)


class EnumeratorDistributor(SplitDistributor):
    """distributes domains by splitting the smallest domain
    in domains of size 1."""
    def __init__(self):
        SplitDistributor.__init__(self, 0)

DefaultDistributor = DichotomyDistributor