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:



188
189
190
 
# File 'lib/solve/solver.rb', line 188

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:



214
215
216
217
218
219
220
 
# File 'lib/solve/solver.rb', line 214

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

  demand
end

#build_sorted_solution ⇒ Object 



143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
 
# File 'lib/solve/solver.rb', line 143

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 



135
136
137
138
139
140
141
 
# File 'lib/solve/solver.rb', line 135

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) 


233
234
235
 
# File 'lib/solve/solver.rb', line 233

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

#remove_demand(demand) ⇒ Object

Parameters:



224
225
226
227
228
 
# File 'lib/solve/solver.rb', line 224

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
128
129
130
131
132
133
 
# File 'lib/solve/solver.rb', line 96

def resolve(options = {})
  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 = (options[:sorted]) ? build_sorted_solution : build_unsorted_solution

  trace("Found Solution")
  trace(solution)

  solution
end