Name | Total Lines | Lines of Code | Total Coverage | Code Coverage |
---|---|---|---|---|

lib/gecoder/interface/search.rb | 229 |
131 |
100.00% |
100.00% |

Code reported as executed by Ruby looks like this...and this: this line is also marked as covered.Lines considered as run by rcov, but not reported by Ruby, look like this,and this: these lines were inferred by rcov (using simple heuristics).Finally, here's a line marked as not executed.

1 module Gecode |

2 # An exception raised when a search failed because there are no |

3 # solutions. |

4 class NoSolutionError < RuntimeError |

5 def initialize #:nodoc: |

6 super('No solution could be found.') |

7 end |

8 end |

9 |

10 # An exception raised when a search has been aborted due to e.g. |

11 # hitting the time limit specified when initiating the search. |

12 class SearchAbortedError < RuntimeError |

13 def initialize #:nodoc: |

14 super('The search was aborted before a solution could be found.') |

15 end |

16 end |

17 |

18 module Mixin |

19 # Finds the first solution to the modelled problem and updates the variables |

20 # to that solution. The found solution is also returned. Raises |

21 # Gecode::NoSolutionError if no solution can be found. |

22 # |

23 # The following options can be specified in a hash with symbols as |

24 # keys when calling the method: |

25 # |

26 # [:time_limit] The number of milliseconds that the solver should be |

27 # allowed to use when searching for a solution. If it can |

28 # not find a solution fast enough, then |

29 # Gecode::SearchAbortedError is raised. |

30 def solve!(options = {}) |

31 dfs = dfs_engine(options) |

32 space = dfs.next |

33 @gecoder_mixin_statistics = dfs.statistics |

34 raise Gecode::SearchAbortedError if dfs.stopped |

35 raise Gecode::NoSolutionError if space.nil? |

36 self.active_space = space |

37 return self |

38 end |

39 |

40 # Returns to the original state, before any search was made (but |

41 # propagation might have been performed). Returns the reset model. |

42 def reset! |

43 self.active_space = base_space |

44 @gecoder_mixin_statistics = nil |

45 return self |

46 end |

47 |

48 # Yields the first solution (if any) to the block. If no solution is found |

49 # then the block is not used. Returns the result of the block (nil in case |

50 # the block wasn't run). |

51 def solution(&block) |

52 begin |

53 solution = self.solve! |

54 res = yield solution |

55 self.reset! |

56 return res |

57 rescue Gecode::NoSolutionError |

58 return nil |

59 end |

60 end |

61 |

62 # Yields each solution that the model has. |

63 def each_solution(&block) |

64 dfs = dfs_engine |

65 next_solution = nil |

66 while not (next_solution = dfs.next).nil? |

67 self.active_space = next_solution |

68 @gecoder_mixin_statistics = dfs.statistics |

69 yield self |

70 end |

71 self.reset! |

72 end |

73 |

74 # Returns search statistics providing various information from Gecode about |

75 # the search that resulted in the model's current variable state. If the |

76 # model's variables have not undergone any search then nil is returned. The |

77 # statistics is a hash with the following keys: |

78 # [:propagations] The number of propagation steps performed. |

79 # [:failures] The number of failed nodes in the search tree. |

80 # [:clones] The number of clones created. |

81 # [:commits] The number of commit operations performed. |

82 # [:memory] The peak memory allocated to Gecode. |

83 def search_stats |

84 return nil if @gecoder_mixin_statistics.nil? |

85 |

86 return { |

87 :propagations => @gecoder_mixin_statistics.propagate, |

88 :failures => @gecoder_mixin_statistics.fail, |

89 :clones => @gecoder_mixin_statistics.clone, |

90 :commits => @gecoder_mixin_statistics.commit, |

91 :memory => @gecoder_mixin_statistics.memory |

92 } |

93 end |

94 |

95 # Finds the optimal solution. Optimality is defined by the provided |

96 # block which is given two parameters, the model and the best |

97 # solution found so far to the problem. The block should constrain |

98 # the model so that that only "better" solutions can be new |

99 # solutions. For instance if one wants to optimize a variable named |

100 # price (accessible from the model) to be as low as possible then |

101 # one should write the following. |

102 # |

103 # model.optimize! do |model, best_so_far| |

104 # model.price.must < best_so_far.price.value |

105 # end |

106 # |

107 # Raises Gecode::NoSolutionError if no solution can be found. |

108 def optimize!(&block) |

109 # Execute constraints. |

110 perform_queued_gecode_interactions |

