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) 


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:



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

Returns:



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.

Parameters:

Returns:

  • (Symbol)

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

Parameters:

Returns:



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

Parameters:

Returns:

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.

Parameters:

Returns:



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

Parameters:

Returns:

  • (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

Parameters:



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

Returns:

  • (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