r806:d66ff32624e2
Mon, 03 Aug 2009 14:35:38
[Not Reviewed]
0 comments (0 inline)
0
1
0
| ... | ... |
@@ -113,145 +113,118 @@ |
| 113 | 113 |
|
| 114 | 114 |
/// Destructor. |
| 115 | 115 |
~MinMeanCycle() {
|
| 116 | 116 |
if (_local_path) delete _cycle_path; |
| 117 | 117 |
} |
| 118 | 118 |
|
| 119 | 119 |
/// \brief Set the path structure for storing the found cycle. |
| 120 | 120 |
/// |
| 121 | 121 |
/// This function sets an external path structure for storing the |
| 122 | 122 |
/// found cycle. |
| 123 | 123 |
/// |
| 124 | 124 |
/// If you don't call this function before calling \ref run() or |
| 125 |
/// \ref |
|
| 125 |
/// \ref findMinMean(), it will allocate a local \ref Path "path" |
|
| 126 | 126 |
/// structure. The destuctor deallocates this automatically |
| 127 | 127 |
/// allocated object, of course. |
| 128 | 128 |
/// |
| 129 | 129 |
/// \note The algorithm calls only the \ref lemon::Path::addBack() |
| 130 | 130 |
/// "addBack()" function of the given path structure. |
| 131 | 131 |
/// |
| 132 | 132 |
/// \return <tt>(*this)</tt> |
| 133 | 133 |
/// |
| 134 | 134 |
/// \sa cycle() |
| 135 | 135 |
MinMeanCycle& cyclePath(Path &path) {
|
| 136 | 136 |
if (_local_path) {
|
| 137 | 137 |
delete _cycle_path; |
| 138 | 138 |
_local_path = false; |
| 139 | 139 |
} |
| 140 | 140 |
_cycle_path = &path; |
| 141 | 141 |
return *this; |
| 142 | 142 |
} |
| 143 | 143 |
|
| 144 | 144 |
/// \name Execution control |
| 145 | 145 |
/// The simplest way to execute the algorithm is to call the \ref run() |
| 146 | 146 |
/// function.\n |
| 147 |
/// If you only need the minimum mean length, you may call \ref init() |
|
| 148 |
/// and \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. |
|
| 147 |
/// If you only need the minimum mean length, you may call |
|
| 148 |
/// \ref findMinMean(). |
|
| 153 | 149 |
|
| 154 | 150 |
/// @{
|
| 155 | 151 |
|
| 156 | 152 |
/// \brief Run the algorithm. |
| 157 | 153 |
/// |
| 158 | 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 | 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 |
|
| 163 |
/// shortcut of the following code. |
|
| 160 |
/// \note <tt>mmc.run()</tt> is just a shortcut of the following code. |
|
| 164 | 161 |
/// \code |
| 165 |
/// mmc.init(); |
|
| 166 |
/// mmc.findMinMean(); |
|
| 167 |
/// mmc.findCycle(); |
|
| 162 |
/// return mmc.findMinMean() && mmc.findCycle(); |
|
| 168 | 163 |
/// \endcode |
| 169 | 164 |
bool run() {
|
| 170 |
init(); |
|
| 171 | 165 |
return findMinMean() && findCycle(); |
| 172 | 166 |
} |
| 173 | 167 |
|
| 174 |
/// \brief |
|
| 168 |
/// \brief Find the minimum cycle mean. |
|
| 175 | 169 |
/// |
| 176 |
/// This function |
|
| 170 |
/// This function finds the minimum mean length of the directed |
|
| 171 |
/// cycles in the digraph. |
|
| 177 | 172 |
/// |
| 178 |
/// \sa reset() |
|
| 179 |
void init() {
|
|
| 173 |
/// \return \c true if a directed cycle exists in the digraph. |
|
| 174 |
bool findMinMean() {
|
|
| 175 |
// Initialize |
|
| 180 | 176 |
_tol.epsilon(1e-6); |
| 181 | 177 |
if (!_cycle_path) {
|
| 182 | 178 |
_local_path = true; |
| 183 | 179 |
_cycle_path = new Path; |
| 184 | 180 |
} |
| 181 |
_cycle_path->clear(); |
|
| 185 | 182 |
_cycle_found = false; |
| 183 |
|
|
| 184 |
// Find the minimum cycle mean in the components |
|
| 186 | 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 | 186 |
for (int comp = 0; comp < _comp_num; ++comp) {
|
| 213 | 187 |
if (!initCurrentComponent(comp)) continue; |
| 214 | 188 |
while (true) {
|
| 215 | 189 |
if (!findPolicyCycles()) break; |
| 216 | 190 |
contractPolicyGraph(comp); |
| 217 | 191 |
if (!computeNodeDistances()) break; |
| 218 | 192 |
} |
| 219 | 193 |
} |
| 220 | 194 |
return _cycle_found; |
| 221 | 195 |
} |
| 222 | 196 |
|
| 223 | 197 |
/// \brief Find a minimum mean directed cycle. |
| 224 | 198 |
/// |
| 225 | 199 |
/// This function finds a directed cycle of minimum mean length |
| 226 | 200 |
/// in the digraph using the data computed by findMinMean(). |
| 227 | 201 |
/// |
| 228 | 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 |
|
| 231 |
/// using this function. |
|
| 204 |
/// \pre \ref findMinMean() must be called before using this function. |
|
| 232 | 205 |
bool findCycle() {
|
| 233 | 206 |
if (!_cycle_found) return false; |
| 234 | 207 |
_cycle_path->addBack(_policy[_cycle_node]); |
| 235 | 208 |
for ( Node v = _cycle_node; |
| 236 | 209 |
(v = _gr.target(_policy[v])) != _cycle_node; ) {
|
| 237 | 210 |
_cycle_path->addBack(_policy[v]); |
| 238 | 211 |
} |
| 239 | 212 |
return true; |
| 240 | 213 |
} |
| 241 | 214 |
|
| 242 | 215 |
/// @} |
| 243 | 216 |
|
| 244 | 217 |
/// \name Query Functions |
| 245 |
/// The |
|
| 218 |
/// The results of the algorithm can be obtained using these |
|
| 246 | 219 |
/// functions.\n |
| 247 | 220 |
/// The algorithm should be executed before using them. |
| 248 | 221 |
|
| 249 | 222 |
/// @{
|
| 250 | 223 |
|
| 251 | 224 |
/// \brief Return the total length of the found cycle. |
| 252 | 225 |
/// |
| 253 | 226 |
/// This function returns the total length of the found cycle. |
| 254 | 227 |
/// |
| 255 | 228 |
/// \pre \ref run() or \ref findCycle() must be called before |
| 256 | 229 |
/// using this function. |
| 257 | 230 |
Value cycleLength() const {
|
0 comments (0 inline)