angel  mercurial changeset:
xaif_interface.cpp
Go to the documentation of this file.
00001 // $Id: xaif_interface.cpp,v 1.15 2008/02/28 14:57:33 gottschling Exp $
00002 /*
00003 #############################################################
00004 # This file is part of angel released under the BSD license #
00005 # The full COPYRIGHT notice can be found in the top         #
00006 # level directory of the angel distribution                 #
00007 #############################################################
00008 */
00009 
00010 #ifdef USEXAIFBOOSTER
00011 
00012 #include <set>
00013 #include <climits>
00014 
00015 #include "angel/include/xaif_interface.hpp"
00016 #include "angel/include/eliminations.hpp"
00017 #include "angel/include/heuristics.hpp"
00018 #include "angel/include/reroutings.hpp"
00019 #include "angel/include/angel_tools.hpp"
00020 
00021 #include "angel/include/angel_io.hpp"
00022 #include "angel/include/sa.hpp"
00023 
00024 namespace angel {
00025 
00026 using namespace std;
00027 using namespace boost;
00028 using namespace xaifBoosterCrossCountryInterface;
00029 
00030 inline size_t which_index (const LinearizedComputationalGraphVertex * const add,
00031                            const vector<const LinearizedComputationalGraphVertex*>& av) {
00032   for (size_t c= 0; c < av.size(); c++) if (add == av[c]) return c;
00033   return av.size(); }
00034 
00035 struct edge_address_t {
00036   ad_edge_t                                   e;
00037   const LinearizedComputationalGraphEdge*     address; 
00038   edge_address_t (int _i, int _j, const LinearizedComputationalGraphEdge* _address) :
00039     e (_i, _j), address (_address) {}
00040 };
00041 
00042 void read_graph_xaif_booster (const LinearizedComputationalGraph& xg, c_graph_t& cg,
00043                               vector<const LinearizedComputationalGraphVertex*>& av,
00044                               vector<edge_address_t>& ae) {
00045   typedef LinearizedComputationalGraph       xgraph_t;
00046   typedef LinearizedComputationalGraphVertex xvertex_t;
00047   typedef LinearizedComputationalGraphEdge   xedge_t;
00048   typedef c_graph_t::vertex_t                vertex_t;
00049 
00050   int nv= xg.numVertices ();
00051   c_graph_t gtmp (0, nv, 0); // all vertices as intermediate for now
00052 
00053   xgraph_t::ConstVertexIteratorPair vip (xg.vertices());
00054 
00055   // independents are first
00056   const xgraph_t::VertexPointerList&  indeps_list= xg.getIndependentList ();
00057   xgraph_t::VertexPointerList::const_iterator 
00058     bi= indeps_list.begin(), be= indeps_list.end();
00059   for (; bi != be; bi++) {
00060     av.push_back (*bi);
00061     // indeps.push_back (c);
00062   }
00063 
00064   // remaining are sorted topologically
00065   while ((int) av.size() < nv) {
00066     xgraph_t::ConstVertexIterator vi (vip.first), v_end (vip.second);
00067     for (; vi != v_end; ++vi) {
00068       if (which_index (&*vi, av) != av.size()) continue;
00069       xgraph_t::ConstInEdgeIteratorPair inedges (xg.getInEdgesOf (*vi));
00070       xgraph_t::ConstInEdgeIterator ie= inedges.first, iend= inedges.second;
00071       bool all_num= true; // all predecessors numbered
00072       for (; ie != iend; ++ie)
00073         if (which_index (&(xg.getSourceOf (*ie)), av) == av.size()) {
00074           all_num= false; break; }
00075       if (all_num) av.push_back (&*vi);
00076     } }
00077 
00078   // re-activated
00079   vector<vertex_t> indeps;
00080   for (bi= indeps_list.begin(); bi != be; bi++) indeps.push_back (which_index (*bi, av));
00081 
00082   // test whether indeps in the beginning
00083   for (size_t c= 0; c < indeps.size(); c++)
00084     // assert (indeps[c] < indeps.size());
00085     THROW_EXCEPT_MACRO (indeps[c] >= indeps.size(), consistency_exception,
00086                      "Independent not at the beginning");
00087     
00088   vector<vertex_t> deps;
00089   const xgraph_t::VertexPointerList&  deps_list= xg.getDependentList ();
00090   bi= deps_list.begin(), be= deps_list.end();
00091   for (; bi != be; bi++) deps.push_back (which_index (*bi, av)); 
00092 
00093   int edge_number= 0;
00094   boost::property_map<c_graph_t, EdgeType>::type eType = get(EdgeType(), cg);
00095   xgraph_t::ConstEdgeIteratorPair eip (xg.edges());
00096   for (xgraph_t::ConstEdgeIterator ei (eip.first), e_end (eip.second); ei != e_end; ++ei) {
00097     vertex_t source= which_index (& (xg.getSourceOf (*ei)), av),
00098              target= which_index (& (xg.getTargetOf (*ei)), av);
00099     pair<c_graph_t::edge_t, bool> new_edge = add_edge (source, target, edge_number++, cg);
00100     ae.push_back (edge_address_t(source, target, &*ei));
00101     if ((*ei).getEdgeLabelType() == LinearizedComputationalGraphEdge::UNIT_LABEL)
00102       eType[new_edge.first] = UNIT_EDGE;
00103     else if ((*ei).getEdgeLabelType() == LinearizedComputationalGraphEdge::CONSTANT_LABEL)
00104       eType[new_edge.first] = CONSTANT_EDGE;
00105     else
00106       eType[new_edge.first] = VARIABLE_EDGE;
00107   } // end for all LCG edges
00108 
00109   cg.X= int (indeps.size()); cg.dependents= deps;
00110 
00111 #ifndef NDEBUG
00112   write_graph ("read_graph_xaif_booster: resulting graph", cg);
00113 #endif
00114 
00115 }
00116 
00117 inline const LinearizedComputationalGraphEdge* 
00118 xaif_edge_pr (line_graph_t::edge_t e, const accu_graph_t& ag, const vector<edge_address_t>& ae) {
00119   line_graph_t::const_evn_t evn= get (vertex_name, ag.lg);
00120   ad_edge_t edge_name= evn[e];
00121   
00122   int first_try= e - ag.lg.x();
00123   if (edge_name == ae[first_try].e) return ae[first_try].address;
00124   for (size_t c= 0; c < ae.size(); c++)
00125     if (edge_name == ae[c].e) return ae[c].address;
00126   return 0;
00127 }
00128 
00129 void write_graph_xaif_booster (const accu_graph_t& ag,
00130                                const vector<const LinearizedComputationalGraphVertex*>& av,
00131                                const vector<edge_address_t>& ae,
00132                                JacobianAccumulationExpressionList& JAElist,
00133                                LinearizedComputationalGraph& remainderLCG,
00134                                VertexCorrelationList& v_cor_list,
00135                                EdgeCorrelationList& e_cor_list) {
00136   remainderLCG.clear();
00137   set<unsigned int> independent_indices, dependent_indices;
00138   // line_graph_t::const_evn_t evn= get (vertex_name, ag.lg);
00139 
00140   // make a preliminary pass to make remainder graph vertices
00141   for (size_t c = 0; c < ag.accu_exp.size(); c++) {
00142     ad_edge_t my_jacobi = ag.jacobi_entries[c];
00143     if (my_jacobi.second != 0) {
00144       // store indices of indep and dep vertices
00145       independent_indices.insert(my_jacobi.first);
00146       dependent_indices.insert(my_jacobi.second);
00147     }
00148   } // end preliminary pass
00149       
00150   // create and correlate remainder graph vertices from indep and dep sets
00151   for (set<unsigned int>::const_iterator sit = independent_indices.begin(); sit != independent_indices.end(); sit++) {
00152     LinearizedComputationalGraphVertex& new_remainder_vertex = remainderLCG.addVertex();
00153     VertexCorrelationEntry new_vertex_correlation;
00154     new_vertex_correlation.myOriginalVertex_p = av[*sit];
00155     new_vertex_correlation.myRemainderVertex_p = &new_remainder_vertex;
00156     v_cor_list.push_back(new_vertex_correlation);
00157   }
00158   for (set<unsigned int>::const_iterator sit = dependent_indices.begin(); sit != dependent_indices.end(); sit++) {
00159     LinearizedComputationalGraphVertex& new_remainder_vertex = remainderLCG.addVertex();
00160     VertexCorrelationEntry new_vertex_correlation;
00161     new_vertex_correlation.myOriginalVertex_p = av[*sit];
00162     new_vertex_correlation.myRemainderVertex_p = &new_remainder_vertex;
00163     v_cor_list.push_back(new_vertex_correlation);
00164   }
00165 
00166   // iterate over all angel JAEs
00167   vector<JacobianAccumulationExpressionVertex*> exp_output_pr; // pointer to output vertex of expression
00168   for (size_t c= 0; c < ag.accu_exp.size(); c++) {
00169     const accu_exp_graph_t& my_exp= ag.accu_exp[c];
00170     property_map<pure_accu_exp_graph_t, vertex_name_t>::const_type vpr= get (vertex_name, my_exp);
00171 
00172     JacobianAccumulationExpression& new_exp = JAElist.addExpression();
00173     //exp_pr.push_back(&new_exp);
00174     vector<JacobianAccumulationExpressionVertex*> vp (my_exp.v());
00175     for (size_t vc= 0; vc < (size_t) my_exp.v(); vc++) {      
00176       const accu_exp_t& prop= vpr[vc];
00177       JacobianAccumulationExpressionVertex& new_vertex = new_exp.addVertex();
00178       vp[vc]= &new_vertex;
00179 
00180       // the last vertex in the expression is the output vertex
00181       if (vc+1 == (size_t) my_exp.v()) exp_output_pr.push_back(&new_vertex);
00182 
00183       switch (prop.ref_kind) { 
00184       case accu_exp_t::nothing: THROW_EXCEPT_MACRO (true, consistency_exception, "Unset vertex"); break;
00185       case accu_exp_t::exp:
00186         THROW_DEBUG_EXCEPT_MACRO (prop.ref.exp_nr >= int (c), consistency_exception, "Expression number too large")
00187         new_vertex.setInternalReference (*exp_output_pr[prop.ref.exp_nr]); break;
00188       case accu_exp_t::lgn: {
00189         const LinearizedComputationalGraphEdge* ptr= xaif_edge_pr (prop.ref.node, ag, ae); 
00190         THROW_DEBUG_EXCEPT_MACRO (ptr == NULL, consistency_exception, "Unset reference");
00191         new_vertex.setExternalReference (*ptr); } break;
00192       case accu_exp_t::isop:    
00193         new_vertex.setOperation (prop.ref.op == accu_exp_t::add ? JacobianAccumulationExpressionVertex::ADD_OP
00194                                                                 : JacobianAccumulationExpressionVertex::MULT_OP);
00195       } // end switch on prop.ref_kind
00196     } // end all expression vertices
00197 
00198     // deal with JAE edges    
00199     graph_traits<pure_accu_exp_graph_t>::edge_iterator ei, e_end;
00200     for (tie (ei, e_end)= edges (my_exp); ei != e_end; ei++)
00201       new_exp.addEdge (*vp[source (*ei, my_exp)], *vp[target (*ei, my_exp)]);
00202 
00203     // deal with JAEs that are Jacobian entries
00204     ad_edge_t my_jacobi = ag.jacobi_entries[c];
00205     if (my_jacobi.second != 0) {
00206       //new_exp.setJacobianEntry (*av[my_jacobi.second], *av[my_jacobi.first]);
00207 
00208       // create edge in the remainder graph
00209       const LinearizedComputationalGraphVertex* original_src_p = av[my_jacobi.first];
00210       const LinearizedComputationalGraphVertex* original_tgt_p = av[my_jacobi.second];
00211       LinearizedComputationalGraphVertex* remainder_src_p = NULL;
00212       LinearizedComputationalGraphVertex* remainder_tgt_p = NULL;
00213       for (VertexCorrelationList::iterator vcori = v_cor_list.begin(); vcori != v_cor_list.end(); vcori++) {
00214         if (vcori->myOriginalVertex_p == original_src_p)        remainder_src_p = vcori->myRemainderVertex_p;
00215         else if (vcori->myOriginalVertex_p == original_tgt_p)   remainder_tgt_p = vcori->myRemainderVertex_p;
00216       } // end all vertex correlation entries
00217       THROW_EXCEPT_MACRO (remainder_src_p == NULL || remainder_tgt_p == NULL, consistency_exception, "Vertex in remainder graph could not be found");
00218       LinearizedComputationalGraphEdge& new_remainder_edge = remainderLCG.addEdge(*remainder_src_p, *remainder_tgt_p);
00219 
00220       // crate the correlation entry
00221       EdgeCorrelationEntry new_edge_correlation;
00222       new_edge_correlation.myRemainderGraphEdge_p = &new_remainder_edge;
00223       new_edge_correlation.myType = EdgeCorrelationEntry::JAE_VERT;
00224       new_edge_correlation.myEliminationReference.myJAEVertex_p = exp_output_pr.back();
00225       //new_edge_correlation.myEliminationReference.myJAEVertex_p = getJAE_p (*ei, angelLCG, edge_ref_list);
00226       e_cor_list.push_back(new_edge_correlation);
00227     } // end if Jacobian entry
00228 
00229   } // end all Jacobian accumulation expressions
00230 } // end write_graph_xaif_booster()
00231 
00232 unsigned int num_nontrivial_edges (const c_graph_t& angelLCG,
00233                                    const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel) {
00234   boost::property_map<c_graph_t, EdgeType>::const_type eType = get (EdgeType(), angelLCG);
00235   unsigned int numNontrivialEdges = 0;
00236   c_graph_t::ei_t ei, e_end;
00237   for (tie (ei, e_end)= edges (angelLCG); ei != e_end; ++ei)
00238     if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS
00239     || (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[*ei] != UNIT_EDGE)
00240     || (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[*ei] == VARIABLE_EDGE))
00241       numNontrivialEdges++;
00242 
00243   return numNontrivialEdges;
00244 } // end of num_nontrivial_edges()
00245 
00246 unsigned int numIntermediateVertices (const c_graph_t& angelLCG) {
00247   unsigned int numIntermediates = 0;
00248   c_graph_t::vi_t vi, v_end;
00249   for (tie (vi, v_end) = vertices (angelLCG); vi != v_end; ++vi)
00250     if (vertex_type (*vi, angelLCG) == intermediate) numIntermediates++;
00251   return numIntermediates;
00252 } // end numIntermediateVertices()
00253 
00254 unsigned int numIntermediateVerticesWithoutUnitEdge (const c_graph_t& angelLCG) {
00255   boost::property_map<c_graph_t, EdgeType>::const_type eType = get(EdgeType(), angelLCG);
00256   unsigned int numIntermediatesWithoutUnitEdge = 0;
00257   c_graph_t::vi_t vi, v_end;
00258   c_graph_t::iei_t iei, ie_end;
00259   c_graph_t::oei_t oei, oe_end;
00260 
00261   for (tie (vi, v_end) = vertices (angelLCG); vi != v_end; ++vi) {
00262     if (vertex_type (*vi, angelLCG) == intermediate) {
00263       for (tie(iei, ie_end) = in_edges (*vi, angelLCG); iei != ie_end; ++iei)
00264         if (eType[*iei] == UNIT_EDGE) break;
00265       for (tie(oei, oe_end) = out_edges (*vi, angelLCG); oei != oe_end; ++oei)
00266         if (eType[*oei] == UNIT_EDGE) break;
00267       if ( iei == ie_end && oei == oe_end) numIntermediatesWithoutUnitEdge++;
00268     }
00269   }
00270   return numIntermediatesWithoutUnitEdge;
00271 } // end numIntermediateVertices()
00272 
00273 void ourLCG_to_angelLCG (const LinearizedComputationalGraph& ourLCG,
00274                          vector<const LinearizedComputationalGraphVertex*>& ourLCG_verts,
00275                          c_graph_t& angelLCG,
00276                          list<EdgeRef_t>& edge_ref_list) {
00277   angelLCG.clear();
00278 
00279   // COPY VERTICES
00280   const LinearizedComputationalGraph::VertexPointerList& ourLCG_indeps = ourLCG.getIndependentList ();
00281   const LinearizedComputationalGraph::VertexPointerList& ourLCG_deps = ourLCG.getDependentList ();
00282   LinearizedComputationalGraph::VertexPointerList::const_iterator LCGvi;
00283 
00284   // Add pointers to independent vertices to vector ourLCG_verts
00285   for (LCGvi = ourLCG_indeps.begin(); LCGvi != ourLCG_indeps.end(); LCGvi++)
00286     ourLCG_verts.push_back (*LCGvi);
00287 
00288   // remaining are sorted topologically
00289   int nv = ourLCG.numVertices ();
00290   LinearizedComputationalGraph::ConstVertexIteratorPair vip (ourLCG.vertices());
00291   while ((int) ourLCG_verts.size() < nv) {
00292     for (LinearizedComputationalGraph::ConstVertexIterator topi (vip.first), top_end (vip.second); topi != top_end; ++topi) {
00293       if (which_index (&*topi, ourLCG_verts) != ourLCG_verts.size()) continue;
00294       bool all_num = true; // all predecessors numbered
00295       LinearizedComputationalGraph::ConstInEdgeIteratorPair inedges (ourLCG.getInEdgesOf (*topi));
00296       for (LinearizedComputationalGraph::ConstInEdgeIterator ie = inedges.first, iend = inedges.second; ie != iend; ++ie)
00297         if (which_index (&(ourLCG.getSourceOf (*ie)), ourLCG_verts) == ourLCG_verts.size()) {
00298           all_num = false;
00299           break;
00300         }
00301       if (all_num) ourLCG_verts.push_back (&*topi);
00302     } // end all vertices
00303   }
00304 
00305   // populate vectors of independent and dependent vertices
00306   vector<c_graph_t::vertex_t> indeps, deps;
00307   for (LCGvi = ourLCG_indeps.begin(); LCGvi != ourLCG_indeps.end(); LCGvi++)
00308     indeps.push_back (which_index (*LCGvi, ourLCG_verts));
00309   angelLCG.x(int (indeps.size()));
00310   for (LCGvi = ourLCG_deps.begin(); LCGvi != ourLCG_deps.end(); LCGvi++)
00311     deps.push_back (which_index (*LCGvi, ourLCG_verts)); 
00312   angelLCG.dependents = deps;
00313 
00314   // ensure that indeps occur in the beginning
00315   for (size_t c = 0; c < indeps.size(); c++)
00316     THROW_EXCEPT_MACRO (indeps[c] >= indeps.size(), consistency_exception, "Independent not at the beginning");
00317 
00318   // COPY EDGES ----------------------------------------------------------------
00319   int edge_number = 0;
00320   boost::property_map<c_graph_t, EdgeType>::type eType = get(EdgeType(), angelLCG);
00321   LinearizedComputationalGraph::ConstEdgeIteratorPair eip (ourLCG.edges());
00322   for (LinearizedComputationalGraph::ConstEdgeIterator ei (eip.first), e_end (eip.second); ei != e_end; ++ei) {
00323     // locate source and target of edge in angelLCG
00324     c_graph_t::vertex_t angelSource = which_index (& (ourLCG.getSourceOf (*ei)), ourLCG_verts);
00325     c_graph_t::vertex_t angelTarget = which_index (& (ourLCG.getTargetOf (*ei)), ourLCG_verts);
00326     pair<c_graph_t::edge_t, bool> new_edge = add_edge (angelSource, angelTarget, edge_number++, angelLCG);
00327     if ((*ei).getEdgeLabelType() == LinearizedComputationalGraphEdge::UNIT_LABEL)
00328       eType[new_edge.first] = UNIT_EDGE;
00329     else if ((*ei).getEdgeLabelType() == LinearizedComputationalGraphEdge::CONSTANT_LABEL)
00330       eType[new_edge.first] = CONSTANT_EDGE;
00331     else
00332       eType[new_edge.first] = VARIABLE_EDGE;
00333 
00334     EdgeRef_t new_edge_ref (new_edge.first, &*ei);
00335     edge_ref_list.push_back(new_edge_ref);
00336   } // end for all LCG edges
00337 
00338 #ifndef NDEBUG
00339   write_graph ("angelLCG (constructed from ourLCG): ", angelLCG);
00340 #endif
00341 
00342 } // end ourLCG_to_angelLCG()
00343 
00344 void populate_remainderGraph_and_correlationLists (const c_graph_t& angelLCG,
00345                                                    const vector<const LinearizedComputationalGraphVertex*> ourLCG_verts,
00346                                                    const list<EdgeRef_t>& edge_ref_list,
00347                                                    LinearizedComputationalGraph& remainderLCG,
00348                                                    VertexCorrelationList& v_cor_list,
00349                                                    EdgeCorrelationList& e_cor_list) {
00350   remainderLCG.clear();
00351 
00352   // copy and correlate vertices
00353   v_cor_list.resize(0);
00354   c_graph_t::vi_t vi, v_end;
00355   for (tie (vi, v_end) = vertices (angelLCG); vi != v_end; ++vi) {
00356     // since vertices aren't removed from angelLCG, only copy non-isolated vertices
00357     if (in_degree (*vi, angelLCG) != 0 || out_degree (*vi, angelLCG) != 0) {
00358       LinearizedComputationalGraphVertex& new_rvert (remainderLCG.addVertex());
00359       // add a new correlation entry to the list
00360       VertexCorrelationEntry new_rvert_cor;
00361       new_rvert_cor.myOriginalVertex_p = ourLCG_verts[*vi];
00362       new_rvert_cor.myRemainderVertex_p = &new_rvert;
00363       v_cor_list.push_back(new_rvert_cor);
00364     }
00365   } // end all vertices
00366 
00367   // copy and correlate edges
00368   boost::property_map<c_graph_t, EdgeType>::const_type eType = get(EdgeType(), angelLCG);
00369   e_cor_list.resize(0);
00370   c_graph_t::ei_t ei, e_end;
00371   for (tie(ei, e_end) = edges(angelLCG); ei != e_end; ++ei) {
00372     // Find source and target in remainder LCG
00373     const LinearizedComputationalGraphVertex* original_src_p = ourLCG_verts[source(*ei, angelLCG)];
00374     const LinearizedComputationalGraphVertex* original_tgt_p = ourLCG_verts[target(*ei, angelLCG)];
00375     LinearizedComputationalGraphVertex* remainder_src_p = NULL;
00376     LinearizedComputationalGraphVertex* remainder_tgt_p = NULL;
00377     for (VertexCorrelationList::iterator vcori = v_cor_list.begin(); vcori != v_cor_list.end(); vcori++) {
00378       if (vcori->myOriginalVertex_p == original_src_p) remainder_src_p = vcori->myRemainderVertex_p;
00379       else if (vcori->myOriginalVertex_p == original_tgt_p) remainder_tgt_p = vcori->myRemainderVertex_p;
00380     } // end all vertex correlation entries
00381     THROW_EXCEPT_MACRO (remainder_src_p == NULL || remainder_tgt_p == NULL, consistency_exception,
00382                                         "Vertex in remainder graph could not be correlated");
00383 
00384     // create the edge and its correlation entry
00385     LinearizedComputationalGraphEdge& new_redge = remainderLCG.addEdge(*remainder_src_p, *remainder_tgt_p);
00386     EdgeCorrelationEntry new_edge_correlation;
00387     new_edge_correlation.myRemainderGraphEdge_p = &new_redge;
00388 
00389     // set the edge type (unit/const/variable)
00390     switch (eType[*ei]) { 
00391     case UNIT_EDGE:
00392       new_redge.setEdgeLabelType(LinearizedComputationalGraphEdge::UNIT_LABEL);
00393       break;
00394     case CONSTANT_EDGE:
00395       new_redge.setEdgeLabelType(LinearizedComputationalGraphEdge::CONSTANT_LABEL);
00396       break;
00397     case VARIABLE_EDGE:
00398       new_redge.setEdgeLabelType(LinearizedComputationalGraphEdge::VARIABLE_LABEL);
00399       break;
00400     }
00401 
00402     // derive contents of correlation entry from the internal edge reference list
00403     EdgeRefType_E new_remainder_edge_ref_t = getRefType (*ei, angelLCG, edge_ref_list);
00404     if (new_remainder_edge_ref_t == LCG_EDGE) {
00405       new_edge_correlation.myEliminationReference.myOriginalEdge_p = getLCG_p (*ei, angelLCG, edge_ref_list);
00406       new_edge_correlation.myType = EdgeCorrelationEntry::LCG_EDGE;
00407     }
00408     else if (new_remainder_edge_ref_t == JAE_VERT) {
00409       new_edge_correlation.myEliminationReference.myJAEVertex_p = getJAE_p (*ei, angelLCG, edge_ref_list);
00410       new_edge_correlation.myType = EdgeCorrelationEntry::JAE_VERT;
00411     }
00412     else THROW_EXCEPT_MACRO (true, consistency_exception, "Edge reference type neither LCG_EDGE nor JAE_VERT");
00413 
00414     e_cor_list.push_back(new_edge_correlation);
00415   } // end all edges in angelLCG
00416 
00417 } // end populate_remainderGraph_and_correlationLists()
00418 
00419 unsigned int replay_transformation_seq(c_graph_t& angelLCG,
00420                                        const vector<Transformation> transformationSeqV,
00421                                        unsigned int& previous_numNontrivialEdges,
00422                                        const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel,
00423                                        transformationSeq_cost_t& dummy_transformationSeq_cost,
00424                                        refillDependenceMap_t& dummy_refillDependenceMap) {
00425   unsigned int computationalCost = 0;
00426   for (size_t i = 0; i < transformationSeqV.size(); i++) {
00427     if (i == transformationSeqV.size() - 1) // save previous_numNontrivialEdges
00428       previous_numNontrivialEdges = num_nontrivial_edges(angelLCG, ourAwarenessLevel);
00429     #ifndef NDEBUG
00430     cout << "\t";
00431     #endif
00432     // REROUTING
00433     if (transformationSeqV[i].isRerouting())
00434       computationalCost += transformationSeqV[i].getRerouting().isPre() ?
00435          prerouteEdge_noJAE(transformationSeqV[i].getRerouting().getER(angelLCG), angelLCG)
00436        : postrouteEdge_noJAE(transformationSeqV[i].getRerouting().getER(angelLCG), angelLCG);
00437     // EDGE ELIMINATION
00438     else
00439       computationalCost += transformationSeqV[i].getEdgeElim().isFront() ?
00440          frontEdgeElimination_noJAE(transformationSeqV[i].getEdgeElim().getE(angelLCG), angelLCG, &dummy_transformationSeq_cost, dummy_refillDependenceMap)
00441        : backEdgeElimination_noJAE(transformationSeqV[i].getEdgeElim().getE(angelLCG), angelLCG, &dummy_transformationSeq_cost, dummy_refillDependenceMap);
00442   } // end iterate over transformations
00443   return computationalCost;
00444 } // end replay_transformation_seq()
00445 
00446 bool isTrivialEdge(const c_graph_t::edge_t& e,
00447                    c_graph_t& theAngelLCG,
00448                    const xaifBoosterCrossCountryInterface::AwarenessLevel::AwarenessLevel_E ourAwarenessLevel) {
00449   boost::property_map<c_graph_t,EdgeType>::type eType = get(EdgeType(),theAngelLCG);
00450   if (ourAwarenessLevel == xaifBoosterCrossCountryInterface::AwarenessLevel::NO_AWARENESS)
00451     return false;
00452   else if (ourAwarenessLevel == xaifBoosterCrossCountryInterface::AwarenessLevel::UNIT_AWARENESS)
00453     return (eType[e] == UNIT_EDGE);
00454   else if (ourAwarenessLevel == xaifBoosterCrossCountryInterface::AwarenessLevel::CONSTANT_AWARENESS)
00455     return (eType[e] != VARIABLE_EDGE);
00456   else
00457     THROW_EXCEPT_MACRO(true, consistency_exception, "isTrivialEdge: unknown AwarenessLevel");
00458 } // end isTrivialEdge()
00459 
00460 void assessPairElim(const c_graph_t::edge_t& e1,
00461                     const c_graph_t::edge_t& e2,
00462                     c_graph_t& theAngelLCG,
00463                     const xaifBoosterCrossCountryInterface::AwarenessLevel::AwarenessLevel_E ourAwarenessLevel,
00464                     unsigned int& cost,
00465                     int& totalEdgecountChange,
00466                     int& nontrivialEdgecountChange) {
00467   boost::property_map<c_graph_t,EdgeType>::type eType = get(EdgeType(),theAngelLCG);
00468   // determine cost
00469   cost = (eType[e1] == UNIT_EDGE || eType[e2] == UNIT_EDGE) ? 0 : 1;
00470 
00471   // determine whether absorption edge is present
00472   c_graph_t::edge_t absorb_e;
00473   bool found_absorb_e;
00474   tie(absorb_e,found_absorb_e) = edge(source(e1,theAngelLCG),
00475                                       target(e2,theAngelLCG),
00476                                       theAngelLCG);
00477   // determine change in total edge count
00478   totalEdgecountChange = (found_absorb_e) ? 0 : 1;
00479 
00480   // determine change in nontrivial edge count
00481   if (found_absorb_e) { // absorption: nontrivial edge count goes up iff absorb edge goes trivial => nontrivial
00482     if (ourAwarenessLevel == xaifBoosterCrossCountryInterface::AwarenessLevel::NO_AWARENESS)
00483       nontrivialEdgecountChange = 0;
00484     else if (ourAwarenessLevel == xaifBoosterCrossCountryInterface::AwarenessLevel::CONSTANT_AWARENESS) {
00485       if (eType[absorb_e] == VARIABLE_EDGE)
00486         nontrivialEdgecountChange = 0; // absorb edge is already nontrivial (variable)
00487       else
00488         nontrivialEdgecountChange = (eType[e1] == VARIABLE_EDGE || eType[e2] == VARIABLE_EDGE) ? 1 : 0;
00489     } // end CONSTANT_AWARENESS
00490     else if (ourAwarenessLevel == xaifBoosterCrossCountryInterface::AwarenessLevel::UNIT_AWARENESS) {
00491       if (eType[absorb_e] != UNIT_EDGE)
00492         nontrivialEdgecountChange = 0; // absorb edge is already nontrivial (nonunit)
00493       else
00494         nontrivialEdgecountChange = (eType[e1] != UNIT_EDGE || eType[e2] != UNIT_EDGE) ? 1 : 0;
00495     } // end UNIT_AWARENESS
00496     else
00497       THROW_EXCEPT_MACRO(true, consistency_exception, "isTrivialEdge: unknown AwarenessLevel");
00498   } // end absorption
00499 
00500   else { // fill-in: nontrivial edge count change iff the fill edge is nontrivial
00501     if (ourAwarenessLevel == xaifBoosterCrossCountryInterface::AwarenessLevel::NO_AWARENESS)
00502       nontrivialEdgecountChange = 1;
00503     else if (ourAwarenessLevel == xaifBoosterCrossCountryInterface::AwarenessLevel::CONSTANT_AWARENESS)
00504       // nontrivial edge count goes up iff e1 or e2 is variable
00505       nontrivialEdgecountChange = (eType[e1] == VARIABLE_EDGE || eType[e2] == VARIABLE_EDGE) ? 1 : 0;
00506     else if (ourAwarenessLevel == xaifBoosterCrossCountryInterface::AwarenessLevel::UNIT_AWARENESS)
00507       // nontrivial edge count goes up iff e1 or e2 is nonunit 
00508       nontrivialEdgecountChange = (eType[e1] != UNIT_EDGE || eType[e2] != UNIT_EDGE) ? 1 : 0;
00509     else
00510       THROW_EXCEPT_MACRO(true, consistency_exception, "assessPairElim: unknown AwarenessLevel");
00511   } // end fill-in
00512 } // end assessPairElim()
00513 
00514 void assessFrontEdgeElim(const c_graph_t::edge_t& e,
00515                          c_graph_t& theAngelLCG,
00516                          const xaifBoosterCrossCountryInterface::AwarenessLevel::AwarenessLevel_E ourAwarenessLevel,
00517                          unsigned int& cost,
00518                          int& totalEdgecountChange,
00519                          int& nontrivialEdgecountChange) {
00520   boost::property_map<c_graph_t,EdgeType>::type eType = get(EdgeType(),theAngelLCG);
00521   bool isIsolated = (in_degree(target(e,theAngelLCG),theAngelLCG) == 1
00522                   && vertex_type(target(e,theAngelLCG),theAngelLCG) != dependent);
00523   c_graph_t::oei_t oei, oe_end;
00524   for (tie(oei,oe_end) = out_edges(target(e,theAngelLCG),theAngelLCG); oei != oe_end; ++oei) {
00525     unsigned int pairCost;
00526     int pairTotalEdgecountChange, pairNontrivialEdgecountChange;
00527     assessPairElim(e,
00528                    *oei,
00529                    theAngelLCG,
00530                    ourAwarenessLevel,
00531                    pairCost,
00532                    pairTotalEdgecountChange,
00533                    pairNontrivialEdgecountChange);
00534     cost += pairCost;
00535     totalEdgecountChange += pairTotalEdgecountChange;
00536     nontrivialEdgecountChange += pairNontrivialEdgecountChange;
00537     // determine effect of isolation
00538     if (isIsolated) {
00539       totalEdgecountChange -= 1;
00540       if (!isTrivialEdge(*oei,theAngelLCG,ourAwarenessLevel))
00541         nontrivialEdgecountChange -= 1;
00542     } // end if isIsolated
00543   } // end for all outedges of the target
00544 } // end assessFrontEdgeElim()
00545 
00546 void assessBackEdgeElim(const c_graph_t::edge_t& e,
00547                         c_graph_t& theAngelLCG,
00548                         const xaifBoosterCrossCountryInterface::AwarenessLevel::AwarenessLevel_E ourAwarenessLevel,
00549                         unsigned int& cost,
00550                         int& totalEdgecountChange,
00551                         int& nontrivialEdgecountChange) {
00552   boost::property_map<c_graph_t,EdgeType>::type eType = get(EdgeType(),theAngelLCG);
00553   bool isIsolated = (out_degree(source(e,theAngelLCG),theAngelLCG) == 1
00554                   && vertex_type(source(e,theAngelLCG),theAngelLCG) != dependent);
00555   c_graph_t::iei_t iei, ie_end;
00556   for (tie(iei,ie_end) = in_edges(source(e,theAngelLCG),theAngelLCG); iei != ie_end; ++iei) {
00557     unsigned int pairCost;
00558     int pairTotalEdgecountChange, pairNontrivialEdgecountChange;
00559     assessPairElim(*iei,
00560                    e,
00561                    theAngelLCG,
00562                    ourAwarenessLevel,
00563                    pairCost,
00564                    pairTotalEdgecountChange,
00565                    pairNontrivialEdgecountChange);
00566     cost += pairCost;
00567     totalEdgecountChange += pairTotalEdgecountChange;
00568     nontrivialEdgecountChange += pairNontrivialEdgecountChange;
00569     // determine effect of isolation
00570     if (isIsolated) {
00571       totalEdgecountChange -= 1;
00572       if (!isTrivialEdge(*iei,theAngelLCG,ourAwarenessLevel))
00573         nontrivialEdgecountChange -= 1;
00574     } // end if isIsolated
00575   } // end for all inedges of the source
00576 } // end assessBackEdgeElim()
00577 
00578 void assessEdgeElim(const EdgeElim& anEdgeElim,
00579                     c_graph_t& theAngelLCG,
00580                     const xaifBoosterCrossCountryInterface::AwarenessLevel::AwarenessLevel_E ourAwarenessLevel,
00581                     unsigned int& cost,
00582                     int& totalEdgecountChange,
00583                     int& nontrivialEdgecountChange) {
00584   cost = 0;
00585   // determine the effect of removing e
00586   totalEdgecountChange = -1;
00587   nontrivialEdgecountChange = isTrivialEdge(anEdgeElim.getE(theAngelLCG),theAngelLCG,ourAwarenessLevel) ? 0 : -1;
00588   if (anEdgeElim.isFront())
00589     assessFrontEdgeElim(anEdgeElim.getE(theAngelLCG),
00590                         theAngelLCG,
00591                         ourAwarenessLevel,
00592                         cost,
00593                         totalEdgecountChange,
00594                         nontrivialEdgecountChange);
00595   else
00596     assessBackEdgeElim(anEdgeElim.getE(theAngelLCG),
00597                        theAngelLCG,
00598                        ourAwarenessLevel,
00599                        cost,
00600                        totalEdgecountChange,
00601                        nontrivialEdgecountChange);
00602 } // end assessEdgeElim()
00603                              
00604 void postProcessRemainderGraph(c_graph_t& theAngelLCG,
00605                                xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionList& theJAEList,
00606                                std::list<EdgeRef_t>& edge_ref_list,
00607                                const xaifBoosterCrossCountryInterface::AwarenessLevel::AwarenessLevel_E ourAwarenessLevel) {
00608   vector<EdgeElim> allEdgeElimsV;
00609   bool done = false;
00610   while (!done) {
00611     done = true;
00612     eliminatable_edges(theAngelLCG,allEdgeElimsV);
00613     if (allEdgeElimsV.empty()) break; // no more eliminatable edges
00614     for (size_t c = 0; c < allEdgeElimsV.size(); c++) {
00615       unsigned int cost;
00616       int totalEdgecountChange, nontrivialEdgecountChange;
00617       assessEdgeElim(allEdgeElimsV[c],
00618                      theAngelLCG,
00619                      ourAwarenessLevel,
00620                      cost,
00621                      totalEdgecountChange,
00622                      nontrivialEdgecountChange);
00623 //    THROW_EXCEPT_MACRO(nontrivialEdgecountChange < 0,consistency_exception,"postProcessRemainderGraph: found reduction in nontrivial edge count in remainder graph produced by scarcity heuristic");
00624       // we require the following
00625       // (1) no computational cost
00626       // (2) some reduction in total edge count
00627       // (3) no change in nontrivial edge count (\todo in the future we will allow decreases, though they shouldn't occur at this point)
00628       if (cost == 0
00629        && totalEdgecountChange < 0
00630        && nontrivialEdgecountChange == 0) {
00631         #ifndef NDEBUG
00632         std::cout << "+++++++++++++++++ GREEDY REDUCTION FOUND: cost=" << cost
00633                                                           << ", totalEdgecountChange=" << totalEdgecountChange
00634                                                           << ", nontrivialEdgecountChange=" << nontrivialEdgecountChange << "+++++++++++++++++++++++" << std::endl;
00635         #endif
00636         unsigned int actualCost = allEdgeElimsV[c].isFront()
00637                ?  front_eliminate_edge_directly(allEdgeElimsV[c].getE(theAngelLCG),
00638                                                 theAngelLCG,
00639                                                 edge_ref_list,
00640                                                 theJAEList)
00641                : back_eliminate_edge_directly(allEdgeElimsV[c].getE(theAngelLCG),
00642                                               theAngelLCG,
00643                                               edge_ref_list,
00644                                               theJAEList);
00645         THROW_EXCEPT_MACRO(cost != actualCost,consistency_exception,"postProcessRemainderGraph: discrepancy in cost between assessEdgeElim and eliminate_edge_directly");
00646                           
00647         allEdgeElimsV.clear();
00648         done = false;
00649         break;
00650       }
00651     } // end for all edge elims
00652   } // end while
00653 } // end postProcessRemainderGraph()
00654 
00655 } // end namespace angel
00656 
00657 
00658 
00659 using namespace angel;
00660 
00661 namespace xaifBoosterCrossCountryInterface {
00662 void compute_partial_elimination_sequence_random(const LinearizedComputationalGraph& ourLCG,
00663                                                  const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel,
00664                                                  const bool allowMaintainingFlag,
00665                                                  JacobianAccumulationExpressionList& jae_list,
00666                                                  LinearizedComputationalGraph& remainderLCG,
00667                                                  VertexCorrelationList& v_cor_list,
00668                                                  EdgeCorrelationList& e_cor_list) {
00669   srand(time(NULL));
00670   // Create internal (angel) LCG from xaifBooster LCG
00671   vector<const LinearizedComputationalGraphVertex*> ourLCG_verts;
00672   c_graph_t angelLCG;
00673   list<EdgeRef_t> edge_ref_list;
00674   ourLCG_to_angelLCG (ourLCG, ourLCG_verts, angelLCG, edge_ref_list);
00675 
00676   unsigned int max_steps = 50 * num_vertices(angelLCG);
00677   unsigned int num_passes = 5;
00678 
00679   c_graph_t angelLCG_copy (angelLCG);
00680   elimSeq_cost_t dummy_elimSeq_cost (0, 0, 0, 0, 0, 0);
00681   transformationSeq_cost_t dummy_tSeqCost (0, 0, 0, 0, 0, 0);
00682   refillDependenceMap_t dummy_refillDependenceMap;
00683   vector<EdgeElim> allEdgeElimsV;
00684   vector<Transformation> edgeElimSeqV, best_edgeElimSeqV;
00685   unsigned int previous_numNontrivialEdges = num_nontrivial_edges(angelLCG_copy, ourAwarenessLevel);
00686   unsigned int bestNumNontrivialEdges = num_nontrivial_edges(angelLCG_copy, ourAwarenessLevel);
00687   unsigned int computationalCost_at_bestEdgeCount = 0;
00688   unsigned int computationalCost = 0;
00689   #ifndef NDEBUG
00690   cout << "datapoint:" << computationalCost << ":" << num_nontrivial_edges(angelLCG_copy, ourAwarenessLevel) << endl;
00691   #endif
00692   for (unsigned int steps_counter = 0; steps_counter < max_steps; steps_counter++) {
00693     // Start over from the beginning
00694     if (steps_counter%(max_steps/num_passes) == 0) {
00695       #ifndef NDEBUG
00696       cout << "Starting a new SA pass (" << steps_counter << "/" << max_steps << " steps):\tbestNumNontrivialEdges = " << bestNumNontrivialEdges << ", computationalCost_at_bestEdgeCount = " << computationalCost_at_bestEdgeCount << endl;
00697       #endif
00698       edgeElimSeqV.clear();
00699       computationalCost = 0;
00700       previous_numNontrivialEdges = num_nontrivial_edges(angelLCG, ourAwarenessLevel);
00701       angelLCG_copy = angelLCG;
00702       continue;
00703     }
00704 
00705     eliminatable_edges(angelLCG_copy, allEdgeElimsV);
00706     if (allEdgeElimsV.empty()) break; // no more eliminatable edges
00707 
00708     // calculate relative probabilities for each possible edge elim
00709     vector<double> deltaE(allEdgeElimsV.size() + 1);
00710     for (size_t c = 0; c < allEdgeElimsV.size(); c++)
00711       deltaE[c] = edge_elim_effect (allEdgeElimsV[c], angelLCG_copy, ourAwarenessLevel);
00712     deltaE[allEdgeElimsV.size()] = (int)previous_numNontrivialEdges - (int)num_nontrivial_edges(angelLCG_copy, ourAwarenessLevel);
00713 
00714     unsigned int choice_index = chooseTarget_sa(deltaE);
00715     if (choice_index != allEdgeElimsV.size()) { // eliminate an edge
00716       previous_numNontrivialEdges = num_nontrivial_edges(angelLCG_copy, ourAwarenessLevel);
00717       computationalCost += allEdgeElimsV[choice_index].isFront() ?
00718          front_elim(allEdgeElimsV[choice_index].getE(angelLCG_copy), angelLCG_copy, dummy_elimSeq_cost, dummy_refillDependenceMap)
00719        : back_elim(allEdgeElimsV[choice_index].getE(angelLCG_copy), angelLCG_copy, dummy_elimSeq_cost, dummy_refillDependenceMap);
00720       edgeElimSeqV.push_back(Transformation (allEdgeElimsV[choice_index]));
00721       // check whether we've beaten our CURRENT best
00722       if (num_nontrivial_edges (angelLCG_copy, ourAwarenessLevel) < bestNumNontrivialEdges
00723        || (num_nontrivial_edges (angelLCG_copy, ourAwarenessLevel) == bestNumNontrivialEdges && computationalCost < computationalCost_at_bestEdgeCount)) {
00724         bestNumNontrivialEdges = num_nontrivial_edges (angelLCG_copy, ourAwarenessLevel);
00725         computationalCost_at_bestEdgeCount = computationalCost;
00726         best_edgeElimSeqV = edgeElimSeqV;
00727         #ifndef NDEBUG
00728         cout << "** New bestNumNontrivialEdges: " << bestNumNontrivialEdges << " with computational cost " << computationalCost << " after " << edgeElimSeqV.size() << " eliminations" << endl;
00729         #endif
00730       }
00731     }
00732     else { // this corresponds to a backtracking (going back cannot lead to a new "best-so-far" result)
00733       #ifndef NDEBUG
00734       cout << "Performing a BACKTRACKING step" << endl;
00735       #endif
00736       if (edgeElimSeqV.empty())
00737         continue;
00738       angelLCG_copy = angelLCG;
00739       edgeElimSeqV.pop_back();
00740       computationalCost = replay_transformation_seq(angelLCG_copy, edgeElimSeqV, previous_numNontrivialEdges, ourAwarenessLevel, dummy_tSeqCost, dummy_refillDependenceMap);
00741     }
00742     #ifndef NDEBUG
00743     cout << "datapoint:" << computationalCost << ":" << num_nontrivial_edges(angelLCG_copy, ourAwarenessLevel) << endl;
00744     #endif
00745   } // end of elimination sequence
00746 
00747   #ifndef NDEBUG
00748   // Really, we output the number of intermediates with no incident unit edge (can be normalized)
00749   cout << "Achieved a nontrivial edge count of " << bestNumNontrivialEdges << " with the following sequence of edge eliminations:";
00750   for (size_t c = 0; c < best_edgeElimSeqV.size(); c++)
00751     cout << endl << best_edgeElimSeqV[c].debug().c_str();
00752   cout << endl << endl << "****** Now re-performing best_edgeElimSeqV until we reach our edge goal of " << bestNumNontrivialEdges << " nontrivial edges" << endl;
00753   #endif
00754 
00755   // Now replay the elimination sequence until we reach edge count goal.
00756   // Additionally, we perform a greedy reduction of the resulting remainder graph,
00757   // which may lead to more concise propagation code.
00758   unsigned int cost_of_elim_seq = 0;
00759   if (best_edgeElimSeqV.empty() ||
00760       num_nontrivial_edges(angelLCG, ourAwarenessLevel) == bestNumNontrivialEdges) {
00761     #ifndef NDEBUG
00762     cout << "No eliminations necessary to reach the desired edge count of " << bestNumNontrivialEdges << endl;
00763     #endif
00764   }
00765   else { //replay the elimination sequence until we reach edge count goal
00766     for (size_t c = 0; c < best_edgeElimSeqV.size(); c++) {
00767       cost_of_elim_seq += best_edgeElimSeqV[c].getEdgeElim().isFront() ?
00768          front_eliminate_edge_directly(best_edgeElimSeqV[c].getEdgeElim().getE(angelLCG), angelLCG, edge_ref_list, jae_list)
00769        : back_eliminate_edge_directly(best_edgeElimSeqV[c].getEdgeElim().getE(angelLCG), angelLCG, edge_ref_list, jae_list);
00770       if (num_nontrivial_edges (angelLCG, ourAwarenessLevel) == bestNumNontrivialEdges) {
00771         #ifndef NDEBUG
00772         cout << "Goal of " << bestNumNontrivialEdges << " reached at a computational cost of " << cost_of_elim_seq << " nontrivial scalar multiplications" << endl;
00773         #endif
00774         break;
00775       }
00776     }
00777   }
00778   // we may want to perform additional no-cost eliminations that don't lead to an increase in nontrivial edges
00779   #ifndef NDEBUG
00780   cout << "Now greedily reducing the remainder graph..." << endl;
00781   #endif
00782   postProcessRemainderGraph(angelLCG,
00783                             jae_list,
00784                             edge_ref_list,
00785                             ourAwarenessLevel);
00786 
00787 #ifndef NDEBUG
00788   write_graph ("angelLCG after partial edge elimination sequence (G prime): ", angelLCG);
00789   writeVertexAndEdgeTypes (cout, angelLCG);
00790   cout << "Cost of partial edge elimination sequence: " << cost_of_elim_seq << endl;
00791 #endif
00792   populate_remainderGraph_and_correlationLists (angelLCG, ourLCG_verts, edge_ref_list, remainderLCG, v_cor_list, e_cor_list);
00793 } // end xaifBoosterCrossCountryInterface::compute_partial_elimination_sequence_random()
00794 
00795 void compute_partial_elimination_sequence (const LinearizedComputationalGraph& ourLCG,
00796                                            const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel,
00797                                            const bool allowMaintainingFlag,
00798                                            JacobianAccumulationExpressionList& jae_list,
00799                                            LinearizedComputationalGraph& remainderLCG,
00800                                            VertexCorrelationList& v_cor_list,
00801                                            EdgeCorrelationList& e_cor_list) {
00802   // Create internal (angel) LCG from xaifBooster LCG
00803   vector<const LinearizedComputationalGraphVertex*> ourLCG_verts;
00804   c_graph_t angelLCG;
00805   list<EdgeRef_t> edge_ref_list;
00806   ourLCG_to_angelLCG (ourLCG, ourLCG_verts, angelLCG, edge_ref_list);
00807 
00808 #ifndef NDEBUG
00809   cout << endl << "****** Performing total elim sequences and building up refill dependence information..." << endl;
00810 #endif
00811 
00812   // To begin with, the best elimination sequence is NO elimination sequence
00813   elimSeq_cost_t *bestEliminationSequence = new elimSeq_cost_t (num_nontrivial_edges(angelLCG, ourAwarenessLevel), // bestNumNontrivialEdges
00814                                                                 0, // cost
00815                                                                 0, // costAtBestEdgecount
00816                                                                 numIntermediateVertices(angelLCG), // numIntermediatesAtBestEdgecount
00817                                                                 numIntermediateVerticesWithoutUnitEdge(angelLCG), // numIntermediatesWithoutUnitEdgeAtBestEdgecount
00818                                                                 0); // lastDesiredElim
00819   elimSeq_cost_t *currentEliminationSequence;
00820 
00821   // while I eliminate, build up list of refill dependences.  This is STATIC, because I store the vertex dependences
00822   refillDependenceMap_t refillDependences;
00823   vector<EdgeElim> eeV1, eeV2, eeV3, eeV4, eeV5;
00824 
00825   unsigned int seqNum = 0;
00826   while (true) {
00827     c_graph_t angelLCG_copy (angelLCG);
00828     currentEliminationSequence = new elimSeq_cost_t (num_nontrivial_edges (angelLCG_copy, ourAwarenessLevel), // bestNumNontrivialEdges
00829                                                      0, // cost
00830                                                      0, // costAtBestEdgecount
00831                                                      numIntermediateVertices(angelLCG_copy), // numIntermediatesAtBestEdgecount
00832                                                      numIntermediateVerticesWithoutUnitEdge(angelLCG), // numIntermediatesWithoutUnitEdgeAtBestEdgecount
00833                                                      0); // lastDesiredElim
00834 #ifndef NDEBUG
00835     cout << "++++++++++++++++++++++++" << "TRYING A NEW COMPLETE ELIMINATION SEQUENCE" << "++++++++++++++++++++++++" << endl;
00836 #endif
00837 
00838     // perform a complete elimination sequence that preserves scarcity and tries to avoid refill
00839     unsigned int elimNum = 0;
00840     while(true) {
00841 #ifndef NDEBUG
00842       write_graph("angelLCG_copy: ", angelLCG_copy);
00843       cout << "datapoint:" << seqNum << ":" << elimNum << ":" << num_nontrivial_edges(angelLCG_copy, ourAwarenessLevel) << endl;
00844 #endif
00845 
00846       // run through the heuristics pipeline
00847       eliminatable_edges(angelLCG_copy, eeV1);
00848       if (eeV1.empty())
00849         break; // no more eliminatable edges
00850 
00851       if (reducing_edge_eliminations(eeV1, angelLCG_copy, ourAwarenessLevel, eeV2) == 0 && allowMaintainingFlag)
00852         maintaining_edge_eliminations(eeV1, angelLCG_copy, ourAwarenessLevel, eeV2);
00853 
00854       if (!eeV2.empty())
00855         refill_avoiding_edge_eliminations(eeV2, angelLCG_copy, refillDependences, eeV3);
00856       else
00857         refill_avoiding_edge_eliminations(eeV1, angelLCG_copy, refillDependences, eeV3);
00858 
00859       if (!eeV3.empty()) // there are some refill avoiding elims
00860         lowestMarkowitzEdgeElim(eeV3, angelLCG_copy, eeV4);
00861       else if (!eeV2.empty()) // there are no refill avoiding elims, but there are scarcity-preserving elims
00862         lowestMarkowitzEdgeElim(eeV2, angelLCG_copy, eeV4);
00863       else // there are no refill avoiding elims, and no scarcity-preserving elims
00864         lowestMarkowitzEdgeElim(eeV1, angelLCG_copy, eeV4);
00865 
00866       reverseModeEdgeElim(eeV4, angelLCG_copy, eeV5);
00867 
00868       EdgeElim thisEdgeElim (eeV5[0]);
00869       currentEliminationSequence->edgeElimVector.push_back(thisEdgeElim);
00870       currentEliminationSequence->cost += thisEdgeElim.isFront() ?
00871          front_elim (thisEdgeElim.getE(angelLCG_copy), angelLCG_copy, *currentEliminationSequence, refillDependences)
00872        : back_elim (thisEdgeElim.getE(angelLCG_copy), angelLCG_copy, *currentEliminationSequence, refillDependences);
00873 
00874       // check whether we've beaten our CURRENT best
00875       if (num_nontrivial_edges (angelLCG_copy, ourAwarenessLevel) < currentEliminationSequence->bestNumNontrivialEdges) {
00876         currentEliminationSequence->bestNumNontrivialEdges = num_nontrivial_edges (angelLCG_copy, ourAwarenessLevel);
00877         currentEliminationSequence->costAtBestEdgecount = currentEliminationSequence->cost;
00878         currentEliminationSequence->numIntermediatesAtBestEdgecount = numIntermediateVertices(angelLCG_copy);
00879         currentEliminationSequence->numIntermediatesWithoutUnitEdgeAtBestEdgecount = numIntermediateVerticesWithoutUnitEdge(angelLCG_copy);
00880         currentEliminationSequence->lastDesiredElim = currentEliminationSequence->edgeElimVector.size();
00881 #ifndef NDEBUG
00882         cout << "** new best_num_edges for currentElimSeq: " << currentEliminationSequence->bestNumNontrivialEdges << endl;
00883 #endif
00884       }
00885 
00886 #ifndef NDEBUG
00887       write_refillDependences (cout, refillDependences);
00888 #endif
00889 
00890       elimNum++;
00891     } // end of elimination sequence
00892     bool finished = !currentEliminationSequence->revealedNewDependence;
00893 
00894 #ifndef NDEBUG
00895     cout << "complete elim sequence complete.  This sequence achieved " << currentEliminationSequence->bestNumNontrivialEdges << " edges and ";
00896     if (currentEliminationSequence->revealedNewDependence) cout << "DID"; else cout << "DID NOT";
00897     cout << " add new dependence information to the dependence map" << endl;
00898 #endif
00899 
00900     // check whether we've beaten our OVERALL best, or MATCHED it with lower cost
00901     if (currentEliminationSequence->bestNumNontrivialEdges < bestEliminationSequence->bestNumNontrivialEdges
00902      || (currentEliminationSequence->bestNumNontrivialEdges == bestEliminationSequence->bestNumNontrivialEdges
00903       && currentEliminationSequence->costAtBestEdgecount < bestEliminationSequence->costAtBestEdgecount)) {
00904       delete bestEliminationSequence;
00905       bestEliminationSequence = currentEliminationSequence;
00906       currentEliminationSequence = NULL;
00907 #ifndef NDEBUG
00908       cout << "This elimination sequence is best so far" << endl;
00909 #endif
00910     }
00911     else { // latest elimination sequence isn't an improvement
00912 #ifndef NDEBUG
00913       cout << "This elimination sequence isn't an improvement" << endl;
00914 #endif
00915       delete currentEliminationSequence;
00916     }
00917 
00918     if (finished) break;
00919     seqNum++;
00920   } // end determine best elimination sequence
00921 
00922   #ifndef NDEBUG
00923   // Really, we output the number of intermediates with no incident unit edge (can be normalized)
00924   cout << "The best partial edge elimination sequence achieves a nontrivial edge count of " << bestEliminationSequence->bestNumNontrivialEdges
00925        << ", at which point there are " << bestEliminationSequence->numIntermediatesWithoutUnitEdgeAtBestEdgecount << " intermediate vertices with no incident unit edge" << endl;
00926   cout << "The best partial edge elimination sequence is: " << endl;
00927   for (size_t i = 0; i < bestEliminationSequence->edgeElimVector.size(); i++)
00928     cout << bestEliminationSequence->edgeElimVector[i].debug().c_str();
00929   cout << endl << endl << "****** Now re-performing bestElimSeqFound until we reach our edge goal of " << bestEliminationSequence->bestNumNontrivialEdges << " nontrivial edges" << endl;
00930   #endif
00931 
00932   if (num_nontrivial_edges (angelLCG, ourAwarenessLevel) > bestEliminationSequence->bestNumNontrivialEdges) {
00933     for (size_t c = 0; c < bestEliminationSequence->edgeElimVector.size(); c++) {
00934       bestEliminationSequence->edgeElimVector[c].isFront() ?
00935          front_eliminate_edge_directly (bestEliminationSequence->edgeElimVector[c].getE(angelLCG), angelLCG, edge_ref_list, jae_list)
00936        : back_eliminate_edge_directly (bestEliminationSequence->edgeElimVector[c].getE(angelLCG), angelLCG, edge_ref_list, jae_list);
00937       if (num_nontrivial_edges (angelLCG, ourAwarenessLevel) == bestEliminationSequence->bestNumNontrivialEdges)
00938         break;
00939     } // end iterate over bestEliminationSequence->edgeElimVector
00940   }
00941   #ifndef NDEBUG
00942   else
00943     cout << "No eliminations necessary to reach the desired edge count of " << bestEliminationSequence->bestNumNontrivialEdges << endl;
00944 
00945   write_graph ("angelLCG after partial edge elimination sequence (G prime): ", angelLCG);
00946   writeVertexAndEdgeTypes (cout, angelLCG);
00947   #endif
00948 
00949   delete bestEliminationSequence;
00950 
00951   // we may want to perform additional no-cost eliminations that don't lead to an increase in nontrivial edges
00952   #ifndef NDEBUG
00953   cout << "Now greedily reducing the remainder graph..." << endl;
00954   #endif
00955   postProcessRemainderGraph(angelLCG,
00956                             jae_list,
00957                             edge_ref_list,
00958                             ourAwarenessLevel);
00959 
00960   populate_remainderGraph_and_correlationLists (angelLCG, ourLCG_verts, edge_ref_list, remainderLCG, v_cor_list, e_cor_list);
00961 } // end xaifBoosterCrossCountryInterface::compute_partial_elimination_sequence()
00962 
00963 void compute_partial_transformation_sequence_random(const LinearizedComputationalGraph& ourLCG,
00964                                                     const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel,
00965                                                     const bool allowMaintainingFlag,
00966                                                     JacobianAccumulationExpressionList& jae_list,
00967                                                     LinearizedComputationalGraph& remainderLCG,
00968                                                     VertexCorrelationList& v_cor_list,
00969                                                     EdgeCorrelationList& e_cor_list,
00970                                                     unsigned int& numReroutings) {
00971   srand(time(NULL));
00972 
00973   // Create internal (angel) LCG from xaifBooster LCG
00974   vector<const LinearizedComputationalGraphVertex*> ourLCG_verts;
00975   c_graph_t angelLCG_orig;
00976   list<EdgeRef_t> edge_ref_list;
00977   ourLCG_to_angelLCG (ourLCG, ourLCG_verts, angelLCG_orig, edge_ref_list);
00978 
00979   unsigned int max_steps = 20 * num_vertices(angelLCG_orig);
00980   unsigned int num_passes = 5;
00981 
00982   transformationSeq_cost_t dummy_transformationSeq_cost (0, 0, 0, 0, 0, 0);
00983   refillDependenceMap_t dummy_refillDependenceMap;
00984   vector<Transformation> allViableTransformationsV, transformationSeqV, best_transformationSeqV;
00985   c_graph_t angelLCG (angelLCG_orig);
00986   unsigned int previous_numNontrivialEdges = num_nontrivial_edges(angelLCG, ourAwarenessLevel);
00987   unsigned int bestNumNontrivialEdges = num_nontrivial_edges(angelLCG, ourAwarenessLevel);
00988   unsigned int computationalCost_at_bestEdgeCount = 0;
00989   unsigned int computationalCost = 0;
00990   for (unsigned int steps_counter = 0; steps_counter < max_steps; steps_counter++) {
00991     #ifndef NDEBUG
00992     cout << "datapoint:" << computationalCost << ":" << num_nontrivial_edges(angelLCG, ourAwarenessLevel) << endl;
00993     #endif
00994 
00995     // Start over from the beginning
00996     if (steps_counter%(max_steps/num_passes) == 0) {
00997       #ifndef NDEBUG
00998       cout << "Starting a new SA pass (" << steps_counter << "/" << max_steps << " steps):\tbestNumNontrivialEdges = " << bestNumNontrivialEdges << ", computationalCost_at_bestEdgeCount = " << computationalCost_at_bestEdgeCount << endl;
00999       #endif
01000       transformationSeqV.clear();
01001       computationalCost = 0;
01002       previous_numNontrivialEdges = num_nontrivial_edges(angelLCG_orig, ourAwarenessLevel);
01003       angelLCG = angelLCG_orig;
01004       continue;
01005     }
01006 
01007     // assess the effect of each viable transformation
01008     all_viable_transformations(angelLCG, transformationSeqV, allViableTransformationsV);
01009     if (allViableTransformationsV.empty())
01010       break;
01011     vector<double> deltaE(allViableTransformationsV.size() + 1);
01012     for (size_t c = 0; c < allViableTransformationsV.size(); c++)
01013       deltaE[c] = transformation_effect(allViableTransformationsV[c], angelLCG, ourAwarenessLevel);
01014     // calculate probability for going backwards one step
01015     deltaE[allViableTransformationsV.size()] = (int)previous_numNontrivialEdges - (int)num_nontrivial_edges(angelLCG, ourAwarenessLevel);
01016 
01017     unsigned int choice_index = chooseTarget_sa(deltaE);
01018     if (choice_index != allViableTransformationsV.size()) { // perform a transformation
01019       previous_numNontrivialEdges = num_nontrivial_edges(angelLCG, ourAwarenessLevel);
01020       transformationSeqV.push_back(allViableTransformationsV[choice_index]);
01021       // REROUTING
01022       if (allViableTransformationsV[choice_index].isRerouting()) {
01023         computationalCost += allViableTransformationsV[choice_index].getRerouting().isPre() ?
01024            prerouteEdge_noJAE(allViableTransformationsV[choice_index].getRerouting().getER(angelLCG), angelLCG)
01025          : postrouteEdge_noJAE(allViableTransformationsV[choice_index].getRerouting().getER(angelLCG), angelLCG);
01026       }
01027       // EDGE ELIM
01028       else {
01029         computationalCost += allViableTransformationsV[choice_index].getEdgeElim().isFront() ?
01030            frontEdgeElimination_noJAE(allViableTransformationsV[choice_index].getEdgeElim().getE(angelLCG), angelLCG, &dummy_transformationSeq_cost, dummy_refillDependenceMap)
01031          : backEdgeElimination_noJAE(allViableTransformationsV[choice_index].getEdgeElim().getE(angelLCG), angelLCG, &dummy_transformationSeq_cost, dummy_refillDependenceMap);
01032       } // end edge elim
01033 
01034       // check whether we've beaten our CURRENT best
01035       if (num_nontrivial_edges (angelLCG, ourAwarenessLevel) < bestNumNontrivialEdges
01036        || (num_nontrivial_edges (angelLCG, ourAwarenessLevel) == bestNumNontrivialEdges && computationalCost < computationalCost_at_bestEdgeCount)) {
01037         bestNumNontrivialEdges = num_nontrivial_edges (angelLCG, ourAwarenessLevel);
01038         computationalCost_at_bestEdgeCount = computationalCost;
01039         best_transformationSeqV = transformationSeqV;
01040         #ifndef NDEBUG
01041         cout << "** New best_num_edges found: " << bestNumNontrivialEdges
01042              << " with computational cost " << computationalCost 
01043              << " after " << transformationSeqV.size() << " transformations" << endl;
01044         #endif
01045       }
01046     } // end perform a transformation
01047     else { // this corresponds to a backtracking (NOTE: going back cannot lead to a new "best-so-far" result)
01048       #ifndef NDEBUG
01049       cout << "Performing a BACKTRACKING step" << endl;
01050       #endif
01051       if (transformationSeqV.empty())
01052         continue;
01053       angelLCG = angelLCG_orig;
01054       transformationSeqV.pop_back();
01055       computationalCost = replay_transformation_seq(angelLCG, transformationSeqV, previous_numNontrivialEdges, ourAwarenessLevel, dummy_transformationSeq_cost, dummy_refillDependenceMap);
01056     } // end backtracking
01057   }
01058 
01059   #ifndef NDEBUG
01060   cout << "Achieved a nontrivial edge count of " << bestNumNontrivialEdges << endl;
01061   cout << "Best sequence of transformations: " << endl;
01062   for (size_t c = 0; c < best_transformationSeqV.size(); c++)
01063     cout << best_transformationSeqV[c].debug().c_str() << endl;
01064   cout << endl << endl << "****** Now re-performing best_transformationSeqV until we reach our edge goal of " << bestNumNontrivialEdges << " nontrivial edges" << endl;
01065   #endif
01066 
01067   //replay the elimination sequence until we reach edge count goal
01068   numReroutings = 0;
01069   if (num_nontrivial_edges (angelLCG_orig, ourAwarenessLevel) > bestNumNontrivialEdges) {
01070     for (size_t c = 0; c < best_transformationSeqV.size(); c++) {
01071       if (best_transformationSeqV[c].isRerouting()) { // REROUTING
01072         numReroutings++;
01073         best_transformationSeqV[c].getRerouting().isPre() ?
01074            preroute_edge_directly(best_transformationSeqV[c].getRerouting().getER(angelLCG_orig), angelLCG_orig, edge_ref_list, jae_list)
01075          : postroute_edge_directly(best_transformationSeqV[c].getRerouting().getER(angelLCG_orig), angelLCG_orig, edge_ref_list, jae_list);
01076       }
01077       else { // EDGE ELIMINATION
01078         best_transformationSeqV[c].getEdgeElim().isFront() ?
01079            front_eliminate_edge_directly(best_transformationSeqV[c].getEdgeElim().getE(angelLCG_orig), angelLCG_orig, edge_ref_list, jae_list)
01080          : back_eliminate_edge_directly(best_transformationSeqV[c].getEdgeElim().getE(angelLCG_orig), angelLCG_orig, edge_ref_list, jae_list);
01081       }
01082       if (num_nontrivial_edges (angelLCG_orig, ourAwarenessLevel) == bestNumNontrivialEdges) {
01083         #ifndef NDEBUG
01084         cout << "Goal of " << bestNumNontrivialEdges << " reached" << endl;
01085         #endif
01086         break;
01087       }
01088     }
01089   }
01090   #ifndef NDEBUG
01091   else
01092     cout << "No eliminations necessary to reach the desired edge count of " << bestNumNontrivialEdges << endl;
01093   #endif
01094 
01095   #ifndef NDEBUG
01096   write_graph ("angelLCG after partial transformation sequence (G prime): ", angelLCG_orig);
01097   writeVertexAndEdgeTypes (cout, angelLCG_orig);
01098   #endif
01099   populate_remainderGraph_and_correlationLists (angelLCG_orig, ourLCG_verts, edge_ref_list, remainderLCG, v_cor_list, e_cor_list);
01100 } // end xaifBoosterCrossCountryInterface::compute_partial_transformation_sequence_random()
01101 
01102 void compute_partial_transformation_sequence (const LinearizedComputationalGraph& ourLCG,
01103                                               const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel,
01104                                               const bool allowMaintainingFlag,
01105                                               JacobianAccumulationExpressionList& jae_list,
01106                                               LinearizedComputationalGraph& remainderLCG,
01107                                               VertexCorrelationList& v_cor_list,
01108                                               EdgeCorrelationList& e_cor_list,
01109                                               unsigned int& numReroutings) {
01110   // Create internal (angel) LCG from xaifBooster LCG
01111   vector<const LinearizedComputationalGraphVertex*> ourLCG_verts;
01112   c_graph_t angelLCG;
01113   list<EdgeRef_t> edge_ref_list;
01114   ourLCG_to_angelLCG (ourLCG, ourLCG_verts, angelLCG, edge_ref_list);
01115 
01116   #ifndef NDEBUG
01117   cout << "Determining a partial sequence of transformations..." << endl;
01118   #endif
01119 
01120   // To begin with, the best transformation sequence is NO transformation sequence
01121   transformationSeq_cost_t *bestTransformationSequence = new transformationSeq_cost_t (num_nontrivial_edges(angelLCG, ourAwarenessLevel),
01122                                                                                        0,
01123                                                                                        0,
01124                                                                                        numIntermediateVertices(angelLCG),
01125                                                                                        numIntermediateVerticesWithoutUnitEdge(angelLCG),
01126                                                                                        0);
01127   transformationSeq_cost_t *currentTransformationSequence;
01128 
01129   refillDependenceMap_t refillDependences;
01130   vector<Transformation> allViableTransformationsV,
01131                          maintainingTransformationsV,
01132                          reducingTransformationsV,
01133                          reroutingConsiderateTransformationsV,
01134                          refillAvoidingTransformationsV,
01135                          lowestMarkowitzTransformationsV,
01136                          reverseModeTransformationsV;
01137 
01138   // determine a best transformation sequence
01139   unsigned int seqNum = 0;
01140   while (true) {
01141     c_graph_t angelLCG_copy (angelLCG);
01142     currentTransformationSequence = new transformationSeq_cost_t (num_nontrivial_edges(angelLCG_copy, ourAwarenessLevel),
01143                                                                   0,
01144                                                                   0,
01145                                                                   numIntermediateVertices(angelLCG_copy),
01146                                                                   numIntermediateVerticesWithoutUnitEdge(angelLCG),
01147                                                                   0);
01148 
01149 #ifndef NDEBUG
01150     cout << "++++++++++++++++++++++++" << endl << "TRYING A NEW COMPLETE TRANSFORMATION SEQUENCE" << "++++++++++++++++++++++++" << endl;
01151 #endif
01152 
01153     // run currentTransformationSequence
01154     unsigned int elimNum = 0;
01155     while (true) {
01156 #ifndef NDEBUG
01157       cout << "datapoint:" << seqNum << ":" << elimNum << ":" << num_nontrivial_edges(angelLCG_copy, ourAwarenessLevel) << endl;
01158 #endif
01159 
01160       // run filters
01161       if (!all_viable_transformations (angelLCG_copy, currentTransformationSequence->transformationVector, allViableTransformationsV))
01162         break;
01163       maintaining_transformations (allViableTransformationsV, angelLCG_copy, ourAwarenessLevel, maintainingTransformationsV);
01164       reducing_transformations (maintainingTransformationsV, angelLCG_copy, ourAwarenessLevel, reducingTransformationsV);
01165       rerouting_considerate_transformations (reducingTransformationsV, angelLCG_copy, currentTransformationSequence->transformationVector, reroutingConsiderateTransformationsV);
01166       refill_avoiding_transformations (reroutingConsiderateTransformationsV, angelLCG_copy, ourAwarenessLevel, refillDependences, refillAvoidingTransformationsV);
01167       lowest_markowitz_transformations (refillAvoidingTransformationsV, angelLCG_copy, lowestMarkowitzTransformationsV);
01168       reverse_mode_transformations (lowestMarkowitzTransformationsV, angelLCG_copy, reverseModeTransformationsV);
01169 
01170       Transformation chosenTransformation (reverseModeTransformationsV[0]);
01171       currentTransformationSequence->transformationVector.push_back(chosenTransformation);
01172 
01173       if (chosenTransformation.isRerouting())
01174         currentTransformationSequence->cost += chosenTransformation.getRerouting().isPre() ?
01175            prerouteEdge_noJAE(chosenTransformation.getRerouting().getER(angelLCG_copy), angelLCG_copy)
01176          : postrouteEdge_noJAE(chosenTransformation.getRerouting().getER(angelLCG_copy), angelLCG_copy);
01177       else
01178         currentTransformationSequence->cost += chosenTransformation.getEdgeElim().isFront() ?
01179            frontEdgeElimination_noJAE(chosenTransformation.getEdgeElim().getE(angelLCG_copy), angelLCG_copy, currentTransformationSequence, refillDependences)
01180          : backEdgeElimination_noJAE(chosenTransformation.getEdgeElim().getE(angelLCG_copy), angelLCG_copy, currentTransformationSequence, refillDependences);
01181 
01182       // check whether we've beaten our CURRENT best
01183       if (num_nontrivial_edges (angelLCG_copy, ourAwarenessLevel) < currentTransformationSequence->bestNumNontrivialEdges) {
01184         currentTransformationSequence->bestNumNontrivialEdges = num_nontrivial_edges (angelLCG_copy, ourAwarenessLevel);
01185         currentTransformationSequence->costAtBestEdgecount = currentTransformationSequence->cost;
01186         currentTransformationSequence->numIntermediatesAtBestEdgecount = numIntermediateVertices(angelLCG_copy);
01187         currentTransformationSequence->numIntermediatesWithoutUnitEdgeAtBestEdgecount = numIntermediateVerticesWithoutUnitEdge(angelLCG_copy);
01188         currentTransformationSequence->lastDesiredTransformation = currentTransformationSequence->transformationVector.size();
01189         #ifndef NDEBUG
01190         cout << "** new currentTransformationSequence->bestNumNontrivialEdges: " << currentTransformationSequence->bestNumNontrivialEdges << endl;
01191         #endif
01192       }
01193 
01194       elimNum++;
01195     } // end of transformation sequence
01196 
01197     bool notFinishedYet = currentTransformationSequence->revealedNewDependence;
01198 
01199 #ifndef NDEBUG
01200     cout << "complete elim sequence complete.  This sequence achieved " << currentTransformationSequence->bestNumNontrivialEdges << " edges and ";
01201     if (currentTransformationSequence->revealedNewDependence) cout << "DID"; else cout << "DID NOT";
01202     cout << " add new dependence information to the dependence map" << endl;
01203     write_refillDependences (cout, refillDependences);
01204 #endif
01205      
01206     // check whether we've beaten our OVERALL best, or MATCHED it with lower cost
01207     if (currentTransformationSequence->bestNumNontrivialEdges < bestTransformationSequence->bestNumNontrivialEdges
01208      || (currentTransformationSequence->bestNumNontrivialEdges == bestTransformationSequence->bestNumNontrivialEdges
01209       && currentTransformationSequence->costAtBestEdgecount < bestTransformationSequence->costAtBestEdgecount)) {
01210       delete bestTransformationSequence;
01211       bestTransformationSequence = currentTransformationSequence;
01212       currentTransformationSequence = NULL;
01213 #ifndef NDEBUG
01214       cout << "This transformation sequence is best so far" << endl;
01215 #endif
01216     }
01217     else { // latest transformation sequence isn't an improvement
01218 #ifndef NDEBUG
01219       cout << "This transformation isn't an improvement" << endl;
01220 #endif
01221       delete currentTransformationSequence;
01222     }
01223      
01224     // determine whether it's time to stop
01225     if (!notFinishedYet) break;
01226 
01227     seqNum++;
01228   } // end determine a best transformation sequence
01229 
01230   #ifndef NDEBUG
01231   // Really, we output the number of intermediates with no incident unit edge (can be normalized)
01232   cout << "The best transformation sequence achieves a nontrivial edge count of " << bestTransformationSequence->bestNumNontrivialEdges
01233        << ", at which point there are " << bestTransformationSequence->numIntermediatesWithoutUnitEdgeAtBestEdgecount << " intermediate vertices" << endl;
01234        //<< ", at which point " << bestTransformationSequence->numIntermediatesWithoutUnitEdgeAtBestEdgecount << " of "
01235        //<< bestTransformationSequence->numIntermediatesAtBestEdgecount << " intermediate vertices have no incident unit edges" << endl;
01236   cout << "Now performing the best partial sequence of transformations..." << endl;
01237   #endif
01238   // Perform the best transformation sequence
01239   numReroutings = 0;
01240   for (size_t i = 0; i < bestTransformationSequence->transformationVector.size(); i++) {
01241     if (bestTransformationSequence->transformationVector[i].isRerouting()) { // rerouting
01242       numReroutings++;
01243       bestTransformationSequence->transformationVector[i].getRerouting().isPre() ?
01244          preroute_edge_directly(bestTransformationSequence->transformationVector[i].getRerouting().getER(angelLCG), angelLCG, edge_ref_list, jae_list)
01245        : postroute_edge_directly(bestTransformationSequence->transformationVector[i].getRerouting().getER(angelLCG), angelLCG, edge_ref_list, jae_list);
01246     } // end rerouting
01247     else { // edge elimination
01248       bestTransformationSequence->transformationVector[i].getEdgeElim().isFront() ?
01249          front_eliminate_edge_directly(bestTransformationSequence->transformationVector[i].getEdgeElim().getE(angelLCG), angelLCG, edge_ref_list, jae_list)
01250        : back_eliminate_edge_directly(bestTransformationSequence->transformationVector[i].getEdgeElim().getE(angelLCG), angelLCG, edge_ref_list, jae_list);
01251     } // end edge elimination
01252     // break when we've reached our goal
01253     if (num_nontrivial_edges (angelLCG, ourAwarenessLevel) == bestTransformationSequence->bestNumNontrivialEdges)
01254       break;
01255   } // end iterate over best transformation sequence 
01256 
01257   #ifndef NDEBUG
01258   cout << "Goal of " << bestTransformationSequence->bestNumNontrivialEdges << " reached" << endl;
01259   #endif
01260   delete bestTransformationSequence; 
01261 
01262   populate_remainderGraph_and_correlationLists (angelLCG, ourLCG_verts, edge_ref_list, remainderLCG, v_cor_list, e_cor_list);
01263 } // end xaifBoosterCrossCountryInterface::compute_partial_transformation_sequence()
01264 
01265 void computeEliminationSequenceRandom(const LinearizedComputationalGraph& ourLCG,
01266                                       JacobianAccumulationExpressionList& jae_list,
01267                                       LinearizedComputationalGraph& remainderLCG,
01268                                       VertexCorrelationList& v_cor_list,
01269                                       EdgeCorrelationList& e_cor_list) {
01270   srand(time(NULL));
01271 
01272   // Create internal (angel) LCG from xaifBooster LCG
01273   vector<const LinearizedComputationalGraphVertex*> ourLCG_verts;
01274   c_graph_t angelLCG_orig;
01275   list<EdgeRef_t> edge_ref_list;
01276   ourLCG_to_angelLCG (ourLCG, ourLCG_verts, angelLCG_orig, edge_ref_list);
01277 
01278   unsigned int max_steps = 100 * num_edges(angelLCG_orig);
01279 
01280   c_graph_t angelLCG_copy (angelLCG_orig);
01281   elimSeq_cost_t dummy_elimSeq_cost (0, 0, 0, 0, 0, 0);
01282   refillDependenceMap_t dummy_refillDependenceMap;
01283   vector<EdgeElim> allEdgeElimsV, edgeElimSeqV, best_edgeElimSeqV;
01284   unsigned int previous_computationalCost = 0;
01285   unsigned int computationalCost = 0;
01286   int best_computationalCost = -1;
01287   for (unsigned int steps_counter = 0; steps_counter < max_steps; steps_counter++) {
01288 /*
01289     // Start over from the beginning
01290     if (steps_counter%(max_steps/num_passes) == 0) {
01291       #ifndef NDEBUG
01292       cout << "Starting a new random pass (" << steps_counter << "/" << max_steps << " steps):\tbest_computationalCost = " << best_computationalCost << endl;
01293       #endif
01294       edgeElimSeqV.clear();
01295       computationalCost = 0;
01296       previous_computationalCost = 0;
01297       angelLCG_copy = angelLCG_orig;
01298       continue;
01299     }
01300 */
01301     eliminatable_edges(angelLCG_copy, allEdgeElimsV);
01302     if (allEdgeElimsV.empty()) {
01303       #ifndef NDEBUG
01304       cout << "Sequence complete. length = " << edgeElimSeqV.size() << ", cost = " << computationalCost;
01305       #endif
01306       if (best_computationalCost == -1 // this is our first sequence
01307        || (int)computationalCost < best_computationalCost) {
01308         #ifndef NDEBUG
01309         cout << " (this sequence is new best) " << endl;
01310         #endif
01311         best_computationalCost = computationalCost;
01312         best_edgeElimSeqV = edgeElimSeqV;
01313       }
01314       #ifndef NDEBUG
01315       else
01316         cout << endl;
01317       #endif
01318       edgeElimSeqV.clear();
01319       computationalCost = 0;
01320       previous_computationalCost = 0;
01321       angelLCG_copy = angelLCG_orig;
01322       continue;
01323     } // end sequence is finished
01324 
01325     // calculate relative probabilities for each possible edge elim
01326     vector<double> deltaE(allEdgeElimsV.size());
01327     for (size_t c = 0; c < allEdgeElimsV.size(); c++)
01328       deltaE[c] = allEdgeElimsV[c].getCost(angelLCG_copy);
01329     int choice_index = chooseEdgeElimRandomly(deltaE);
01330     if (choice_index == -1) { // BACKTRACKING
01331       #ifndef NDEBUG
01332       cout << "Performing a BACKTRACKING step" << endl;
01333       #endif
01334       if (edgeElimSeqV.empty())
01335         continue;
01336       angelLCG_copy = angelLCG_orig;
01337       edgeElimSeqV.pop_back();
01338       computationalCost = 0;
01339       for (size_t i = 0; i < edgeElimSeqV.size(); i++) {
01340         if (i == edgeElimSeqV.size() - 1) // save previous_computationalCost
01341           previous_computationalCost = computationalCost;
01342         #ifndef NDEBUG
01343         cout << "\t";
01344         #endif
01345         computationalCost += edgeElimSeqV[i].isFront() ?
01346            front_elim(edgeElimSeqV[i].getE(angelLCG_copy), angelLCG_copy, dummy_elimSeq_cost, dummy_refillDependenceMap)
01347          : back_elim(edgeElimSeqV[i].getE(angelLCG_copy), angelLCG_copy, dummy_elimSeq_cost, dummy_refillDependenceMap);
01348       } // end iterate over edge elims
01349     } // end backtracking
01350     else { // eliminate an edge
01351       previous_computationalCost = computationalCost;
01352       edgeElimSeqV.push_back(allEdgeElimsV[choice_index]);
01353       computationalCost += allEdgeElimsV[choice_index].isFront() ?
01354          front_elim(allEdgeElimsV[choice_index].getE(angelLCG_copy), angelLCG_copy, dummy_elimSeq_cost, dummy_refillDependenceMap)
01355        : back_elim(allEdgeElimsV[choice_index].getE(angelLCG_copy), angelLCG_copy, dummy_elimSeq_cost, dummy_refillDependenceMap);
01356     } // end edge elim.
01357     #ifndef NDEBUG
01358     cout << "datapoint:" << edgeElimSeqV.size() << ":" << computationalCost << endl;
01359     #endif
01360   } // end outer loop
01361 
01362   #ifndef NDEBUG
01363   cout << "Achieved cost " << best_computationalCost << " with the following sequence of edge eliminations:";
01364   for (size_t c = 0; c < best_edgeElimSeqV.size(); c++)
01365     cout << endl << best_edgeElimSeqV[c].debug().c_str();
01366   cout << endl << endl << "****** Now re-performing best_edgeElimSeqV" << endl;
01367   #endif
01368   unsigned int cost_of_elim_seq = 0;
01369   for (size_t c = 0; c < best_edgeElimSeqV.size(); c++)
01370     cost_of_elim_seq += best_edgeElimSeqV[c].isFront() ?
01371        front_eliminate_edge_directly(best_edgeElimSeqV[c].getE(angelLCG_orig), angelLCG_orig, edge_ref_list, jae_list)
01372      : back_eliminate_edge_directly(best_edgeElimSeqV[c].getE(angelLCG_orig), angelLCG_orig, edge_ref_list, jae_list);
01373   #ifndef NDEBUG
01374   write_graph ("angelLCG_orig after complete edge elimination sequence (G prime): ", angelLCG_orig);
01375   writeVertexAndEdgeTypes (cout, angelLCG_orig);
01376   cout << "computeEliminationSequenceRandom: cost " << cost_of_elim_seq << endl;
01377   #endif
01378   populate_remainderGraph_and_correlationLists (angelLCG_orig, ourLCG_verts, edge_ref_list, remainderLCG, v_cor_list, e_cor_list);
01379 } // end xaifBoosterCrossCountryInterface::compute_elimination_sequence_random()
01380 
01381 void compute_elimination_sequence (const LinearizedComputationalGraph& xgraph,
01382                                    JacobianAccumulationExpressionList& JAElist,
01383                                    LinearizedComputationalGraph& remainderLCG,
01384                                    VertexCorrelationList& v_cor_list,
01385                                    EdgeCorrelationList& e_cor_list) {
01386   c_graph_t cg;
01387   vector<const LinearizedComputationalGraphVertex*> av;
01388   vector<edge_address_t> ae;
01389   read_graph_xaif_booster (xgraph, cg, av, ae);
01390 
01391   typedef heuristic_pair_t<lowest_markowitz_vertex_t, reverse_mode_vertex_t>                   lm_rm_t;
01392   typedef heuristic_pair_t<lmmd_vertex_t, reverse_mode_vertex_t>                               lmmd_rm_t;
01393   typedef heuristic_triplet_t<momr_vertex_t, lowest_markowitz_vertex_t, reverse_mode_vertex_t> momr_lm_rm_t;
01394   lm_rm_t                       lm_rm_v (lowest_markowitz_vertex, reverse_mode_vertex); 
01395   lmmd_rm_t                     lmmd_rm_v (lmmd_vertex, reverse_mode_vertex);
01396   momr_lm_rm_t                  momr_lm_rm_v (momr_vertex, lowest_markowitz_vertex, reverse_mode_vertex); 
01397 
01398   edge_ij_elim_heuristic_t<forward_mode_edge_t>      fm_ij (forward_mode_edge);
01399   edge_ij_elim_heuristic_t<reverse_mode_edge_t>      rm_ij (reverse_mode_edge);
01400   emulated_vertex_heuristic_t<lm_rm_t>               lm_rm_e (lm_rm_v);
01401   emulated_vertex_heuristic_t<lmmd_rm_t>             lmmd_rm_e (lmmd_rm_v);
01402   emulated_vertex_heuristic_t<momr_lm_rm_t>          momr_lm_rm_e (momr_lm_rm_v);
01403 
01404   vector<c_graph_t::vertex_t>   vseq;
01405   vector<edge_ij_elim_t>        eseq,v_eseq; 
01406   int vCost=INT_MAX, eCost;
01407 
01408   if (vertex_eliminatable (cg)) {
01409     vCost = best_heuristic (cg, vseq, forward_mode_vertex, reverse_mode_vertex, 
01410                             lm_rm_v, lmmd_rm_v, momr_lm_rm_v);
01411 #ifndef NDEBUG
01412     write_vector("Vertex elimination: sequence",vseq);
01413     cout << "Costs are " << vCost << '\n';
01414 #endif
01415     convert_elimination_sequence (vseq, cg, v_eseq);
01416 #ifndef NDEBUG
01417     write_vector("Same elimination sequence as edge eliminations", v_eseq);
01418 #endif
01419   }
01420   eCost = best_heuristic (cg, eseq, fm_ij, rm_ij, lm_rm_e, lmmd_rm_e, momr_lm_rm_e);
01421 #ifndef NDEBUG
01422   write_vector("Edge elimination: sequence",eseq);
01423   cout << "Costs are " << eCost << '\n'; 
01424 #endif
01425   if (vCost<eCost)
01426     eseq=v_eseq;
01427 
01428   line_graph_t lg (cg);
01429   vector<triplet_t>               tv;
01430   convert_elimination_sequence (eseq, lg, tv);
01431 
01432 #ifndef NDEBUG
01433   write_vector("Same elimination sequence as face eliminations", tv);  
01434 #endif
01435 
01436   accu_graph_t ac (cg, lg);
01437   for (size_t c= 0; c < tv.size(); c++) 
01438     face_elimination (tv[c], lg, ac);
01439 
01440 #ifndef NDEBUG
01441   write_graph ("Empty line graph", lg);
01442   line_graph_t::evn_t            evn= get(vertex_name, lg);
01443   write_vertex_property (cout, "vertices of this edge graph", evn, lg);
01444 #endif
01445   
01446   ac.set_jacobi_entries ();
01447 
01448 #ifndef NDEBUG
01449   for (size_t c= 0; c < ac.accu_exp.size(); c++) {
01450     write_graph ("Accumulation graph", ac.accu_exp[c]);
01451     property_map<pure_accu_exp_graph_t, vertex_name_t>::type vprop= 
01452       get (vertex_name, ac.accu_exp[c]);
01453     write_vertex_property (cout, "Vertex props", vprop, ac.accu_exp[c]); 
01454     ad_edge_t my_jacobi= ac.jacobi_entries[c];
01455     if (my_jacobi.second == 0) cout << "isn't Jacobian entry\n";
01456     else cout << "is Jacoby entry: " << my_jacobi << std::endl; }
01457 #endif
01458 
01459   write_graph_xaif_booster (ac, av, ae, JAElist, remainderLCG, v_cor_list, e_cor_list);
01460 } // end xaifBoosterCrossCountryInterface::compute_elimination_sequence()
01461 
01462 void compute_elimination_sequence_lsa_face (const LinearizedComputationalGraph& xgraph,
01463                                             int iterations, 
01464                                             double gamma,
01465                                             JacobianAccumulationExpressionList& JAElist,
01466                                             LinearizedComputationalGraph& remainderLCG,
01467                                             VertexCorrelationList& v_cor_list,
01468                                             EdgeCorrelationList& e_cor_list) {
01469   c_graph_t                                            cg;
01470   vector<const LinearizedComputationalGraphVertex*>    av;
01471   vector<edge_address_t>                               ae;
01472   read_graph_xaif_booster (xgraph, cg, av, ae);
01473   line_graph_t                                         lg (cg);
01474 
01475   face_elimination_history_t                           feh (lg);
01476   typedef triplet_heuristic_t<reverse_mode_face_t>     rm_t;
01477   rm_t                                                 rm (reverse_mode_face);
01478   SA_elimination_cost_t<rm_t>                          cost (rm);
01479   neighbor_sequence_check_t                            neighbor;
01480   
01481   // int elim_costs= 
01482     LSA (feh, neighbor, cost, gamma, iterations);
01483   feh.complete_sequence (rm);
01484 
01485   accu_graph_t ac (cg, lg);
01486   for (size_t c= 0; c < feh.seq.size(); c++) 
01487     face_elimination (feh.seq[c], lg, ac);
01488   ac.set_jacobi_entries ();
01489 
01490   write_graph_xaif_booster (ac, av, ae, JAElist, remainderLCG, v_cor_list, e_cor_list);
01491 
01492 } // end xaifBoosterCrossCountryInterface::compute_elimination_sequence_lsa_face()
01493 
01494 void compute_elimination_sequence_lsa_vertex (const LinearizedComputationalGraph& xgraph,
01495                                               int iterations, 
01496                                               double gamma,
01497                                               JacobianAccumulationExpressionList& JAElist,
01498                                               LinearizedComputationalGraph& remainderLCG,
01499                                               VertexCorrelationList& v_cor_list,
01500                                               EdgeCorrelationList& e_cor_list) {
01501   c_graph_t                                            cg;
01502   vector<const LinearizedComputationalGraphVertex*>    av;
01503   vector<edge_address_t>                               ae;
01504   read_graph_xaif_booster (xgraph, cg, av, ae);
01505 
01506   // Check if vertex elimination works
01507   for (size_t i= 0; i != cg.dependents.size(); i++)
01508     // version 1
01509     if (out_degree (cg.dependents[i], cg) > 0) {
01510       cerr << "Warning! Vertex elimination not possible with this graph, because at least one dependent vertex has at least one outedge.\n"
01511            << "Calling LSA for face elimination with same parameters (may take longer)...\n";
01512       return compute_elimination_sequence_lsa_face (xgraph, iterations, gamma, JAElist, remainderLCG, v_cor_list, e_cor_list);}
01513     // version 2
01514     // THROW_EXCEPT_MACRO (out_degree (cg.dependents[i], cg) > 0, consistency_exception, "Vertex elimination not possible with these graph.");
01515       
01516   vertex_elimination_history_t                         veh (cg);
01517   SA_elimination_cost_t<reverse_mode_vertex_t>         cost (reverse_mode_vertex);
01518   neighbor_sequence_check_t                            neighbor;
01519 
01520   // int elim_costs= 
01521     LSA (veh, neighbor, cost, gamma, iterations);
01522   veh.complete_sequence (reverse_mode_vertex);
01523 
01524   vector<edge_ij_elim_t>                              eseq; 
01525   vector<triplet_t>                                   tv;
01526   line_graph_t                                        lg (cg);
01527   convert_elimination_sequence (veh.seq, cg, eseq);
01528   convert_elimination_sequence (eseq, lg, tv);
01529 
01530   accu_graph_t ac (cg, lg);
01531   for (size_t c= 0; c < tv.size(); c++) 
01532     face_elimination (tv[c], lg, ac);
01533   ac.set_jacobi_entries ();
01534 
01535   write_graph_xaif_booster (ac, av, ae, JAElist, remainderLCG, v_cor_list, e_cor_list);
01536 } // end of angel::compute_elimination_sequence_lsa_vertex()
01537 
01538 void Elimination::eliminate() {
01539 
01540   try {
01541     switch (myType) {
01542       case OPS_ELIMTYPE:
01543         compute_elimination_sequence(*myLCG_p,
01544                                      myJAEList,
01545                                      myRemainderLCG,
01546                                      myVertexCorrelationList,
01547                                      myEdgeCorrelationList);
01548         break;
01549       case OPS_RANDOM_ELIMTYPE:
01550         computeEliminationSequenceRandom(*myLCG_p,
01551                                          myJAEList,
01552                                          myRemainderLCG,
01553                                          myVertexCorrelationList,
01554                                          myEdgeCorrelationList);
01555         break;
01556       case OPS_LSA_VERTEX_ELIMTYPE:
01557         compute_elimination_sequence_lsa_vertex(*myLCG_p,
01558                                                 getNumIterations(),
01559                                                 getGamma(),
01560                                                 myJAEList,
01561                                                 myRemainderLCG,
01562                                                 myVertexCorrelationList,
01563                                                 myEdgeCorrelationList);
01564         break;
01565       case OPS_LSA_FACE_ELIMTYPE:
01566         compute_elimination_sequence_lsa_face(*myLCG_p,
01567                                               getNumIterations(),
01568                                               getGamma(),
01569                                               myJAEList,
01570                                               myRemainderLCG,
01571                                               myVertexCorrelationList,
01572                                               myEdgeCorrelationList);
01573         break;
01574       case SCARCE_ELIMTYPE:
01575         compute_partial_elimination_sequence(*myLCG_p,
01576                                              ourAwarenessLevel,
01577                                              ourAllowMaintainingFlag,
01578                                              myJAEList,
01579                                              myRemainderLCG,
01580                                              myVertexCorrelationList,
01581                                              myEdgeCorrelationList);
01582         break;
01583       case SCARCE_RANDOM_ELIMTYPE:
01584         compute_partial_elimination_sequence_random(*myLCG_p,
01585                                                     ourAwarenessLevel,
01586                                                     ourAllowMaintainingFlag,
01587                                                     myJAEList,
01588                                                     myRemainderLCG,
01589                                                     myVertexCorrelationList,
01590                                                     myEdgeCorrelationList);
01591         break;
01592       case SCARCE_TRANSFORMATIONTYPE:
01593         compute_partial_transformation_sequence(*myLCG_p,
01594                                                 ourAwarenessLevel,
01595                                                 ourAllowMaintainingFlag,
01596                                                 myJAEList,
01597                                                 myRemainderLCG,
01598                                                 myVertexCorrelationList,
01599                                                 myEdgeCorrelationList,
01600                                                 myNumReroutings);
01601         break;
01602       case SCARCE_RANDOM_TRANSFORMATIONTYPE:
01603         compute_partial_transformation_sequence_random(*myLCG_p,
01604                                                        ourAwarenessLevel,
01605                                                        ourAllowMaintainingFlag,
01606                                                        myJAEList,
01607                                                        myRemainderLCG,
01608                                                        myVertexCorrelationList,
01609                                                        myEdgeCorrelationList,
01610                                                        myNumReroutings);
01611         break;
01612       default:
01613        THROW_EXCEPT_MACRO (true, consistency_exception, "Missing or invalid elimination type");
01614         break;
01615     } // end switch (myType)
01616   } // end try
01617   catch (base_exception e) { 
01618     throw EliminationException(std::string("angel exception caught within Elimination::eliminate() : ")+e.what_reason());
01619   }
01620 
01621 } // end of xaifBoosterCrossCountryInterface::Elimination::eliminate()
01622 
01623 } // end namespace xaifBoosterCrossCountryInterface
01624 
01625 #endif // USEXAIFBOOSTER
01626 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines