angel  mercurial changeset: <a href="http://mercurial.mcs.anl.gov/ad/angel/rev/b39b3ee16224" target="_parent">b39b3ee16224</a>
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
heuristics.cpp
Go to the documentation of this file.
1 // $Id: heuristics.cpp,v 1.11 2008/02/28 14:57:33 gottschling Exp $
2 /*
3 #############################################################
4 # This file is part of angel released under the BSD license #
5 # The full COPYRIGHT notice can be found in the top #
6 # level directory of the angel distribution #
7 #############################################################
8 */
9 
10 
11 #include <limits.h>
12 #include <algorithm>
13 
14 #include "angel/include/heuristics.hpp"
15 #include "angel/include/angel_exceptions.hpp"
16 #include "angel/include/angel_tools.hpp"
17 #ifdef USEXAIFBOOSTER
18 #include "angel/include/reroutings.hpp"
19 using namespace xaifBoosterCrossCountryInterface;
20 #endif
21 
22 namespace angel {
23 
24 using namespace std;
25 using namespace boost;
26 
27 // =====================================================
28 // for vertex elimination
29 // =====================================================
30 
31 int forward_mode_vertex_t::operator() (const vector<c_graph_t::vertex_t>& vv1,
32  const c_graph_t& cg,
33  vector<c_graph_t::vertex_t>& vv2) {
34  vv2.resize (0);
35  if (vv1.size() == 0) {set_empty_objective (); return 0; }
36  vv2.push_back (vv1[0]);
37 
38  for (size_t c= 1; c < vv1.size(); c++)
39  if (vv1[c] < vv2[0]) vv2[0]= vv1[c];
40  set_objective (vv2[0]);
41  return 1;
42 }
43 
44 forward_mode_vertex_t forward_mode_vertex;
45 
46 // -------------------------------------------------------------------------
47 // reverse mode
48 // -------------------------------------------------------------------------
49 
50 int reverse_mode_vertex_t::operator() (const vector<c_graph_t::vertex_t>& vv1,
51  const c_graph_t& cg,
52  vector<c_graph_t::vertex_t>& vv2) {
53  vv2.resize (0);
54  if (vv1.size() == 0) {set_empty_objective (); return 0; }
55  vv2.push_back (vv1[0]);
56 
57  for (size_t c= 1; c < vv1.size(); c++)
58  if (vv1[c] > vv2[0]) vv2[0]= vv1[c];
59  set_objective (vv2[0]);
60  return 1;
61 }
62 
63 reverse_mode_vertex_t reverse_mode_vertex;
64 
65 // -------------------------------------------------------------------------
66 // Lowest Markowitz
67 // -------------------------------------------------------------------------
68 
69 // operator for lowest Markowitz on vertices
70 struct lmv_op_t {
71  int operator() (c_graph_t::vertex_t v, const c_graph_t& cg) {
72  return in_degree (v, cg) * out_degree (v, cg); }
73 };
74 
75 int lowest_markowitz_vertex_t::operator() (const vector<c_graph_t::vertex_t>& vv1,
76  const c_graph_t& cg,
77  vector<c_graph_t::vertex_t>& vv2) {
78  lmv_op_t lmv_op;
79  return standard_heuristic_op (vv1, cg, vv2, lmv_op, *this);
80 }
81 
82 lowest_markowitz_vertex_t lowest_markowitz_vertex;
83 
84 // -------------------------------------------------------------------------
85 // Lowest relative Markowitz
86 // -------------------------------------------------------------------------
87 
88 // operator for lowest relative Markowitz on vertices and edges
89 struct lrm_op_t {
90  vector<int> indep, dep;
91  lrm_op_t (const c_graph_t& cg) : indep (num_vertices (cg)), dep (num_vertices (cg)) {
92  number_independent_vertices (cg, indep); number_dependent_vertices (cg, dep); }
93  int operator() (bool front, c_graph_t::edge_t edge, const c_graph_t& cg) {
94  return front ? out_degree (target (edge, cg), cg) - dep[target (edge, cg)]
95  : in_degree (source (edge, cg), cg) - indep[source (edge, cg)]; }
96  int operator() (edge_bool_t eb, const c_graph_t& cg) {
97  return eb.second ? out_degree (target (eb.first, cg), cg) - dep[target (eb.first, cg)]
98  : in_degree (source (eb.first, cg), cg) - indep[source (eb.first, cg)]; }
99  int operator() (c_graph_t::vertex_t v, const c_graph_t& cg) {
100  return in_degree (v, cg) * out_degree (v, cg) - indep[v] * dep[v]; }
101 };
102 
103 int lowest_relative_markowitz_vertex_t::operator() (const vector<c_graph_t::vertex_t>& vv1,
104  const c_graph_t& cg,
105  vector<c_graph_t::vertex_t>& vv2) {
106  lrm_op_t lrm_op (cg);
107  return standard_heuristic_op (vv1, cg, vv2, lrm_op, *this);
108 }
109 
110 lowest_relative_markowitz_vertex_t lowest_relative_markowitz_vertex;
111 
112 // -------------------------------------------------------------------------
113 // subroutine of Lowest fill-in
114 // -------------------------------------------------------------------------
115 
116 // how many new in_edges has j:target(e) by back-eliminating e
117 int new_in_edges (c_graph_t::edge_t e, const c_graph_t& cg) {
118 
119  typedef c_graph_t::vertex_t vertex_t;
120  typedef c_graph_t::iei_t iei_t;
121 
122  iei_t siei, sie_end, tiei, tie_end;
123  tie (siei, sie_end)= in_edges (source (e, cg), cg);
124  tie (tiei, tie_end)= in_edges (target (e, cg), cg);
125  int new_edges= 0;
126 
127  vector<vertex_t> nsl; // list of new sources to check double insertions
128 
129  for (; siei != sie_end; ++siei) {
130  vertex_t ss= source (*siei, cg);
131  iei_t i= tiei;
132  for (; i != tie_end; ++i)
133  if (source (*i, cg) == ss) break;
134  if (i == tie_end
135  && find (nsl.begin(), nsl.end(), ss) == nsl.end()) {
136  nsl.push_back (ss); new_edges++; }
137  }
138 
139  return new_edges;
140 }
141 
142 // how many new out_edges has j:=source(e) by front-eliminating e
143 int new_out_edges (c_graph_t::edge_t e, const c_graph_t& cg) {
144 
145  typedef c_graph_t::vertex_t vertex_t;
146  typedef c_graph_t::oei_t oei_t;
147 
148  oei_t soei, soe_end, toei, toe_end;
149  tie (soei, soe_end)= out_edges (source (e, cg), cg);
150  tie (toei, toe_end)= out_edges (target (e, cg), cg);
151  int new_edges= 0;
152 
153  vector<vertex_t> ntl; // list of new targets to check double insertions
154 
155  for (; toei != toe_end; ++toei) {
156  vertex_t tt= target (*toei, cg);
157  oei_t i= soei;
158  for (; i != soe_end; ++i)
159  if (target (*i, cg) == tt) break;
160  if (i == soe_end
161  && find (ntl.begin(), ntl.end(), tt) == ntl.end()) {
162  ntl.push_back (tt); new_edges++; }
163  }
164 
165  return new_edges;
166 }
167 
168 
169 // -------------------------------------------------------------------------
170 // Lowest fill-in
171 // -------------------------------------------------------------------------
172 
173 
174 // operator for lowest fill-in on vertices
175 struct fiv_op_t {
176  int operator() (c_graph_t::vertex_t v, const c_graph_t& cg) {
177  int fill_ins= 0;
178  c_graph_t::iei_t iei, ie_end;
179  for (tie (iei, ie_end)= in_edges (v, cg); iei != ie_end; ++iei)
180  fill_ins+= new_out_edges (*iei, cg);
181  return fill_ins; }
182 };
183 
184 int lowest_fill_in_vertex_t::operator() (const vector<c_graph_t::vertex_t>& vv1,
185  const c_graph_t& cg,
186  vector<c_graph_t::vertex_t>& vv2) {
187  fiv_op_t fiv_op;
188  return standard_heuristic_op (vv1, cg, vv2, fiv_op, *this);
189 }
190 
191 lowest_fill_in_vertex_t lowest_fill_in_vertex;
192 
193 // -------------------------------------------------------------------------
194 // subroutines of LMMD MOMR
195 // -------------------------------------------------------------------------
196 
197 // how much the markowitz degree of j:=source(e) is enlarged by front-eliminating e
198 // this is in_degree(j) * #new out_edges(j)
199 int markowitz_enlargement_front (c_graph_t::edge_t e, const c_graph_t& cg,
200  bool eliminate_parallel_edges= false) {
201  int ee= 0; // number of eliminated edges
202  c_graph_t::vertex_t s= source (e, cg), t= target (e, cg);
203  if (vertex_type (t, cg) == intermediate){ // if dependent edges are not eliminated
204  if (eliminate_parallel_edges) {
205  c_graph_t::oei_t soei, soe_end;
206  for (tie (soei, soe_end)= out_edges (s, cg); soei != soe_end; soei++)
207  ee+= target (*soei, cg) == t;
208  } else ee= 1;
209  }
210  return in_degree (source (e, cg), cg) * (new_out_edges (e, cg) - ee);
211 }
212 
213 // how much is the markowitz degree of j:=target(e2) enlarged by front-eliminating e
214 int markowitz_enlargement_front (c_graph_t::edge_t e, c_graph_t::edge_t e2,
215  const c_graph_t& cg) {
216 
217  THROW_DEBUG_EXCEPT_MACRO (target (e, cg) != source (e2, cg), consistency_exception,
218  "e and e2 does not match");
219 
220  c_graph_t::vertex_t j= target (e2, cg), se= source (e, cg), te= target (e, cg);
221 
222  // if e is last in_edge of te than e2 will be eliminated -> j has one in_edge less
223  // int in_edge_change= in_degree (te, cg) == 1 ? -1 : 0;
224 
225  // if e is last in_edge of te than e2 and its parallel edges will be eliminated
226  // -> j has one or more in_edges less
227  int in_edge_change= in_degree (te, cg) == 1 ? - count_parallel_edges (e2, cg) : 0;
228 
229  // if source(e) is not source of an in_edge of j -> j has one in_edge more
230  c_graph_t::iei_t iei, ie_end;
231  for (tie (iei, ie_end)= in_edges (j, cg); iei != ie_end; ++iei)
232  if (source (*iei, cg) == se) break;
233  if (iei == ie_end) in_edge_change++;
234 
235  return in_edge_change * out_degree (j, cg);
236 }
237 
238 // how much the markowitz degree of j:=target(e) is enlarged by back-eliminating e
239 // this is out_degree(j) * #new in_edges(j)
240 int markowitz_enlargement_back (c_graph_t::edge_t e, const c_graph_t& cg,
241  bool eliminate_parallel_edges= false) {
242 
243  int ee= 0; // number of eliminated edges
244  if (eliminate_parallel_edges) {
245  c_graph_t::vertex_t s= source (e, cg), t= target (e, cg);
246  c_graph_t::iei_t tiei, tie_end;
247  for (tie (tiei, tie_end)= in_edges (t, cg); tiei != tie_end; ++tiei)
248  ee+= source (*tiei, cg) == s;
249  } else ee= 1;
250 
251  return out_degree (target (e, cg), cg) * (new_in_edges (e, cg) - ee);
252 }
253 
254 // how much is the markowitz degree of j:=source(e2) enlarged by back-eliminating e
255 int markowitz_enlargement_back (c_graph_t::edge_t e, c_graph_t::edge_t e2,
256  const c_graph_t& cg) {
257 
258  // assert (source (e, cg) == target (e2, cg));
259  THROW_DEBUG_EXCEPT_MACRO (source (e, cg) != target (e2, cg), consistency_exception,
260  "e and e2 does not match");
261 
262  c_graph_t::vertex_t j= source (e2, cg), se= source (e, cg), te= target (e, cg);
263 
264  // if e is last out_edge of se than e2 will be eliminated -> j has one out_edge less
265  int out_edge_change= out_degree (se, cg) == 1 ? -1 : 0;
266 
267  // if target(e) is not target of an out_edge of j -> j has one out_edge more
268  c_graph_t::oei_t oei, oe_end;
269  for (tie (oei, oe_end)= out_edges (j, cg); oei != oe_end; ++oei)
270  if (target (*oei, cg) == te) break;
271  if (oei == oe_end) out_edge_change++;
272 
273  return out_edge_change * in_degree (j, cg);
274 }
275 
276 // how much is the markowitz degree of all neighbors of v increased by its elimination
277 // multiply occurred neighbors are counted only once
278 int markowitz_enlargement_all_neighbors (c_graph_t::vertex_t v, const c_graph_t& cg) {
279 
280  using namespace std;
281 
282  typedef c_graph_t::vertex_t vertex_t;
283 
284  int enl= 0;
285 
286  // parallel edges does not cause multiple Markowitz changes
287  vector<vertex_t> cv; // already checked vertices
288  cv.reserve (10); // reduce mallocs
289 
290  c_graph_t::iei_t iei, ie_end;
291  tie (iei, ie_end)= in_edges (v, cg);
292  for (; iei != ie_end; ++iei) {
293  vertex_t v= source (*iei, cg);
294  if (find (cv.begin(), cv.end(), v) == cv.end()) {
295  enl+= markowitz_enlargement_front (*iei, cg, true);
296  cv.push_back (v); } }
297 
298  cv.resize (0); // reduce search space
299  c_graph_t::oei_t oei, oe_end;
300  tie (oei, oe_end)= out_edges (v, cg);
301  for (; oei != oe_end; ++oei) {
302  vertex_t v= target (*oei, cg);
303  if (find (cv.begin(), cv.end(), v) == cv.end()) {
304  enl+= markowitz_enlargement_back (*oei, cg, true);
305  cv.push_back (v); } }
306  return enl;
307 }
308 
309 struct markowitz_enlargement_front_t {
310  c_graph_t::edge_t _e; // first edge is stored
311  markowitz_enlargement_front_t (c_graph_t::edge_t e) : _e (e) {}
312  int operator() (c_graph_t::edge_t e2, const c_graph_t& cg) const {
313  return markowitz_enlargement_front (_e, e2, cg); }
314 };
315 
316 struct markowitz_enlargement_back_t {
317  c_graph_t::edge_t _e; // first edge is stored
318  markowitz_enlargement_back_t (c_graph_t::edge_t e) : _e (e) {}
319  int operator() (c_graph_t::edge_t e2, const c_graph_t& cg) const {
320  return markowitz_enlargement_back (_e, e2, cg); }
321 };
322 
323 
324 // -------------------------------------------------------------------------
325 // LMMD
326 // -------------------------------------------------------------------------
327 
328 // operator that computes LMMD value for a single vertex
329 struct lmmdv_op_t {
330  double w; // weight
331  lmmdv_op_t (double _w) : w (_w) {}
332  int operator() (c_graph_t::vertex_t v, const c_graph_t& cg) {
333  int markowitz= in_degree (v, cg) * out_degree (v, cg),
334  damage= markowitz_enlargement_all_neighbors (v, cg);
335  return int (double (markowitz) + w * double (damage)); }
336 };
337 
338 int lmmd_vertex_t::operator() (const vector<c_graph_t::vertex_t>& vv1,
339  const c_graph_t& cg,
340  vector<c_graph_t::vertex_t>& vv2) {
341  lmmdv_op_t lmmdv_op (weight);
342  return standard_heuristic_op (vv1, cg, vv2, lmmdv_op, *this);
343 }
344 
345 lmmd_vertex_t lmmd_vertex (1.0);
346 
347 // -------------------------------------------------------------------------
348 // MOMR
349 // -------------------------------------------------------------------------
350 
351 // operator that computes MOMR value for a single vertex
352 struct momrv_op_t {
353  int operator() (c_graph_t::vertex_t v, const c_graph_t& cg) {
354  int momr= in_degree (v, cg) * out_degree (v, cg)
355  - markowitz_enlargement_all_neighbors (v, cg);
356 #ifndef NDEBUG
357  c_graph_t gtmp (cg); vertex_elimination (v, gtmp);
358  THROW_DEBUG_EXCEPT_MACRO (overall_markowitz_degree (cg) - overall_markowitz_degree (gtmp) != momr,
359  consistency_exception, "momr not correct");
360 #endif
361  return momr; }
362 };
363 
364 int momr_vertex_t::operator() (const vector<c_graph_t::vertex_t>& vv1,
365  const c_graph_t& cg,
366  vector<c_graph_t::vertex_t>& vv2) {
367  momrv_op_t momrv_op;
368  return standard_heuristic_op (vv1, cg, vv2, momrv_op, *this);
369 }
370 
371 momr_vertex_t momr_vertex;
372 
373 // -------------------------------------------------------------------------
374 // subroutines of Maximal overall path length reduction
375 // -------------------------------------------------------------------------
376 
377 // overall path length reduction of face (e1, e2)
378 inline int oplr_face (c_graph_t::edge_t e1, c_graph_t::edge_t e2,
379  const vector<int>& vni, const vector<int>& vli,
380  const vector<int>& vno, const vector<int>& vlo,
381  const c_graph_t& cg) {
382 
383  // assert (target (e1, cg) == source (e2, cg));
384  THROW_DEBUG_EXCEPT_MACRO (target (e1, cg) != source (e2, cg), consistency_exception,
385  "e1 and e2 does not match");
386 
387  c_graph_t::vertex_t p= source (e1, cg), s= target (e2, cg);
388 
389  c_graph_t::edge_t e;
390  bool found;
391  boost::tie (e, found)= edge (p, s, cg);
392 
393  return found ? vno[s] * (vni[p] + vli[p]) + vni[p] * (vno[s] + vlo[s])
394  : vni[p] * vno[s];
395 }
396 
397 int oplr_edge_front (c_graph_t::edge_t e,
398  const vector<int>& vni, const vector<int>& vli,
399  const vector<int>& vno, const vector<int>& vlo,
400  const c_graph_t& cg) {
401 
402  int oplr= 0;
403  graph_traits<c_graph_t>::out_edge_iterator oei, oe_end;
404  tie (oei, oe_end)= out_edges (target (e, cg), cg);
405 
406  for (; oei != oe_end; ++oei)
407  oplr+= oplr_face (e, *oei, vni, vli, vno, vlo, cg);
408 
409  return oplr;
410 }
411 
412 int oplr_edge_back (c_graph_t::edge_t e,
413  const vector<int>& vni, const vector<int>& vli,
414  const vector<int>& vno, const vector<int>& vlo,
415  const c_graph_t& cg) {
416 
417  int oplr= 0;
418  graph_traits<c_graph_t>::in_edge_iterator iei, ie_end;
419  tie (iei, ie_end)= in_edges (source (e, cg), cg);
420 
421  for (; iei != ie_end; ++iei)
422  oplr+= oplr_face (*iei, e, vni, vli, vno, vlo, cg);
423 
424  return oplr;
425 }
426 
427 // -------------------------------------------------------------------------
428 // Maximal overall path length reduction
429 // -------------------------------------------------------------------------
430 
431 // operator that computes path length reduction for a single vertex
432 struct oplrv_op_t {
433  vector<int> vni, vli, vno, vlo;
434  oplrv_op_t (const c_graph_t& cg) {
435  in_out_path_lengths (cg, vni, vli, vno, vlo); }
436  int operator () (c_graph_t::vertex_t v, const c_graph_t& cg) {
437  int oplr= 0;
438  c_graph_t::iei_t iei, ie_end;
439  for (tie (iei, ie_end)= in_edges (v, cg); iei != ie_end; ++iei)
440  oplr+= oplr_edge_front (*iei, vni, vli, vno, vlo, cg);
441  return oplr; }
442 };
443 
444 int moplr_vertex_t::operator() (const vector<c_graph_t::vertex_t>& vv1,
445  const c_graph_t& cg,
446  vector<c_graph_t::vertex_t>& vv2) {
447  oplrv_op_t oplrv_op (cg);
448  return standard_heuristic_op (vv1, cg, vv2, oplrv_op, *this);
449 }
450 
451 moplr_vertex_t moplr_vertex;
452 
453 // =====================================================
454 // for edge elimination (in c-graph)
455 // =====================================================
456 
457 int forward_mode_edge_f (const vector<c_graph_t::edge_t>& ev1,
458  bool front,
459  const c_graph_t& cg,
460  vector<c_graph_t::edge_t>& ev2) {
461  ev2.resize (0);
462 
463  if (ev1.size() == 0) return 0;
464  ev2.push_back (ev1[0]);
465 
466  for (size_t c= 1; c < ev1.size(); c++)
467  if (front ? inv_lex_less (ev1[c], ev2[0], cg) : lex_less (ev1[c], ev2[0], cg))
468  ev2[0]= ev1[c];
469 
470  return 1;
471 }
472 
473 // objective function for forward mode in edge elimination
474 // works up to 47 million vertices in IEEE arithmetic
475 inline double fme_obj (edge_bool_t eb, const c_graph_t& cg) {
476  c_graph_t::edge_t edge= eb.first;
477  // front is prefered -> add something if not front because we minimize
478  int high, low, notfront;
479  if (eb.second) high= target (edge, cg), low= source (edge, cg), notfront= 0;
480  else high= source (edge, cg), low= target (edge, cg), notfront= 1;
481  return (2 * high + notfront) * double (cg.x()) + low;
482 }
483 
484 int forward_mode_edge_t::operator() (const vector<edge_bool_t>& ev1,
485  const c_graph_t& cg,
486  vector<edge_bool_t>& ev2) {
487  ev2.resize (0);
488  if (ev1.size() == 0) {set_empty_objective (); return 0; }
489  ev2.push_back (ev1[0]);
490 
491  for (size_t c= 1; c < ev1.size(); c++) {
492 // THROW_DEBUG_EXCEPT_MACRO (fme_obj (ev1[c], cg) < fme_obj (ev2[0], cg) != lex_less (ev1[c], ev2[0], cg),
493 // consistency_exception, "objective function and comparator does not match");
494  if (lex_less (ev1[c], ev2[0], cg)) ev2[0]= ev1[c]; }
495  set_objective (fme_obj (ev2[0], cg));
496  return 1;
497 }
498 
499 forward_mode_edge_t forward_mode_edge;
500 
501 // remark fm: if all eliminatable edges are considered than only front elimination is used
502 // this way one can force same sequences in vertex, edge and face elimination
503 // when forward mode is used as sole criterion
504 
505 // -------------------------------------------------------------------------
506 // reverse mode
507 // -------------------------------------------------------------------------
508 
509 int reverse_mode_edge_f (const vector<c_graph_t::edge_t>& ev1,
510  bool front,
511  const c_graph_t& cg,
512  vector<c_graph_t::edge_t>& ev2) {
513  ev2.resize (0);
514 
515  if (ev1.size() == 0) return 0;
516  ev2.push_back (ev1[0]);
517 
518  for (size_t c= 1; c < ev1.size(); c++)
519  if (front ? inv_lex_greater (ev1[c], ev2[0], cg) : lex_greater (ev1[c], ev2[0], cg))
520  ev2[0]= ev1[c];
521 
522  return 1;
523 }
524 
525 // objective function for reverse mode in edge elimination
526 // works up to 47 million vertices in IEEE arithmetic
527 inline double rme_obj (edge_bool_t eb, const c_graph_t& cg) {
528  c_graph_t::edge_t edge= eb.first;
529  // front is prefered -> add something if front because we maximize
530  int high, low, front;
531  if (eb.second) high= target (edge, cg), low= source (edge, cg), front= 1;
532  else high= source (edge, cg), low= target (edge, cg), front= 0;
533  return (2 * high + front) * double (cg.x()) + low;
534 }
535 
536 int reverse_mode_edge_t::operator() (const vector<edge_bool_t>& ev1,
537  const c_graph_t& cg,
538  vector<edge_bool_t>& ev2) {
539  ev2.resize (0);
540 
541  if (ev1.size() == 0) {set_empty_objective (); return 0; }
542  ev2.push_back (ev1[0]);
543 
544  for (size_t c= 1; c < ev1.size(); c++) {
545 // THROW_DEBUG_EXCEPT_MACRO ((rme_obj (ev1[c], cg) > rme_obj (ev2[0], cg)) != lex_greater (ev1[c], ev2[0], cg),
546 // consistency_exception, "objective function and comparator does not match");
547  if (lex_greater (ev1[c], ev2[0], cg)) ev2[0]= ev1[c]; }
548  set_objective (rme_obj (ev2[0], cg));
549  return 1;
550 }
551 
552 reverse_mode_edge_t reverse_mode_edge;
553 
554 // remark rm: if all eliminatable edges are considered than only front elimination is used
555 // this way one can force same sequences in vertex, edge and face elimination
556 // when reverse mode is used as sole criterion
557 
558 // -------------------------------------------------------------------------
559 // Lowest Markowitz
560 // -------------------------------------------------------------------------
561 
562 int lowest_markowitz_edge_f (const vector<c_graph_t::edge_t>& ev1,
563  bool front,
564  const c_graph_t& cg,
565  vector<c_graph_t::edge_t>& ev2) {
566  ev2.resize (0);
567 
568  if (ev1.size() == 0) return 0;
569  int min_degree= front ? out_degree (target (ev1[0], cg), cg)
570  : in_degree (source (ev1[0], cg), cg);
571  ev2.push_back (ev1[0]);
572 
573  for (size_t c= 1; c < ev1.size(); c++) {
574  c_graph_t::edge_t e= ev1[c];
575  int degree= front ? out_degree (target (e, cg), cg)
576  : in_degree (source (e, cg), cg);
577  if (degree < min_degree) ev2.resize (0);
578  if (degree <= min_degree) {
579  ev2.push_back (e); min_degree= degree;}
580  }
581  return ev2.size();
582 }
583 
584 // operator that computes the Markowitz degree for a single edge elimination
585 struct lme_op_t {
586  int operator() (edge_bool_t eb, const c_graph_t& cg) {
587  return eb.second ? out_degree (target (eb.first, cg), cg)
588  : in_degree (source (eb.first, cg), cg); }
589 };
590 
591 int lowest_markowitz_edge_t::operator() (const vector<edge_bool_t>& ev1,
592  const c_graph_t& cg,
593  vector<edge_bool_t>& ev2) {
594  lme_op_t lme_op;
595  return standard_heuristic_op (ev1, cg, ev2, lme_op, *this);
596 }
597 
598 lowest_markowitz_edge_t lowest_markowitz_edge;
599 
600 // -------------------------------------------------------------------------
601 // Lowest relative Markowitz
602 // -------------------------------------------------------------------------
603 
604 int lowest_relative_markowitz_edge_f (const vector<c_graph_t::edge_t>& ev1,
605  bool front,
606  const c_graph_t& cg,
607  vector<c_graph_t::edge_t>& ev2) {
608  ev2.resize (0);
609  if (ev1.size() == 0) return 0;
610  lrm_op_t lrm_op (cg);
611  int min_degree= lrm_op (front, ev1[0], cg);
612  ev2.push_back (ev1[0]);
613 
614  for (size_t c= 1; c < ev1.size(); c++) {
615  int degree= lrm_op (front, ev1[c], cg);
616  if (degree < min_degree) ev2.resize (0);
617  if (degree <= min_degree) {
618  ev2.push_back (ev1[c]); min_degree= degree;} }
619  return ev2.size();
620 }
621 
622 int lowest_relative_markowitz_edge_t::operator() (const vector<edge_bool_t>& ev1,
623  const c_graph_t& cg,
624  vector<edge_bool_t>& ev2) {
625  lrm_op_t lrm_op (cg);
626  return standard_heuristic_op (ev1, cg, ev2, lrm_op, *this);
627 }
628 
629 lowest_relative_markowitz_edge_t lowest_relative_markowitz_edge;
630 
631 // -------------------------------------------------------------------------
632 // Lowest fill-in
633 // -------------------------------------------------------------------------
634 
635 inline int fill_in_front (c_graph_t::edge_t e, const c_graph_t& cg) {
636  return new_out_edges (e, cg);
637 }
638 
639 inline int fill_in_back (c_graph_t::edge_t e, const c_graph_t& cg) {
640  return new_in_edges (e, cg);
641 }
642 
643 
644 int lowest_fill_in_edge_f (const vector<c_graph_t::edge_t>& ev1,
645  bool front,
646  const c_graph_t& cg,
647  vector<c_graph_t::edge_t>& ev2) {
648  ev2.resize (0);
649 
650  if (ev1.size() == 0) return 0;
651  int min_degree= front ? fill_in_front (ev1[0], cg)
652  : fill_in_back (ev1[0], cg);
653  ev2.push_back (ev1[0]);
654 
655  for (size_t c= 1; c < ev1.size(); c++) {
656  c_graph_t::edge_t e= ev1[c];
657  int degree= front ? fill_in_front (e, cg)
658  : fill_in_back (e, cg);
659  if (degree < min_degree) ev2.resize (0);
660  if (degree <= min_degree) {
661  ev2.push_back (e); min_degree= degree;}
662  }
663 
664  return ev2.size();
665 }
666 
667 
668 // -------------------------------------------------------------------------
669 // LMMD
670 // -------------------------------------------------------------------------
671 
672 lmmd_edge_t lmmd_edge (1.0);
673 
674 inline int lmmd_edge_front (c_graph_t::edge_t e, double w, const c_graph_t& cg) {
675  int markowitz= out_degree (target (e, cg), cg);
676  markowitz_enlargement_front_t me (e);
677  int damage= markowitz_enlargement_front (e, cg)
678  + sum_over_all_out_edges (target (e, cg), cg, me);
679  return int (double (markowitz) + w * double (damage));
680 }
681 
682 inline int lmmd_edge_back (c_graph_t::edge_t e, double w, const c_graph_t& cg) {
683  int markowitz= in_degree (source (e, cg), cg);
684  markowitz_enlargement_back_t me (e);
685  int damage= markowitz_enlargement_back (e, cg)
686  + sum_over_all_in_edges (source (e, cg), cg, me);
687  return int (double (markowitz) + w * double (damage));
688 }
689 
690 struct lmmde_op_t {
691  double w; // weight
692  lmmde_op_t (double _w) : w (_w) {}
693  int operator() (edge_bool_t eb, const c_graph_t& cg) {
694  return eb.second ? lmmd_edge_front (eb.first, w, cg)
695  : lmmd_edge_back (eb.first, w, cg); }
696 };
697 
698 int lmmd_edge_t::operator() (const vector<edge_bool_t>& ev1,
699  const c_graph_t& cg,
700  vector<edge_bool_t>& ev2) {
701  lmmde_op_t lmmde_op (weight);
702  return standard_heuristic_op (ev1, cg, ev2, lmmde_op, *this);
703 }
704 
705 
706 // -------------------------------------------------------------------------
707 // MOMR
708 // -------------------------------------------------------------------------
709 
710 inline int momr_edge_front (c_graph_t::edge_t e, const c_graph_t& cg) {
711 
712  markowitz_enlargement_front_t me (e);
713  int momr= out_degree (target (e, cg), cg) - markowitz_enlargement_front (e, cg)
714  - sum_over_all_out_edges (target (e, cg), cg, me);
715 
716 #ifndef NDEBUG
717  c_graph_t gtmp (cg);
718 
719  // eliminating e in gtmp does not work -> edge_descriptor from gtmp needed
720  c_graph_t::edge_t etmp;
721  c_graph_t::ei_t ei, e_end;
722  c_graph_t::vertex_t s= source (e, cg), t= target (e, cg);
723  for (boost::tie (ei, e_end)= edges (gtmp); ei != e_end; ++ei)
724  if (source (*ei, gtmp) == s && target (*ei, gtmp) == t) {
725  etmp= *ei; break; }
726  // assert (ei != e_end); // otherwise edge not found
727  THROW_DEBUG_EXCEPT_MACRO (ei == e_end, consistency_exception, "No matching edge found");
728 
729  front_edge_elimination (etmp, gtmp);
730  // assert (overall_markowitz_degree (cg) - overall_markowitz_degree (gtmp) == momr);
731  THROW_DEBUG_EXCEPT_MACRO (overall_markowitz_degree (cg) - overall_markowitz_degree (gtmp) != momr,
732  consistency_exception, "momr not correct");
733 #endif
734  return momr;
735 }
736 
737 inline int momr_edge_back (c_graph_t::edge_t e, const c_graph_t& cg) {
738  // reduction of markowitz degree in vertex source (e)
739  int momr= in_degree (source (e, cg), cg);
740  // target (e) can get a larger markowitz degree due to new in_edges
741  momr-= markowitz_enlargement_back (e, cg);
742 
743  // the predecessors of source (e) can get a larger markowitz degree
744  // due to a new out_edge to target (e)
745  c_graph_t::iei_t iei, ie_end;
746  tie (iei, ie_end)= in_edges (source (e, cg), cg);
747  for (; iei != ie_end; ++iei)
748  momr-= markowitz_enlargement_back (e, *iei, cg);
749 #ifndef NDEBUG
750  markowitz_enlargement_back_t me (e);
751  int momr2= in_degree (source (e, cg), cg) - markowitz_enlargement_back (e, cg)
752  - sum_over_all_in_edges (source (e, cg), cg, me);
753  // assert (momr == momr2);
754  THROW_DEBUG_EXCEPT_MACRO (momr2 != momr, consistency_exception, "momr not correct");
755 
756  c_graph_t gtmp (cg);
757  c_graph_t::vi_t vi, v_end;
758  int old_overall_markowitz= 0, new_overall_markowitz= 0;
759  for (boost::tie (vi, v_end)= vertices (gtmp); vi != v_end; ++vi)
760  old_overall_markowitz+= in_degree (*vi, gtmp) * out_degree (*vi, gtmp);
761 
762  // eliminating e in gtmp does not work -> edge_descriptor from gtmp needed
763  c_graph_t::edge_t etmp;
764  c_graph_t::ei_t ei, e_end;
765  c_graph_t::vertex_t s= source (e, cg), t= target (e, cg);
766  for (boost::tie (ei, e_end)= edges (gtmp); ei != e_end; ++ei)
767  if (source (*ei, gtmp) == s && target (*ei, gtmp) == t) {
768  etmp= *ei; break; }
769  // assert (ei != e_end); // otherwise edge not found
770  THROW_DEBUG_EXCEPT_MACRO (ei == e_end, consistency_exception, "No matching edge found");
771 
772  back_edge_elimination (etmp, gtmp);
773  for (boost::tie (vi, v_end)= vertices (gtmp); vi != v_end; ++vi)
774  new_overall_markowitz+= in_degree (*vi, gtmp) * out_degree (*vi, gtmp);
775  // assert (old_overall_markowitz-new_overall_markowitz == momr);
776  THROW_DEBUG_EXCEPT_MACRO (old_overall_markowitz-new_overall_markowitz != momr,
777  consistency_exception, "momr not correct");
778 #endif
779  return momr;
780 }
781 
782 // operator for MOMR on edges
783 struct momre_op_t {
784  int operator() (bool front, c_graph_t::edge_t edge, const c_graph_t& cg) {
785  return front ? momr_edge_front (edge, cg) : momr_edge_back (edge, cg); }
786  int operator() (edge_bool_t eb, const c_graph_t& cg) {
787  return eb.second ? momr_edge_front (eb.first, cg) : momr_edge_back (eb.first, cg); }
788 };
789 
790 int momr_edge_f (const vector<c_graph_t::edge_t>& ev1,
791  bool front,
792  const c_graph_t& cg,
793  vector<c_graph_t::edge_t>& ev2) {
794  ev2.resize (0);
795  if (ev1.size() == 0) return 0;
796  momre_op_t momre_op;
797  int max_momr= momre_op (front, ev1[0], cg);
798  ev2.push_back (ev1[0]);
799 
800  for (size_t c= 1; c < ev1.size(); c++) {
801  int momr= momre_op (front, ev1[c], cg);
802  if (momr > max_momr) ev2.resize (0);
803  if (momr >= max_momr) {
804  ev2.push_back (ev1[c]); max_momr= momr;}
805  }
806  return ev2.size();
807 }
808 
809 int momr_edge_t::operator() (const vector<edge_bool_t>& ev1, const c_graph_t& cg,
810  vector<edge_bool_t>& ev2) {
811  momre_op_t momre_op;
812  return standard_heuristic_op (ev1, cg, ev2, momre_op, *this);
813 }
814 
815 momr_edge_t momr_edge;
816 
817 // -------------------------------------------------------------------------
818 // Minimal distance
819 // -------------------------------------------------------------------------
820 
821 // operator for minimal distances on faces
822 struct diste_op_t {
823  int operator() (edge_bool_t eb, const c_graph_t& cg) {
824  c_graph_t::vertex_t i= source (eb.first, cg), j= target (eb.first, cg), dist= 0;
825  vector<c_graph_t::vertex_t> nb;
826  if (eb.second) {
827  successor_set (j, cg, nb);
828  for (size_t c= 0; c < nb.size(); c++)
829  if (nb[c] - i > dist) dist= nb[c] - i;
830  } else {
831  predecessor_set (j, cg, nb);
832  for (size_t c= 0; c < nb.size(); c++)
833  if (j - nb[c] > dist) dist= j - nb[c]; }
834  THROW_DEBUG_EXCEPT_MACRO (dist <= 0, consistency_exception, "Wrong distance in edge elimination");
835  return dist; }
836 };
837 
838 int minimal_distance_edge_t::operator() (const vector<edge_bool_t>& ev1, const c_graph_t& cg,
839  vector<edge_bool_t>& ev2) {
840  return standard_heuristic_op (ev1, cg, ev2, diste_op_t(), *this);
841 }
842 
843 minimal_distance_edge_t minimal_distance_edge;
844 
845 // -------------------------------------------------------------------------
846 // Maximal overall path length reduction
847 // -------------------------------------------------------------------------
848 
849 int moplr_edge (const vector<c_graph_t::edge_t>& ev1,
850  bool front,
851  const c_graph_t& cg,
852  vector<c_graph_t::edge_t>& ev2) {
853  ev2.resize (0);
854  if (ev1.size() == 0) return 0;
855 
856  vector<int> vni, vli, vno, vlo;
857  in_out_path_lengths (cg, vni, vli, vno, vlo);
858 
859  int max_oplr= front ? oplr_edge_front (ev1[0], vni, vli, vno, vlo, cg)
860  : oplr_edge_back (ev1[0], vni, vli, vno, vlo, cg);
861  ev2.push_back (ev1[0]);
862 
863  for (size_t c= 1; c < ev1.size(); c++) {
864  c_graph_t::edge_t e= ev1[c];
865  int oplr= front ? oplr_edge_front (e, vni, vli, vno, vlo, cg)
866  : oplr_edge_back (e, vni, vli, vno, vlo, cg);
867  if (oplr > max_oplr) ev2.resize (0);
868  if (oplr >= max_oplr) {
869  ev2.push_back (e); max_oplr= oplr;}
870  }
871 
872  return ev2.size();
873 }
874 
875 
876 
877 // =====================================================
878 // for face elimination
879 // =====================================================
880 
881 // objective function for forward and reverse mode in face elimination
882 // works up to 165 thousands vertices in IEEE arithmetic
883 inline double fmf_obj (line_graph_t::face_t f, const line_graph_t& lg) {
884  int i, j, k, x= lg.x();
885  face_vertex_name (f, lg, i, j, k);
886  return ((double (j) * double (x)) + double (i)) * double (x) + double (k);
887 }
888 
889 int forward_mode_face_t::operator() (const vector<line_graph_t::face_t>& fv1,
890  const line_graph_t& lg,
891  vector<line_graph_t::face_t>& fv2) {
892  fv2.resize (0);
893  if (fv1.size() == 0) {set_empty_objective (); return 0; }
894  fv2.push_back (fv1[0]);
895 
896  for (size_t c= 1; c < fv1.size(); c++) {
897 // THROW_DEBUG_EXCEPT_MACRO (fmf_obj (fv1[c], lg) < fmf_obj (fv2[0], lg) != lex_less_face (fv1[c], fv2[0], lg),
898 // consistency_exception, "objective function and comparator does not match");
899  if (lex_less_face (fv1[c], fv2[0], lg)) fv2[0]= fv1[c]; }
900  set_objective (fmf_obj (fv2[0], lg));
901  return 1;
902 }
903 
904 forward_mode_face_t forward_mode_face;
905 
906 // -------------------------------------------------------------------------
907 // reverse mode
908 // -------------------------------------------------------------------------
909 
910 int reverse_mode_face_t::operator() (const vector<line_graph_t::face_t>& fv1,
911  const line_graph_t& lg,
912  vector<line_graph_t::face_t>& fv2) {
913  fv2.resize (0);
914  if (fv1.size() == 0) {set_empty_objective (); return 0; }
915  fv2.push_back (fv1[0]);
916 
917  for (size_t c= 1; c < fv1.size(); c++) {
918 // THROW_DEBUG_EXCEPT_MACRO (fmf_obj (fv1[c], lg) < fmf_obj (fv2[0], lg) != lex_less_face (fv1[c], fv2[0], lg),
919 // consistency_exception, "objective function and comparator does not match");
920  if (!lex_less_face (fv1[c], fv2[0], lg)) fv2[0]= fv1[c]; }
921  set_objective (fmf_obj (fv2[0], lg));
922  return 1;
923 }
924 
925 reverse_mode_face_t reverse_mode_face;
926 
927 int reverse_mode_face_whole_vertex_t::operator() (const vector<line_graph_t::face_t>& fv1,
928  const line_graph_t& lg,
929  vector<line_graph_t::face_t>& fv2) {
930  fv2.resize (0);
931  if (fv1.size() == 0) return 0;
932  fv2.push_back (fv1[0]);
933  line_graph_t::const_evn_t evn= get(boost::vertex_name, lg);
934 
935  int maxv= evn[source(fv1[0], lg)].second;
936 
937  for (size_t c= 1; c < fv1.size(); c++) {
938  line_graph_t::face_t f= fv1[c];
939  int v= evn[source(f, lg)].second;
940  if (v > maxv) {fv2.resize (0); maxv= v;}
941  if (v == maxv) fv2.push_back (f); }
942 
943  return fv2.size();
944 }
945 
946 reverse_mode_face_whole_vertex_t reverse_mode_face_whole_vertex;
947 
948 // -------------------------------------------------------------------------
949 // subroutine of Lowest Markowitz on line graph
950 // -------------------------------------------------------------------------
951 
952 void markowitz_on_line_graph (const line_graph_t& lg,
953  vector<int>& mdegree) {
954 
955  line_graph_t::const_evn_t evn= get(vertex_name, lg);
956  int max_vertex_cg= 0;
957  line_graph_t::ei_t ei, e_end;
958  for (boost::tie (ei, e_end)= vertices (lg); ei != e_end; ++ei)
959  if (max_vertex_cg < evn[*ei].second) max_vertex_cg= evn[*ei].second;
960 
961  // number of faces in which vertex j occurs in the center
962  // filter out independent and dependent vertices (i,i,k) or (i,k,k)
963  mdegree.resize (0); mdegree.resize (max_vertex_cg+1);
964  line_graph_t::fi_t fi, f_end;
965  for (boost::tie (fi, f_end)= edges (lg); fi != f_end; ++fi) {
966  line_graph_t::edge_t s= source (*fi, lg), t= target (*fi, lg);
967  if (evn[s].first != evn[s].second && evn[t].first != evn[t].second)
968  mdegree[evn[s].second]++; }
969 }
970 
971 
972 
973 // -------------------------------------------------------------------------
974 // Lowest Markowitz
975 // -------------------------------------------------------------------------
976 
977 // operator for lowest Markowitz on faces
978 struct lmf_op_t {
979  vector<int> mdegree;
980  lmf_op_t (const line_graph_t& lg) {
981  markowitz_on_line_graph (lg, mdegree); }
982  int operator() (line_graph_t::face_t f, const line_graph_t& lg) {
983  int i, j, k; face_vertex_name (f, lg, i, j, k);
984  THROW_DEBUG_EXCEPT_MACRO (mdegree[j] == 0, consistency_exception, "Un-eliminatable face in fv1");
985  return mdegree[j]; }
986 };
987 
988 int lowest_markowitz_face_t::operator() (const vector<line_graph_t::face_t>& fv1,
989  const line_graph_t& lg,
990  vector<line_graph_t::face_t>& fv2) {
991  lmf_op_t lmf_op (lg);
992  return standard_heuristic_op (fv1, lg, fv2, lmf_op, *this);
993 }
994 
995 
996 // -------------------------------------------------------------------------
997 // MOMR
998 // -------------------------------------------------------------------------
999 
1000 // will a face (p,i,k) from (i,j)'s predecessor (p,i) to (i,k) be inserted ?
1001 // or does it already exist
1002 class new_pik_t {
1003  int i, k;
1004 public:
1005  new_pik_t (int _i, int _k) : i (_i), k (_k) {}
1006  int operator() (line_graph_t::face_t pij, const line_graph_t& lg) const {
1007  line_graph_t::edge_t pi= source (pij, lg);
1008  // for independent edges, new faces doesn't affect Mark. -> stop
1009  if (vertex_type (pi, lg) == independent) return 0;
1010  line_graph_t::ofi_t ofi, of_end;
1011  for (tie (ofi, of_end)= out_edges (pi, lg); ofi != of_end; ++ofi) {
1012  int v1, v2;
1013  edge_vertex_name (target (*ofi, lg), lg, v1, v2);
1014  // assert (v1 == i);
1015  THROW_DEBUG_EXCEPT_MACRO (v1 != i, consistency_exception, "Adjacency corrupted in line graph");
1016  if (v2 == k) return 0; } // (p,i,k) found
1017  return 1;
1018  }
1019 };
1020 
1021 struct source_not_independent_t {
1022  int operator() (line_graph_t::face_t f, const line_graph_t& lg) const {
1023  return (vertex_type (source (f, lg), lg) != independent); }
1024 };
1025 
1026 // will a face (i,k,s) to (j,k)'s successor (k,s) from (i,k) be inserted ?
1027 // or does it already exist
1028 class new_iks_t {
1029  int i, k;
1030 public:
1031  new_iks_t (int _i, int _k) : i (_i), k (_k) {}
1032  int operator() (line_graph_t::face_t jks, const line_graph_t& lg) const {
1033  line_graph_t::edge_t ks= target (jks, lg);
1034  // for dependent edges, new faces doesn't affect Mark. -> stop
1035  if (vertex_type (ks, lg) == dependent) return 0;
1036  line_graph_t::ifi_t ifi, if_end;
1037  for (tie (ifi, if_end)= in_edges (ks, lg); ifi != if_end; ++ifi) {
1038  int v1, v2;
1039  edge_vertex_name (source (*ifi, lg), lg, v1, v2);
1040  // assert (v2 == k);
1041  THROW_DEBUG_EXCEPT_MACRO (v2 != k, consistency_exception, "Adjacency corrupted in line graph");
1042  if (v1 == i) return 0; } // (i,k,s) found
1043  return 1;
1044  }
1045 };
1046 
1047 struct target_not_dependent_t {
1048  int operator() (line_graph_t::face_t f, const line_graph_t& lg) const {
1049  return (vertex_type (target (f, lg), lg) != dependent); }
1050 };
1051 
1052 // operator for MOMR on faces
1053 struct momrf_op_t {
1054  int operator() (line_graph_t::face_t f, const line_graph_t& lg) {
1055  int momr= 1; // the face itself
1056  int i, j, k; // f's vertices w.r.t. c-graph
1057  face_vertex_name (f, lg, i, j, k);
1058  line_graph_t::edge_t ij= source (f, lg), jk= target (f, lg);
1059 
1060  new_pik_t new_pik (i, k);
1061  momr-= sum_over_all_in_edges (ij, lg, new_pik);
1062  if (out_degree (ij, lg) == 1)
1063  momr+= sum_over_all_in_edges (ij, lg, source_not_independent_t());
1064 
1065  new_iks_t new_iks (i, k);
1066  momr-= sum_over_all_out_edges (jk, lg, new_iks);
1067  if (in_degree (jk, lg) == 1)
1068  momr+= sum_over_all_out_edges (jk, lg, target_not_dependent_t());
1069 #ifndef NDEBUG
1070  line_graph_t gtmp (lg);
1071 
1072  // eliminating f in gtmp does not work -> edge_descriptor from gtmp needed
1073  line_graph_t::face_t ftmp;
1074  ftmp= *same_edge (f, lg, gtmp);
1075  face_elimination (ftmp, gtmp);
1076 
1077  int old_overall_markowitz= overall_markowitz_degree (lg);
1078  int new_overall_markowitz= overall_markowitz_degree (gtmp);
1079  if (old_overall_markowitz - new_overall_markowitz != momr) {
1080  write_graph ("AD edge before elimination", lg);
1081  line_graph_t::const_evn_t evn= get(vertex_name, lg);
1082  write_vertex_property (cout, "vertices of this edge graph", evn, lg);
1083  cout << "overall_markowitz_degree is " << old_overall_markowitz << "\n";
1084  cout << "elimination of face: ";
1085  write_face_op_t wf (gtmp); wf (cout, ftmp);
1086  cout << endl;
1087  write_graph ("AD edge after elimination", gtmp);
1088  line_graph_t::evn_t evntmp= get(vertex_name, gtmp);
1089  write_vertex_property (cout, "vertices of this edge graph", evntmp, lg);
1090  cout << "overall_markowitz_degree is " << new_overall_markowitz
1091  << " momr is " << momr << "\n";
1092  line_graph_t gtmp2 (lg);
1093  ftmp= *same_edge (f, lg, gtmp2);
1094  face_elimination (ftmp, gtmp2);
1095  }
1096  // assert (overall_markowitz_degree (lg) - overall_markowitz_degree (gtmp) == momr);
1097  THROW_DEBUG_EXCEPT_MACRO (overall_markowitz_degree (lg) - overall_markowitz_degree (gtmp) != momr,
1098  consistency_exception, "momr not correct");
1099 #endif
1100  return momr; }
1101 };
1102 
1103 int momr_face_t::operator() (const vector<line_graph_t::face_t>& fv1,
1104  const line_graph_t& lg,
1105  vector<line_graph_t::face_t>& fv2) {
1106  momrf_op_t momrf_op;
1107  return standard_heuristic_op (fv1, lg, fv2, momrf_op, *this);
1108 }
1109 
1110 momr_face_t momr_face;
1111 
1112 // -------------------------------------------------------------------------
1113 // Minimal distance
1114 // -------------------------------------------------------------------------
1115 
1116 // operator for minimal distances on faces
1117 struct distf_op_t {
1118  int operator() (line_graph_t::face_t f, const line_graph_t& lg) {
1119  int i, j, k; face_vertex_name (f, lg, i, j, k);
1120  return k - i; }
1121 };
1122 
1123 int minimal_distance_face_t::operator() (const vector<line_graph_t::face_t>& fv1,
1124  const line_graph_t& lg, vector<line_graph_t::face_t>& fv2) {
1125  return standard_heuristic_op (fv1, lg, fv2, distf_op_t(), *this);
1126 }
1127 
1128 #ifdef USEXAIFBOOSTER
1129 
1130 // -------------------------------------------------------------------------
1131 // Scarcity preserving edge eliminations
1132 // -------------------------------------------------------------------------
1133 int edge_elim_effect (const edge_bool_t be,
1134  const c_graph_t& angelLCG,
1135  const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel) {
1136 
1137  boost::property_map<c_graph_t, EdgeType>::const_type eType = get(EdgeType(), angelLCG);
1138  c_graph_t::oei_t oei, oe_end;
1139  c_graph_t::iei_t iei, ie_end;
1140  c_graph_t::edge_t absorb_e;
1141  bool found_absorb;
1142 
1143  c_graph_t::edge_t e = be.first;
1144  bool isFront = be.second;
1145  int nontrivialEdgeChange = 0;
1146 
1147  // No awareness: removal of e decreases edge count
1148  if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS) nontrivialEdgeChange--;
1149  // unit awareness: e must be nonunit for its removal to decrease nontrivial edges
1150  else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[e] != UNIT_EDGE) nontrivialEdgeChange--;
1151  // constant awareness: e must be variable for its removal to decrease nontrivial edges
1152  else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[e] == VARIABLE_EDGE) nontrivialEdgeChange--;
1153 
1154  if (isFront) { // front-elimination
1155  // if tgt(e) is isolated by the elimination
1156  if (in_degree (target (e, angelLCG), angelLCG) == 1) {
1157  for (tie (oei, oe_end) = out_edges (target (e, angelLCG), angelLCG); oei != oe_end; ++oei) {
1158  // all the outedges of tgt(e) will go away. we need to see how this affects nontrivial edge count
1159  if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS) nontrivialEdgeChange--;
1160  else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[*oei] != UNIT_EDGE) nontrivialEdgeChange--;
1161  else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[*oei] == VARIABLE_EDGE) nontrivialEdgeChange--;
1162  } // end all outedges of tgt(e)
1163  }
1164 
1165  // determine effect of absorption/fill-in
1166  for (tie (oei, oe_end) = out_edges (target (e, angelLCG), angelLCG); oei != oe_end; ++oei) {
1167  tie (absorb_e, found_absorb) = edge (source (e, angelLCG), target (*oei, angelLCG), angelLCG);
1168  if (found_absorb) { // absorption
1169  //no awareness: no increase in edge count
1170  //unit awareness: absorb_e will be nonunit afterwards. increase only if absorb_e was previously unit
1171  if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[absorb_e] == UNIT_EDGE) nontrivialEdgeChange++;
1172  // constant awareness: increase if absorb edge is nonvariable and either e or *oei is variable
1173  else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[absorb_e] != VARIABLE_EDGE)
1174  if (eType[e] == VARIABLE_EDGE || eType[*oei] == VARIABLE_EDGE) nontrivialEdgeChange++;
1175  }
1176  else { // fill-in
1177  if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS) nontrivialEdgeChange++;
1178  // unit awareness: if either is nonunit, the fill-in is nonunit
1179  else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && (eType[e] != UNIT_EDGE || eType[*oei] != UNIT_EDGE)) nontrivialEdgeChange++;
1180  // constant awareness: if either is variable, the fill-in is variable
1181  else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && (eType[e] == VARIABLE_EDGE || eType[*oei] == VARIABLE_EDGE)) nontrivialEdgeChange++;
1182  }
1183  } // end all successors of tgt(e)
1184 
1185  } // end front-elimination
1186  else { // back-elimination
1187 
1188  // consider in-edges lost due to isolating src(e) (requires src(e) is not dependent)
1189  if (out_degree (source (e, angelLCG), angelLCG) == 1 && vertex_type (source (e, angelLCG), angelLCG) != dependent) {
1190  for (tie (iei, ie_end) = in_edges (source (e, angelLCG), angelLCG); iei != ie_end; ++iei) {
1191  if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS) nontrivialEdgeChange--;
1192  else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[*iei] != UNIT_EDGE) nontrivialEdgeChange--;
1193  else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[*iei] == VARIABLE_EDGE) nontrivialEdgeChange--;
1194  } // end all inedges of src(e)
1195  }
1196 
1197  // determine effect of absorption/fill-in
1198  for (tie (iei, ie_end) = in_edges (source (e, angelLCG), angelLCG); iei != ie_end; ++iei) {
1199  tie (absorb_e, found_absorb) = edge (source (*iei, angelLCG), target (e, angelLCG), angelLCG);
1200  if (found_absorb) { // absorption
1201  //no awareness: no increase in edge count
1202  //unit awareness: absorb_e will be nonunit afterwards. increase only if absorb_e was previously unit
1203  if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[absorb_e] == UNIT_EDGE) nontrivialEdgeChange++;
1204  // constant awareness: increase if absorb edge is nonvariable and either e or *oei is variable
1205  else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[absorb_e] != VARIABLE_EDGE)
1206  if (eType[e] == VARIABLE_EDGE || eType[*iei] == VARIABLE_EDGE) nontrivialEdgeChange++;
1207  }
1208  else { // fill-in
1209  if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS) nontrivialEdgeChange++;
1210  // unit awareness: if either is nonunit, the fill-in is nonunit
1211  else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && (eType[e] != UNIT_EDGE || eType[*iei] != UNIT_EDGE)) nontrivialEdgeChange++;
1212  // constant awareness: if either is variable, the fill-in is variable
1213  else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && (eType[e] == VARIABLE_EDGE || eType[*iei] == VARIABLE_EDGE)) nontrivialEdgeChange++;
1214  }
1215  } // end all predecessors of src(e)
1216  } // end back-elimination
1217 
1218  return nontrivialEdgeChange;
1219 }
1220 
1221 int edge_elim_effect(const EdgeElim ee,
1222  const c_graph_t& angelLCG,
1223  const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel) {
1224  return edge_elim_effect(make_pair(ee.getE(angelLCG), ee.isFront()), angelLCG, ourAwarenessLevel);
1225 } // end edge_elim_effect()
1226 
1227 bool maintaining_edge_eliminations(const vector<EdgeElim>& bev1,
1228  const c_graph_t& angelLCG,
1229  const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel,
1230  vector<EdgeElim>& bev2) {
1231  bev2.clear();
1232  if (bev1.empty()) return 0;
1233 
1234  for (size_t c = 0; c < bev1.size(); c++)
1235  if (edge_elim_effect (bev1[c], angelLCG, ourAwarenessLevel) <= 0)
1236  bev2.push_back (bev1[c]);
1237 
1238 #ifndef NDEBUG
1239  cout << " Of " << bev1.size() << " edge eliminations passed to maintaining_edge_eliminations(), " << bev2.size() << " maintain the nontrivial edge count" << endl;
1240 #endif
1241 
1242  if (bev2.empty()) {
1243  bev2 = bev1;
1244  return false;
1245  }
1246  else return true;
1247 } // end count_maintain_edge_eliminations()
1248 
1249 bool reducing_edge_eliminations(const vector<EdgeElim>& bev1,
1250  const c_graph_t& angelLCG,
1251  const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel,
1252  vector<EdgeElim>& bev2) {
1253  bev2.clear();
1254  if (bev1.empty()) return 0;
1255 
1256  for (size_t c = 0; c < bev1.size(); c++)
1257  if (edge_elim_effect (bev1[c], angelLCG, ourAwarenessLevel) < 0)
1258  bev2.push_back (bev1[c]);
1259 
1260  #ifndef NDEBUG
1261  cout << " Of " << bev1.size() << " edge eliminations passed to reducing_edge_eliminations()"
1262  << ", " << bev2.size() << " reduce the nontrivial edge count" << endl;
1263  #endif
1264 
1265  if(bev2.empty()) {
1266  bev2 = bev1;
1267  return false;
1268  }
1269  else return true;
1270 } // end count_maintain_edge_eliminations()
1271 
1272 bool refill_avoiding_edge_eliminations(const vector<EdgeElim>& bev1,
1273  c_graph_t& angelLCG,
1274  const refillDependenceMap_t refillDependences,
1275  vector<EdgeElim>& bev2) {
1276  bev2.clear();
1277  if (bev1.empty())
1278  return 0;
1279 
1280  c_graph_t::iei_t iei, ie_end;
1281  c_graph_t::oei_t oei, oe_end;
1282  refillDependenceMap_t::const_iterator depMap_i;
1283  vertex_set_t::const_iterator vDepSet_i;
1284  property_map<pure_c_graph_t, VertexVisited>::type visited = get(VertexVisited(), angelLCG);
1285  c_graph_t::vi_t cleari, clear_end;
1286 
1287  for (size_t c = 0; c < bev1.size(); c++) {
1288  c_graph_t::edge_t e = bev1[c].getE(angelLCG); // the direction of elimination (front/back) doesn't matter
1289 
1290  depMap_i = refillDependences.find(make_pair(source (e, angelLCG), target(e, angelLCG)));
1291  if (depMap_i != refillDependences.end()) { // we have refill dependences to consider for e
1292 #ifndef NDEBUG
1293  cout << "edge " << e << " has some refill dependences. Checking them..." << endl;
1294 #endif
1295  vertex_set_t vDepSet = depMap_i->second; // extract the vertex dependence set for e
1296 
1297  // check all vertices that this edge depends on
1298  // the dependence vertex can't be both below tgt(e) and above src(e)
1299  for (vDepSet_i = vDepSet.begin(); vDepSet_i != vDepSet.end(); vDepSet_i++) {
1300  // clear visited property for all vertices
1301  for (tie(cleari, clear_end) = vertices(angelLCG); cleari != clear_end; ++cleari) visited[*cleari] = false;
1302  if (reachable (source (e, angelLCG), *vDepSet_i, angelLCG)) {
1303  // clear visited property for all vertices (again)
1304  for (tie(cleari, clear_end) = vertices(angelLCG); cleari != clear_end; ++cleari) visited[*cleari] = false;
1305  if (reachable (*vDepSet_i, target (e, angelLCG), angelLCG)) {
1306 #ifndef NDEBUG
1307  cout << "edge " << e << " has an unmet refill dependence on vertex " << *vDepSet_i << endl;
1308 #endif
1309  break;
1310  } // end if vertex dependency is not met
1311  }
1312  } // end all vertex dependences
1313 
1314  // all vertex dependences for this edge have been met
1315  if (vDepSet_i == vDepSet.end())
1316  bev2.push_back(bev1[c]);
1317  } // end if vertex dependences exist
1318  else bev2.push_back(bev1[c]);
1319 
1320  } // end iterate over bev1
1321 
1322 #ifndef NDEBUG
1323  cout << " Of " << bev1.size() << " edge eliminations passed to refill_avoiding_edge_eliminations(), " << bev2.size() << " don't violate refill dependences" << endl;
1324 #endif
1325 
1326  if (bev2.empty()) {
1327  bev2 = bev1;
1328  return false;
1329  }
1330  else return true;
1331 } // end refill_avoiding_edge_eliminations()
1332 
1333 bool rerouting_considerate_edge_eliminations(const vector<EdgeElim>& bev,
1334  const c_graph_t& angelLCG,
1335  const std::vector<Transformation>& transformationsPerformedV,
1336  vector<EdgeElim>& reroutingConsiderateEdgeElimsV) {
1337  reroutingConsiderateEdgeElimsV.clear();
1338  if (bev.empty())
1339  return false;
1340 
1341  // Check every for every possible edge elimination
1342  for (size_t i = 0; i < bev.size(); i++) {
1343  size_t j;
1344 
1345  if (bev[i].isFront()) { // front-elimination
1346  // check all previously performed reroutings to see if the edge elim undoes it
1347  for (j = 0; j < transformationsPerformedV.size(); j++) {
1348  if (transformationsPerformedV[j].isRerouting()
1349  && transformationsPerformedV[j].getRerouting().isPre()
1350  && source(transformationsPerformedV[j].getRerouting().getE(angelLCG), angelLCG) == bev[i].getSource()
1351  && source(transformationsPerformedV[j].getRerouting().getPivotE(angelLCG), angelLCG) == bev[i].getTarget())
1352  break;
1353  }
1354  } // end front-elimination
1355 
1356  else { // back-elimination
1357  for (j = 0; j < transformationsPerformedV.size(); j++) {
1358  if (transformationsPerformedV[j].isRerouting()
1359  && !transformationsPerformedV[j].getRerouting().isPre()
1360  && target(transformationsPerformedV[j].getRerouting().getE(angelLCG), angelLCG) == bev[i].getTarget()
1361  && target(transformationsPerformedV[j].getRerouting().getPivotE(angelLCG), angelLCG) == bev[i].getSource())
1362  break;
1363  } // end all transformations
1364  } // end back-elimination
1365 
1366  if (j == transformationsPerformedV.size())
1367  reroutingConsiderateEdgeElimsV.push_back(bev[i]);
1368  } // end iterate over bev
1369 
1370 #ifndef NDEBUG
1371  cout << " Of " << bev.size() << " edge eliminations passed to rerouting_considerate_edge_eliminations(), " << reroutingConsiderateEdgeElimsV.size() << " don't undo a rerouting" << endl;
1372 #endif
1373 
1374  if (reroutingConsiderateEdgeElimsV.empty()) {
1375  reroutingConsiderateEdgeElimsV = bev;
1376  return false;
1377  }
1378  else return true;
1379 } // end rerouting_considerate_edge_eliminations()
1380 
1381 unsigned int lowestMarkowitzEdgeElim(const vector<EdgeElim>& inEEV,
1382  const c_graph_t& angelLCG,
1383  vector<EdgeElim>& outEEV) {
1384  outEEV.clear();
1385  if (inEEV.empty())
1386  return 0;
1387 
1388  vector<edge_bool_t> inBEV, outBEV;
1389 
1390  for (size_t i = 0; i < inEEV.size(); i++)
1391  inBEV.push_back(inEEV[i].getBool(angelLCG));
1392 
1393  lowest_markowitz_edge(inBEV, angelLCG, outBEV);
1394 
1395  for (size_t i = 0; i < outBEV.size(); i++)
1396  outEEV.push_back(EdgeElim (outBEV[i], angelLCG));
1397 
1398  return outEEV.size();
1399 } // end lowestMarkowitzEdgeElim()
1400 
1401 bool reverseModeEdgeElim(const vector<EdgeElim>& inEEV,
1402  const c_graph_t& angelLCG,
1403  vector<EdgeElim>& outEEV) {
1404  outEEV.clear();
1405  if (inEEV.empty())
1406  return false;
1407 
1408  vector<edge_bool_t> inBEV, outBEV;
1409 
1410  for (size_t i = 0; i < inEEV.size(); i++)
1411  inBEV.push_back(inEEV[i].getBool(angelLCG));
1412 
1413  reverse_mode_edge(inBEV, angelLCG, outBEV);
1414 
1415  for (size_t i = 0; i < outBEV.size(); i++)
1416  outEEV.push_back(EdgeElim (outBEV[i], angelLCG));
1417 
1418  return true;
1419 } // end reverseModeEdgeElim()
1420 
1421 // ==============================================================================
1422 // | FILTERS FOR REROUTINGS |
1423 // ==============================================================================
1424 
1425 size_t noncyclicReroutings (const vector<Rerouting>& erv,
1426  const std::vector<Transformation>& transformationsPerformedV,
1427  const c_graph_t& angelLCG,
1428  vector<Rerouting>& noncyclicReroutingsV) {
1429  noncyclicReroutingsV.clear();
1430  if (erv.empty())
1431  return 0;
1432  size_t j;
1433  // check each rerouting in erv to see whether it has already been performed
1434  for (size_t i = 0; i < erv.size(); i++) {
1435  // go through the history
1436  for (j = 0; j < transformationsPerformedV.size(); j++)
1437  if (transformationsPerformedV[j].isRerouting()
1438  && transformationsPerformedV[j].getRerouting() == erv[i]);
1439  break;
1440  if (j == transformationsPerformedV.size()) // if it made it all the way through, the rerouting hasn't already been performed
1441  noncyclicReroutingsV.push_back(erv[i]);
1442  } // end iterate over erv
1443  return noncyclicReroutingsV.size();
1444 } // end noncyclicReroutings()
1445 
1446 /*
1447 bool maintaining_reroutings (const vector<edge_reroute_t>& erv,
1448  const c_graph_t& angelLCG,
1449  const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel,
1450  vector<edge_reroute_t>& maintainingReroutingsV) {
1451  maintainingReroutingsV.clear();
1452  if (erv.empty()) return 0;
1453 
1454  bool dummyBool;
1455 
1456  for (size_t i = 0; i < erv.size(); i++) {
1457  cout << "reroute_effect = " << reroute_effect(erv[i], angelLCG, ourAwarenessLevel, dummyBool) << endl;
1458  if (reroute_effect(erv[i], angelLCG, ourAwarenessLevel, dummyBool) <= 0)
1459  maintainingReroutingsV.push_back(erv[i]);
1460  }
1461  cout << "Of " << erv.size() << " reroutings passed to maintaining_reroutings(), " << maintainingReroutingsV.size() << " maintain the nontrivial edge count" << endl;
1462 
1463  if (maintainingReroutingsV.empty()) {
1464  maintainingReroutingsV = erv;
1465  return false;
1466  }
1467  else return true;
1468 } // end maintaining_reroutings()
1469 */
1470 
1471 /*
1472 bool reducing_reroutings (const vector<edge_reroute_t>& erv,
1473  const c_graph_t& angelLCG,
1474  const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel,
1475  vector<edge_reroute_t>& reducingReroutingsV) {
1476  reducingReroutingsV.clear();
1477  if (erv.empty()) return 0;
1478  size_t i;
1479 
1480  vector<edge_reroute_t> reducingReroutingstypes12V, reducingReroutingstype3V;
1481 
1482  if (edge_reducing_rerouteElims_types12 (erv, angelLCG, ourAwarenessLevel, false, reducingReroutingstypes12V))
1483  for (i = 0; i < reducingReroutingstypes12V.size(); i++)
1484  reducingReroutingsV.push_back(reducingReroutingstypes12V[i]);
1485 
1486  if (edge_reducing_rerouteElims_type3 (erv, angelLCG, ourAwarenessLevel, false, reducingReroutingstype3V))
1487  for (i = 0; i < reducingReroutingstype3V.size(); i++)
1488  reducingReroutingsV.push_back(reducingReroutingstype3V[i]);
1489 #ifndef NDEBUG
1490  cout << " Of " << erv.size() << " reroutings passed to reducing_reroutings(), " << reducingReroutingsV.size() << " reduce the nontrivial edge count when followed by elimination" << endl;
1491 #endif
1492  if (reducingReroutingsV.empty()) {
1493  //reducingReroutingsV = erv;
1494  return false;
1495  }
1496  else return true;
1497 } // end reducing_reroutings()
1498 */
1499 
1500 bool reducing_reroutings (const vector<Rerouting>& erv,
1501  const c_graph_t& angelLCG,
1502  const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel,
1503  vector<Rerouting>& reducingReroutingsV) {
1504  reducingReroutingsV.clear();
1505  if (erv.empty())
1506  return 0;
1507 
1508  boost::property_map<c_graph_t, EdgeType>::const_type eType = get(EdgeType(), angelLCG);
1509  c_graph_t::iei_t iei, ie_end;
1510  c_graph_t::oei_t oei, oe_end;
1511  c_graph_t::edge_t absorb_e, increment_absorb_e, decrement_absorb_e;
1512  bool found_absorb_e;
1513 
1514  for (size_t i = 0; i < erv.size(); i++) {
1515  edge_reroute_t er = erv[i].getER(angelLCG);
1516  // first record effect of the rerouting itself
1517  bool incrementIsTrivial;
1518  int nontrivialEdgeChange_rerouting = reroute_effect (er, angelLCG, ourAwarenessLevel, incrementIsTrivial);
1519 
1520  c_graph_t::edge_t e = er.e;
1521  c_graph_t::edge_t pe = er.pivot_e;
1522  er.pivot_eliminatable = false;
1523  er.increment_eliminatable = false;
1524  er.type3EdgeElimVector.clear();
1525 
1526  int nontrivialEdgeChange_elimIncrement = 0;
1527  int nontrivialEdgeChange_elimPivot = 0;
1528 
1529  if (er.isPre) { // pre-routing
1530  //---------------------------------------------------------------------------------------------------------------------------
1531  // determine effect of back-eliminating the increment edge on the nontrivial edge count (nontrivialEdgeChange_elimIncrement)
1532  //---------------------------------------------------------------------------------------------------------------------------
1533 
1534  // cannot back-eliminate the increment edge if src(e) is an independent
1535  if (in_degree (source (e, angelLCG), angelLCG) > 0) {
1536  // determine effect of removing the increment edge
1537  if (!incrementIsTrivial) nontrivialEdgeChange_elimIncrement--;
1538 
1539  // examine effect of back-eliminating increment edge
1540  for (tie(iei, ie_end) = in_edges(source(e, angelLCG), angelLCG); iei != ie_end; ++iei) {
1541  tie(absorb_e, found_absorb_e) = edge(source(*iei, angelLCG), source(pe, angelLCG), angelLCG);
1542  if (found_absorb_e) { // absorption: count when the absorb_e goes from trivial to nontrivial
1543  if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[absorb_e] == UNIT_EDGE) nontrivialEdgeChange_elimIncrement++;
1544  else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[absorb_e] != VARIABLE_EDGE)
1545  if (eType[*iei] == VARIABLE_EDGE || !incrementIsTrivial) nontrivialEdgeChange_elimIncrement++;
1546  } // end absorption
1547  else { // fill-in: is the fill-in trivial or not?
1548  if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS) nontrivialEdgeChange_elimIncrement++;
1549  else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && (eType[*iei] != UNIT_EDGE || !incrementIsTrivial)) nontrivialEdgeChange_elimIncrement++;
1550  else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && (eType[*iei] == VARIABLE_EDGE || !incrementIsTrivial)) nontrivialEdgeChange_elimIncrement++;
1551  } // end fill-in
1552  } // end all preds of src(e)
1553  if (nontrivialEdgeChange_rerouting + nontrivialEdgeChange_elimIncrement < 0) er.increment_eliminatable = true;
1554  } // end if increment edge can be back-eliminated
1555 
1556  //------------------------------------------------------------------------------------------------------------------------------------------------
1557  // determine effect of front-eliminating the pivot edge on the nontrivial edge count (nontrivialEdgeChange_elimPivot)
1558  //------------------------------------------------------------------------------------------------------------------------------------------------
1559 
1560  // front-elimination of pivot edge MUST isolate the target
1561  if (in_degree(target(pe, angelLCG), angelLCG) == 2 && vertex_type(target(pe, angelLCG), angelLCG) != dependent) {
1562 
1563  // determine effect of eliminating the pivot edge
1564  if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS) nontrivialEdgeChange_elimPivot--;
1565  else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[pe] != UNIT_EDGE) nontrivialEdgeChange_elimPivot--;
1566  else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[pe] == VARIABLE_EDGE) nontrivialEdgeChange_elimPivot--;
1567 
1568  // iterate over successors of tgt(pe); the fill/absorb edges will have the same source as the pivot edge
1569  for (tie (oei, oe_end) = out_edges(target(pe, angelLCG), angelLCG); oei != oe_end; ++oei) {
1570  // determine effect of removing *oei
1571  if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS) nontrivialEdgeChange_elimPivot--;
1572  else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[*oei] != UNIT_EDGE) nontrivialEdgeChange_elimPivot--;
1573  else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[*oei] == VARIABLE_EDGE) nontrivialEdgeChange_elimPivot--;
1574 
1575  tie (absorb_e, found_absorb_e) = edge (source(pe, angelLCG), target(*oei, angelLCG), angelLCG);
1576  if (found_absorb_e) { // absorption: we need to detect of it goes from trivial to nontrivial
1577  if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[absorb_e] == UNIT_EDGE) nontrivialEdgeChange_elimPivot++;
1578  else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[absorb_e] != VARIABLE_EDGE)
1579  if (eType[pe] == VARIABLE_EDGE || eType[*oei] == VARIABLE_EDGE) nontrivialEdgeChange_elimPivot++;
1580  } // end absorption case
1581  else { // fill-in
1582  if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS) nontrivialEdgeChange_elimPivot++;
1583  else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && (eType[pe] != UNIT_EDGE || eType[*oei] != UNIT_EDGE)) nontrivialEdgeChange_elimPivot++;
1584  else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && (eType[pe] == VARIABLE_EDGE || eType[*oei] == VARIABLE_EDGE)) nontrivialEdgeChange_elimPivot++;
1585  } // end fill-in case
1586 
1587  } // end all successors of tgt(e)=tgt(pe)
1588  if (nontrivialEdgeChange_rerouting + nontrivialEdgeChange_elimPivot < 0) er.pivot_eliminatable = true;
1589  } // end determine nontrivialEdgeChange_elimPivot
1590 
1591  //------------------------------------------------------------------------------------------------------------------------------------------------
1592  // determine effect of back-eliminating (type 3)
1593  //------------------------------------------------------------------------------------------------------------------------------------------------
1594 
1595  // iterate over outedges of tgt(e), consider back-elimination of *oei
1596  for (tie(oei, oe_end) = out_edges(target(e, angelLCG), angelLCG); oei != oe_end; ++oei) {
1597  int nontrivialEdgeChange_backElimination = 0;
1598 
1599  // consider loss of *oei
1600  if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS
1601  || (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[*oei] != UNIT_EDGE)
1602  || (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[*oei] == VARIABLE_EDGE)) nontrivialEdgeChange_backElimination--;
1603 
1604  // consider fill/absorb effect of back-eliminating *oei
1605  for (tie(iei, ie_end) = in_edges(target(e, angelLCG), angelLCG); iei != ie_end; ++iei) {
1606  if (*iei == e) continue; // skip the rerouted edge
1607  tie(absorb_e, found_absorb_e) = edge(source(*iei, angelLCG), target(*oei, angelLCG), angelLCG);
1608  if (found_absorb_e) { // absorption: only counts if it goes from trivial to nontrivial
1609  if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[absorb_e] == UNIT_EDGE) nontrivialEdgeChange_backElimination++;
1610  else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[absorb_e] != VARIABLE_EDGE)
1611  if (eType[*oei] == VARIABLE_EDGE || eType[*iei] == VARIABLE_EDGE) nontrivialEdgeChange_backElimination++;
1612  }
1613  else { // fill-in
1614  if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS) nontrivialEdgeChange_backElimination++;
1615  else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && (eType[*oei] != UNIT_EDGE || eType[*iei] != UNIT_EDGE)) nontrivialEdgeChange_backElimination++;
1616  else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && (eType[*oei] == VARIABLE_EDGE || eType[*iei] == VARIABLE_EDGE)) nontrivialEdgeChange_backElimination++;
1617  }
1618  } // end all inedges of tgt(e)
1619  if (nontrivialEdgeChange_rerouting + nontrivialEdgeChange_backElimination < 0) er.type3EdgeElimVector.push_back(target(*oei, angelLCG));
1620  } // end all outedges of tgt(e) (end type 3)
1621 
1622  } // end pre-routing
1623  else { // post-routing
1624 
1625  //------------------------------------------------------------------------------------------------------------------------------------------------
1626  // determine effect of front-eliminating the increment edge on the nontrivial edge count
1627  //------------------------------------------------------------------------------------------------------------------------------------------------
1628 
1629  // cannot front-eliminate the increment edge if tgt(e) is a dependent
1630  if (vertex_type(target(e, angelLCG), angelLCG) != dependent) {
1631  // determine effect of removing the increment edge
1632  if (!incrementIsTrivial) nontrivialEdgeChange_elimIncrement--;
1633 
1634  // examine effect of front-eliminating increment edge
1635  for (tie (oei, oe_end) = out_edges(target(e, angelLCG), angelLCG); oei != oe_end; ++oei) {
1636  tie (absorb_e, found_absorb_e) = edge(target(pe, angelLCG), target(*oei, angelLCG), angelLCG);
1637  if (found_absorb_e) { // absorption: count when the absorb_e goes from trivial to nontrivial
1638  if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[absorb_e] == UNIT_EDGE) nontrivialEdgeChange_elimIncrement++;
1639  else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[absorb_e] != VARIABLE_EDGE)
1640  if (eType[*oei] == VARIABLE_EDGE || !incrementIsTrivial) nontrivialEdgeChange_elimIncrement++;
1641  } // end absorption
1642  else { // fill-in: is the fill-in trivial or not?
1643  if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS) nontrivialEdgeChange_elimIncrement++;
1644  else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && (eType[*oei] != UNIT_EDGE || !incrementIsTrivial)) nontrivialEdgeChange_elimIncrement++;
1645  else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && (eType[*oei] == VARIABLE_EDGE || !incrementIsTrivial)) nontrivialEdgeChange_elimIncrement++;
1646  } // end fill-in
1647  } // end all preds of src(e)
1648  if (nontrivialEdgeChange_rerouting + nontrivialEdgeChange_elimIncrement < 0) er.increment_eliminatable = true;
1649  } // end if increment edge can be front-eliminated
1650 
1651  //------------------------------------------------------------------------------------------------------------------------------------------------
1652  // determine effect of back-eliminating the pivot edge on the nontrivial edge count
1653  //------------------------------------------------------------------------------------------------------------------------------------------------
1654 
1655  // front-elimination of pivot edge MUST isolate the target
1656  if (out_degree (source(pe, angelLCG), angelLCG) == 2 && in_degree (source(pe, angelLCG), angelLCG) > 0) {
1657 
1658  // determine effect of eliminating the pivot edge
1659  if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS) nontrivialEdgeChange_elimPivot--;
1660  else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[pe] != UNIT_EDGE) nontrivialEdgeChange_elimPivot--;
1661  else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[pe] == VARIABLE_EDGE) nontrivialEdgeChange_elimPivot--;
1662 
1663  // iterate over predecessors of src(pe)
1664  // the fill/absorb edges will have the same target as the pivot edge
1665  for (tie (iei, ie_end) = in_edges(source(pe, angelLCG), angelLCG); iei != ie_end; ++iei) {
1666  // determine effect of removing the outedge
1667  if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS) nontrivialEdgeChange_elimPivot--;
1668  else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[*iei] != UNIT_EDGE) nontrivialEdgeChange_elimPivot--;
1669  else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[*iei] == VARIABLE_EDGE) nontrivialEdgeChange_elimPivot--;
1670 
1671  tie (absorb_e, found_absorb_e) = edge (source(*iei, angelLCG), target(pe, angelLCG), angelLCG);
1672  if (found_absorb_e) { // absorption: we need to detect of it goes from trivial to nontrivial
1673  if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[absorb_e] == UNIT_EDGE) nontrivialEdgeChange_elimPivot++;
1674  else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[absorb_e] != VARIABLE_EDGE)
1675  if (eType[pe] == VARIABLE_EDGE || eType[*iei] == VARIABLE_EDGE) nontrivialEdgeChange_elimPivot++;
1676  } // end absorption case
1677  else { // fill-in
1678  if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS) nontrivialEdgeChange_elimPivot++;
1679  else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && (eType[pe] != UNIT_EDGE || eType[*iei] != UNIT_EDGE)) nontrivialEdgeChange_elimPivot++;
1680  else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && (eType[pe] == VARIABLE_EDGE || eType[*iei] == VARIABLE_EDGE)) nontrivialEdgeChange_elimPivot++;
1681  } // end fill-in case
1682 
1683  } // end all successors of tgt(e)=tgt(pe)
1684  if (nontrivialEdgeChange_rerouting + nontrivialEdgeChange_elimPivot < 0) er.pivot_eliminatable = true;
1685  } // end determine nontrivialEdgeChange_elimPivot
1686 
1687  //------------------------------------------------------------------------------------------------------------------------------------------------
1688  // determine effect of front-eliminating (type 3)
1689  //------------------------------------------------------------------------------------------------------------------------------------------------
1690 
1691  // iterate over inedges of src(e), consider front-elimination of *iei
1692  if (vertex_type(source(e, angelLCG), angelLCG) != dependent) {
1693  for (tie(iei, ie_end) = in_edges(source(e, angelLCG), angelLCG); iei != ie_end; ++iei) {
1694  int nontrivialEdgeChange_frontElimination = 0;
1695 
1696  // consider loss of *iei
1697  if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS
1698  || (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[*iei] != UNIT_EDGE)
1699  || (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[*iei] == VARIABLE_EDGE)) nontrivialEdgeChange_frontElimination--;
1700 
1701  // consider fill/absorb effect of front-eliminating *iei
1702  for (tie(oei, oe_end) = out_edges(source(e, angelLCG), angelLCG); oei != oe_end; ++oei) {
1703  if (*oei == e) continue; // skip the rerouted edge
1704  tie(absorb_e, found_absorb_e) = edge(source(*iei, angelLCG), target(*oei, angelLCG), angelLCG);
1705  if (found_absorb_e) { // absorption: only counts if it goes from trivial to nontrivial
1706  if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[absorb_e] == UNIT_EDGE) nontrivialEdgeChange_frontElimination++;
1707  else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[absorb_e] != VARIABLE_EDGE)
1708  if (eType[*oei] == VARIABLE_EDGE || eType[*iei] == VARIABLE_EDGE) nontrivialEdgeChange_frontElimination++;
1709  }
1710  else { // fill-in
1711  if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS) nontrivialEdgeChange_frontElimination++;
1712  else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && (eType[*oei] != UNIT_EDGE || eType[*iei] != UNIT_EDGE)) nontrivialEdgeChange_frontElimination++;
1713  else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && (eType[*oei] == VARIABLE_EDGE || eType[*iei] == VARIABLE_EDGE)) nontrivialEdgeChange_frontElimination++;
1714  } // end fill-in
1715  } // end all outedges of src(e)
1716  if (nontrivialEdgeChange_rerouting + nontrivialEdgeChange_frontElimination < 0) er.type3EdgeElimVector.push_back(source(*iei, angelLCG));
1717  } // end all inedges of src(e)
1718  } // end type 3
1719  } // end post-routing
1720 
1721  if (er.pivot_eliminatable || er.increment_eliminatable || !er.type3EdgeElimVector.empty())
1722  reducingReroutingsV.push_back(Rerouting (er, angelLCG));
1723 
1724  } // end iterate through erv
1725 
1726 #ifndef NDEBUG
1727  cout << " Of " << erv.size() << " reroutings passed to reducing_reroutings(), " << reducingReroutingsV.size() << " reduce the nontrivial edge count when followed by elimination" << endl;
1728 #endif
1729 
1730  return !reducingReroutingsV.empty();
1731 } // end reducing_reroutings()
1732 
1733 // ==============================================================================
1734 // | FILTERS FOR ELIMINATIONS AND REROUTINGS (TRANSFORMATIONS) |
1735 // ==============================================================================
1736 
1737 int transformation_effect(const Transformation t,
1738  const c_graph_t& angelLCG,
1739  const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel) {
1740  int effect;
1741  if (t.isRerouting()) {
1742  bool dummy_incrementIsTrivial;
1743  effect = reroute_effect(t.getRerouting().getER(angelLCG), angelLCG, ourAwarenessLevel, dummy_incrementIsTrivial);
1744  }
1745  else
1746  effect = edge_elim_effect(t.getEdgeElim(), angelLCG, ourAwarenessLevel);
1747  return effect;
1748 } // end transformation_effect()
1749 
1750 bool all_viable_transformations (c_graph_t& angelLCG,
1751  const std::vector<Transformation>& transformationsPerformedV,
1752  vector<Transformation>& allViableTransformationsV) {
1753  allViableTransformationsV.clear();
1754  // find all eliminatable edges
1755  vector<EdgeElim> allEdgeElimsV;
1756  eliminatable_edges(angelLCG, allEdgeElimsV);
1757  for (size_t i = 0; i < allEdgeElimsV.size(); i++)
1758  allViableTransformationsV.push_back(Transformation (allEdgeElimsV[i]));
1759  // find viable reroutings
1760  vector<Rerouting> allReroutingsV, noncyclicReroutingsV;
1761  reroutable_edges (angelLCG, allReroutingsV);
1762  noncyclicReroutings (allReroutingsV, transformationsPerformedV, angelLCG, noncyclicReroutingsV);
1763  for (size_t i = 0; i < noncyclicReroutingsV.size(); i++)
1764  allViableTransformationsV.push_back(Transformation (noncyclicReroutingsV[i]));
1765  #ifndef NDEBUG
1766  cout << "\tThere are " << allEdgeElimsV.size() << " viable Edge eliminations in G" << endl;
1767  cout << "\tOf " << allReroutingsV.size() << " possible reroutings, " << noncyclicReroutingsV.size() << " are noncyclic" << endl;
1768  cout << "\t\tThere are " << allViableTransformationsV.size() << " viable transformations in G" << endl;
1769  #endif
1770  return !allViableTransformationsV.empty();
1771 } // end all_viable_transformations()
1772 
1773 bool maintaining_transformations(const vector<Transformation>& tv,
1774  const c_graph_t& angelLCG,
1775  const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel,
1776  vector<Transformation>& maintainingTransformationsV) {
1777  maintainingTransformationsV.clear();
1778  if (tv.empty())
1779  return false;
1780 
1781  vector<Rerouting> tempReroutingsV;
1782  vector<EdgeElim> tempEdgeElimsV, tempMaintainingEdgeElimsV;
1783 
1784  // create temporary lists
1785  for (size_t i = 0; i < tv.size(); i++)
1786  tv[i].isRerouting() ? tempReroutingsV.push_back(tv[i].getRerouting())
1787  : tempEdgeElimsV.push_back(tv[i].getEdgeElim());
1788 
1789  // if there are edge elims, push them to the transformation vector
1790  if (maintaining_edge_eliminations(tempEdgeElimsV, angelLCG, ourAwarenessLevel, tempMaintainingEdgeElimsV))
1791  for (size_t i = 0; i < tempMaintainingEdgeElimsV.size(); i++)
1792  maintainingTransformationsV.push_back(Transformation (tempMaintainingEdgeElimsV[i]));
1793 
1794  // push all reroutings to the transformation vector
1795  for (size_t i = 0; i < tempReroutingsV.size(); i++)
1796  maintainingTransformationsV.push_back(Transformation (tempReroutingsV[i]));
1797 
1798  #ifndef NDEBUG
1799  cout << "Of " << tv.size() << " transformations passed to maintaining_transformations()"
1800  << ", " << maintainingTransformationsV.size() << " maintain the nontrivial edge count" << endl;
1801  #endif
1802 
1803  // if there are neither edge elims nor reroutings, return the transformation vector we were passed
1804  if (maintainingTransformationsV.empty()) {
1805  maintainingTransformationsV = tv;
1806  return false;
1807  }
1808  else return true;
1809 } // end count_maintaining_transformations()
1810 
1811 bool reducing_transformations(const vector<Transformation>& tv,
1812  const c_graph_t& angelLCG,
1813  const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel,
1814  vector<Transformation>& reducingTransformationsV) {
1815  reducingTransformationsV.clear();
1816  if (tv.empty())
1817  return 0;
1818 
1819  vector<Rerouting> tempReroutingsV, tempReducingReroutingsV;
1820  vector<EdgeElim> tempEdgeElimsV, tempReducingEdgeElimsV;
1821 
1822  // split tv into separate temporary lists
1823  for (size_t i = 0; i < tv.size(); i++)
1824  tv[i].isRerouting() ? tempReroutingsV.push_back(tv[i].getRerouting())
1825  : tempEdgeElimsV.push_back(tv[i].getEdgeElim());
1826 
1827  // if there are edge elims, push them to the transformation vector
1828  if (reducing_edge_eliminations(tempEdgeElimsV, angelLCG, ourAwarenessLevel, tempReducingEdgeElimsV))
1829  for (size_t i = 0; i < tempReducingEdgeElimsV.size(); i++)
1830  reducingTransformationsV.push_back(Transformation (tempReducingEdgeElimsV[i]));
1831 
1832  // if there are reroutings, push them to the transformation vector
1833  if (reducing_reroutings(tempReroutingsV, angelLCG, ourAwarenessLevel, tempReducingReroutingsV))
1834  for (size_t i = 0; i < tempReducingReroutingsV.size(); i++)
1835  reducingTransformationsV.push_back(Transformation (tempReducingReroutingsV[i]));
1836 
1837 #ifndef NDEBUG
1838  cout << "Of " << tv.size() << " transformations passed to reducing_transformations(), " << reducingTransformationsV.size() << " reduce the nontrivial edge count" << endl;
1839 #endif
1840 
1841  // if there are neither edge elims nor reroutings, return only the edge elims
1842  if (reducingTransformationsV.empty()) {
1843  for (size_t i = 0; i < tempEdgeElimsV.size(); i++) // push back all the edge elims
1844  reducingTransformationsV.push_back(Transformation (tempEdgeElimsV[i]));
1845  // if there are no edge elims that maintain or reduce, and no reroutings that reduce: push back all edge elims
1846  if (reducingTransformationsV.empty()) {
1847  vector<EdgeElim> allEdgeElimsV;
1848  eliminatable_edges(angelLCG, allEdgeElimsV);
1849  for (size_t j = 0; j < allEdgeElimsV.size(); j++)
1850  reducingTransformationsV.push_back(Transformation (allEdgeElimsV[j]));
1851  }
1852  return false;
1853  }
1854 /*
1855  // if there are neither edge elims nor reroutings, return the transformation vector we were passed
1856  if (reducingTransformationsV.empty()) {
1857  reducingTransformationsV = tv;
1858  return false;
1859  } */
1860  else return true;
1861 
1862 } // end count_reducing_transformations()
1863 
1864 bool refill_avoiding_transformations(const vector<Transformation>& tv,
1865  c_graph_t& angelLCG,
1866  const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel,
1867  const refillDependenceMap_t& refillDependences,
1868  vector<Transformation>& refillAvoidingTransformationsV) {
1869  refillAvoidingTransformationsV.clear();
1870  if (tv.empty())
1871  return false;
1872 
1873  vector<Rerouting> tempReroutingsV;
1874  vector<EdgeElim> tempEdgeElimsV, tempRefillAvoidingEdgeElimsV;
1875 
1876  // create temporary edge elim and rerouting vectors
1877  for (size_t i = 0; i < tv.size(); i++)
1878  tv[i].isRerouting() ? tempReroutingsV.push_back(tv[i].getRerouting())
1879  : tempEdgeElimsV.push_back(tv[i].getEdgeElim());
1880 
1881  // run edge elims through the refill filter
1882  if (refill_avoiding_edge_eliminations(tempEdgeElimsV, angelLCG, refillDependences, tempRefillAvoidingEdgeElimsV)) {
1883  // push refill avoiding edge elims to the transformation vector
1884  for (size_t i = 0; i < tempRefillAvoidingEdgeElimsV.size(); i++)
1885  refillAvoidingTransformationsV.push_back(Transformation (tempRefillAvoidingEdgeElimsV[i]));
1886  // push all reroutings to the transformation vector
1887  for (size_t i = 0; i < tempReroutingsV.size(); i++)
1888  refillAvoidingTransformationsV.push_back(Transformation (tempReroutingsV[i]));
1889  return true;
1890  } // end if refill avoiders were found
1891 
1892  else { // none of the edge elims avoid refill
1893  refillAvoidingTransformationsV = tv;
1894  return false;
1895  }
1896 } // end refill_avoiding_transformations()
1897 
1898 bool rerouting_considerate_transformations(const vector<Transformation>& tv,
1899  const c_graph_t& angelLCG,
1900  const std::vector<Transformation>& transformationsPerformedV,
1901  vector<Transformation>& reroutingConsiderateTransformationsV) {
1902  reroutingConsiderateTransformationsV.clear();
1903  if (tv.empty())
1904  return false;
1905 
1906  vector<Transformation> tempReroutingsV;
1907  vector<EdgeElim> tempEdgeElimsV, tempReroutingConsiderateEdgeElimsV;
1908 
1909  // create temporary edge elim and rerouting vectors
1910  for (size_t i = 0; i < tv.size(); i++)
1911  tv[i].isRerouting() ? tempReroutingsV.push_back(tv[i].getRerouting())
1912  : tempEdgeElimsV.push_back(tv[i].getEdgeElim());
1913 
1914  // pass all edge elims through the edge elim filter
1915  if (rerouting_considerate_edge_eliminations(tempEdgeElimsV, angelLCG, transformationsPerformedV, tempReroutingConsiderateEdgeElimsV)) {
1916  // add preferred edge elims to the transformations vector to be returned
1917  for (size_t i = 0; i < tempReroutingConsiderateEdgeElimsV.size(); i++)
1918  reroutingConsiderateTransformationsV.push_back(Transformation (tempReroutingConsiderateEdgeElimsV[i]));
1919  // push all reroutings to the transformation vector
1920  for (size_t i = 0; i < tempReroutingsV.size(); i++)
1921  reroutingConsiderateTransformationsV.push_back(Transformation (tempReroutingsV[i]));
1922  return true;
1923  } // end if rerouting considerate edge elims were found
1924 
1925  else { // none of the edge elims are rerouting considerate
1926  reroutingConsiderateTransformationsV = tv;
1927  return false;
1928  }
1929 } // end rerouting_considerate_transformations ()
1930 
1931 bool lowest_markowitz_transformations(const vector<Transformation>& tv,
1932  const c_graph_t& angelLCG,
1933  vector<Transformation>& lowestMarkowitzTransformationsV) {
1934  lowestMarkowitzTransformationsV.clear();
1935  if (tv.empty())
1936  return false;
1937  // create temporary edge elim vector
1938  vector<EdgeElim> tempEdgeElimsV, tempLowestMarkowitzEdgeElimsV;
1939  for (size_t i = 0; i < tv.size(); i++)
1940  if (!tv[i].isRerouting())
1941  tempEdgeElimsV.push_back(tv[i].getEdgeElim());
1942  // if no edge elims, return exactly what we got
1943  if (tempEdgeElimsV.empty()) {
1944  lowestMarkowitzTransformationsV = tv;
1945  return false;
1946  }
1947  lowestMarkowitzEdgeElim(tempEdgeElimsV, angelLCG, tempLowestMarkowitzEdgeElimsV);
1948  // add preferred edge elims to the transformations vector to be returned
1949  for (size_t i = 0; i < tempLowestMarkowitzEdgeElimsV.size(); i++)
1950  lowestMarkowitzTransformationsV.push_back(Transformation (tempLowestMarkowitzEdgeElimsV[i]));
1951  return true;
1952 } // end lowest_markowitz_transformations()
1953 
1954 bool reverse_mode_transformations(const vector<Transformation>& tv,
1955  const c_graph_t& angelLCG,
1956  vector<Transformation>& reverseModeTransformationsV) {
1957  reverseModeTransformationsV.clear();
1958  if (tv.empty())
1959  return false;
1960  // create temporary edge elim vector
1961  vector<EdgeElim> tempEdgeElimsV, tempReverseModeEdgeElimsV;
1962  for (size_t i = 0; i < tv.size(); i++)
1963  if (!tv[i].isRerouting())
1964  tempEdgeElimsV.push_back(tv[i].getEdgeElim());
1965  // if no edge elims, return exactly what we got
1966  if (tempEdgeElimsV.empty()) {
1967  reverseModeTransformationsV = tv;
1968  return false;
1969  }
1970  reverseModeEdgeElim(tempEdgeElimsV, angelLCG, tempReverseModeEdgeElimsV);
1971  // add preferred edge elims to the transformations vector to be returned
1972  for (size_t i = 0; i < tempReverseModeEdgeElimsV.size(); i++)
1973  reverseModeTransformationsV.push_back(Transformation (tempReverseModeEdgeElimsV[i]));
1974  return true;
1975 } // end reverse_mode_transformations()
1976 
1977 #endif // USEXAIFBOOSTER
1978 
1979 } // namespace angel
1980 
1981 // to do: some names are confusing, e.g. ev for a face vector