Method: ConstraintSolver::AllDifferentConstraint#revise_hyperarc

Defined in:
lib/AllDifferentConstraint.rb

#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