leveled.cpp
Go to the documentation of this file.
00001 /*************************************************************************** 00002 file : $URL: http://svn.code.sf.net/p/frepple/code/trunk/src/model/leveled.cpp $ 00003 version : $LastChangedRevision: 1713 $ $LastChangedBy: jdetaeye $ 00004 date : $LastChangedDate: 2012-07-18 11:46:01 +0200 (Wed, 18 Jul 2012) $ 00005 ***************************************************************************/ 00006 00007 /*************************************************************************** 00008 * * 00009 * Copyright (C) 2007-2012 by Johan De Taeye, frePPLe bvba * 00010 * * 00011 * This library is free software; you can redistribute it and/or modify it * 00012 * under the terms of the GNU Affero General Public License as published * 00013 * by the Free Software Foundation; either version 3 of the License, or * 00014 * (at your option) any later version. * 00015 * * 00016 * This library is distributed in the hope that it will be useful, * 00017 * but WITHOUT ANY WARRANTY; without even the implied warranty of * 00018 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * 00019 * GNU Affero General Public License for more details. * 00020 * * 00021 * You should have received a copy of the GNU Affero General Public * 00022 * License along with this program. * 00023 * If not, see <http://www.gnu.org/licenses/>. * 00024 * * 00025 ***************************************************************************/ 00026 00027 #define FREPPLE_CORE 00028 #include "frepple/model.h" 00029 #include <climits> 00030 00031 00032 // Uncomment the following line to create debugging statements during the 00033 // clustering and leveling algorithm. 00034 //#define CLUSTERDEBUG 00035 00036 00037 namespace frepple 00038 { 00039 00040 00041 DECLARE_EXPORT bool HasLevel::recomputeLevels = false; 00042 DECLARE_EXPORT bool HasLevel::computationBusy = false; 00043 DECLARE_EXPORT short unsigned HasLevel::numberOfClusters = 0; 00044 DECLARE_EXPORT short unsigned HasLevel::numberOfHangingClusters = 0; 00045 00046 00047 DECLARE_EXPORT void HasLevel::computeLevels() 00048 { 00049 computationBusy = true; 00050 // Get exclusive access to this function in a multi-threaded environment. 00051 static Mutex levelcomputationbusy; 00052 ScopeMutexLock l(levelcomputationbusy); 00053 00054 // Another thread may already have computed the levels while this thread was 00055 // waiting for the lock. In that case the while loop will be skipped. 00056 while (recomputeLevels) 00057 { 00058 // Reset the recomputation flag. Note that during the computation the flag 00059 // could be switched on again by some model change in a different thread. 00060 // In that case, the while loop will be rerun. 00061 recomputeLevels = false; 00062 00063 // Reset current levels on buffers, resources and operations 00064 for (Buffer::iterator gbuf = Buffer::begin(); 00065 gbuf != Buffer::end(); ++gbuf) 00066 { 00067 gbuf->cluster = 0; 00068 gbuf->lvl = -1; 00069 } 00070 for (Resource::iterator gres = Resource::begin(); 00071 gres != Resource::end(); ++gres) 00072 { 00073 gres->cluster = 0; 00074 gres->lvl = -1; 00075 } 00076 for (Operation::iterator gop = Operation::begin(); 00077 gop != Operation::end(); ++gop) 00078 { 00079 gop->cluster = 0; 00080 gop->lvl = -1; 00081 } 00082 00083 // Loop through all operations 00084 stack< pair<Operation*,int> > stack; 00085 Operation* cur_oper; 00086 int cur_level; 00087 Buffer *cur_buf; 00088 const Flow* cur_Flow; 00089 bool search_level; 00090 int cur_cluster; 00091 numberOfClusters = 0; 00092 numberOfHangingClusters = 0; 00093 map<Operation*,short> visited; 00094 for (Operation::iterator g = Operation::begin(); 00095 g != Operation::end(); ++g) 00096 { 00097 00098 #ifdef CLUSTERDEBUG 00099 logger << "Investigating operation '" << &*g 00100 << "' - current cluster " << g->cluster << endl; 00101 #endif 00102 00103 // Select a new cluster number 00104 if (g->cluster) 00105 cur_cluster = g->cluster; 00106 else 00107 { 00108 cur_cluster = ++numberOfClusters; 00109 if (numberOfClusters >= USHRT_MAX) 00110 throw LogicException("Too many clusters"); 00111 00112 // Detect hanging operations 00113 if (g->getFlows().empty() && g->getLoads().empty() 00114 && g->getSuperOperations().empty() 00115 && g->getSubOperations().empty() 00116 ) 00117 { 00118 ++numberOfHangingClusters; 00119 g->lvl = 0; 00120 continue; 00121 } 00122 } 00123 00124 // Do we need to activate the level search? 00125 // Criterion are: 00126 // - Not used in a super operation 00127 // - Have a producing flow on the operation itself 00128 // or on any of its sub operations 00129 search_level = false; 00130 if (g->getSuperOperations().empty()) 00131 { 00132 search_level = true; 00133 // Does the operation itself have producing flows? 00134 for (Operation::flowlist::const_iterator fl = g->getFlows().begin(); 00135 fl != g->getFlows().end() && search_level; ++fl) 00136 if (fl->isProducer()) search_level = false; 00137 if (search_level) 00138 { 00139 // Do suboperations have a producing flow? 00140 for (Operation::Operationlist::const_reverse_iterator 00141 i = g->getSubOperations().rbegin(); 00142 i != g->getSubOperations().rend() && search_level; 00143 ++i) 00144 for (Operation::flowlist::const_iterator 00145 fl = (*i)->getFlows().begin(); 00146 fl != (*i)->getFlows().end() && search_level; 00147 ++fl) 00148 if (fl->isProducer()) search_level = false; 00149 } 00150 } 00151 00152 // If both the level and the cluster are de-activated, then we can move on 00153 if (!search_level && g->cluster) continue; 00154 00155 // Start recursing 00156 // Note that as soon as push an operation on the stack we set its 00157 // cluster and/or level. This is avoid that operations are needlessly 00158 // pushed a second time on the stack. 00159 stack.push(make_pair(&*g, search_level ? 0 : -1)); 00160 visited.clear(); 00161 g->cluster = cur_cluster; 00162 if (search_level) g->lvl = 0; 00163 while (!stack.empty()) 00164 { 00165 // Take the top of the stack 00166 cur_oper = stack.top().first; 00167 cur_level = stack.top().second; 00168 stack.pop(); 00169 00170 #ifdef CLUSTERDEBUG 00171 logger << " Recursing in Operation '" << *(cur_oper) 00172 << "' - current level " << cur_level << endl; 00173 #endif 00174 // Detect loops in the supply chain 00175 map<Operation*,short>::iterator detectloop = visited.find(cur_oper); 00176 if (detectloop == visited.end()) 00177 // Keep track of operations already visited 00178 visited.insert(make_pair(cur_oper,0)); 00179 else if (++(detectloop->second) > 1) 00180 // Already visited this operation enough times - don't repeat 00181 continue; 00182 00183 // Push sub operations on the stack 00184 for (Operation::Operationlist::const_reverse_iterator 00185 i = cur_oper->getSubOperations().rbegin(); 00186 i != cur_oper->getSubOperations().rend(); 00187 ++i) 00188 { 00189 if ((*i)->lvl < cur_level) 00190 { 00191 // Search level and cluster 00192 stack.push(make_pair(*i,cur_level)); 00193 (*i)->lvl = cur_level; 00194 (*i)->cluster = cur_cluster; 00195 } 00196 else if (!(*i)->cluster) 00197 { 00198 // Search for clusters information only 00199 stack.push(make_pair(*i,-1)); 00200 (*i)->cluster = cur_cluster; 00201 } 00202 // else: no search required 00203 } 00204 00205 // Push super operations on the stack 00206 for (Operation::Operationlist::const_reverse_iterator 00207 j = cur_oper->getSuperOperations().rbegin(); 00208 j != cur_oper->getSuperOperations().rend(); 00209 ++j) 00210 { 00211 if ((*j)->lvl < cur_level) 00212 { 00213 // Search level and cluster 00214 stack.push(make_pair(*j,cur_level)); 00215 (*j)->lvl = cur_level; 00216 (*j)->cluster = cur_cluster; 00217 } 00218 else if (!(*j)->cluster) 00219 { 00220 // Search for clusters information only 00221 stack.push(make_pair(*j,-1)); 00222 (*j)->cluster = cur_cluster; 00223 } 00224 // else: no search required 00225 } 00226 00227 // Update level of resources linked to current operation 00228 for (Operation::loadlist::const_iterator gres = 00229 cur_oper->getLoads().begin(); 00230 gres != cur_oper->getLoads().end(); ++gres) 00231 { 00232 Resource *resptr = gres->getResource(); 00233 // Update the level of the resource 00234 if (resptr->lvl < cur_level) resptr->lvl = cur_level; 00235 // Update the cluster of the resource and operations using it 00236 if (!resptr->cluster) 00237 { 00238 resptr->cluster = cur_cluster; 00239 // Find more operations connected to this cluster by the resource 00240 for (Resource::loadlist::const_iterator resops = 00241 resptr->getLoads().begin(); 00242 resops != resptr->getLoads().end(); ++resops) 00243 if (!resops->getOperation()->cluster) 00244 { 00245 stack.push(make_pair(resops->getOperation(),-1)); 00246 resops->getOperation()->cluster = cur_cluster; 00247 } 00248 } 00249 } 00250 00251 // Now loop through all flows of the operation 00252 for (Operation::flowlist::const_iterator 00253 gflow = cur_oper->getFlows().begin(); 00254 gflow != cur_oper->getFlows().end(); 00255 ++gflow) 00256 { 00257 cur_Flow = &*gflow; 00258 cur_buf = cur_Flow->getBuffer(); 00259 00260 // Check whether the level search needs to continue 00261 search_level = cur_level!=-1 && cur_buf->lvl<cur_level+1; 00262 00263 // Check if the buffer needs processing 00264 if (search_level || !cur_buf->cluster) 00265 { 00266 // Update the cluster of the current buffer 00267 cur_buf->cluster = cur_cluster; 00268 00269 // Loop through all flows of the buffer 00270 for (Buffer::flowlist::const_iterator 00271 buffl = cur_buf->getFlows().begin(); 00272 buffl != cur_buf->getFlows().end(); 00273 ++buffl) 00274 { 00275 // Check level recursion 00276 if (cur_Flow->isConsumer() && search_level) 00277 { 00278 if (buffl->getOperation()->lvl < cur_level+1 00279 && &*buffl != cur_Flow && buffl->isProducer()) 00280 { 00281 stack.push(make_pair(buffl->getOperation(),cur_level+1)); 00282 buffl->getOperation()->lvl = cur_level+1; 00283 buffl->getOperation()->cluster = cur_cluster; 00284 } 00285 else if (!buffl->getOperation()->cluster) 00286 { 00287 stack.push(make_pair(buffl->getOperation(),-1)); 00288 buffl->getOperation()->cluster = cur_cluster; 00289 } 00290 cur_buf->lvl = cur_level+1; 00291 } 00292 // Check cluster recursion 00293 else if (!buffl->getOperation()->cluster) 00294 { 00295 stack.push(make_pair(buffl->getOperation(),-1)); 00296 buffl->getOperation()->cluster = cur_cluster; 00297 } 00298 } 00299 } // End of needs-procssing if statement 00300 } // End of flow loop 00301 00302 } // End while stack not empty 00303 00304 } // End of Operation loop 00305 00306 // The above loop will visit ALL operations and recurse through the 00307 // buffers and resources connected to them. 00308 // Missing from the loop are buffers and resources that have no flows or 00309 // loads at all. We catch those poor lonely fellows now... 00310 for (Buffer::iterator gbuf2 = Buffer::begin(); 00311 gbuf2 != Buffer::end(); ++gbuf2) 00312 if (gbuf2->getFlows().empty()) 00313 { 00314 gbuf2->cluster = ++numberOfClusters; 00315 if (numberOfClusters >= USHRT_MAX) 00316 throw LogicException("Too many clusters"); 00317 ++numberOfHangingClusters; 00318 } 00319 for (Resource::iterator gres2 = Resource::begin(); 00320 gres2 != Resource::end(); ++gres2) 00321 if (gres2->getLoads().empty()) 00322 { 00323 gres2->cluster = ++numberOfClusters; 00324 if (numberOfClusters >= USHRT_MAX) 00325 throw LogicException("Too many clusters"); 00326 ++numberOfHangingClusters; 00327 } 00328 00329 } // End of while recomputeLevels. The loop will be repeated as long as model 00330 // changes are done during the recomputation. 00331 00332 // Unlock the exclusive access to this function 00333 computationBusy = false; 00334 } 00335 00336 } // End Namespace