Class: Solve::Solver

Inherits:
Object
  • Object
show all
Defined in:
lib/solve/solver.rb,
lib/solve/solver/serializer.rb,
lib/solve/solver/variable_row.rb,
lib/solve/solver/constraint_row.rb,
lib/solve/solver/variable_table.rb,
lib/solve/solver/constraint_table.rb

Overview

Author:

Defined Under Namespace

Classes: ConstraintRow, ConstraintTable, Serializer, VariableRow, VariableTable

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(graph, demands = Array.new, ui = nil) ⇒ Solver

Returns a new instance of Solver.

Parameters:

  • graph (Solve::Graph)
  • demands (Array<String>, Array<Array<String, String>>) (defaults to: Array.new)
  • ui (#say) (defaults to: nil) 


76
77
78
79
80
81
82
83
84
85
86
87
88
89
 
# File 'lib/solve/solver.rb', line 76

def initialize(graph, demands = Array.new, ui=nil) 
  @graph = graph
  @demands = Hash.new
  @ui = ui.respond_to?(:say) ? ui : nil

  @domain = Hash.new
  @possible_values = Hash.new
  @constraint_table = ConstraintTable.new
  @variable_table = VariableTable.new

  Array(demands).each do |l_demand|
    demands(*l_demand)
  end
end

Instance Attribute Details

#constraint_table ⇒ Object (readonly)

Returns the value of attribute constraint_table.



70
71
72
 
# File 'lib/solve/solver.rb', line 70

def constraint_table
  @constraint_table
end

#demands(name, constraint) ⇒ Solve::Demand (readonly) #demands(name) ⇒ Solve::Demand (readonly) #demands ⇒ Array<Solve::Demand> (readonly)

Overloads:



154
155
156
 
# File 'lib/solve/solver.rb', line 154

def demands
  @demands
end

#domain ⇒ Object (readonly)

Returns the value of attribute domain.



68
69
70
 
# File 'lib/solve/solver.rb', line 68

def domain
  @domain
end

#graph ⇒ Solve::Graph (readonly)

The world as we know it

Returns:



64
65
66
 
# File 'lib/solve/solver.rb', line 64

def graph
  @graph
end

#possible_values ⇒ Object (readonly)

Returns the value of attribute possible_values.



71
72
73
 
# File 'lib/solve/solver.rb', line 71

def possible_values
  @possible_values
end

#ui ⇒ Object (readonly)

Returns the value of attribute ui.



66
67
68
 
# File 'lib/solve/solver.rb', line 66

def ui
  @ui
end

#variable_table ⇒ Object (readonly)

Returns the value of attribute variable_table.



69
70
71
 
# File 'lib/solve/solver.rb', line 69

def variable_table
  @variable_table
end

Class Method Details

.demand_key(demand) ⇒ Symbol

Create a key to identify a demand on a Solver.

Parameters:

Returns:

  • (Symbol)

Raises:

  • (NoSolutionError) 


18
19
20
 
# File 'lib/solve/solver.rb', line 18

def demand_key(demand)
  "#{demand.name}-#{demand.constraint}".to_sym
end

.satisfy_all(constraints, versions) ⇒ Array<Solve::Version>

Returns all of the versions which satisfy all of the given constraints

Parameters:

Returns:



28
29
30
31
32
33
34
35
36
37
38
39
40
 
# File 'lib/solve/solver.rb', line 28

def satisfy_all(constraints, versions)
  constraints = Array(constraints).collect do |con|
    con.is_a?(Constraint) ? con : Constraint.new(con.to_s)
  end.uniq

  versions = Array(versions).collect do |ver|
    ver.is_a?(Version) ? ver : Version.new(ver.to_s)
  end.uniq

  versions.select do |ver|
    constraints.all? { |constraint| constraint.satisfies?(ver) }
  end
end

.satisfy_best(constraints, versions) ⇒ Solve::Version

Return the best version from the given list of versions for the given list of constraints

Parameters:

Returns:

Raises:

  • (NoSolutionError) —

    if version matches the given constraints



50
51
52
53
54
55
56
57
58
 
# File 'lib/solve/solver.rb', line 50

def satisfy_best(constraints, versions)
  solution = satisfy_all(constraints, versions)

  if solution.empty?
    raise Errors::NoSolutionError
  end

  solution.sort.last
end

Instance Method Details

#add_demand(demand) ⇒ Solve::Demand Also known as: demand

Add a Solve::Demand to the collection of demands and return the added Solve::Demand. No change will be made if the demand is already a member of the collection.

Parameters:

Returns:



180
181
182
183
184
185
186
 
# File 'lib/solve/solver.rb', line 180

def add_demand(demand)
  unless has_demand?(demand)
    @demands[self.class.demand_key(demand)] = demand
  end

  demand
end

#has_demand?(demand) ⇒ Boolean

Parameters:

Returns:

  • (Boolean) 


199
200
201
 
# File 'lib/solve/solver.rb', line 199

def has_demand?(demand)
  @demands.has_key?(self.class.demand_key(demand))
end

#remove_demand(demand) ⇒ Object

Parameters:



190
191
192
193
194
 
# File 'lib/solve/solver.rb', line 190

def remove_demand(demand)
  if has_demand?(demand)
    @demands.delete(self.class.demand_key(demand))
  end
end

#resolve ⇒ Hash

Returns:

  • (Hash) 


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
 
# File 'lib/solve/solver.rb', line 92

def resolve
  trace("Attempting to find a solution")
  seed_demand_dependencies

  while unbound_variable = variable_table.first_unbound
    possible_values_for_unbound = possible_values_for(unbound_variable)
    trace("Searching for a value for #{unbound_variable.artifact}")
    trace("Constraints are")
    constraint_table.constraints_on_artifact(unbound_variable.artifact).each do |constraint|
      trace("\t#{constraint}")
    end
    trace("Possible values are #{possible_values_for_unbound}")
    
    while possible_value = possible_values_for_unbound.shift
      possible_artifact = graph.get_artifact(unbound_variable.artifact, possible_value.version)
      possible_dependencies = possible_artifact.dependencies
      all_ok = possible_dependencies.all? { |dependency| can_add_new_constraint?(dependency) }
      if all_ok
        trace("Attempting to use #{possible_artifact}")
        add_dependencies(possible_dependencies, possible_artifact) 
        unbound_variable.bind(possible_value)
        break
      end
    end

    unless unbound_variable.bound?
      trace("Could not find an acceptable value for #{unbound_variable.artifact}")
      backtrack(unbound_variable) 
    end
  end

  solution = {}.tap do |solution|
    variable_table.rows.each do |variable|
      solution[variable.artifact] = variable.value.version.to_s
    end
  end

  trace("Found Solution")
  trace(solution)

  solution
end