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

Documentation generated for frePPLe by  doxygen