Class: ConstraintSolver::TupleConstraint

Inherits:
AbstractConstraint show all
Defined in:
lib/TupleConstraint.rb

Overview

Represents a constraint which is specified by the allowed or disallowed tuples of arbitrary arity.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(variables, tuples, allowedTuples = true, violationCost = 1) ⇒ TupleConstraint

Initialises a new tuple constraint. The first argument is the list of variables involved in the constraint, the second argument is an array of tuples. Each element of the array is an array with exactly as many elements as the array of variables. The third argument specifies whether the array of tuples lists the allowed or disallowed tuples. Default is allowed tuples. Optionally, a cost for violating the constraint can be specified.



18
19
20
21
22
23
24
25
26
 
# File 'lib/TupleConstraint.rb', line 18

def initialize(variables, tuples, allowedTuples=true, violationCost=1)
    @variables = variables
    unless tuples.inject(true) { |bool,tuple| bool & (tuple.size == variables.size) }
	raise ArgumentError, "All tuples must have " + variables.size.to_s + " elements!"
    end
    @tuples = tuples
    @violationCost = violationCost
    @allowedTuples = allowedTuples
end

Instance Attribute Details

#allowedTuples ⇒ Object (readonly)

Returns the value of attribute allowedTuples.



10
11
12
 
# File 'lib/TupleConstraint.rb', line 10

def allowedTuples
  @allowedTuples
end

#tuples ⇒ Object (readonly)

Returns the value of attribute tuples.



10
11
12
 
# File 'lib/TupleConstraint.rb', line 10

def tuples
  @tuples
end

#variables ⇒ Object (readonly)

Returns the value of attribute variables.



10
11
12
 
# File 'lib/TupleConstraint.rb', line 10

def variables
  @variables
end

#violationCost ⇒ Object (readonly)

Returns the value of attribute violationCost.



10
11
12
 
# File 'lib/TupleConstraint.rb', line 10

def violationCost
  @violationCost
end

Instance Method Details

#==(constraint) ⇒ Object 



63
64
65
66
67
 
# File 'lib/TupleConstraint.rb', line 63

def ==(constraint)
    return false unless constraint.kind_of?(TupleConstraint)
    (@variables == constraint.variables) and (@tuples == constraint.tuples) and
	(@allowedTuples == constraint.allowedTuples) and (@violationCost == constraint.violationCost)
end

#allAssigned? ⇒ Boolean

Returns:

  • (Boolean) 


44
45
46
47
48
49
 
# File 'lib/TupleConstraint.rb', line 44

def allAssigned?
    @variables.each { |var|
	return false if not var.assigned?
    }
    return true
end

#each ⇒ Object 



69
70
71
72
73
 
# File 'lib/TupleConstraint.rb', line 69

def each
    @variables.each { |var|
	yield var
    }
end

#holds? ⇒ Boolean

Checks whether the assignments to the variables are allowed tuples.

Returns:

  • (Boolean) 


29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
# File 'lib/TupleConstraint.rb', line 29

def holds?
    tups = @tuples
    @variables.each_with_index { |var,i|
	next unless var.assigned?
	tups = tups.find_all { |tup| tup[i] == var.value }
	if @allowedTuples
	    return false if tups.empty?
	end
    }
    if not @allowedTuples and allAssigned? and tuples.include?(@variables.collect { |var| var.value })
	return false
    end
    return true
end

#include?(variable) ⇒ Boolean

Returns:

  • (Boolean) 


51
52
53
 
# File 'lib/TupleConstraint.rb', line 51

def include?(variable)
    @variables.include?(variable)
end

#revise ⇒ Object 



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
 
# File 'lib/TupleConstraint.rb', line 75

def revise
    revisedVariables = []
    checks = 0
    wipeout = false
    assignedIndices, unassignedIndices = (0..(@variables.size - 1)).partition { |i| @variables[i].assigned? }
    pruneTuples = (@allowedTuples ? @tuples : [])
    assignedIndices.each { |i|
	if @allowedTuples
	    pruneTuples = pruneTuples.find_all { |tup| tup[i] == @variables[i].value }
	else
	    (@tuples - pruneTuples).each { |tup|
		if @variables[i].value == tup[i]
		    pruneTuples << tup
		end
	    }
	end
    }
    unassignedIndices.each { |i|
	var = @variables[i]
	pruneList = pruneTuples.collect { |tup| tup[i] }.to_set
	if @allowedTuples
	    pruneList = var.domain.values - pruneList
	end
	if var.domain.include_any?(pruneList)
	    begin
		var.domain.prune(pruneList)
	    rescue DomainWipeoutException
		wipeout = true
	    end
	    revisedVariables << var
	    break if wipeout
	end
    }
    return revisedVariables, checks, wipeout
end

#to_s ⇒ Object 



55
56
57
 
# File 'lib/TupleConstraint.rb', line 55

def to_s
    @variables.collect { |var| var.name }.join(", ") + ": " + tuples.join(", ")
end

#to_s_full ⇒ Object 



59
60
61
 
# File 'lib/TupleConstraint.rb', line 59

def to_s_full
    @variables.collect { |var| var.to_s }.join(", ") + ": " + tuples.join(", ")
end