Github repo: https://github.com/mgritter/soffit
I completely replaced or-tools with python-constraint, a pure-Python constraint solver. What effect this will have on my ability to handle large graphs I don't know. I had written tests that gave me pretty good coverage, so I was easily able to verify that my replacement was working (which, of course, it wasn't the first few times due to various stupid errors or omissions.)
The constraint library lacked the "allowed assignments" I'd been using with or-tools, so I wrote a Constraint subclass that did the same thing. It uses some advanced features of constraint to limit the domain of variables.
The constructor takes a list of tuples that are allowed assignments of the variables. Which variables will be specified when the constraint is added; they're not included in the Constraint object itself, so in theory the same Constraint could be used for different sets of variables.
class TupleConstraint(Constraint):
"""Provided a collection of tuples, verify that the variable values
appear as a tuple (in the order specified for the variables.)."""
def __init__( self, tupleList ):
self.allowedSet = set( tuple( t ) for t in tupleList )
if len( self.allowedSet ) > 0:
someTuple = next( iter( self.allowedSet ) )
self.nthSet = [ set( t[i] for t in self.allowedSet )
for i in range( len( someTuple ) ) ]
else:
self.nthSet = []
The main interface to Constraint classes is the "function call" operator. It receives a list of variables, a domain for each variable (as a map), and the preliminary assignment for some subset of the variables (another map.)
For now I just do the simple thing--- if any variables are unassigned, then the constraint isn't violated and if all variables have values, then we can just do set membership.
def __call__(self, variables, domains, assignments, forwardcheck=False):
current = tuple( assignments.get( v, Unassigned ) for v in variables )
if Unassigned in current:
return True
else:
return current in self.allowedSet
The final part of the Constraint class that I implemented was a preprocess step which is allowed to edit the domain for each variable to limit the search. The constraint can even remove itself from the list of constraints, if editing the domain is sufficient to ensure the constraint is always satisfied.
If there is only one tuple, that's equivalent to a direct assignment to each variable. If there are multiple tuples, then each variable can only have the values that occur in corresponding locations within each tuple.
def preProcess(self, variables, domains, constraints, vconstraints):
# If only a single value allowed, variables must be equal to that.
# If domain already chopped, then what?
if len( self.allowedSet ) == 0:
# Impossible
for v in variables:
domains[v] = Domain( [] )
vcontraints[v].remove( (self,variables) )
constraints.remove( (self,variables) )
return
elif len( self.allowedSet ) == 1:
allowed = next( iter( self.allowedSet ) )
for (v, val) in zip( variables, allowed ):
if val in domains[v]:
domains[v] = Domain( [val] )
else:
domains[v] = Domain( [] )
vconstraints[v].remove( (self,variables) )
constraints.remove( (self,variables) )
return
# If some variable is only allowed a subset of values in its domain,
# then restrict to that subset.
for (i,v) in enumerate( variables ):
for val in domains[v][:]:
if val not in self.nthSet[i]:
domains[v].remove( val )
Example use of this new Constraint class in my test:
def test_real_problem( self ):
p = Problem()
p.addVariable( 'a', range( 5 ) )
p.addVariable( 'b', range( 5 ) )
p.addVariable( 'c', range( 5 ) )
firstPair = [ (1, 2),
(2, 3),
(3, 4) ]
secondPair = [ (2, 3),
(3, 0),
(4, 0) ]
p.addConstraint( TupleConstraint( firstPair ), ['a', 'b'] )
p.addConstraint( TupleConstraint( secondPair ), ['b', 'c'] )
soln = p.getSolutions()
self.assertIn( {'a' : 1, 'b': 2, 'c': 3 }, soln )
self.assertIn( {'a' : 2, 'b': 3, 'c': 0 }, soln )
self.assertIn( {'a' : 3, 'b': 4, 'c': 0 }, soln )
self.assertEqual( len( soln ), 3 )