leveled.cpp
Go to the documentation of this file.
1 /***************************************************************************
2  * *
3  * Copyright (C) 2007-2013 by Johan De Taeye, frePPLe bvba *
4  * *
5  * This library is free software; you can redistribute it and/or modify it *
6  * under the terms of the GNU Affero General Public License as published *
7  * by the Free Software Foundation; either version 3 of the License, or *
8  * (at your option) any later version. *
9  * *
10  * This library is distributed in the hope that it will be useful, *
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of *
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
13  * GNU Affero General Public License for more details. *
14  * *
15  * You should have received a copy of the GNU Affero General Public *
16  * License along with this program. *
17  * If not, see <http://www.gnu.org/licenses/>. *
18  * *
19  ***************************************************************************/
20 
21 #define FREPPLE_CORE
22 #include "frepple/model.h"
23 #include <climits>
24 
25 
26 // Uncomment the following line to create debugging statements during the
27 // clustering and leveling algorithm.
28 //#define CLUSTERDEBUG
29 
30 
31 namespace frepple
32 {
33 
34 
35 DECLARE_EXPORT bool HasLevel::recomputeLevels = false;
36 DECLARE_EXPORT bool HasLevel::computationBusy = false;
37 DECLARE_EXPORT short unsigned HasLevel::numberOfClusters = 0;
38 DECLARE_EXPORT short unsigned HasLevel::numberOfHangingClusters = 0;
39 
40 
42 {
43  computationBusy = true;
44  // Get exclusive access to this function in a multi-threaded environment.
45  static Mutex levelcomputationbusy;
46  ScopeMutexLock l(levelcomputationbusy);
47 
48  // Another thread may already have computed the levels while this thread was
49  // waiting for the lock. In that case the while loop will be skipped.
50  while (recomputeLevels)
51  {
52  // Reset the recomputation flag. Note that during the computation the flag
53  // could be switched on again by some model change in a different thread.
54  // In that case, the while loop will be rerun.
55  recomputeLevels = false;
56 
57  // Reset current levels on buffers, resources and operations
58  for (Buffer::iterator gbuf = Buffer::begin();
59  gbuf != Buffer::end(); ++gbuf)
60  {
61  gbuf->cluster = 0;
62  gbuf->lvl = -1;
63  }
64  for (Resource::iterator gres = Resource::begin();
65  gres != Resource::end(); ++gres)
66  {
67  gres->cluster = 0;
68  gres->lvl = -1;
69  }
70  for (Operation::iterator gop = Operation::begin();
71  gop != Operation::end(); ++gop)
72  {
73  gop->cluster = 0;
74  gop->lvl = -1;
75  }
76 
77  // Loop through all operations
78  stack< pair<Operation*,int> > stack;
79  Operation* cur_oper;
80  int cur_level;
81  Buffer *cur_buf;
82  const Flow* cur_Flow;
83  bool search_level;
84  int cur_cluster;
85  numberOfClusters = 0;
86  numberOfHangingClusters = 0;
87  map<Operation*,short> visited;
88  for (Operation::iterator g = Operation::begin();
89  g != Operation::end(); ++g)
90  {
91 
92 #ifdef CLUSTERDEBUG
93  logger << "Investigating operation '" << &*g
94  << "' - current cluster " << g->cluster << endl;
95 #endif
96 
97  // Select a new cluster number
98  if (g->cluster)
99  cur_cluster = g->cluster;
100  else
101  {
102  cur_cluster = ++numberOfClusters;
103  if (numberOfClusters >= USHRT_MAX)
104  throw LogicException("Too many clusters");
105 
106  // Detect hanging operations
107  if (g->getFlows().empty() && g->getLoads().empty()
108  && g->getSuperOperations().empty()
109  && g->getSubOperations().empty()
110  )
111  {
112  ++numberOfHangingClusters;
113  g->lvl = 0;
114  continue;
115  }
116  }
117 
118  // Do we need to activate the level search?
119  // Criterion are:
120  // - Not used in a super operation
121  // - Have a producing flow on the operation itself
122  // or on any of its sub operations
123  search_level = false;
124  if (g->getSuperOperations().empty())
125  {
126  search_level = true;
127  // Does the operation itself have producing flows?
128  for (Operation::flowlist::const_iterator fl = g->getFlows().begin();
129  fl != g->getFlows().end() && search_level; ++fl)
130  if (fl->isProducer()) search_level = false;
131  if (search_level)
132  {
133  // Do suboperations have a producing flow?
134  for (Operation::Operationlist::const_reverse_iterator
135  i = g->getSubOperations().rbegin();
136  i != g->getSubOperations().rend() && search_level;
137  ++i)
139  fl = (*i)->getFlows().begin();
140  fl != (*i)->getFlows().end() && search_level;
141  ++fl)
142  if (fl->isProducer()) search_level = false;
143  }
144  }
145 
146  // If both the level and the cluster are de-activated, then we can move on
147  if (!search_level && g->cluster) continue;
148 
149  // Start recursing
150  // Note that as soon as push an operation on the stack we set its
151  // cluster and/or level. This is avoid that operations are needlessly
152  // pushed a second time on the stack.
153  stack.push(make_pair(&*g, search_level ? 0 : -1));
154  visited.clear();
155  g->cluster = cur_cluster;
156  if (search_level) g->lvl = 0;
157  while (!stack.empty())
158  {
159  // Take the top of the stack
160  cur_oper = stack.top().first;
161  cur_level = stack.top().second;
162  stack.pop();
163 
164 #ifdef CLUSTERDEBUG
165  logger << " Recursing in Operation '" << *(cur_oper)
166  << "' - current level " << cur_level << endl;
167 #endif
168  // Detect loops in the supply chain
169  map<Operation*,short>::iterator detectloop = visited.find(cur_oper);
170  if (detectloop == visited.end())
171  // Keep track of operations already visited
172  visited.insert(make_pair(cur_oper,0));
173  else if (++(detectloop->second) > 1)
174  // Already visited this operation enough times - don't repeat
175  continue;
176 
177  // Push sub operations on the stack
178  for (Operation::Operationlist::const_reverse_iterator
179  i = cur_oper->getSubOperations().rbegin();
180  i != cur_oper->getSubOperations().rend();
181  ++i)
182  {
183  if ((*i)->lvl < cur_level)
184  {
185  // Search level and cluster
186  stack.push(make_pair(*i,cur_level));
187  (*i)->lvl = cur_level;
188  (*i)->cluster = cur_cluster;
189  }
190  else if (!(*i)->cluster)
191  {
192  // Search for clusters information only
193  stack.push(make_pair(*i,-1));
194  (*i)->cluster = cur_cluster;
195  }
196  // else: no search required
197  }
198 
199  // Push super operations on the stack
200  for (Operation::Operationlist::const_reverse_iterator
201  j = cur_oper->getSuperOperations().rbegin();
202  j != cur_oper->getSuperOperations().rend();
203  ++j)
204  {
205  if ((*j)->lvl < cur_level)
206  {
207  // Search level and cluster
208  stack.push(make_pair(*j,cur_level));
209  (*j)->lvl = cur_level;
210  (*j)->cluster = cur_cluster;
211  }
212  else if (!(*j)->cluster)
213  {
214  // Search for clusters information only
215  stack.push(make_pair(*j,-1));
216  (*j)->cluster = cur_cluster;
217  }
218  // else: no search required
219  }
220 
221  // Update level of resources linked to current operation
222  for (Operation::loadlist::const_iterator gres =
223  cur_oper->getLoads().begin();
224  gres != cur_oper->getLoads().end(); ++gres)
225  {
226  Resource *resptr = gres->getResource();
227  // Update the level of the resource
228  if (resptr->lvl < cur_level) resptr->lvl = cur_level;
229  // Update the cluster of the resource and operations using it
230  if (!resptr->cluster)
231  {
232  resptr->cluster = cur_cluster;
233  // Find more operations connected to this cluster by the resource
234  for (Resource::loadlist::const_iterator resops =
235  resptr->getLoads().begin();
236  resops != resptr->getLoads().end(); ++resops)
237  if (!resops->getOperation()->cluster)
238  {
239  stack.push(make_pair(resops->getOperation(),-1));
240  resops->getOperation()->cluster = cur_cluster;
241  }
242  }
243  }
244 
245  // Now loop through all flows of the operation
247  gflow = cur_oper->getFlows().begin();
248  gflow != cur_oper->getFlows().end();
249  ++gflow)
250  {
251  cur_Flow = &*gflow;
252  cur_buf = cur_Flow->getBuffer();
253 
254  // Check whether the level search needs to continue
255  search_level = cur_level!=-1 && cur_buf->lvl<cur_level+1;
256 
257  // Check if the buffer needs processing
258  if (search_level || !cur_buf->cluster)
259  {
260  // Update the cluster of the current buffer
261  cur_buf->cluster = cur_cluster;
262 
263  // Loop through all flows of the buffer
265  buffl = cur_buf->getFlows().begin();
266  buffl != cur_buf->getFlows().end();
267  ++buffl)
268  {
269  // Check level recursion
270  if (cur_Flow->isConsumer() && search_level)
271  {
272  if (buffl->getOperation()->lvl < cur_level+1
273  && &*buffl != cur_Flow && buffl->isProducer())
274  {
275  stack.push(make_pair(buffl->getOperation(),cur_level+1));
276  buffl->getOperation()->lvl = cur_level+1;
277  buffl->getOperation()->cluster = cur_cluster;
278  }
279  else if (!buffl->getOperation()->cluster)
280  {
281  stack.push(make_pair(buffl->getOperation(),-1));
282  buffl->getOperation()->cluster = cur_cluster;
283  }
284  cur_buf->lvl = cur_level+1;
285  }
286  // Check cluster recursion
287  else if (!buffl->getOperation()->cluster)
288  {
289  stack.push(make_pair(buffl->getOperation(),-1));
290  buffl->getOperation()->cluster = cur_cluster;
291  }
292  }
293  } // End of needs-procssing if statement
294  } // End of flow loop
295 
296  } // End while stack not empty
297 
298  } // End of Operation loop
299 
300  // The above loop will visit ALL operations and recurse through the
301  // buffers and resources connected to them.
302  // Missing from the loop are buffers and resources that have no flows or
303  // loads at all. We catch those poor lonely fellows now...
304  for (Buffer::iterator gbuf2 = Buffer::begin();
305  gbuf2 != Buffer::end(); ++gbuf2)
306  if (gbuf2->getFlows().empty())
307  {
308  gbuf2->cluster = ++numberOfClusters;
309  if (numberOfClusters >= USHRT_MAX)
310  throw LogicException("Too many clusters");
311  ++numberOfHangingClusters;
312  }
313  for (Resource::iterator gres2 = Resource::begin();
314  gres2 != Resource::end(); ++gres2)
315  if (gres2->getLoads().empty())
316  {
317  gres2->cluster = ++numberOfClusters;
318  if (numberOfClusters >= USHRT_MAX)
319  throw LogicException("Too many clusters");
320  ++numberOfHangingClusters;
321  }
322 
323  } // End of while recomputeLevels. The loop will be repeated as long as model
324  // changes are done during the recomputation.
325 
326  // Unlock the exclusive access to this function
327  computationBusy = false;
328 }
329 
330 } // End Namespace