Changeset 2413:21eb3ccdc3df in lemon-0.x for lemon/min_mean_cycle.h
- Timestamp:
- 03/22/07 16:40:50 (17 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3244
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/min_mean_cycle.h
r2409 r2413 34 34 /// @{ 35 35 36 /// \brief Implementation of Karp's algorithm for finding a 37 /// minimum mean cycle.36 /// \brief Implementation of Karp's algorithm for finding a 37 /// minimum mean (directed) cycle. 38 38 /// 39 /// The \ref lemon::MinMeanCycle "MinMeanCycle" implements Karp's 40 /// algorithm for finding a minimum mean cycle.39 /// The \ref lemon::MinMeanCycle "MinMeanCycle" implements Karp's 40 /// algorithm for finding a minimum mean (directed) cycle. 41 41 /// 42 42 /// \param Graph The directed graph type the algorithm runs on. … … 58 58 typedef typename Graph::Edge Edge; 59 59 typedef typename Graph::EdgeIt EdgeIt; 60 typedef typename Graph::InEdgeIt InEdgeIt;61 60 typedef typename Graph::OutEdgeIt OutEdgeIt; 62 61 63 62 typedef typename LengthMap::Value Length; 64 63 65 64 typedef typename Graph::template NodeMap<int> IntNodeMap; 66 65 typedef typename Graph::template NodeMap<Edge> PredNodeMap; … … 70 69 71 70 protected: 72 71 73 72 /// \brief Data sturcture for path data. 74 struct PathData { 73 struct PathData 74 { 75 75 bool found; 76 76 Length dist; 77 77 Edge pred; 78 PathData(bool _found = false, Length _dist = 0) : 78 PathData(bool _found = false, Length _dist = 0) : 79 79 found(_found), dist(_dist), pred(INVALID) {} 80 PathData(bool _found, Length _dist, Edge _pred) : 80 PathData(bool _found, Length _dist, Edge _pred) : 81 81 found(_found), dist(_dist), pred(_pred) {} 82 82 }; 83 83 84 84 private: 85 86 typedef typename Graph::template NodeMap<std::vector<PathData> > PathVectorNodeMap; 87 85 86 typedef typename Graph::template NodeMap<std::vector<PathData> > 87 PathDataNodeMap; 88 88 89 protected: 89 90 … … 93 94 /// component. dmap[v][k] is the length of a shortest directed walk 94 95 /// to node v from the starting node containing exactly k edges. 95 Path VectorNodeMap dmap;96 PathDataNodeMap dmap; 96 97 97 98 /// \brief The directed graph the algorithm runs on. … … 104 105 /// \brief The number of edges in the found cycle. 105 106 int cycle_size; 107 /// \brief A node for obtaining a minimum mean cycle. 108 Node cycle_node; 109 106 110 /// \brief The found cycle. 107 111 Path *cycle_path; 108 /// \brief The found cycle. 112 /// \brief The algorithm uses local \ref lemon::Path "Path" 113 /// structure to store the found cycle. 109 114 bool local_path; 110 115 … … 113 118 /// \brief The number of strongly connected components. 114 119 int comp_num; 115 /// \brief %Counter for identifying the current component.120 /// \brief Counter for identifying the current component. 116 121 int comp_cnt; 117 122 /// \brief Nodes of the current component. … … 130 135 MinMeanCycle( const Graph& _graph, 131 136 const LengthMap& _length ) : 132 graph(_graph), length(_length), dmap(_graph), 133 cycle_length(0), cycle_size(-1), c omp(_graph),137 graph(_graph), length(_length), dmap(_graph), comp(_graph), 138 cycle_length(0), cycle_size(-1), cycle_node(INVALID), 134 139 cycle_path(NULL), local_path(false) 135 140 { } … … 141 146 142 147 protected: 143 144 /// \brief Initializes the internal data structures.145 void init() {146 comp_num = stronglyConnectedComponents(graph, comp);147 if (!cycle_path) {148 local_path = true;149 cycle_path = new Path;150 }151 }152 148 153 149 /// \brief Initializes the internal data structures for the current … … 159 155 if (comp[v] == comp_cnt) nodes.push_back(v); 160 156 } 161 162 157 // Creating vectors for all nodes 163 158 int n = nodes.size(); … … 167 162 } 168 163 169 /// \brief Processes all rounds of computing required path data. 164 /// \brief Processes all rounds of computing required path data for 165 /// the current component. 170 166 void processRounds() { 171 167 dmap[nodes[0]][0] = PathData(true, 0); 172 168 process.clear(); 173 for (OutEdgeIt oe(graph, nodes[0]); oe != INVALID; ++oe) { 174 Node v = graph.target(oe); 169 // Processing the first round 170 for (OutEdgeIt e(graph, nodes[0]); e != INVALID; ++e) { 171 Node v = graph.target(e); 175 172 if (comp[v] != comp_cnt || v == nodes[0]) continue; 176 dmap[v][1] = PathData(true, length[ oe], oe);173 dmap[v][1] = PathData(true, length[e], e); 177 174 process.push_back(v); 178 175 } 176 // Processing other rounds 179 177 int n = nodes.size(), k; 180 178 for (k = 2; k <= n && process.size() < n; ++k) { … … 191 189 NodeVector next; 192 190 for (NodeVectorIt ui = process.begin(); ui != process.end(); ++ui) { 193 for (OutEdgeIt oe(graph, *ui); oe != INVALID; ++oe) {194 Node v = graph.target( oe);191 for (OutEdgeIt e(graph, *ui); e != INVALID; ++e) { 192 Node v = graph.target(e); 195 193 if (comp[v] != comp_cnt) continue; 196 if ( !dmap[v][k].found || (dmap[v][k].dist > dmap[*ui][k-1].dist + length[oe]) ) { 197 if (!dmap[v][k].found) next.push_back(v); 198 dmap[v][k] = PathData(true, dmap[*ui][k-1].dist + length[oe], oe); 194 if (!dmap[v][k].found) { 195 next.push_back(v); 196 dmap[v][k] = PathData(true, dmap[*ui][k-1].dist + length[e], e); 197 } 198 else if (dmap[*ui][k-1].dist + length[e] < dmap[v][k].dist) { 199 dmap[v][k] = PathData(true, dmap[*ui][k-1].dist + length[e], e); 199 200 } 200 201 } … … 207 208 void processNextFullRound(int k) { 208 209 for (NodeVectorIt ui = nodes.begin(); ui != nodes.end(); ++ui) { 209 for (OutEdgeIt oe(graph, *ui); oe != INVALID; ++oe) {210 Node v = graph.target( oe);210 for (OutEdgeIt e(graph, *ui); e != INVALID; ++e) { 211 Node v = graph.target(e); 211 212 if (comp[v] != comp_cnt) continue; 212 if ( !dmap[v][k].found || (dmap[v][k].dist > dmap[*ui][k-1].dist + length[oe]) ) { 213 dmap[v][k] = PathData(true, dmap[*ui][k-1].dist + length[oe], oe); 213 if ( !dmap[v][k].found || 214 dmap[*ui][k-1].dist + length[e] < dmap[v][k].dist ) { 215 dmap[v][k] = PathData(true, dmap[*ui][k-1].dist + length[e], e); 214 216 } 215 217 } … … 217 219 } 218 220 219 /// \brief Finds the minimum cycle mean value according to the path 220 /// data stored in \ref dmap. 221 /// 222 /// Finds the minimum cycle mean value according to the path data 223 /// stored in \ref dmap. 224 /// 225 /// \retval min_length The total length of the found cycle. 226 /// \retval min_size The number of edges in the found cycle. 227 /// \retval min_node A node for obtaining a critical cycle. 228 /// 229 /// \return \c true if a cycle exists in the graph. 230 bool findMinCycleMean(Length &min_length, int &min_size, Node &min_node) { 221 /// \brief Finds the minimum cycle mean value in the current 222 /// component. 223 bool findCurrentMin(Length &min_length, int &min_size, Node &min_node) { 231 224 bool found_min = false; 232 225 for (NodeVectorIt vi = nodes.begin(); vi != nodes.end(); ++vi) { 226 int n = nodes.size(); 227 if (!dmap[*vi][n].found) continue; 233 228 Length len; 234 229 int size; 235 230 bool found_one = false; 236 int n = nodes.size();237 231 for (int k = 0; k < n; ++k) { 232 if (!dmap[*vi][k].found) continue; 238 233 Length _len = dmap[*vi][n].dist - dmap[*vi][k].dist; 239 234 int _size = n - k; 240 if ( dmap[*vi][n].found && dmap[*vi][k].found && (!found_one || len * _size < _len * size)) {235 if (!found_one || len * _size < _len * size) { 241 236 found_one = true; 242 237 len = _len; … … 244 239 } 245 240 } 246 if (found_one && (!found_min || len * min_size < min_length * size)) { 241 if ( found_one && 242 (!found_min || len * min_size < min_length * size) ) { 247 243 found_min = true; 248 244 min_length = len; … … 254 250 } 255 251 256 /// \brief Finds a critical (minimum mean) cycle according to the 257 /// path data stored in \ref dmap. 258 void findCycle(const Node &min_n) { 259 IntNodeMap reached(graph, -1); 260 int r = reached[min_n] = dmap[min_n].size() - 1; 261 Node u = graph.source(dmap[min_n][r].pred); 262 while (reached[u] < 0) { 263 reached[u] = --r; 264 u = graph.source(dmap[u][r].pred); 265 } 266 r = reached[u]; 267 Edge ce = dmap[u][r].pred; 268 cycle_path->addFront(ce); 269 Node v; 270 while ((v = graph.source(ce)) != u) { 271 ce = dmap[v][--r].pred; 272 cycle_path->addFront(ce); 273 } 274 } 275 276 public: 277 252 public: 253 278 254 /// \brief Runs the algorithm. 279 255 /// … … 281 257 /// 282 258 /// \return \c true if a cycle exists in the graph. 259 /// 260 /// \note Apart from the return value, m.run() is just a shortcut 261 /// of the following code. 262 /// \code 263 /// m.init(); 264 /// m.findMinMean(); 265 /// m.findCycle(); 266 /// \endcode 283 267 bool run() { 284 268 init(); 285 // Searching for the minimum mean cycle in all components 286 bool found_cycle = false; 287 Node cycle_node; 269 findMinMean(); 270 return findCycle(); 271 } 272 273 /// \brief Initializes the internal data structures. 274 void init() { 275 comp_num = stronglyConnectedComponents(graph, comp); 276 if (!cycle_path) { 277 local_path = true; 278 cycle_path = new Path; 279 } 280 } 281 282 /// \brief Finds the minimum cycle mean value in the graph. 283 /// 284 /// Computes all the required path data and finds the minimum cycle 285 /// mean value in the graph. 286 /// 287 /// \return \c true if a cycle exists in the graph. 288 /// 289 /// \pre \ref init() must be called before using this function. 290 bool findMinMean() { 291 cycle_node = INVALID; 288 292 for (comp_cnt = 0; comp_cnt < comp_num; ++comp_cnt) { 289 290 293 initCurrent(); 291 294 processRounds(); … … 294 297 int min_size; 295 298 Node min_node; 296 bool found_min = find MinCycleMean(min_length, min_size, min_node);299 bool found_min = findCurrentMin(min_length, min_size, min_node); 297 300 298 if ( found_min && ( !found_cycle || min_length * cycle_size < cycle_length * min_size) ) {299 found_cycle = true;301 if ( found_min && (cycle_node == INVALID || 302 min_length * cycle_size < cycle_length * min_size) ) { 300 303 cycle_length = min_length; 301 304 cycle_size = min_size; … … 303 306 } 304 307 } 305 if (found_cycle) findCycle(cycle_node); 306 return found_cycle; 307 } 308 309 /// \brief Returns the total length of the found critical cycle. 310 /// 311 /// Returns the total length of the found critical cycle. 308 return (cycle_node != INVALID); 309 } 310 311 /// \brief Finds a critical (minimum mean) cycle. 312 /// 313 /// Finds a critical (minimum mean) cycle using the path data 314 /// stored in \ref dmap. 315 /// 316 /// \return \c true if a cycle exists in the graph. 317 /// 318 /// \pre \ref init() and \ref findMinMean() must be called before 319 /// using this function. 320 bool findCycle() { 321 if (cycle_node == INVALID) return false; 322 cycle_length = 0; 323 cycle_size = 0; 324 IntNodeMap reached(graph, -1); 325 int r = reached[cycle_node] = dmap[cycle_node].size() - 1; 326 Node u = graph.source(dmap[cycle_node][r].pred); 327 while (reached[u] < 0) { 328 reached[u] = --r; 329 u = graph.source(dmap[u][r].pred); 330 } 331 r = reached[u]; 332 Edge e = dmap[u][r].pred; 333 cycle_path->addFront(e); 334 cycle_length = cycle_length + length[e]; 335 ++cycle_size; 336 Node v; 337 while ((v = graph.source(e)) != u) { 338 e = dmap[v][--r].pred; 339 cycle_path->addFront(e); 340 cycle_length = cycle_length + length[e]; 341 ++cycle_size; 342 } 343 return true; 344 } 345 346 /// \brief Resets the internal data structures. 347 /// 348 /// Resets the internal data structures so that \ref findMinMean() 349 /// and \ref findCycle() can be called again (e.g. when the 350 /// underlaying graph has been modified). 351 void reset() { 352 for (NodeIt u(graph); u != INVALID; ++u) 353 dmap[u].clear(); 354 cycle_node = INVALID; 355 if (cycle_path) cycle_path->clear(); 356 comp_num = stronglyConnectedComponents(graph, comp); 357 } 358 359 /// \brief Returns the total length of the found cycle. 360 /// 361 /// Returns the total length of the found cycle. 312 362 /// 313 363 /// \pre \ref run() must be called before using this function. … … 316 366 } 317 367 318 /// \brief Returns the number of edges in the found critical 319 /// cycle. 320 /// 321 /// Returns the number of edges in the found critical cycle. 368 /// \brief Returns the number of edges in the found cycle. 369 /// 370 /// Returns the number of edges in the found cycle. 322 371 /// 323 372 /// \pre \ref run() must be called before using this function. … … 326 375 } 327 376 328 /// \brief Returns the mean length of the found c ritical cycle.329 /// 330 /// Returns the mean length of the found c ritical cycle.377 /// \brief Returns the mean length of the found cycle. 378 /// 379 /// Returns the mean length of the found cycle. 331 380 /// 332 381 /// \pre \ref run() must be called before using this function. 333 382 /// 334 383 /// \warning LengthMap::Value must be convertible to double. 384 /// 385 /// \note m.minMean() is just a shortcut of the following code. 386 /// \code 387 /// return m.cycleEdgeNum() / double(m.cycleLength()); 388 /// \endcode 335 389 double minMean() const { 336 return (double)cycle_length / (double)cycle_size;390 return cycle_length / (double)cycle_size; 337 391 } 338 392 339 393 /// \brief Returns a const reference to the \ref lemon::Path "Path" 340 /// structure of the found flow.394 /// structure of the found cycle. 341 395 /// 342 396 /// Returns a const reference to the \ref lemon::Path "Path" 343 /// structure of the found flow.397 /// structure of the found cycle. 344 398 /// 345 399 /// \pre \ref run() must be called before using this function.
Note: See TracChangeset
for help on using the changeset viewer.