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) 


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

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.



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

def constraint_table
  @constraint_table
end

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

Overloads:



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

def demands
  @demands
end

#domain ⇒ Object (readonly)

Returns the value of attribute domain.



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

def domain
  @domain
end

#graph ⇒ Solve::Graph (readonly)

The world as we know it

Returns:



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

def graph
  @graph
end

#possible_values ⇒ Object (readonly)

Returns the value of attribute possible_values.



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

def possible_values
  @possible_values
end

#ui ⇒ Object (readonly)

Returns the value of attribute ui.



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

def ui
  @ui
end

#variable_table ⇒ Object (readonly)

Returns the value of attribute variable_table.



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

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) 


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

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:



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

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



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

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:



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

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) 


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

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

#remove_demand(demand) ⇒ Object

Parameters:



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

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

#resolve ⇒ Hash

Returns:

  • (Hash) 


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

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