Class: ConstraintSolver::AllDifferentConstraint

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

Overview

Represents the all different constraint.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(variables, violationCost = 1) ⇒ AllDifferentConstraint

Initialises a new all different constraint. The constructor takes the list of variables that must be different as an argument. Optionally, a cost for violating the constraint can be specified.



16
17
18
19
20
21
22
 
# File 'lib/AllDifferentConstraint.rb', line 16

def initialize(variables, violationCost=1)
    if variables.empty? or variables.size == 1
	raise ArgumentError, "List of variables must contain at least two elements!"
    end
    @variables = variables
    @violationCost = violationCost
end

Instance Attribute Details

#variables ⇒ Object (readonly)

Returns the value of attribute variables.



11
12
13
 
# File 'lib/AllDifferentConstraint.rb', line 11

def variables
  @variables
end

#violationCost ⇒ Object (readonly)

Returns the value of attribute violationCost.



11
12
13
 
# File 'lib/AllDifferentConstraint.rb', line 11

def violationCost
  @violationCost
end

Instance Method Details

#==(constraint) ⇒ Object 



57
58
59
60
 
# File 'lib/AllDifferentConstraint.rb', line 57

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

#allAssigned? ⇒ Boolean

Returns:

  • (Boolean) 


38
39
40
41
42
43
 
# File 'lib/AllDifferentConstraint.rb', line 38

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

#each ⇒ Object 



62
63
64
65
66
 
# File 'lib/AllDifferentConstraint.rb', line 62

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

#holds? ⇒ Boolean

Checks whether all the variables have different values assigned to them.

Returns:

  • (Boolean) 


26
27
28
29
30
31
32
33
34
35
36
 
# File 'lib/AllDifferentConstraint.rb', line 26

def holds?
    assigned = @variables.select { |var| var.assigned? }
    assigned.each { |variable|
	assigned.eachAfter(variable) { |otherVariable|
	    if variable.value == otherVariable.value
		return false
	    end
	}
    }
    return true
end

#include?(variable) ⇒ Boolean

Returns:

  • (Boolean) 


45
46
47
 
# File 'lib/AllDifferentConstraint.rb', line 45

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

#revise_decomposed_local ⇒ Object Also known as: revise 



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

def revise_decomposed_local
    revisedVariables = []
    wipeout = false
    pruneList = Set.new
    assignedVariables, unassignedVariables = @variables.partition { |var| var.assigned? }
    pruneList.merge(assignedVariables.collect { |var| var.value })
    unassignedVariables.find_all { |var| var.domain.include_any?(pruneList) }.each { |var|
	begin
	    var.domain.prune(pruneList)
	rescue DomainWipeoutException
	    wipeout = true
	end
	revisedVariables << var
	break if wipeout
    }
    unless wipeout
	workQueue = unassignedVariables.find_all { |var| var.domain.size == 1 }
	while not workQueue.empty?
	    currentVariable = workQueue.shift
	    currentValue = currentVariable.domain.first
	    ((unassignedVariables - [ currentVariable ]).find_all { |var|
		var.domain.include?(currentValue)
	    }).each { |var|
		begin
		    var.domain.prune(currentValue)
		rescue DomainWipeoutException
		    wipeout = true
		end
		revisedVariables << var
		break if wipeout
		workQueue << var if var.domain.size == 1
	    }
	end

	unless wipeout
	    # check satisfiability
	    valueList = Set.new
	    unassignedVariables.each { |var|
		valueList.merge(var.values)
	    }
	    if unassignedVariables.size > valueList.size
		wipeout = true
	    end
	end
    end
    return revisedVariables, 0, wipeout
end

#revise_hyperarc ⇒ Object

hyperarc consistency algorithm due Regin (1994)



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

def revise_hyperarc
    wipeout = false
    unless @value_graph
	e = Hash.new
	@variables.each { |var|
	    e[var.name] = var.domain.values.dup
	}
	@value_graph = GraphUtils::BipartiteGraph.new(e.keys.to_set, e.values.to_set.flatten, e)
    else
	# update graph
	@value_graph.e.clear
	@variables.each { |var|
	    @value_graph.e[var.name] = var.domain.values.dup
	}
	# The set of values is not updated because spurious values with
	# no edges attached to them add only minimal overhead
	#@value_graph.y = @value_graph.e.values.to_set.flatten
    end

    matching = @value_graph.maximum_matching
    if matching.size < @variables.size
	return [], 0, true
    end

    pruneMap = @value_graph.removable_values(matching)

    revisedVariables = Array.new
    pruneMap.each { |name,pruneList|
	var = @variables.find { |var| var.name == name }
	begin
	    var.domain.prune(pruneList)
	rescue DomainWipeoutException
	    wipeout = true
	end
	revisedVariables << var
	break if wipeout
    }

    return revisedVariables, 0, wipeout
end

#to_s ⇒ Object 



49
50
51
 
# File 'lib/AllDifferentConstraint.rb', line 49

def to_s
    @variables.collect { |var| var.name }.join(" != ")
end

#to_s_full ⇒ Object 



53
54
55
 
# File 'lib/AllDifferentConstraint.rb', line 53

def to_s_full
    @variables.collect { |var| var.to_s }.join(" != ")
end