|
QSapecNG
|
|
QSapecNG
|
00001 /* 00002 SapecNG - Next Generation Symbolic Analysis Program for Electric Circuit 00003 Copyright (C) 2009, Michele Caini 00004 00005 This program is free software: you can redistribute it and/or modify 00006 it under the terms of the GNU General Public License as published by 00007 the Free Software Foundation, either version 3 of the License, or 00008 (at your option) any later version. 00009 00010 This program is distributed in the hope that it will be useful, 00011 but WITHOUT ANY WARRANTY; without even the implied warranty of 00012 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00013 GNU General Public License for more details. 00014 00015 You should have received a copy of the GNU General Public License 00016 along with this program. If not, see <http://www.gnu.org/licenses/>. 00017 */ 00018 00019 00020 // Two Graphs Common Spanning Trees Algorithm 00021 00022 #ifndef MRT_H 00023 #define MRT_H 00024 00025 00026 #include <boost/config.hpp> 00027 00028 #include <boost/bimap.hpp> 00029 #include <boost/type_traits.hpp> 00030 #include <boost/concept/requires.hpp> 00031 #include <boost/graph/graph_traits.hpp> 00032 #include <boost/graph/undirected_dfs.hpp> 00033 #include <boost/graph/connected_components.hpp> 00034 #include <boost/graph/filtered_graph.hpp> 00035 #include <vector> 00036 #include <stack> 00037 #include <map> 00038 00039 00040 namespace boost 00041 { 00042 00043 00044 namespace detail { 00045 00046 00047 template 00048 < 00049 class TreeMap, 00050 class PredMap, 00051 class DistMap, 00052 class LowMap, 00053 class Buffer 00054 > 00055 struct bridges_visitor: public default_dfs_visitor 00056 { 00057 bridges_visitor( 00058 TreeMap tree, 00059 PredMap pred, 00060 DistMap dist, 00061 LowMap low, 00062 Buffer& buffer 00063 ): tree_(tree), pred_(pred), dist_(dist), low_(low), buffer_(buffer) 00064 { num_ = -1; } 00065 00066 template <class Vertex, class Graph> 00067 void initialize_vertex(const Vertex& u, const Graph& g) 00068 { 00069 put(pred_, u, u); 00070 put(dist_, u, -1); 00071 } 00072 00073 template <class Vertex, class Graph> 00074 void discover_vertex(const Vertex& u, const Graph& g) 00075 { 00076 put(dist_, u, ++num_); 00077 put(low_, u, get(dist_, u)); 00078 } 00079 00080 template <class Edge, class Graph> 00081 void tree_edge(const Edge& e, const Graph& g) 00082 { 00083 put(pred_, target(e, g), source(e, g)); 00084 put(tree_, target(e, g), e); 00085 } 00086 00087 template <class Edge, class Graph> 00088 void back_edge(const Edge& e, const Graph& g) 00089 { 00090 put(low_, source(e, g), 00091 std::min(get(low_, source(e, g)), get(dist_, target(e, g)))); 00092 } 00093 00094 template <class Vertex, class Graph> 00095 void finish_vertex(const Vertex& u, const Graph& g) 00096 { 00097 Vertex parent = get(pred_, u); 00098 if(get(low_, u) > get(dist_, parent)) 00099 buffer_.push(get(tree_, u)); 00100 put(low_, parent, 00101 std::min(get(low_, parent), get(low_, u))); 00102 } 00103 00104 TreeMap tree_; 00105 PredMap pred_; 00106 DistMap dist_; 00107 LowMap low_; 00108 Buffer& buffer_; 00109 int num_; 00110 }; 00111 00112 00113 template <class Buffer> 00114 struct cycle_finder: public base_visitor< cycle_finder<Buffer> > 00115 { 00116 typedef on_back_edge event_filter; 00117 cycle_finder(): buffer_(0) { } 00118 cycle_finder(Buffer* buffer) 00119 : buffer_(buffer) { } 00120 template <class Edge, class Graph> 00121 void operator()(const Edge& e, const Graph& g) 00122 { 00123 if(buffer_) 00124 buffer_->push(e); 00125 } 00126 Buffer* buffer_; 00127 }; 00128 00129 00130 template <class DeletedMap> 00131 struct deleted_edge_status 00132 { 00133 deleted_edge_status() { } 00134 deleted_edge_status(DeletedMap map): map_(map) { } 00135 template <class Edge> 00136 bool operator()(const Edge& e) const 00137 { return (!get(map_, e)); } 00138 DeletedMap map_; 00139 }; 00140 00141 00142 template <class InLMap> 00143 struct inL_edge_status 00144 { 00145 inL_edge_status() { } 00146 inL_edge_status(InLMap map): map_(map) { } 00147 template <class Edge> 00148 bool operator()(const Edge& e) const 00149 { return get(map_, e); } 00150 InLMap map_; 00151 }; 00152 00153 00154 template < 00155 class Graph, 00156 class Func, 00157 class Seq, 00158 class Map 00159 > 00160 void rec_mrt_two_graphs_common_spanning_trees 00161 ( 00162 const Graph& iG, 00163 bimap< 00164 bimaps::set_of<int>, 00165 bimaps::set_of< typename graph_traits<Graph>::edge_descriptor > 00166 > iG_bimap, 00167 Map aiG_inL, 00168 Map diG, 00169 const Graph& vG, 00170 bimap< 00171 bimaps::set_of<int>, 00172 bimaps::set_of< typename graph_traits<Graph>::edge_descriptor > 00173 > vG_bimap, 00174 Map avG_inL, 00175 Map dvG, 00176 Func func, 00177 Seq inL 00178 ) 00179 { 00180 typedef graph_traits<Graph> GraphTraits; 00181 00182 typedef typename GraphTraits::vertex_descriptor vertex_descriptor; 00183 typedef typename GraphTraits::edge_descriptor edge_descriptor; 00184 00185 typedef typename Seq::size_type seq_size_type; 00186 00187 int edges = num_vertices(iG) - 1; 00188 // 00189 // Using (edges != 0) condition drives to accidental non-tree 00190 // ((V-1+1)-fake-tree, named here fat-tree) submission. 00191 // Remove this condition acts as a workaround to the fat-trees problem. 00192 // Please do not add that condition to improve performance. 00193 // 00194 // Here previous (wrong) guard is presented: 00195 // for(seq_size_type i = 0; (i < inL.size()) && (edges != 0); ++i) 00196 // 00197 { 00198 for(seq_size_type i = 0; i < inL.size(); ++i) 00199 if(inL[i]) 00200 --edges; 00201 00202 if(edges < 0) 00203 return; 00204 } 00205 00206 bool is_tree = (edges == 0); 00207 if(is_tree) { 00208 func(inL); 00209 } else { 00210 std::map<vertex_descriptor, default_color_type> vertex_color; 00211 std::map<edge_descriptor, default_color_type> edge_color; 00212 00213 std::stack<edge_descriptor> iG_buf, vG_buf; 00214 bool found = false; 00215 00216 seq_size_type m; 00217 for(seq_size_type j = 0; j < inL.size() && !found; ++j) { 00218 if(!inL[j] 00219 && !get(diG, iG_bimap.left.at(j)) 00220 && !get(dvG, vG_bimap.left.at(j))) 00221 { 00222 put(aiG_inL, iG_bimap.left.at(j), true); 00223 put(avG_inL, vG_bimap.left.at(j), true); 00224 00225 undirected_dfs( 00226 make_filtered_graph(iG, 00227 detail::inL_edge_status< associative_property_map< 00228 std::map<edge_descriptor, bool> > >(aiG_inL)), 00229 make_dfs_visitor( 00230 detail::cycle_finder< std::stack<edge_descriptor> > (&iG_buf)), 00231 associative_property_map< 00232 std::map<vertex_descriptor, default_color_type> >(vertex_color), 00233 associative_property_map< 00234 std::map<edge_descriptor, default_color_type> >(edge_color) 00235 ); 00236 undirected_dfs( 00237 make_filtered_graph(vG, 00238 detail::inL_edge_status< associative_property_map< 00239 std::map<edge_descriptor, bool> > >(avG_inL)), 00240 make_dfs_visitor( 00241 detail::cycle_finder< std::stack<edge_descriptor> > (&vG_buf)), 00242 associative_property_map< 00243 std::map<vertex_descriptor, default_color_type> >(vertex_color), 00244 associative_property_map< 00245 std::map<edge_descriptor, default_color_type> >(edge_color) 00246 ); 00247 00248 if(iG_buf.empty() && vG_buf.empty()) { 00249 inL[j] = true; 00250 found = true; 00251 m = j; 00252 } else { 00253 while(!iG_buf.empty()) iG_buf.pop(); 00254 while(!vG_buf.empty()) vG_buf.pop(); 00255 put(aiG_inL, iG_bimap.left.at(j), false); 00256 put(avG_inL, vG_bimap.left.at(j), false); 00257 } 00258 } 00259 } 00260 00261 if(found) { 00262 00263 std::stack<edge_descriptor> iG_buf_copy, vG_buf_copy; 00264 for(seq_size_type j = 0; j < inL.size(); ++j) { 00265 if(!inL[j] 00266 && !get(diG, iG_bimap.left.at(j)) 00267 && !get(dvG, vG_bimap.left.at(j))) 00268 { 00269 00270 put(aiG_inL, iG_bimap.left.at(j), true); 00271 put(avG_inL, vG_bimap.left.at(j), true); 00272 00273 undirected_dfs( 00274 make_filtered_graph(iG, 00275 detail::inL_edge_status< associative_property_map< 00276 std::map<edge_descriptor, bool> > >(aiG_inL)), 00277 make_dfs_visitor( 00278 detail::cycle_finder< std::stack<edge_descriptor> > (&iG_buf)), 00279 associative_property_map< 00280 std::map<vertex_descriptor, default_color_type> >(vertex_color), 00281 associative_property_map< 00282 std::map<edge_descriptor, default_color_type> >(edge_color) 00283 ); 00284 undirected_dfs( 00285 make_filtered_graph(vG, 00286 detail::inL_edge_status< associative_property_map< 00287 std::map<edge_descriptor, bool> > >(avG_inL)), 00288 make_dfs_visitor( 00289 detail::cycle_finder< std::stack<edge_descriptor> > (&vG_buf)), 00290 associative_property_map< 00291 std::map<vertex_descriptor, default_color_type> >(vertex_color), 00292 associative_property_map< 00293 std::map<edge_descriptor, default_color_type> >(edge_color) 00294 ); 00295 00296 if(!iG_buf.empty() || !vG_buf.empty()) { 00297 while(!iG_buf.empty()) iG_buf.pop(); 00298 while(!vG_buf.empty()) vG_buf.pop(); 00299 put(diG, iG_bimap.left.at(j), true); 00300 put(dvG, vG_bimap.left.at(j), true); 00301 iG_buf_copy.push(iG_bimap.left.at(j)); 00302 vG_buf_copy.push(vG_bimap.left.at(j)); 00303 } 00304 00305 put(aiG_inL, iG_bimap.left.at(j), false); 00306 put(avG_inL, vG_bimap.left.at(j), false); 00307 } 00308 } 00309 00310 // REC_MRT 00311 detail::rec_mrt_two_graphs_common_spanning_trees<Graph, Func, Seq, Map> 00312 (iG, iG_bimap, aiG_inL, diG, vG, vG_bimap, aiG_inL, dvG, func, inL); 00313 00314 while(!iG_buf_copy.empty()) { 00315 put(diG, iG_buf_copy.top(), false); 00316 put(dvG, vG_bimap.left.at( 00317 iG_bimap.right.at(iG_buf_copy.top())), false); 00318 iG_buf_copy.pop(); 00319 } 00320 while(!vG_buf_copy.empty()) { 00321 put(dvG, vG_buf_copy.top(), false); 00322 put(diG, iG_bimap.left.at( 00323 vG_bimap.right.at(vG_buf_copy.top())), false); 00324 vG_buf_copy.pop(); 00325 } 00326 00327 inL[m] = false; 00328 put(aiG_inL, iG_bimap.left.at(m), false); 00329 put(avG_inL, vG_bimap.left.at(m), false); 00330 00331 put(diG, iG_bimap.left.at(m), true); 00332 put(dvG, vG_bimap.left.at(m), true); 00333 00334 std::map<vertex_descriptor, edge_descriptor> tree_map; 00335 std::map<vertex_descriptor, vertex_descriptor> pred_map; 00336 std::map<vertex_descriptor, int> dist_map, low_map; 00337 00338 detail::bridges_visitor< 00339 associative_property_map< 00340 std::map<vertex_descriptor, edge_descriptor> 00341 >, 00342 associative_property_map< 00343 std::map<vertex_descriptor, vertex_descriptor> 00344 >, 00345 associative_property_map< std::map<vertex_descriptor, int> >, 00346 associative_property_map< std::map<vertex_descriptor, int> >, 00347 std::stack<edge_descriptor> 00348 > 00349 iG_vis( 00350 associative_property_map< 00351 std::map< vertex_descriptor, edge_descriptor> >(tree_map), 00352 associative_property_map< 00353 std::map< vertex_descriptor, vertex_descriptor> >(pred_map), 00354 associative_property_map< 00355 std::map< vertex_descriptor, int> >(dist_map), 00356 associative_property_map< 00357 std::map< vertex_descriptor, int> >(low_map), 00358 iG_buf 00359 ), 00360 vG_vis( 00361 associative_property_map< 00362 std::map< vertex_descriptor, edge_descriptor> >(tree_map), 00363 associative_property_map< 00364 std::map< vertex_descriptor, vertex_descriptor> >(pred_map), 00365 associative_property_map< 00366 std::map< vertex_descriptor, int> >(dist_map), 00367 associative_property_map< 00368 std::map< vertex_descriptor, int> >(low_map), 00369 vG_buf 00370 ); 00371 00372 undirected_dfs(make_filtered_graph(iG, 00373 detail::deleted_edge_status< associative_property_map< 00374 std::map<edge_descriptor, bool> > >(diG)), 00375 iG_vis, 00376 associative_property_map< 00377 std::map<vertex_descriptor, default_color_type> >(vertex_color), 00378 associative_property_map< 00379 std::map<edge_descriptor, default_color_type> >(edge_color) 00380 ); 00381 undirected_dfs(make_filtered_graph(vG, 00382 detail::deleted_edge_status< associative_property_map< 00383 std::map<edge_descriptor, bool> > >(dvG)), 00384 vG_vis, 00385 associative_property_map< 00386 std::map<vertex_descriptor, default_color_type> >(vertex_color), 00387 associative_property_map< 00388 std::map<edge_descriptor, default_color_type> >(edge_color) 00389 ); 00390 00391 found = false; 00392 std::stack<edge_descriptor> iG_buf_tmp, vG_buf_tmp; 00393 while(!iG_buf.empty() && !found) { 00394 if(!inL[iG_bimap.right.at(iG_buf.top())]) { 00395 put(aiG_inL, iG_buf.top(), true); 00396 put(avG_inL, vG_bimap.left.at( 00397 iG_bimap.right.at(iG_buf.top())), true); 00398 00399 undirected_dfs( 00400 make_filtered_graph(iG, 00401 detail::inL_edge_status< associative_property_map< 00402 std::map<edge_descriptor, bool> > >(aiG_inL)), 00403 make_dfs_visitor( 00404 detail::cycle_finder< 00405 std::stack<edge_descriptor> > (&iG_buf_tmp)), 00406 associative_property_map< 00407 std::map< 00408 vertex_descriptor, default_color_type> >(vertex_color), 00409 associative_property_map< 00410 std::map<edge_descriptor, default_color_type> >(edge_color) 00411 ); 00412 undirected_dfs( 00413 make_filtered_graph(vG, 00414 detail::inL_edge_status< associative_property_map< 00415 std::map<edge_descriptor, bool> > >(avG_inL)), 00416 make_dfs_visitor( 00417 detail::cycle_finder< 00418 std::stack<edge_descriptor> > (&vG_buf_tmp)), 00419 associative_property_map< 00420 std::map< 00421 vertex_descriptor, default_color_type> >(vertex_color), 00422 associative_property_map< 00423 std::map<edge_descriptor, default_color_type> >(edge_color) 00424 ); 00425 00426 if(!iG_buf_tmp.empty() || !vG_buf_tmp.empty()) { 00427 found = true; 00428 } else { 00429 while(!iG_buf_tmp.empty()) iG_buf_tmp.pop(); 00430 while(!vG_buf_tmp.empty()) vG_buf_tmp.pop(); 00431 iG_buf_copy.push(iG_buf.top()); 00432 } 00433 00434 put(aiG_inL, iG_buf.top(), false); 00435 put(avG_inL, vG_bimap.left.at( 00436 iG_bimap.right.at(iG_buf.top())), false); 00437 } 00438 iG_buf.pop(); 00439 } 00440 while(!vG_buf.empty() && !found) { 00441 if(!inL[vG_bimap.right.at(vG_buf.top())]) { 00442 put(avG_inL, vG_buf.top(), true); 00443 put(aiG_inL, iG_bimap.left.at( 00444 vG_bimap.right.at(vG_buf.top())), true); 00445 00446 undirected_dfs( 00447 make_filtered_graph(iG, 00448 detail::inL_edge_status< associative_property_map< 00449 std::map<edge_descriptor, bool> > >(aiG_inL)), 00450 make_dfs_visitor( 00451 detail::cycle_finder< 00452 std::stack<edge_descriptor> > (&iG_buf_tmp)), 00453 associative_property_map< 00454 std::map< 00455 vertex_descriptor, default_color_type> >(vertex_color), 00456 associative_property_map< 00457 std::map<edge_descriptor, default_color_type> >(edge_color) 00458 ); 00459 undirected_dfs( 00460 make_filtered_graph(vG, 00461 detail::inL_edge_status< associative_property_map< 00462 std::map<edge_descriptor, bool> > >(avG_inL)), 00463 make_dfs_visitor( 00464 detail::cycle_finder< 00465 std::stack<edge_descriptor> > (&vG_buf_tmp)), 00466 associative_property_map< 00467 std::map< 00468 vertex_descriptor, default_color_type> >(vertex_color), 00469 associative_property_map< 00470 std::map<edge_descriptor, default_color_type> >(edge_color) 00471 ); 00472 00473 if(!iG_buf_tmp.empty() || !vG_buf_tmp.empty()) { 00474 found = true; 00475 } else { 00476 while(!iG_buf_tmp.empty()) iG_buf_tmp.pop(); 00477 while(!vG_buf_tmp.empty()) vG_buf_tmp.pop(); 00478 vG_buf_copy.push(vG_buf.top()); 00479 } 00480 00481 put(avG_inL, vG_buf.top(), false); 00482 put(aiG_inL, iG_bimap.left.at( 00483 vG_bimap.right.at(vG_buf.top())), false); 00484 } 00485 vG_buf.pop(); 00486 } 00487 00488 if(!found) { 00489 00490 while(!iG_buf_copy.empty()) { 00491 inL[iG_bimap.right.at(iG_buf_copy.top())] = true; 00492 put(aiG_inL, iG_buf_copy.top(), true); 00493 put(avG_inL, vG_bimap.left.at( 00494 iG_bimap.right.at(iG_buf_copy.top())), true); 00495 iG_buf.push(iG_buf_copy.top()); 00496 iG_buf_copy.pop(); 00497 } 00498 while(!vG_buf_copy.empty()) { 00499 inL[vG_bimap.right.at(vG_buf_copy.top())] = true; 00500 put(avG_inL, vG_buf_copy.top(), true); 00501 put(aiG_inL, iG_bimap.left.at( 00502 vG_bimap.right.at(vG_buf_copy.top())), true); 00503 vG_buf.push(vG_buf_copy.top()); 00504 vG_buf_copy.pop(); 00505 } 00506 00507 // REC_MRT 00508 detail::rec_mrt_two_graphs_common_spanning_trees< 00509 Graph, Func, Seq, Map> 00510 (iG, iG_bimap, aiG_inL, diG, vG, vG_bimap, aiG_inL, dvG, func, inL); 00511 00512 while(!iG_buf.empty()) { 00513 inL[iG_bimap.right.at(iG_buf.top())] = false; 00514 put(aiG_inL, iG_buf.top(), false); 00515 put(avG_inL, vG_bimap.left.at( 00516 iG_bimap.right.at(iG_buf.top())), false); 00517 iG_buf.pop(); 00518 } 00519 while(!vG_buf.empty()) { 00520 inL[vG_bimap.right.at(vG_buf.top())] = false; 00521 put(avG_inL, vG_buf.top(), false); 00522 put(aiG_inL, iG_bimap.left.at( 00523 vG_bimap.right.at(vG_buf.top())), false); 00524 vG_buf.pop(); 00525 } 00526 00527 } 00528 00529 put(diG, iG_bimap.left.at(m), false); 00530 put(dvG, vG_bimap.left.at(m), false); 00531 00532 } 00533 } 00534 } 00535 00536 } // namespace detail 00537 00538 00539 00540 template <class Coll, class Seq> 00541 struct tree_collector 00542 { 00543 00544 public: 00545 BOOST_CONCEPT_ASSERT((BackInsertionSequence<Coll>)); 00546 BOOST_CONCEPT_ASSERT((RandomAccessContainer<Seq>)); 00547 BOOST_CONCEPT_ASSERT((CopyConstructible<Seq>)); 00548 00549 typedef typename Coll::value_type coll_value_type; 00550 typedef typename Seq::value_type seq_value_type; 00551 00552 BOOST_STATIC_ASSERT((is_same<coll_value_type, Seq>::value)); 00553 BOOST_STATIC_ASSERT((is_same<seq_value_type, bool>::value)); 00554 00555 tree_collector(Coll& seqs): seqs_(seqs) { } 00556 00557 inline void operator()(Seq seq) 00558 { seqs_.push_back(seq); } 00559 00560 private: 00561 Coll& seqs_; 00562 00563 }; 00564 00565 00566 00567 template < 00568 class Graph, 00569 class Order, 00570 class Func, 00571 class Seq 00572 > 00573 BOOST_CONCEPT_REQUIRES( 00574 ((RandomAccessContainer<Order>)) 00575 ((IncidenceGraphConcept<Graph>)) 00576 ((UnaryFunction<Func, void, Seq>)) 00577 ((Mutable_RandomAccessContainer<Seq>)) 00578 ((VertexAndEdgeListGraphConcept<Graph>)), 00579 (void) 00580 ) 00581 mrt_two_graphs_common_spanning_trees 00582 ( 00583 const Graph& iG, 00584 Order iG_map, 00585 const Graph& vG, 00586 Order vG_map, 00587 Func func, 00588 Seq inL 00589 ) 00590 { 00591 typedef graph_traits<Graph> GraphTraits; 00592 00593 typedef typename GraphTraits::directed_category directed_category; 00594 typedef typename GraphTraits::vertex_descriptor vertex_descriptor; 00595 typedef typename GraphTraits::edge_descriptor edge_descriptor; 00596 00597 typedef typename GraphTraits::edges_size_type edges_size_type; 00598 typedef typename GraphTraits::edge_iterator edge_iterator; 00599 00600 typedef typename Seq::const_iterator seq_const_iterator; 00601 typedef typename Seq::difference_type seq_diff_type; 00602 typedef typename Seq::value_type seq_value_type; 00603 typedef typename Seq::size_type seq_size_type; 00604 typedef typename Seq::iterator seq_iterator; 00605 00606 typedef typename Order::const_iterator order_const_iterator; 00607 typedef typename Order::difference_type order_diff_type; 00608 typedef typename Order::value_type order_value_type; 00609 typedef typename Order::size_type order_size_type; 00610 typedef typename Order::iterator order_iterator; 00611 00612 BOOST_STATIC_ASSERT((is_same<order_value_type, edge_descriptor>::value)); 00613 BOOST_CONCEPT_ASSERT((Convertible<order_size_type, edges_size_type>)); 00614 00615 BOOST_CONCEPT_ASSERT((Convertible<seq_size_type, edges_size_type>)); 00616 BOOST_STATIC_ASSERT((is_same<seq_value_type, bool>::value)); 00617 00618 BOOST_STATIC_ASSERT((is_same<directed_category, undirected_tag>::value)); 00619 00620 if(num_vertices(iG) != num_vertices(vG)) 00621 return; 00622 00623 if(inL.size() != num_edges(iG) 00624 || inL.size() != num_edges(vG)) 00625 return; 00626 00627 if(iG_map.size() != num_edges(iG) 00628 || vG_map.size() != num_edges(vG)) 00629 return; 00630 00631 typedef bimaps::bimap< 00632 bimaps::set_of< int >, 00633 bimaps::set_of< order_value_type > 00634 > bimap_type; 00635 typedef typename bimap_type::value_type bimap_value; 00636 00637 bimap_type iG_bimap, vG_bimap; 00638 for(order_size_type i = 0; i < iG_map.size(); ++i) 00639 iG_bimap.insert(bimap_value(i, iG_map[i])); 00640 for(order_size_type i = 0; i < vG_map.size(); ++i) 00641 vG_bimap.insert(bimap_value(i, vG_map[i])); 00642 00643 edge_iterator current, last; 00644 tie(current, last) = edges(iG); 00645 for(; current != last; ++current) 00646 if(iG_bimap.right.find(*current) == iG_bimap.right.end()) 00647 return; 00648 tie(current, last) = edges(vG); 00649 for(; current != last; ++current) 00650 if(vG_bimap.right.find(*current) == vG_bimap.right.end()) 00651 return; 00652 00653 std::stack<edge_descriptor> iG_buf, vG_buf; 00654 00655 std::map<vertex_descriptor, edge_descriptor> tree_map; 00656 std::map<vertex_descriptor, vertex_descriptor> pred_map; 00657 std::map<vertex_descriptor, int> dist_map, low_map; 00658 00659 detail::bridges_visitor< 00660 associative_property_map< 00661 std::map<vertex_descriptor, edge_descriptor> 00662 >, 00663 associative_property_map< 00664 std::map<vertex_descriptor, vertex_descriptor> 00665 >, 00666 associative_property_map< std::map<vertex_descriptor, int> >, 00667 associative_property_map< std::map<vertex_descriptor, int> >, 00668 std::stack<edge_descriptor> 00669 > 00670 iG_vis( 00671 associative_property_map< 00672 std::map< vertex_descriptor, edge_descriptor> >(tree_map), 00673 associative_property_map< 00674 std::map< vertex_descriptor, vertex_descriptor> >(pred_map), 00675 associative_property_map<std::map< vertex_descriptor, int> >(dist_map), 00676 associative_property_map<std::map< vertex_descriptor, int> >(low_map), 00677 iG_buf 00678 ), 00679 vG_vis( 00680 associative_property_map< 00681 std::map< vertex_descriptor, edge_descriptor> >(tree_map), 00682 associative_property_map< 00683 std::map< vertex_descriptor, vertex_descriptor> >(pred_map), 00684 associative_property_map<std::map< vertex_descriptor, int> >(dist_map), 00685 associative_property_map<std::map< vertex_descriptor, int> >(low_map), 00686 vG_buf 00687 ); 00688 00689 std::map<vertex_descriptor, default_color_type> vertex_color; 00690 std::map<edge_descriptor, default_color_type> edge_color; 00691 00692 undirected_dfs(iG, iG_vis, 00693 associative_property_map< 00694 std::map<vertex_descriptor, default_color_type> >(vertex_color), 00695 associative_property_map< 00696 std::map<edge_descriptor, default_color_type> >(edge_color) 00697 ); 00698 undirected_dfs(vG, vG_vis, 00699 associative_property_map< 00700 std::map<vertex_descriptor, default_color_type> >(vertex_color), 00701 associative_property_map< 00702 std::map<edge_descriptor, default_color_type> >(edge_color) 00703 ); 00704 00705 while(!iG_buf.empty()) { 00706 inL[iG_bimap.right.at(iG_buf.top())] = true; 00707 iG_buf.pop(); 00708 } 00709 while(!vG_buf.empty()) { 00710 inL[vG_bimap.right.at(vG_buf.top())] = true; 00711 vG_buf.pop(); 00712 } 00713 00714 std::map<edge_descriptor, bool> iG_inL, vG_inL; 00715 associative_property_map< std::map<edge_descriptor, bool> > 00716 aiG_inL(iG_inL), avG_inL(vG_inL); 00717 00718 for(seq_size_type i = 0; i < inL.size(); ++i) 00719 { 00720 if(inL[i]) { 00721 put(aiG_inL, iG_bimap.left.at(i), true); 00722 put(avG_inL, vG_bimap.left.at(i), true); 00723 } else { 00724 put(aiG_inL, iG_bimap.left.at(i), false); 00725 put(avG_inL, vG_bimap.left.at(i), false); 00726 } 00727 } 00728 00729 undirected_dfs( 00730 make_filtered_graph(iG, 00731 detail::inL_edge_status< associative_property_map< 00732 std::map<edge_descriptor, bool> > >(aiG_inL)), 00733 make_dfs_visitor( 00734 detail::cycle_finder< std::stack<edge_descriptor> > (&iG_buf)), 00735 associative_property_map< 00736 std::map<vertex_descriptor, default_color_type> >(vertex_color), 00737 associative_property_map< 00738 std::map<edge_descriptor, default_color_type> >(edge_color) 00739 ); 00740 undirected_dfs( 00741 make_filtered_graph(vG, 00742 detail::inL_edge_status< associative_property_map< 00743 std::map<edge_descriptor, bool> > >(avG_inL)), 00744 make_dfs_visitor( 00745 detail::cycle_finder< std::stack<edge_descriptor> > (&vG_buf)), 00746 associative_property_map< 00747 std::map<vertex_descriptor, default_color_type> >(vertex_color), 00748 associative_property_map< 00749 std::map<edge_descriptor, default_color_type> >(edge_color) 00750 ); 00751 00752 if(iG_buf.empty() && vG_buf.empty()) { 00753 00754 std::map<edge_descriptor, bool> iG_deleted, vG_deleted; 00755 associative_property_map< std::map<edge_descriptor, bool> > diG(iG_deleted); 00756 associative_property_map< std::map<edge_descriptor, bool> > dvG(vG_deleted); 00757 00758 tie(current, last) = edges(iG); 00759 for(;current != last; ++current) 00760 put(diG, *current, false); 00761 tie(current, last) = edges(vG); 00762 for(;current != last; ++current) 00763 put(dvG, *current, false); 00764 00765 for(seq_size_type j = 0; j < inL.size(); ++j) { 00766 if(!inL[j]) { 00767 put(aiG_inL, iG_bimap.left.at(j), true); 00768 put(avG_inL, vG_bimap.left.at(j), true); 00769 00770 undirected_dfs( 00771 make_filtered_graph(iG, 00772 detail::inL_edge_status< associative_property_map< 00773 std::map<edge_descriptor, bool> > >(aiG_inL)), 00774 make_dfs_visitor( 00775 detail::cycle_finder< std::stack<edge_descriptor> > (&iG_buf)), 00776 associative_property_map< 00777 std::map<vertex_descriptor, default_color_type> >(vertex_color), 00778 associative_property_map< 00779 std::map<edge_descriptor, default_color_type> >(edge_color) 00780 ); 00781 undirected_dfs( 00782 make_filtered_graph(vG, 00783 detail::inL_edge_status< associative_property_map< 00784 std::map<edge_descriptor, bool> > >(avG_inL)), 00785 make_dfs_visitor( 00786 detail::cycle_finder< std::stack<edge_descriptor> > (&vG_buf)), 00787 associative_property_map< 00788 std::map<vertex_descriptor, default_color_type> >(vertex_color), 00789 associative_property_map< 00790 std::map<edge_descriptor, default_color_type> >(edge_color) 00791 ); 00792 00793 if(!iG_buf.empty() || !vG_buf.empty()) { 00794 while(!iG_buf.empty()) iG_buf.pop(); 00795 while(!vG_buf.empty()) vG_buf.pop(); 00796 put(diG, iG_bimap.left.at(j), true); 00797 put(dvG, vG_bimap.left.at(j), true); 00798 } 00799 00800 put(aiG_inL, iG_bimap.left.at(j), false); 00801 put(avG_inL, vG_bimap.left.at(j), false); 00802 } 00803 } 00804 00805 int cc = 0; 00806 00807 std::map<vertex_descriptor, int> com_map; 00808 cc += connected_components( 00809 make_filtered_graph(iG, 00810 detail::deleted_edge_status<associative_property_map< 00811 std::map<edge_descriptor, bool> > >(diG)), 00812 associative_property_map<std::map<vertex_descriptor, int> >(com_map) 00813 ); 00814 cc += connected_components( 00815 make_filtered_graph(vG, 00816 detail::deleted_edge_status<associative_property_map< 00817 std::map<edge_descriptor, bool> > >(dvG)), 00818 associative_property_map< std::map<vertex_descriptor, int> >(com_map) 00819 ); 00820 00821 if(cc != 2) 00822 return; 00823 00824 // REC_MRT 00825 detail::rec_mrt_two_graphs_common_spanning_trees<Graph, Func, Seq, 00826 associative_property_map< std::map<edge_descriptor, bool> > > 00827 (iG, iG_bimap, aiG_inL, diG, vG, vG_bimap, aiG_inL, dvG, func, inL); 00828 00829 } 00830 00831 } 00832 00833 00834 template < 00835 class Graph, 00836 class Func, 00837 class Seq 00838 > 00839 BOOST_CONCEPT_REQUIRES( 00840 ((IncidenceGraphConcept<Graph>)) 00841 ((EdgeListGraphConcept<Graph>)), 00842 (void) 00843 ) 00844 mrt_two_graphs_common_spanning_trees 00845 ( 00846 const Graph& iG, 00847 const Graph& vG, 00848 Func func, 00849 Seq inL 00850 ) 00851 { 00852 typedef graph_traits<Graph> GraphTraits; 00853 00854 typedef typename GraphTraits::edge_descriptor edge_descriptor; 00855 typedef typename GraphTraits::edges_size_type edges_size_type; 00856 typedef typename GraphTraits::edge_iterator edge_iterator; 00857 00858 std::vector<edge_descriptor> iGO, vGO; 00859 edge_iterator curr, last; 00860 00861 tie(curr, last) = edges(iG); 00862 for(; curr != last; ++curr) 00863 iGO.push_back(*curr); 00864 00865 tie(curr, last) = edges(vG); 00866 for(; curr != last; ++curr) 00867 vGO.push_back(*curr); 00868 00869 mrt_two_graphs_common_spanning_trees(iG, iGO, vG, vGO, func, inL); 00870 } 00871 00872 00873 } // namespace boost 00874 00875 00876 #endif // MRT_H
1.7.6.1
