Gecoder C0 Coverage Information - RCov

lib/gecoder/interface/search.rb

Name Total Lines Lines of Code Total Coverage Code Coverage
lib/gecoder/interface/search.rb 229 131
100.00%
100.00%

Key

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.

Coverage Details

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