111 |

112 # Set the method used for constrain calls by the BAB-search. |

113 Mixin.constrain_proc = lambda do |home_space, best_space| |

114 self.active_space = best_space |

115 @gecoder_mixin_variable_creation_space = home_space |

116 yield(self, self) |

117 self.active_space = home_space |

118 @gecoder_mixin_variable_creation_space = nil |

119 |

120 perform_queued_gecode_interactions |

121 end |

122 |

123 # Perform the search. |

124 options = Gecode::Raw::Search::Options.new |

125 options.c_d = Gecode::Raw::Search::Config::MINIMAL_DISTANCE |

126 options.a_d = Gecode::Raw::Search::Config::ADAPTIVE_DISTANCE |

127 options.stop = nil |

128 bab = Gecode::Raw::BAB.new(selected_space, options) |

129 |

130 result = nil |

131 previous_solution = nil |

132 until (previous_solution = bab.next).nil? |

133 result = previous_solution |

134 end |

135 @gecoder_mixin_statistics = bab.statistics |

136 |

137 # Reset the method used constrain calls and return the result. |

138 Mixin.constrain_proc = nil |

139 raise Gecode::NoSolutionError if result.nil? |

140 |

141 # Switch to the result. |

142 self.active_space = result |

143 return self |

144 end |

145 |

146 # Finds the solution that maximizes a given integer variable. The name of |

147 # the method that accesses the variable from the model should be given. To |

148 # for instance maximize a variable named "profit", that's accessible |

149 # through the model, one would use the following. |

150 # |

151 # model.maximize! :profit |

152 # |

153 # Raises Gecode::NoSolutionError if no solution can be found. |

154 def maximize!(var) |

155 variable = self.method(var).call |

156 unless variable.kind_of? Gecode::IntVar |

157 raise ArgumentError.new("Expected integer variable, got #{variable.class}.") |

158 end |

159 |

160 optimize! do |model, best_so_far| |

161 model.method(var).call.must > best_so_far.method(var).call.value |

162 end |

163 end |

164 |

165 # Finds the solution that minimizes a given integer variable. The name of |

166 # the method that accesses the variable from the model should be given. To |

167 # for instance minimize a variable named "cost", that's accessible through |

168 # the model, one would use the following. |

169 # |

170 # model.minimize! :cost |

171 # |

172 # Raises Gecode::NoSolutionError if no solution can be found. |

173 def minimize!(var) |

174 variable = self.method(var).call |

175 unless variable.kind_of? Gecode::IntVar |

176 raise ArgumentError.new("Expected integer variable, got #{variable.class}.") |

177 end |

178 |

179 optimize! do |model, best_so_far| |

180 model.method(var).call.must < best_so_far.method(var).call.value |

181 end |

182 end |

183 |

184 class <<self |

185 # Sets the proc that should be used to handle constrain requests. |

186 def constrain_proc=(proc) #:nodoc: |

187 @constrain_proc = proc |

188 end |

189 |

190 # Called by spaces when they want to constrain as part of BAB-search. |

191 def constrain(home, best) #:nodoc: |

192 if @constrain_proc.nil? |

193 raise NotImplementedError, 'Constrain method not implemented.' |

194 else |

195 @constrain_proc.call(home, best) |

196 end |

197 end |

198 end |

199 |

200 private |

201 |

202 # Creates a depth first search engine for search, executing any |

203 # unexecuted constraints first. |

204 def dfs_engine(options = {}) |

205 # Execute constraints. |

206 perform_queued_gecode_interactions |

207 |

208 # Begin constructing the option struct. |

209 opt_struct = Gecode::Raw::Search::Options.new |

210 opt_struct.c_d = Gecode::Raw::Search::Config::MINIMAL_DISTANCE |

211 opt_struct.a_d = Gecode::Raw::Search::Config::ADAPTIVE_DISTANCE |

212 |

213 # Decode the options. |

214 if options.has_key? :time_limit |

215 opt_struct.stop = Gecode::Raw::Search::Stop.new(-1, options.delete(:time_limit), -1) |

216 else |

217 opt_struct.stop = nil |

218 end |

219 |

220 unless options.empty? |

221 raise ArgumentError, 'Unrecognized search option: ' + |

222 options.keys.first.to_s |

223 end |

224 |

225 # Construct the engine. |

226 Gecode::Raw::DFS.new(selected_space, opt_struct) |

227 end |

228 end |

229 end |

Generated on Thu Jan 08 13:27:03 +0100 2015 with rcov 1.0.0