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 



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

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.



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

def constraint_table
  @constraint_table
end

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

Overloads:

  • #demands(name, constraint) ⇒ Solve::Demand

    Return the Solve::Demand from the collection of demands with the given name and constraint.

  • #demands(name) ⇒ Solve::Demand

    Return the Solve::Demand from the collection of demands with the given name.

  • #demands ⇒ Array<Solve::Demand>

    Return the collection of demands



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

def demands
  @demands
end

#domain ⇒ Object (readonly)

Returns the value of attribute domain.



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

def domain
  @domain
end

#graph ⇒ Solve::Graph (readonly)

The world as we know it



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

def graph
  @graph
end

#possible_values ⇒ Object (readonly)

Returns the value of attribute possible_values.



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

def possible_values
  @possible_values
end

#ui ⇒ Object (readonly)

Returns the value of attribute ui.



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

def ui
  @ui
end

#variable_table ⇒ Object (readonly)

Returns the value of attribute variable_table.



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

def variable_table
  @variable_table
end

Class Method Details

.demand_key(demand) ⇒ Symbol

Create a key to identify a demand on a Solver.

Raises:

  • (NoSolutionError) 


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

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



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

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

Raises:

  • (NoSolutionError) —

    if version matches the given constraints



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

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.



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

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

  demand
end

#has_demand?(demand) ⇒ Boolean 



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

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

#remove_demand(demand) ⇒ Object 



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

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

#resolve ⇒ Hash 



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

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