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