leveled.cpp

Go to the documentation of this file.
00001 /***************************************************************************
00002   file : $URL: https://frepple.svn.sourceforge.net/svnroot/frepple/trunk/src/model/leveled.cpp $
00003   version : $LastChangedRevision: 1315 $  $LastChangedBy: jdetaeye $
00004   date : $LastChangedDate: 2010-07-17 18:08:53 +0200 (Sat, 17 Jul 2010) $
00005  ***************************************************************************/
00006 
00007 /***************************************************************************
00008  *                                                                         *
00009  * Copyright (C) 2007-2010 by Johan De Taeye                               *
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

Documentation generated for frePPLe by  doxygen