angel
mercurial changeset:
|
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