120 /// |
120 /// |
121 /// This function sets an external path structure for storing the |
121 /// This function sets an external path structure for storing the |
122 /// found cycle. |
122 /// found cycle. |
123 /// |
123 /// |
124 /// If you don't call this function before calling \ref run() or |
124 /// If you don't call this function before calling \ref run() or |
125 /// \ref init(), it will allocate a local \ref Path "path" |
125 /// \ref findMinMean(), it will allocate a local \ref Path "path" |
126 /// structure. The destuctor deallocates this automatically |
126 /// structure. The destuctor deallocates this automatically |
127 /// allocated object, of course. |
127 /// allocated object, of course. |
128 /// |
128 /// |
129 /// \note The algorithm calls only the \ref lemon::Path::addBack() |
129 /// \note The algorithm calls only the \ref lemon::Path::addBack() |
130 /// "addBack()" function of the given path structure. |
130 /// "addBack()" function of the given path structure. |
142 } |
142 } |
143 |
143 |
144 /// \name Execution control |
144 /// \name Execution control |
145 /// The simplest way to execute the algorithm is to call the \ref run() |
145 /// The simplest way to execute the algorithm is to call the \ref run() |
146 /// function.\n |
146 /// function.\n |
147 /// If you only need the minimum mean length, you may call \ref init() |
147 /// If you only need the minimum mean length, you may call |
148 /// and \ref findMinMean(). |
148 /// \ref findMinMean(). |
149 /// If you would like to run the algorithm again (e.g. the underlying |
|
150 /// digraph and/or the arc lengths has been modified), you may not |
|
151 /// create a new instance of the class, rather call \ref reset(), |
|
152 /// \ref findMinMean() and \ref findCycle() instead. |
|
153 |
149 |
154 /// @{ |
150 /// @{ |
155 |
151 |
156 /// \brief Run the algorithm. |
152 /// \brief Run the algorithm. |
157 /// |
153 /// |
158 /// This function runs the algorithm. |
154 /// This function runs the algorithm. |
|
155 /// It can be called more than once (e.g. if the underlying digraph |
|
156 /// and/or the arc lengths have been modified). |
159 /// |
157 /// |
160 /// \return \c true if a directed cycle exists in the digraph. |
158 /// \return \c true if a directed cycle exists in the digraph. |
161 /// |
159 /// |
162 /// \note Apart from the return value, <tt>mmc.run()</tt> is just a |
160 /// \note <tt>mmc.run()</tt> is just a shortcut of the following code. |
163 /// shortcut of the following code. |
|
164 /// \code |
161 /// \code |
165 /// mmc.init(); |
162 /// return mmc.findMinMean() && mmc.findCycle(); |
166 /// mmc.findMinMean(); |
|
167 /// mmc.findCycle(); |
|
168 /// \endcode |
163 /// \endcode |
169 bool run() { |
164 bool run() { |
170 init(); |
|
171 return findMinMean() && findCycle(); |
165 return findMinMean() && findCycle(); |
172 } |
166 } |
173 |
167 |
174 /// \brief Initialize the internal data structures. |
168 /// \brief Find the minimum cycle mean. |
175 /// |
169 /// |
176 /// This function initializes the internal data structures. |
170 /// This function finds the minimum mean length of the directed |
177 /// |
171 /// cycles in the digraph. |
178 /// \sa reset() |
172 /// |
179 void init() { |
173 /// \return \c true if a directed cycle exists in the digraph. |
|
174 bool findMinMean() { |
|
175 // Initialize |
180 _tol.epsilon(1e-6); |
176 _tol.epsilon(1e-6); |
181 if (!_cycle_path) { |
177 if (!_cycle_path) { |
182 _local_path = true; |
178 _local_path = true; |
183 _cycle_path = new Path; |
179 _cycle_path = new Path; |
184 } |
180 } |
|
181 _cycle_path->clear(); |
185 _cycle_found = false; |
182 _cycle_found = false; |
|
183 |
|
184 // Find the minimum cycle mean in the components |
186 _comp_num = stronglyConnectedComponents(_gr, _comp); |
185 _comp_num = stronglyConnectedComponents(_gr, _comp); |
187 } |
|
188 |
|
189 /// \brief Reset the internal data structures. |
|
190 /// |
|
191 /// This function resets the internal data structures so that |
|
192 /// findMinMean() and findCycle() can be called again (e.g. when the |
|
193 /// underlying digraph and/or the arc lengths has been modified). |
|
194 /// |
|
195 /// \sa init() |
|
196 void reset() { |
|
197 if (_cycle_path) _cycle_path->clear(); |
|
198 _cycle_found = false; |
|
199 _comp_num = stronglyConnectedComponents(_gr, _comp); |
|
200 } |
|
201 |
|
202 /// \brief Find the minimum cycle mean. |
|
203 /// |
|
204 /// This function computes all the required data and finds the |
|
205 /// minimum mean length of the directed cycles in the digraph. |
|
206 /// |
|
207 /// \return \c true if a directed cycle exists in the digraph. |
|
208 /// |
|
209 /// \pre \ref init() must be called before using this function. |
|
210 bool findMinMean() { |
|
211 // Find the minimum cycle mean in the components |
|
212 for (int comp = 0; comp < _comp_num; ++comp) { |
186 for (int comp = 0; comp < _comp_num; ++comp) { |
213 if (!initCurrentComponent(comp)) continue; |
187 if (!initCurrentComponent(comp)) continue; |
214 while (true) { |
188 while (true) { |
215 if (!findPolicyCycles()) break; |
189 if (!findPolicyCycles()) break; |
216 contractPolicyGraph(comp); |
190 contractPolicyGraph(comp); |
225 /// This function finds a directed cycle of minimum mean length |
199 /// This function finds a directed cycle of minimum mean length |
226 /// in the digraph using the data computed by findMinMean(). |
200 /// in the digraph using the data computed by findMinMean(). |
227 /// |
201 /// |
228 /// \return \c true if a directed cycle exists in the digraph. |
202 /// \return \c true if a directed cycle exists in the digraph. |
229 /// |
203 /// |
230 /// \pre \ref init() and \ref findMinMean() must be called before |
204 /// \pre \ref findMinMean() must be called before using this function. |
231 /// using this function. |
|
232 bool findCycle() { |
205 bool findCycle() { |
233 if (!_cycle_found) return false; |
206 if (!_cycle_found) return false; |
234 _cycle_path->addBack(_policy[_cycle_node]); |
207 _cycle_path->addBack(_policy[_cycle_node]); |
235 for ( Node v = _cycle_node; |
208 for ( Node v = _cycle_node; |
236 (v = _gr.target(_policy[v])) != _cycle_node; ) { |
209 (v = _gr.target(_policy[v])) != _cycle_node; ) { |