angel  mercurial changeset:
include/angel_tools.hpp
Go to the documentation of this file.
00001 // $Id: angel_tools.hpp,v 1.10 2004/02/22 18:44:46 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 
00011 #ifndef         _angel_tools_include_
00012 #define         _angel_tools_include_
00013 
00014 
00015 //
00016 //
00017 //
00018 
00019 #include <cstdlib>
00020 #include <string>
00021 #include <vector>
00022 #include <queue>
00023 #include <algorithm>
00024 #include <cmath>
00025 #include <numeric>
00026 #include <iostream>
00027 #include <deque>
00028 
00029 #include "angel_exceptions.hpp"
00030 #include "angel_types.hpp"
00031 
00032 namespace angel {
00033 
00034   using std::vector;
00035   using boost::tie;
00036   using boost::get;
00037   using boost::graph_traits;
00038 
00039 //                       some Operators
00040 // ===========================================================
00041 
00042 class write_vertex_op_t {
00043   const c_graph_t& cg;
00044 public:
00045   write_vertex_op_t (const c_graph_t& _cg) : cg (_cg) {}
00046   std::ostream& operator() (std::ostream& stream, c_graph_t::vertex_t v) {
00047     stream << v;
00048     return stream;
00049   }
00050 };
00051 
00052 class write_edge_op_t {
00053   const c_graph_t& cg;
00054 public:
00055   write_edge_op_t (const c_graph_t& _cg) : cg (_cg) {}
00056   std::ostream& operator() (std::ostream& stream, c_graph_t::edge_t e) {
00057     stream << "(" << source (e, cg) << ", " << target (e, cg) << ")";
00058     return stream;
00059   }
00060 };
00061 
00062 class write_edge_bool_op_t {
00063   const c_graph_t& cg;
00064 public:
00065   write_edge_bool_op_t (const c_graph_t& _cg) : cg (_cg) {}
00066   std::ostream& operator() (std::ostream& stream, std::pair<c_graph_t::edge_t,bool> eb) {
00067     c_graph_t::edge_t e= eb.first;
00068     stream << "((" << source (e, cg) << ", " << target (e, cg) << "), "
00069            << (eb.second ? "forward)" : "reverse)");
00070     return stream;
00071   }
00072 };
00073 
00074 class write_edge_name_op_t {
00075   const line_graph_t& lg;
00076   line_graph_t::const_evn_t  evn;
00077 public:
00078   write_edge_name_op_t (const line_graph_t& _lg) : lg (_lg) {
00079     evn= get(boost::vertex_name, lg); }
00080   std::ostream& operator() (std::ostream& stream, line_graph_t::edge_t e) {
00081     stream << '(' << evn[e].first << ", " << evn[e].second << ')';
00082     return stream;
00083   }
00084 };
00085 
00086 class write_face_op_t {
00087   const line_graph_t& lg;
00088   line_graph_t::const_evn_t  evn; 
00089 public:
00090   write_face_op_t (const line_graph_t& _lg) : lg (_lg) {
00091     evn= get(boost::vertex_name, lg); }
00092   std::ostream& operator() (std::ostream& stream, line_graph_t::face_t f) {
00093     line_graph_t::edge_t   ij= source (f, lg), jk= target (f, lg);
00094     int i= evn[ij].first, j= evn[ij].second, k= evn[jk].second;
00095     THROW_DEBUG_EXCEPT_MACRO (j != evn[jk].first, consistency_exception, "Adjacency corrupted in line graph"); 
00096     stream << '(' << i << ", " << j << ", " << k << ')';
00097     return stream;
00098   }
00099 };
00100 
00101 
00102 class write_face_number_op_t {
00103   const line_graph_t& lg;
00104 public:
00105   write_face_number_op_t (const line_graph_t& _lg) : lg (_lg) {}
00106   std::ostream& operator() (std::ostream& stream, line_graph_t::face_t f) {
00107     line_graph_t::edge_t   ij= source (f, lg), jk= target (f, lg);
00108     stream << '(' << ij << ", " << jk << ')';
00109     return stream;
00110   }
00111 };
00112 
00113 
00114 //                        Iterations
00115 // ===========================================================
00116 
00118 template <typename Ad_graph_t, typename Op_t>
00119 inline void for_all_edges (Ad_graph_t& adg, const Op_t& op) {
00120   typename graph_traits<Ad_graph_t>::edge_iterator  ei, e_end;
00121   for (tie (ei, e_end)= edges (adg); ei != e_end; ++ei)
00122     op (*ei, adg);
00123 }
00124 
00126 template <typename Ad_graph_t, typename Op_t>
00127 inline void for_all_edges (const Ad_graph_t& adg, Op_t& op) {
00128   typename graph_traits<Ad_graph_t>::edge_iterator  ei, e_end;
00129   for (tie (ei, e_end)= edges (adg); ei != e_end; ++ei)
00130     op (*ei, adg);
00131 }
00132 
00134 template <typename Ad_graph_t, typename Op_t>
00135 inline void for_all_in_edges (typename Ad_graph_t::vertex_descriptor v, 
00136                               Ad_graph_t& adg, const Op_t& op) {
00137   typename graph_traits<Ad_graph_t>::in_edge_iterator  iei, ie_end;
00138   for (tie (iei, ie_end)= in_edges (v, adg); iei != ie_end; ++iei)
00139     op (*iei, adg);
00140 }
00141 
00143 template <typename Ad_graph_t, typename Op_t>
00144 inline void for_all_out_edges (typename Ad_graph_t::vertex_descriptor v, 
00145                                Ad_graph_t& adg, const Op_t& op) {
00146   typename graph_traits<Ad_graph_t>::out_edge_iterator  oei, oe_end;
00147   for (tie (oei, oe_end)= out_edges (v, adg); oei != oe_end; ++oei)
00148     op (*oei, adg);
00149 }
00150 
00152 template <typename Ad_graph_t, typename Op_t>
00153 inline int sum_over_all_in_edges (typename Ad_graph_t::vertex_descriptor v, 
00154                                   Ad_graph_t& adg, const Op_t& op) {
00155   int value= 0;
00156   typename graph_traits<Ad_graph_t>::in_edge_iterator  iei, ie_end;
00157   for (tie (iei, ie_end)= in_edges (v, adg); iei != ie_end; ++iei)
00158     value+= op (*iei, adg);
00159   return value;
00160 }
00161 
00163 template <typename Ad_graph_t, typename Op_t>
00164 inline int sum_over_all_out_edges (typename Ad_graph_t::vertex_descriptor v, 
00165                                    const Ad_graph_t& adg, const Op_t& op) {
00166   int value= 0;
00167   typename graph_traits<Ad_graph_t>::out_edge_iterator  oei, oe_end;
00168   for (tie (oei, oe_end)= out_edges (v, adg); oei != oe_end; ++oei)
00169     value+= op (*oei, adg);
00170   return value;
00171 }
00172 
00174 template <typename Ad_graph_t>
00175 inline void successor_set (typename Ad_graph_t::vertex_descriptor v, 
00176                            const Ad_graph_t& adg, 
00177                            typename std::vector<typename Ad_graph_t::vertex_descriptor>& vec) {
00178   vec.resize (0); vec.reserve (out_degree (v, adg));
00179   typename graph_traits<Ad_graph_t>::out_edge_iterator  oei, oe_end;
00180   for (tie (oei, oe_end)= out_edges (v, adg); oei != oe_end; ++oei)
00181     vec.push_back (target (*oei, adg));
00182 }
00183 
00185 template <typename Ad_graph_t>
00186 inline void sorted_successor_set (typename Ad_graph_t::vertex_descriptor v, 
00187                                   const Ad_graph_t& adg, 
00188                                   typename std::vector<typename Ad_graph_t::vertex_descriptor>& vec) {
00189   successor_set (v, adg, vec);
00190   std::sort (vec.begin(), vec.end());
00191 }
00192 
00194 template <typename Ad_graph_t>
00195 inline void predecessor_set (typename Ad_graph_t::vertex_descriptor v, 
00196                              const Ad_graph_t& adg, 
00197                              typename std::vector<typename Ad_graph_t::vertex_descriptor>& vec) {
00198   vec.resize (0); vec.reserve (out_degree (v, adg));
00199   typename graph_traits<Ad_graph_t>::in_edge_iterator  iei, ie_end;
00200   for (tie (iei, ie_end)= in_edges (v, adg); iei != ie_end; ++iei)
00201     vec.push_back (source (*iei, adg));
00202 }
00203 
00205 template <typename Ad_graph_t>
00206 inline void sorted_predecessor_set (typename Ad_graph_t::vertex_descriptor v, 
00207                                     const Ad_graph_t& adg, 
00208                                     typename std::vector<typename Ad_graph_t::vertex_descriptor>& vec) {
00209   predecessor_set (v, adg, vec);
00210   std::sort (vec.begin(), vec.end());
00211 }
00212 
00214 bool reachable (const c_graph_t::vertex_t src,
00215                 const c_graph_t::vertex_t tgt,
00216                 c_graph_t& angelLCG);
00217 
00219 void vertex_upset (const c_graph_t::vertex_t v,
00220                    const c_graph_t& angelLCG,
00221                    vertex_set_t& upset);
00222 
00224 void vertex_downset (const c_graph_t::vertex_t v,
00225                      const c_graph_t& angelLCG,
00226                      vertex_set_t& downset);
00227 
00229 template <typename El_t>
00230 void unique_vector (std::vector<El_t>& v) {
00231   std::sort (v.begin(), v.end());
00232   typename vector<El_t>::iterator it= unique (v.begin(), v.end());
00233   v.resize (it-v.begin());
00234 }
00235 
00236 
00238 template <typename Ad_graph_t>
00239 inline void common_successors (typename Ad_graph_t::vertex_descriptor v, 
00240                                const Ad_graph_t& adg, 
00241                                typename std::vector<typename Ad_graph_t::vertex_descriptor>& vec) {
00242   typename graph_traits<Ad_graph_t>::out_edge_iterator  oei, oe_end;
00243   typename graph_traits<Ad_graph_t>::in_edge_iterator   iei, ie_end;
00244   for (tie (oei, oe_end)= out_edges (v, adg); oei != oe_end; ++oei)
00245     for (tie (iei, ie_end)= in_edges (target (*oei, adg), adg); iei != ie_end; ++iei)
00246       if (source (*iei, adg) != v)
00247         vec.push_back (source (*iei, adg));
00248   unique_vector (vec);
00249 }
00250 
00252 template <typename Ad_graph_t>
00253 inline void same_successors (typename Ad_graph_t::vertex_descriptor v, 
00254                              const Ad_graph_t& adg, 
00255                              typename std::vector<typename Ad_graph_t::vertex_descriptor>& vec) {
00256   typename graph_traits<Ad_graph_t>::out_edge_iterator      oei, oe_end;
00257   typename graph_traits<Ad_graph_t>::in_edge_iterator       iei, ie_end;
00258   typename std::vector<typename Ad_graph_t::vertex_descriptor>   sv, s;
00259  
00260   sorted_successor_set (v, adg, sv);
00261   for (tie (oei, oe_end)= out_edges (v, adg); oei != oe_end; ++oei)
00262     for (tie (iei, ie_end)= in_edges (target (*oei, adg), adg); iei != ie_end; ++iei)
00263       if (source (*iei, adg) != v) {
00264         sorted_successor_set (source (*iei, adg), adg, s);
00265         if (s == sv) vec.push_back (source (*iei, adg)); }
00266   unique_vector (vec);
00267 }
00268 
00270 template <typename Ad_graph_t>
00271 inline void common_predecessor (typename Ad_graph_t::vertex_descriptor v, 
00272                                 const Ad_graph_t& adg, 
00273                                 typename std::vector<typename Ad_graph_t::vertex_descriptor>& vec) {
00274   typename graph_traits<Ad_graph_t>::out_edge_iterator  oei, oe_end;
00275   typename graph_traits<Ad_graph_t>::in_edge_iterator   iei, ie_end;
00276   for (tie (iei, ie_end)= in_edges (v, adg); iei != ie_end; ++iei)
00277     for (tie (oei, oe_end)= out_edges (source (*iei, adg), adg); oei != oe_end; ++oei)
00278       if (target (*oei, adg) != v)
00279         vec.push_back (target (*oei, adg));
00280   unique_vector (vec);
00281 }
00282 
00284 template <typename Ad_graph_t>
00285 inline void same_predecessors (typename Ad_graph_t::vertex_descriptor v, 
00286                                const Ad_graph_t& adg, 
00287                                typename std::vector<typename Ad_graph_t::vertex_descriptor>& vec) {
00288   typename graph_traits<Ad_graph_t>::out_edge_iterator      oei, oe_end;
00289   typename graph_traits<Ad_graph_t>::in_edge_iterator       iei, ie_end;
00290   typename std::vector<typename Ad_graph_t::vertex_descriptor>   pv, p;
00291  
00292   sorted_predecessor_set (v, adg, pv);
00293   for (tie (iei, ie_end)= in_edges (v, adg); iei != ie_end; ++iei) 
00294     for (tie (oei, oe_end)= out_edges (source (*iei, adg), adg); oei != oe_end; ++oei) 
00295       if (target (*oei, adg) != v) {
00296         sorted_predecessor_set (target (*oei, adg), adg, p);
00297         if (p == pv) vec.push_back (target (*oei, adg)); }
00298   unique_vector (vec);
00299 }
00300 
00302 template <typename Ad_graph_t>
00303 inline void same_neighbors (typename Ad_graph_t::vertex_descriptor v, 
00304                             const Ad_graph_t& adg, 
00305                             typename std::vector<typename Ad_graph_t::vertex_descriptor>& vec) {
00306   typename std::vector<typename Ad_graph_t::vertex_descriptor> same_p, same_s;
00307   same_predecessors (v, adg, same_p); // same pred. as i
00308   same_successors (v, adg, same_s);
00309   vec.resize (std::max (same_p.size(), same_s.size()));
00310   typename std::vector<typename Ad_graph_t::vertex_descriptor>::iterator vend;
00311   vend= std::set_intersection (same_p.begin(), same_p.end(), same_s.begin(), same_s.end(), vec.begin());
00312   vec.resize (vend-vec.begin());
00313 }
00314 
00315 //                        Iterations
00316 // ===========================================================
00317 
00318 template<typename It_t, typename Op_t>
00319 std::ostream& write_iterators (std::ostream& stream, const std::string& s, 
00320                                It_t begin, It_t end, Op_t op) {
00321   stream << s << " = {";
00322   if (begin != end) op (stream, *begin++); 
00323   for (; begin != end; ++begin)
00324     stream << ", ", op (stream, *begin);
00325   stream << '}' << std::endl;
00326   return stream;
00327 }  
00328 
00329 //                      Others
00330 // ===========================================================
00331 
00332 // e is an edge of g1, same_egde return a pointer to 
00333 // the same edge (equal source and equal target) in g2 (or e_end)
00339 template <typename Ad_graph_t>
00340 inline typename graph_traits<Ad_graph_t>::edge_iterator
00341 same_edge (typename Ad_graph_t::edge_descriptor e,
00342            const Ad_graph_t& g1, const Ad_graph_t& g2) {
00343   typename graph_traits<Ad_graph_t>::edge_iterator ei, e_end;
00344   typename Ad_graph_t::vertex_descriptor s= source (e, g1), 
00345                                          t= target (e, g1);
00346   for (tie (ei, e_end)= edges (g2); ei != e_end; ++ei)
00347     if (source (*ei, g2) == s && target (*ei, g2) == t)
00348       return ei;
00349   return e_end; // not found
00350 }
00351 
00352 
00354 template <typename Ad_graph_t> 
00355 vertex_type_t vertex_type (typename Ad_graph_t::vertex_descriptor v, 
00356                            const Ad_graph_t& adg) {
00357   return adg.vertex_type (v); 
00358 }
00359 
00361 template <typename Ad_graph_t> 
00362 struct edge_equal_t : public std::binary_function<typename Ad_graph_t::edge_descriptor,
00363                                                   typename Ad_graph_t::edge_descriptor,bool> {
00364   const Ad_graph_t& g1;
00365   const Ad_graph_t& g2;
00367   edge_equal_t (const Ad_graph_t& _g1, const Ad_graph_t& _g2) : 
00368     g1 (_g1), g2 (_g2) {}
00370   bool operator() (typename Ad_graph_t::edge_descriptor e1,
00371                    typename Ad_graph_t::edge_descriptor e2) {
00372     typename Ad_graph_t::vertex_descriptor s1= source (e1, g1), s2= source (e2, g2);
00373     return s1 == s2 && target (e1, g1) == target (e2, g2);}
00374 };
00375 
00377 template <typename Ad_graph_t> 
00378 struct edge_less_t : public std::binary_function<typename Ad_graph_t::edge_descriptor,
00379                                             typename Ad_graph_t::edge_descriptor,bool> {
00380   const Ad_graph_t& g1;
00381   const Ad_graph_t& g2;
00383   edge_less_t (const Ad_graph_t& _g1, const Ad_graph_t& _g2) : 
00384     g1 (_g1), g2 (_g2) {}
00386   bool operator() (typename Ad_graph_t::edge_descriptor e1,
00387                    typename Ad_graph_t::edge_descriptor e2) {
00388     typename Ad_graph_t::vertex_descriptor s1= source (e1, g1), s2= source (e2, g2);
00389     return s1 < s2 || (s1 == s2 && target (e1, g1) < target (e2, g2));}
00390 };
00391 
00392 template <typename Ad_graph_t> 
00393 inline int count_parallel_edges (typename Ad_graph_t::edge_descriptor e, 
00394                                  const Ad_graph_t& g) {
00395   typename Ad_graph_t::vertex_descriptor s= source (e, g), t= target (e, g);
00396   typename graph_traits<Ad_graph_t>::out_edge_iterator oei, oe_end;
00397   int pe= 0;
00398   for (tie (oei, oe_end)= out_edges (s, g); oei != oe_end; oei++)
00399     if (target (*oei, g) == t) pe++;
00400   return pe;
00401 }
00402 
00404 c_graph_t::edge_t getEdge(unsigned int i,
00405                           unsigned int j,
00406                           const c_graph_t& angelLCG);
00407 
00408 // =====================================================
00409 // comparisons
00410 // =====================================================
00411 
00413 inline bool lex_greater (c_graph_t::edge_t e1, c_graph_t::edge_t e2,
00414                          const c_graph_t& cg) {
00415 
00416   c_graph_t::vertex_t s1= source (e1, cg), s2= source (e2, cg);
00417 
00418   return s1 > s2 || (s1 == s2 && target (e1, cg) >= target (e2, cg));
00419 
00420 }
00421 
00423 inline bool lex_less (c_graph_t::edge_t e1, c_graph_t::edge_t e2,
00424                       const c_graph_t& cg) {
00425 
00426   c_graph_t::vertex_t s1= source (e1, cg), s2= source (e2, cg);
00427 
00428   return s1 < s2 || (s1 == s2 && target (e1, cg) <= target (e2, cg));
00429 
00430 }
00431 
00433 inline bool inv_lex_greater (c_graph_t::edge_t e1, c_graph_t::edge_t e2,
00434                              const c_graph_t& cg) {
00435 
00436   c_graph_t::vertex_t s1= source (e1, cg), s2= source (e2, cg),
00437                       t1= target (e1, cg), t2= target (e2, cg); 
00438   return t1 > t2 || (t1 == t2 && s1 >= s2);
00439 }
00440 
00442 inline bool inv_lex_less (c_graph_t::edge_t e1, c_graph_t::edge_t e2,
00443                           const c_graph_t& cg) {
00444 
00445   c_graph_t::vertex_t s1= source (e1, cg), s2= source (e2, cg),
00446                       t1= target (e1, cg), t2= target (e2, cg);
00447   return t1 < t2 || (t1 == t2 && s1 <= s2); 
00448 }
00449 
00450 inline bool lex_greater (edge_bool_t eb1, edge_bool_t eb2, const c_graph_t& cg) {
00451 
00452   c_graph_t::edge_t   e1= eb1.first, e2= eb2.first;
00453   c_graph_t::vertex_t s1= source (e1, cg), s2= source (e2, cg), 
00454                        t1= target (e1, cg), t2= target (e2, cg); 
00455   bool                 f1= eb1.second, f2= eb2.second;
00456   c_graph_t::vertex_t j1= f1 ? t1 : s1, j2= f2 ? t2 : s2;
00457 
00458   // e1 is eliminated during vertex elimination of j1 (e2 resp.)
00459   if (j1 > j2) return true; else if (j1 < j2) return false;
00460 
00461   // prefer front elimination, rm 1
00462   if (f1 && !f2) return true; else if (!f1 && f2) return false;
00463   
00464   // f1==f2, start with front elimination
00465   if (f1) return s1 > s2; else return t1 > t2;
00466 }
00467 
00468 inline bool lex_less (edge_bool_t eb1, edge_bool_t eb2, const c_graph_t& cg) {
00469 
00470   c_graph_t::edge_t   e1= eb1.first, e2= eb2.first;
00471   c_graph_t::vertex_t s1= source (e1, cg), s2= source (e2, cg), 
00472                        t1= target (e1, cg), t2= target (e2, cg); 
00473   bool                 f1= eb1.second, f2= eb2.second;
00474   c_graph_t::vertex_t j1= f1 ? t1 : s1, j2= f2 ? t2 : s2;
00475 
00476   // e1 is eliminated during vertex elimination of j1 (e2 resp.)
00477   if (j1 < j2) return true; else if (j1 > j2) return false;
00478 
00479   // prefer front elimination, rm 1
00480   if (f1 && !f2) return true; else if (!f1 && f2) return false;
00481   
00482   // f1==f2, start with front elimination
00483   if (f1) return s1 < s2; else return t1 < t2;
00484 }
00485 
00486 bool lex_less_face (line_graph_t::face_t e1, line_graph_t::face_t e2,
00487                     const line_graph_t& lg);
00488 
00489 // to use lex_less_face with std::sort, see face_elimination_heuristic.cpp for an example
00490 class lex_less_face_line_t {
00491   const line_graph_t& lg;
00492 
00493 public:
00494   lex_less_face_line_t (const line_graph_t& g) : lg (g) {}
00495 
00496   bool operator() (const line_graph_t::face_t& e1,
00497                    const line_graph_t::face_t& e2) {
00498     return lex_less_face (e1, e2, lg); }
00499 };
00500 
00501 // same as lex_less_face_line_t, but for decreasing order in std::sort
00502 // it is supposed that faces do not occur twice, 
00503 // i.e. e1 != e2 iff (i,j,k)_1 != (i,j,k)_2,
00504 // so e1 > e2 iff not e1 < e2 
00505 class not_lex_less_face_line_t {
00506   const line_graph_t& lg;
00507 
00508 public:
00509   not_lex_less_face_line_t (const line_graph_t& g) : lg (g) {}
00510 
00511   bool operator() (const line_graph_t::face_t& e1,
00512                    const line_graph_t::face_t& e2) {
00513     return !lex_less_face (e1, e2, lg); }
00514 };
00515 
00516 // =====================================================
00517 // random number generators
00518 // =====================================================
00519 
00521 inline int random (int min, int max) {  
00522   return min + int (double (max-min+1)*rand() / (RAND_MAX+1.0)); }
00523 
00525 inline double random (double n) {
00526   return n*rand() / (RAND_MAX+1.0); }
00527 
00529 inline int random (int n) {
00530   return int (double (n)*rand() / (RAND_MAX+1.0)); }
00531 
00533 inline int random_high (int n, int exp= 2) {
00534   double tmp= rand() / (RAND_MAX+1.0);
00535   return int (double (n) * (1 - pow (tmp, exp))); }
00536 
00544 inline int random (const std::vector<double>& p) {
00545   size_t ps= p.size();
00546 #ifndef NDEBUG
00547   for (size_t j= 0; j < ps; j++)
00548     // assert (p[j] > 0.0 && p[j] <= 1.0);
00549     THROW_EXCEPT_MACRO (p[j] < 0.0 || p[j] > 1.0, consistency_exception, "p[i] not between 0 and 1");
00550   for (size_t j= 1; j < ps; j++)
00551     // assert (p[j-1] <= p[j]);
00552     THROW_EXCEPT_MACRO (p[j-1] > p[j], consistency_exception, "p[i] > p[i-1]");
00553   // assert (p[ps-1] == 1.0);
00554   THROW_EXCEPT_MACRO (p[ps-1] != 1.0, consistency_exception, "Last value must be 1");
00555 #endif
00556   double r= random (1.0);
00557   for (size_t j= 0; j < ps; j++)
00558     if (r < p[j]) return int (j);
00559   return int (ps);
00560 }
00561 
00562 
00563 // =====================================================
00564 // path lengths
00565 // =====================================================
00566 
00575 void in_out_path_lengths (const c_graph_t& cg,
00576                           std::vector<int>& vni, std::vector<int>& vli, 
00577                           std::vector<int>& vno, std::vector<int>& vlo);
00578 
00579 // =====================================================
00580 // find nodes in line graph that correspond to edge (i,j) in c-graph
00581 // =====================================================
00582 
00584 inline bool find_edge (int s, int t, const line_graph_t& lg, 
00585                        std::vector<line_graph_t::edge_t>& ev) {
00586   ev.resize (0);
00587   line_graph_t::const_evn_t evn= get(boost::vertex_name, lg);
00588   line_graph_t::ei_t        ei, eend;
00589   for (tie (ei, eend)= vertices (lg); ei != eend; ++ei) 
00590     if (evn[*ei].first == s && evn[*ei].second == t) ev.push_back (*ei);
00591   return !ev.empty();
00592 }
00593 
00594 // =====================================================
00595 // test whether c-/line graph is bi-/tri-partite
00596 // =====================================================
00597 
00599 inline bool is_bipartite (const c_graph_t& cg) {
00600   c_graph_t::ei_t     ei, e_end;
00601   for (tie(ei, e_end) = edges (cg); ei != e_end; ++ei)
00602     if (vertex_type (source (*ei, cg), cg) != independent 
00603         || vertex_type (target (*ei, cg), cg) != dependent)
00604       return false;
00605   return true;
00606 }
00607 
00609 inline bool is_tripartite (const line_graph_t& lg) {
00610   line_graph_t::fi_t     fi, f_end;
00611   for (tie(fi, f_end) = edges (lg); fi != f_end; ++fi)
00612     if (vertex_type (source (*fi, lg), lg) != independent 
00613         && vertex_type (target (*fi, lg), lg) != dependent)
00614       return false;
00615   return true;
00616 }
00617 
00618 // =====================================================
00619 // vertex properties
00620 // =====================================================
00621 
00623 void number_dependent_vertices (const c_graph_t& cg, std::vector<int>& v);
00624 
00626 void number_independent_vertices (const c_graph_t& cg, std::vector<int>& v);
00627 
00633 template <typename Ad_graph_t> 
00634 void reachable_vertices (const Ad_graph_t& adg, std::vector<bool>& rv) {
00635 
00636   typedef typename Ad_graph_t::vertex_descriptor                         vertex_t;
00637   typedef typename graph_traits<Ad_graph_t>::vertex_iterator      vi_t;
00638   typedef typename graph_traits<Ad_graph_t>::adjacency_iterator   ai_t;
00639 
00640   rv.resize (num_vertices (adg));
00641   std::fill (rv.begin(), rv.end(), false);
00642 
00643   typename std::queue<vertex_t> q;
00644   vi_t                          vi, v_end;
00645   int                           c;
00646   // all independent vertices are reachable and inserted into the queue
00647   for (tie(vi, v_end)= vertices(adg), c= 0; c < adg.x() && vi != v_end; ++c, ++vi) {
00648     rv[*vi]= true; q.push (*vi); }
00649 
00650   // search for reachable (intermediate and dependent) vertices
00651   while (!q.empty()) {
00652     vertex_t v= q.front();
00653     ai_t ai, a_end;
00654     for (tie(ai, a_end)= adjacent_vertices(v, adg); ai != a_end; ++ai)
00655       if (!rv[*ai]) {
00656         rv[*ai]= true; q.push (*ai); }
00657     q.pop(); }
00658 }       
00659 
00665 template <typename Ad_graph_t> 
00666 void relevant_vertices (const Ad_graph_t& adg, std::vector<bool>& rv) {
00667 
00668   typedef typename Ad_graph_t::vertex_descriptor               vertex_t;
00669   typedef typename graph_traits<Ad_graph_t>::vertex_iterator   vi_t;
00670   typedef typename graph_traits<Ad_graph_t>::in_edge_iterator  ie_t;
00671 
00672   rv.resize (num_vertices (adg));
00673   std::fill (rv.begin(), rv.end(), false);
00674 
00675   typename std::queue<vertex_t> q;
00676   // all dependent vertices are relevant and inserted into the queue
00677   for (size_t i= 0; i < adg.dependents.size(); i++) {
00678     vertex_t v= adg.dependents[i];
00679     rv[v]= true; q.push (v); }
00680 
00681   // search for relevant (intermediate and independent) vertices
00682   while (!q.empty()) {
00683     vertex_t v= q.front();
00684     ie_t     iei, ie_end;
00685     for (tie(iei, ie_end)= in_edges(v, adg); iei != ie_end; ++iei) {
00686       vertex_t vin= source (*iei, adg);
00687       if (!rv[vin]) {
00688         rv[vin]= true; q.push (vin); } }
00689     q.pop();  }
00690 }
00691 
00692 template <typename Neighbor_t>
00693 bool search_path (const std::vector<c_graph_t::vertex_t>& from, 
00694                   const std::vector<c_graph_t::vertex_t>& to, const Neighbor_t& n,
00695                   std::vector<c_graph_t::vertex_t>& path,
00696                   bool breadth_first= false);
00697 
00698 template <typename Neighbor_t>
00699 int maximal_paths (c_graph_t::vertex_t v, const Neighbor_t& nin, 
00700                    std::vector<std::vector<c_graph_t::vertex_t> >& paths);
00701 
00702 template <typename Neighbor_t>
00703 inline int minimal_in_out_degree (c_graph_t::vertex_t v, const Neighbor_t& nin) {
00704   std::vector<std::vector<c_graph_t::vertex_t> >    all_paths;
00705   return maximal_paths (v, nin, all_paths);
00706 }
00707 
00709 inline void minimal_markowitz_degree (const c_graph_t& cg, std::vector<int>& v) {
00710   v.resize (cg.v());
00711   predecessor_t<c_graph_t> pred (cg);
00712   successor_t<c_graph_t>   succ (cg);
00713   c_graph_t::vi_t          vi, v_end;
00714   for (tie (vi, v_end)= vertices (cg); vi != v_end; ++vi) {
00715     if (vertex_type (*vi, cg) == intermediate)
00716       v[*vi]= minimal_in_out_degree (*vi, pred) * minimal_in_out_degree (*vi, succ); }
00717 }
00718 
00720 inline int overall_minimal_markowitz_degree (const c_graph_t& cg) {
00721   std::vector<int> v;
00722   minimal_markowitz_degree (cg, v);
00723   return std::accumulate (v.begin(), v.end(), 0);
00724 }  
00725 
00726 
00727 // =====================================================
00728 // graph transformations
00729 // =====================================================
00730 
00732 void permutate_vertices (const c_graph_t& gin, const std::vector<c_graph_t::vertex_t>& p,
00733                          c_graph_t& gout);
00734 
00736 void independent_vertices_to_front (const c_graph_t& gin, 
00737                                     const std::vector<c_graph_t::vertex_t>& indeps,
00738                                     c_graph_t& gout);
00739 
00741 inline void put_unit_vertex_weight (line_graph_t& lg) {
00742   line_graph_t::ed_t  ed= get(boost::vertex_degree, lg);
00743   line_graph_t::ei_t  ei, eend;
00744   for (tie(ei, eend) = vertices (lg); ei != eend; ++ei) ed[*ei]= 1;
00745 }
00746 
00748 inline void put_unit_edge_weight (c_graph_t& cg) {
00749   c_graph_t::ew_t     ew= get(boost::edge_weight, cg);
00750   c_graph_t::ei_t     ei, eend;
00751   for (tie(ei, eend) = edges (cg); ei != eend; ++ei) ew[*ei]= 1;
00752 }
00753 
00755 int renumber_edges (c_graph_t& cg);
00756 
00757 // v2 take over the successors of v1
00758 // - v1 is a vertex of g1 and v2 is a vertex of g2
00759 // - each successor of v1 has an equivalent in g2
00760 //   such that the indices of both vertices differ by offset
00761 // - edge_number is read and updated
00762 // - useful to compose graphs, e.g. in stats2block
00763 //
00764 void take_over_successors (c_graph_t::vertex_t v1, c_graph_t::vertex_t v2, 
00765                            int offset, const c_graph_t& g1,  
00766                            int& edge_number, c_graph_t& g2);
00767 
00768 
00769 // -----------------------------------------------------
00770 // remove irrelevant and unreachable edges
00771 // -----------------------------------------------------
00772 //
00773 // remove_irrelevant_edges removes all in-edges of vertix 'i' if 'i' has no out-edges
00774 //   and continues, in this case, recursively with the predecessors of 'i'
00775 // remove_unreachable_edges removes all out-edges of vertix 'i' if 'i' has no in-edges
00776 //   and continues, in this case, recursively with the successors of 'i'
00777 // remove_edges does both
00778 // all functions return the number of removed edges
00779 // the set of removed edges is not complete, e.g. 'i' may have out-edges but no path to 
00780 //   dependent nodes
00781 //
00782 
00788 template <typename Ad_graph_t>
00789 int remove_irrelevant_edges (typename Ad_graph_t::vertex_descriptor i, 
00790                              Ad_graph_t& adg, bool fast= false) {
00791   typedef typename Ad_graph_t::vertex_descriptor               vertex_t;
00792   typedef typename graph_traits<Ad_graph_t>::in_edge_iterator  iei_t;
00793 
00794   if (fast) {
00795     int e= in_degree (i, adg);
00796     if (out_degree (i, adg) == 0) {
00797       clear_vertex (i, adg);
00798       return e; }
00799     else return 0; }
00800 
00801   int nre= 0; // number of removed edges
00802   typename std::queue<vertex_t> q;
00803   q.push (i);
00804 
00805   while (!q.empty()) {
00806     vertex_t v= q.front();
00807     if (out_degree (v, adg) == 0) {
00808       iei_t iei, ie_end;
00809       for (tie (iei, ie_end)= in_edges (v, adg); iei != ie_end; ) {
00810         q.push (source (*iei, adg));
00811         remove_edge (*iei, adg); 
00812         nre++;
00813         tie (iei, ie_end)= in_edges (v, adg); // now without first in-edge
00814       }
00815     }
00816     q.pop(); }
00817   return nre;
00818 }
00819 
00825 template <typename Ad_graph_t>
00826 int remove_unreachable_edges (typename Ad_graph_t::vertex_descriptor i, 
00827                               Ad_graph_t& adg, bool fast= false) {
00828   typedef typename Ad_graph_t::vertex_descriptor                  vertex_t;
00829   typedef typename graph_traits<Ad_graph_t>::out_edge_iterator    oei_t;
00830 
00831   if (fast) {
00832     int e= out_degree (i, adg);
00833     if (in_degree (i, adg) == 0) {
00834       clear_vertex (i, adg);
00835       return e; }
00836     else return 0; }
00837 
00838   int nre= 0; // number of removed edges
00839   typename std::queue<vertex_t> q;
00840   q.push (i);
00841 
00842   while (!q.empty()) {
00843     vertex_t v= q.front();
00844     if (in_degree (v, adg) == 0) {
00845       oei_t oei, oe_end;
00846       for (tie (oei, oe_end)= out_edges (v, adg); oei != oe_end; ) {
00847         q.push (target (*oei, adg));
00848         remove_edge (oei, adg); // iterator is faster than edge itself
00849         nre++;
00850         tie (oei, oe_end)= out_edges (v, adg); // now without first out-edge
00851       }
00852     }
00853     q.pop(); }
00854   return nre;
00855 }
00856 
00858 template <typename Ad_graph_t>
00859 inline int remove_edges (typename Ad_graph_t::vertex_descriptor i, 
00860                          Ad_graph_t& adg) {
00861   return remove_irrelevant_edges (i, adg)
00862          + remove_unreachable_edges (i, adg);
00863 }
00864 
00865 // -----------------------------------------------------
00866 // clear graph
00867 // -----------------------------------------------------
00868 
00869 template <typename vertex_t>
00870 struct dec_greater : public std::unary_function<vertex_t, void> {
00871   vertex_t vc;
00872   dec_greater (vertex_t _vc) : vc (_vc) {}
00873   void operator() (vertex_t& v) {if (v > vc) v--;}
00874 };
00875 
00876 // clear_graph is member function of c_graph_t and line_graph_t either
00877 
00878 // -----------------------------------------------------
00879 // some preprocessing removals
00880 // -----------------------------------------------------
00881 
00883 int remove_hoisting_vertices (c_graph_t& cg);
00884 
00891 void remove_parallel_edges (c_graph_t& cg);
00892 
00894 void remove_trivial_edges (c_graph_t& cg);
00895 
00897 template <class operand_t>
00898 struct empty_operator_t {
00899   void operator() (const operand_t&) {}
00900   void operator() (operand_t&) {}
00901 };
00902 
00904 inline size_t block_begin (size_t i, size_t p, size_t n) {
00905   return i * (n/p) + std::min (i, n%p); }
00906 
00907 // =====================================================
00908 // Functions for simulated annealing for partial accumulation (scarcity exploitation)
00909 // =====================================================
00910 
00914 double gen_prob();
00915 
00920 unsigned int chooseTarget_sa(std::vector<double>& deltaE);
00921 
00922 int chooseEdgeElimRandomly(std::vector<double>& deltaE);
00923 int chooseEdgeElimRandomlyGreedy(std::vector<double>& deltaE);
00924 
00925 } // namespace angel
00926 
00927 
00928 #endif  // _angel_tools_include_
00929 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines