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

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:



182
183
184
 
# File 'lib/solve/solver.rb', line 182

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:



208
209
210
211
212
213
214
 
# File 'lib/solve/solver.rb', line 208

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

  demand
end

#build_sorted_solution ⇒ Object 



137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
 
# File 'lib/solve/solver.rb', line 137

def build_sorted_solution
  unsorted_solution = build_unsorted_solution
  nodes = Hash.new
  unsorted_solution.each do |name, version|
    nodes[name] = @graph.get_artifact(name, version).dependencies.map(&:name)
  end

  # Modified from http://ruby-doc.org/stdlib-1.9.3/libdoc/tsort/rdoc/TSort.html
  class << nodes
    include TSort
    alias tsort_each_node each_key
    def tsort_each_child(node, &block)
      fetch(node).each(&block)
    end
  end
  begin
    sorted_names = nodes.tsort
  rescue TSort::Cyclic => e
    raise Solve::Errors::UnsortableSolutionError.new(e, unsorted_solution)
  end

  sorted_names.map do |artifact|
    [artifact, unsorted_solution[artifact]]
  end
end

#build_unsorted_solution ⇒ Object 



129
130
131
132
133
134
135
 
# File 'lib/solve/solver.rb', line 129

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

#has_demand?(demand) ⇒ Boolean

Parameters:

Returns:

  • (Boolean) 


227
228
229
 
# File 'lib/solve/solver.rb', line 227

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

#remove_demand(demand) ⇒ Object

Parameters:



218
219
220
221
222
 
# File 'lib/solve/solver.rb', line 218

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

#resolve(options = {}) ⇒ Hash, List

Returns a hash like { “Artifact Name” => “Version”,… } unless options, then it returns a list like [[“Artifact Name”, “Version],…]

Parameters:

  • options (Hash) (defaults to: {}) —

    a customizable set of options

Options Hash (options):

  • :sorted (Boolean) —

    return the solution as a sorted list instead of a Hash

Returns:

  • (Hash, List) —

    Returns a hash like { “Artifact Name” => “Version”,… } unless options, then it returns a list like [[“Artifact Name”, “Version],…]



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

def resolve(options = {})
  Solve.tracer.start
  seed_demand_dependencies

  while unbound_variable = variable_table.first_unbound
    possible_values_for_unbound = possible_values_for(unbound_variable)
    constraints = constraint_table.constraints_on_artifact(unbound_variable.artifact)
    Solve.tracer.searching_for(unbound_variable, constraints, possible_values)

    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
        Solve.tracer.trying(possible_artifact)
        add_dependencies(possible_dependencies, possible_artifact)
        unbound_variable.bind(possible_value)
        break
      end
    end

    unless unbound_variable.bound?
      backtrack(unbound_variable)
    end
  end

  solution = (options[:sorted]) ? build_sorted_solution : build_unsorted_solution

  Solve.tracer.solution(solution)

  solution
end