boost/graph/two_graphs_common_spanning_trees.hpp

   1 //          Copyright (C) 2012, Michele Caini.
   2 // Distributed under the Boost Software License, Version 1.0.
   3 //    (See accompanying file LICENSE_1_0.txt or copy at
   4 //          http://www.boost.org/LICENSE_1_0.txt)
   5
   6 //          Two Graphs Common Spanning Trees Algorithm
   7 //      Based on academic article of Mint, Read and Tarjan
   8 //     Efficient Algorithm for Common Spanning Tree Problem
   9 // Electron. Lett., 28 April 1983, Volume 19, Issue 9, p.346-347
  10
  11
  12 #ifndef BOOST_GRAPH_TWO_GRAPHS_COMMON_SPANNING_TREES_HPP
  13 #define BOOST_GRAPH_TWO_GRAPHS_COMMON_SPANNING_TREES_HPP
  14
  15
  16 #include <boost/config.hpp>
  17
  18 #include <boost/bimap.hpp>
  19 #include <boost/type_traits.hpp>
  20 #include <boost/concept/requires.hpp>
  21 #include <boost/graph/graph_traits.hpp>
  22 #include <boost/graph/undirected_dfs.hpp>
  23 #include <boost/graph/connected_components.hpp>
  24 #include <boost/graph/filtered_graph.hpp>
  25 #include <vector>
  26 #include <stack>
  27 #include <map>
  28
  29
  30 namespace boost
  31 {
  32
  33
  34 namespace detail {
  35
  36
  37   template
  38     <
  39       typename TreeMap,
  40       typename PredMap,
  41       typename DistMap,
  42       typename LowMap,
  43       typename Buffer
  44     >
  45   struct bridges_visitor: public default_dfs_visitor
  46   {
  47     bridges_visitor(
  48         TreeMap tree,
  49         PredMap pred,
  50         DistMap dist,
  51         LowMap low,
  52         Buffer& buffer
  53       ): mTree(tree), mPred(pred), mDist(dist), mLow(low), mBuffer(buffer)
  54     { mNum = -1; }
  55
  56     template <typename Vertex, typename Graph>
  57     void initialize_vertex(const Vertex& u, const Graph& g)
  58     {
  59       put(mPred, u, u);
  60       put(mDist, u, -1);
  61     }
  62
  63     template <typename Vertex, typename Graph>
  64     void discover_vertex(const Vertex& u, const Graph& g)
  65     {
  66       put(mDist, u, ++mNum);
  67       put(mLow, u, get(mDist, u));
  68     }
  69
  70     template <typename Edge, typename Graph>
  71     void tree_edge(const Edge& e, const Graph& g)
  72     {
  73       put(mPred, target(e, g), source(e, g));
  74       put(mTree, target(e, g), e);
  75     }
  76
  77     template <typename Edge, typename Graph>
  78     void back_edge(const Edge& e, const Graph& g)
  79     {
  80       put(mLow, source(e, g),
  81         (std::min)(get(mLow, source(e, g)), get(mDist, target(e, g))));
  82     }
  83
  84     template <typename Vertex, typename Graph>
  85     void finish_vertex(const Vertex& u, const Graph& g)
  86     {
  87       Vertex parent = get(mPred, u);
  88       if(get(mLow, u) > get(mDist, parent))
  89         mBuffer.push(get(mTree, u));
  90       put(mLow, parent,
  91         (std::min)(get(mLow, parent), get(mLow, u)));
  92     }
  93
  94     TreeMap mTree;
  95     PredMap mPred;
  96     DistMap mDist;
  97     LowMap mLow;
  98     Buffer& mBuffer;
  99     int mNum;
 100   };
 101
 102
 103   template <typename Buffer>
 104   struct cycle_finder: public base_visitor< cycle_finder<Buffer> >
 105   {
 106     typedef on_back_edge event_filter;
 107     cycle_finder(): mBuffer(0) { }
 108     cycle_finder(Buffer* buffer)
 109       : mBuffer(buffer) { }
 110     template <typename Edge, typename Graph>
 111     void operator()(const Edge& e, const Graph& g)
 112       {
 113         if(mBuffer)
 114           mBuffer->push(e);
 115       }
 116     Buffer* mBuffer;
 117   };
 118
 119
 120   template <typename DeletedMap>
 121   struct deleted_edge_status
 122   {
 123     deleted_edge_status() { }
 124     deleted_edge_status(DeletedMap map): mMap(map) { }
 125     template <typename Edge>
 126     bool operator()(const Edge& e) const
 127       { return (!get(mMap, e)); }
 128     DeletedMap mMap;
 129   };
 130
 131
 132   template <typename InLMap>
 133   struct inL_edge_status
 134   {
 135     inL_edge_status() { }
 136     inL_edge_status(InLMap map): mMap(map) { }
 137     template <typename Edge>
 138     bool operator()(const Edge& e) const
 139       { return get(mMap, e); }
 140     InLMap mMap;
 141   };
 142
 143
 144   template <
 145     typename Graph,
 146     typename Func,
 147     typename Seq,
 148     typename Map
 149   >
 150   void rec_two_graphs_common_spanning_trees
 151     (
 152       const Graph& iG,
 153       bimap<
 154           bimaps::set_of<int>,
 155           bimaps::set_of< typename graph_traits<Graph>::edge_descriptor >
 156         > iG_bimap,
 157       Map aiG_inL,
 158       Map diG,
 159       const Graph& vG,
 160       bimap<
 161           bimaps::set_of<int>,
 162           bimaps::set_of< typename graph_traits<Graph>::edge_descriptor >
 163         > vG_bimap,
 164       Map avG_inL,
 165       Map dvG,
 166       Func func,
 167       Seq inL
 168     )
 169   {
 170     typedef graph_traits<Graph> GraphTraits;
 171
 172     typedef typename GraphTraits::vertex_descriptor vertex_descriptor;
 173     typedef typename GraphTraits::edge_descriptor edge_descriptor;
 174
 175     typedef typename Seq::size_type seq_size_type;
 176
 177     int edges = num_vertices(iG) - 1;
 178 //
 179 //  [ Michele Caini ]
 180 //
 181 //  Using the condition (edges != 0) leads to the accidental submission of
 182 //    sub-graphs ((V-1+1)-fake-tree, named here fat-tree).
 183 //  Remove this condition is a workaround for the problem of fat-trees.
 184 //  Please do not add that condition, even if it improves performance.
 185 //
 186 //  Here is proposed the previous guard (that was wrong):
 187 //     for(seq_size_type i = 0; (i < inL.size()) && (edges != 0); ++i)
 188 //
 189     {
 190       for(seq_size_type i = 0; i < inL.size(); ++i)
 191         if(inL[i])
 192           --edges;
 193
 194       if(edges < 0)
 195         return;
 196     }
 197
 198     bool is_tree = (edges == 0);
 199     if(is_tree) {
 200       func(inL);
 201     } else {
 202       std::map<vertex_descriptor, default_color_type> vertex_color;
 203       std::map<edge_descriptor, default_color_type> edge_color;
 204
 205       std::stack<edge_descriptor> iG_buf, vG_buf;
 206       bool found = false;
 207
 208       seq_size_type m;
 209       for(seq_size_type j = 0; j < inL.size() && !found; ++j) {
 210         if(!inL[j]
 211             && !get(diG, iG_bimap.left.at(j))
 212             && !get(dvG, vG_bimap.left.at(j)))
 213         {
 214           put(aiG_inL, iG_bimap.left.at(j), true);
 215           put(avG_inL, vG_bimap.left.at(j), true);
 216
 217           undirected_dfs(
 218               make_filtered_graph(iG,
 219                 detail::inL_edge_status< associative_property_map<
 220                   std::map<edge_descriptor, bool> > >(aiG_inL)),
 221               make_dfs_visitor(
 222                 detail::cycle_finder< std::stack<edge_descriptor> > (&iG_buf)),
 223               associative_property_map<
 224                 std::map<vertex_descriptor, default_color_type> >(vertex_color),
 225               associative_property_map<
 226                 std::map<edge_descriptor, default_color_type> >(edge_color)
 227             );
 228           undirected_dfs(
 229               make_filtered_graph(vG,
 230                 detail::inL_edge_status< associative_property_map<
 231                   std::map<edge_descriptor, bool> > >(avG_inL)),
 232               make_dfs_visitor(
 233                 detail::cycle_finder< std::stack<edge_descriptor> > (&vG_buf)),
 234               associative_property_map<
 235                 std::map<vertex_descriptor, default_color_type> >(vertex_color),
 236               associative_property_map<
 237                 std::map<edge_descriptor, default_color_type> >(edge_color)
 238             );
 239
 240           if(iG_buf.empty() && vG_buf.empty()) {
 241             inL[j] = true;
 242             found = true;
 243             m = j;
 244           } else {
 245             while(!iG_buf.empty()) iG_buf.pop();
 246             while(!vG_buf.empty()) vG_buf.pop();
 247             put(aiG_inL, iG_bimap.left.at(j), false);
 248             put(avG_inL, vG_bimap.left.at(j), false);
 249           }
 250         }
 251       }
 252
 253       if(found) {
 254
 255         std::stack<edge_descriptor> iG_buf_copy, vG_buf_copy;
 256         for(seq_size_type j = 0; j < inL.size(); ++j) {
 257           if(!inL[j]
 258               && !get(diG, iG_bimap.left.at(j))
 259               && !get(dvG, vG_bimap.left.at(j)))
 260           {
 261
 262             put(aiG_inL, iG_bimap.left.at(j), true);
 263             put(avG_inL, vG_bimap.left.at(j), true);
 264
 265             undirected_dfs(
 266                 make_filtered_graph(iG,
 267                   detail::inL_edge_status< associative_property_map<
 268                     std::map<edge_descriptor, bool> > >(aiG_inL)),
 269                 make_dfs_visitor(
 270                   detail::cycle_finder<
 271                     std::stack<edge_descriptor> > (&iG_buf)),
 272                associative_property_map< std::map<
 273                   vertex_descriptor, default_color_type> >(vertex_color),
 274                 associative_property_map<
 275                   std::map<edge_descriptor, default_color_type> >(edge_color)
 276               );
 277             undirected_dfs(
 278                 make_filtered_graph(vG,
 279                   detail::inL_edge_status< associative_property_map<
 280                     std::map<edge_descriptor, bool> > >(avG_inL)),
 281                 make_dfs_visitor(
 282                   detail::cycle_finder<
 283                     std::stack<edge_descriptor> > (&vG_buf)),
 284                 associative_property_map< std::map<
 285                   vertex_descriptor, default_color_type> >(vertex_color),
 286                 associative_property_map<
 287                   std::map<edge_descriptor, default_color_type> >(edge_color)
 288               );
 289
 290             if(!iG_buf.empty() || !vG_buf.empty()) {
 291               while(!iG_buf.empty()) iG_buf.pop();
 292               while(!vG_buf.empty()) vG_buf.pop();
 293               put(diG, iG_bimap.left.at(j), true);
 294               put(dvG, vG_bimap.left.at(j), true);
 295               iG_buf_copy.push(iG_bimap.left.at(j));
 296               vG_buf_copy.push(vG_bimap.left.at(j));
 297             }
 298
 299             put(aiG_inL, iG_bimap.left.at(j), false);
 300             put(avG_inL, vG_bimap.left.at(j), false);
 301           }
 302         }
 303
 304         // REC
 305         detail::rec_two_graphs_common_spanning_trees<Graph, Func, Seq, Map>
 306           (iG, iG_bimap, aiG_inL, diG, vG, vG_bimap, aiG_inL, dvG, func, inL);
 307
 308         while(!iG_buf_copy.empty()) {
 309           put(diG, iG_buf_copy.top(), false);
 310           put(dvG, vG_bimap.left.at(
 311             iG_bimap.right.at(iG_buf_copy.top())), false);
 312           iG_buf_copy.pop();
 313         }
 314         while(!vG_buf_copy.empty()) {
 315           put(dvG, vG_buf_copy.top(), false);
 316           put(diG, iG_bimap.left.at(
 317             vG_bimap.right.at(vG_buf_copy.top())), false);
 318           vG_buf_copy.pop();
 319         }
 320
 321         inL[m] = false;
 322         put(aiG_inL, iG_bimap.left.at(m), false);
 323         put(avG_inL, vG_bimap.left.at(m), false);
 324
 325         put(diG, iG_bimap.left.at(m), true);
 326         put(dvG, vG_bimap.left.at(m), true);
 327
 328         std::map<vertex_descriptor, edge_descriptor> tree_map;
 329         std::map<vertex_descriptor, vertex_descriptor> pred_map;
 330         std::map<vertex_descriptor, int> dist_map, low_map;
 331
 332         detail::bridges_visitor<
 333             associative_property_map<
 334                 std::map<vertex_descriptor, edge_descriptor>
 335               >,
 336             associative_property_map<
 337                 std::map<vertex_descriptor, vertex_descriptor>
 338               >,
 339             associative_property_map< std::map<vertex_descriptor, int> >,
 340             associative_property_map< std::map<vertex_descriptor, int> >,
 341             std::stack<edge_descriptor>
 342           >
 343         iG_vis(
 344             associative_property_map<
 345               std::map< vertex_descriptor, edge_descriptor> >(tree_map),
 346             associative_property_map<
 347               std::map< vertex_descriptor, vertex_descriptor> >(pred_map),
 348             associative_property_map<
 349               std::map< vertex_descriptor, int> >(dist_map),
 350             associative_property_map<
 351               std::map< vertex_descriptor, int> >(low_map),
 352             iG_buf
 353           ),
 354         vG_vis(
 355             associative_property_map<
 356               std::map< vertex_descriptor, edge_descriptor> >(tree_map),
 357             associative_property_map<
 358               std::map< vertex_descriptor, vertex_descriptor> >(pred_map),
 359             associative_property_map<
 360               std::map< vertex_descriptor, int> >(dist_map),
 361             associative_property_map<
 362               std::map< vertex_descriptor, int> >(low_map),
 363             vG_buf
 364           );
 365
 366         undirected_dfs(make_filtered_graph(iG,
 367               detail::deleted_edge_status< associative_property_map<
 368               std::map<edge_descriptor, bool> > >(diG)),
 369             iG_vis,
 370             associative_property_map<
 371               std::map<vertex_descriptor, default_color_type> >(vertex_color),
 372             associative_property_map<
 373               std::map<edge_descriptor, default_color_type> >(edge_color)
 374           );
 375         undirected_dfs(make_filtered_graph(vG,
 376               detail::deleted_edge_status< associative_property_map<
 377               std::map<edge_descriptor, bool> > >(dvG)),
 378             vG_vis,
 379             associative_property_map<
 380               std::map<vertex_descriptor, default_color_type> >(vertex_color),
 381             associative_property_map<
 382               std::map<edge_descriptor, default_color_type> >(edge_color)
 383           );
 384
 385         found = false;
 386         std::stack<edge_descriptor> iG_buf_tmp, vG_buf_tmp;
 387         while(!iG_buf.empty() && !found) {
 388           if(!inL[iG_bimap.right.at(iG_buf.top())]) {
 389             put(aiG_inL, iG_buf.top(), true);
 390             put(avG_inL, vG_bimap.left.at(
 391               iG_bimap.right.at(iG_buf.top())), true);
 392
 393             undirected_dfs(
 394                 make_filtered_graph(iG,
 395                   detail::inL_edge_status< associative_property_map<
 396                     std::map<edge_descriptor, bool> > >(aiG_inL)),
 397                 make_dfs_visitor(
 398                   detail::cycle_finder<
 399                     std::stack<edge_descriptor> > (&iG_buf_tmp)),
 400                 associative_property_map<
 401                   std::map<
 402                     vertex_descriptor, default_color_type> >(vertex_color),
 403                 associative_property_map<
 404                   std::map<edge_descriptor, default_color_type> >(edge_color)
 405               );
 406             undirected_dfs(
 407                 make_filtered_graph(vG,
 408                   detail::inL_edge_status< associative_property_map<
 409                     std::map<edge_descriptor, bool> > >(avG_inL)),
 410                 make_dfs_visitor(
 411                   detail::cycle_finder<
 412                     std::stack<edge_descriptor> > (&vG_buf_tmp)),
 413                 associative_property_map<
 414                   std::map<
 415                     vertex_descriptor, default_color_type> >(vertex_color),
 416                 associative_property_map<
 417                   std::map<edge_descriptor, default_color_type> >(edge_color)
 418               );
 419
 420             if(!iG_buf_tmp.empty() || !vG_buf_tmp.empty()) {
 421               found = true;
 422             } else {
 423               while(!iG_buf_tmp.empty()) iG_buf_tmp.pop();
 424               while(!vG_buf_tmp.empty()) vG_buf_tmp.pop();
 425               iG_buf_copy.push(iG_buf.top());
 426             }
 427
 428             put(aiG_inL, iG_buf.top(), false);
 429             put(avG_inL, vG_bimap.left.at(
 430               iG_bimap.right.at(iG_buf.top())), false);
 431           }
 432           iG_buf.pop();
 433         }
 434         while(!vG_buf.empty() && !found) {
 435           if(!inL[vG_bimap.right.at(vG_buf.top())]) {
 436             put(avG_inL, vG_buf.top(), true);
 437             put(aiG_inL, iG_bimap.left.at(
 438               vG_bimap.right.at(vG_buf.top())), true);
 439
 440             undirected_dfs(
 441                 make_filtered_graph(iG,
 442                   detail::inL_edge_status< associative_property_map<
 443                     std::map<edge_descriptor, bool> > >(aiG_inL)),
 444                 make_dfs_visitor(
 445                   detail::cycle_finder<
 446                     std::stack<edge_descriptor> > (&iG_buf_tmp)),
 447                 associative_property_map<
 448                   std::map<
 449                     vertex_descriptor, default_color_type> >(vertex_color),
 450                 associative_property_map<
 451                   std::map<edge_descriptor, default_color_type> >(edge_color)
 452               );
 453             undirected_dfs(
 454                 make_filtered_graph(vG,
 455                   detail::inL_edge_status< associative_property_map<
 456                     std::map<edge_descriptor, bool> > >(avG_inL)),
 457                 make_dfs_visitor(
 458                   detail::cycle_finder<
 459                     std::stack<edge_descriptor> > (&vG_buf_tmp)),
 460                 associative_property_map<
 461                   std::map<
 462                     vertex_descriptor, default_color_type> >(vertex_color),
 463                 associative_property_map<
 464                   std::map<edge_descriptor, default_color_type> >(edge_color)
 465               );
 466
 467             if(!iG_buf_tmp.empty() || !vG_buf_tmp.empty()) {
 468               found = true;
 469             } else {
 470               while(!iG_buf_tmp.empty()) iG_buf_tmp.pop();
 471               while(!vG_buf_tmp.empty()) vG_buf_tmp.pop();
 472               vG_buf_copy.push(vG_buf.top());
 473             }
 474
 475             put(avG_inL, vG_buf.top(), false);
 476             put(aiG_inL, iG_bimap.left.at(
 477               vG_bimap.right.at(vG_buf.top())), false);
 478           }
 479           vG_buf.pop();
 480         }
 481
 482         if(!found) {
 483
 484           while(!iG_buf_copy.empty()) {
 485             inL[iG_bimap.right.at(iG_buf_copy.top())] = true;
 486             put(aiG_inL, iG_buf_copy.top(), true);
 487             put(avG_inL, vG_bimap.left.at(
 488               iG_bimap.right.at(iG_buf_copy.top())), true);
 489             iG_buf.push(iG_buf_copy.top());
 490             iG_buf_copy.pop();
 491           }
 492           while(!vG_buf_copy.empty()) {
 493             inL[vG_bimap.right.at(vG_buf_copy.top())] = true;
 494             put(avG_inL, vG_buf_copy.top(), true);
 495             put(aiG_inL, iG_bimap.left.at(
 496               vG_bimap.right.at(vG_buf_copy.top())), true);
 497             vG_buf.push(vG_buf_copy.top());
 498             vG_buf_copy.pop();
 499           }
 500
 501           // REC
 502           detail::rec_two_graphs_common_spanning_trees<
 503               Graph, Func, Seq, Map>
 504             (iG, iG_bimap, aiG_inL, diG, vG, vG_bimap, aiG_inL, dvG, func, inL);
 505
 506           while(!iG_buf.empty()) {
 507             inL[iG_bimap.right.at(iG_buf.top())] = false;
 508             put(aiG_inL, iG_buf.top(), false);
 509             put(avG_inL, vG_bimap.left.at(
 510               iG_bimap.right.at(iG_buf.top())), false);
 511             iG_buf.pop();
 512           }
 513           while(!vG_buf.empty()) {
 514             inL[vG_bimap.right.at(vG_buf.top())] = false;
 515             put(avG_inL, vG_buf.top(), false);
 516             put(aiG_inL, iG_bimap.left.at(
 517               vG_bimap.right.at(vG_buf.top())), false);
 518             vG_buf.pop();
 519           }
 520
 521         }
 522
 523         put(diG, iG_bimap.left.at(m), false);
 524         put(dvG, vG_bimap.left.at(m), false);
 525
 526       }
 527     }
 528   }
 529
 530 } // namespace detail
 531
 532
 533
 534 template <typename Coll, typename Seq>
 535 struct tree_collector
 536 {
 537
 538 public:
 539   BOOST_CONCEPT_ASSERT((BackInsertionSequence<Coll>));
 540   BOOST_CONCEPT_ASSERT((RandomAccessContainer<Seq>));
 541   BOOST_CONCEPT_ASSERT((CopyConstructible<Seq>));
 542
 543   typedef typename Coll::value_type coll_value_type;
 544   typedef typename Seq::value_type seq_value_type;
 545
 546   BOOST_STATIC_ASSERT((is_same<coll_value_type, Seq>::value));
 547   BOOST_STATIC_ASSERT((is_same<seq_value_type, bool>::value));
 548
 549   tree_collector(Coll& seqs): mSeqs(seqs) { }
 550
 551   inline void operator()(Seq seq)
 552     { mSeqs.push_back(seq); }
 553
 554 private:
 555   Coll& mSeqs;
 556
 557 };
 558
 559
 560
 561 template <
 562   typename Graph,
 563   typename Order,
 564   typename Func,
 565   typename Seq
 566 >
 567 BOOST_CONCEPT_REQUIRES(
 568   ((RandomAccessContainer<Order>))
 569   ((IncidenceGraphConcept<Graph>))
 570   ((UnaryFunction<Func, void, Seq>))
 571   ((Mutable_RandomAccessContainer<Seq>))
 572   ((VertexAndEdgeListGraphConcept<Graph>)),
 573   (void)
 574 )
 575 two_graphs_common_spanning_trees
 576   (
 577     const Graph& iG,
 578     Order iG_map,
 579     const Graph& vG,
 580     Order vG_map,
 581     Func func,
 582     Seq inL
 583   )
 584 {
 585   typedef graph_traits<Graph> GraphTraits;
 586
 587   typedef typename GraphTraits::directed_category directed_category;
 588   typedef typename GraphTraits::vertex_descriptor vertex_descriptor;
 589   typedef typename GraphTraits::edge_descriptor edge_descriptor;
 590
 591   typedef typename GraphTraits::edges_size_type edges_size_type;
 592   typedef typename GraphTraits::edge_iterator edge_iterator;
 593
 594   typedef typename Seq::const_iterator seq_const_iterator;
 595   typedef typename Seq::difference_type seq_diff_type;
 596   typedef typename Seq::value_type seq_value_type;
 597   typedef typename Seq::size_type seq_size_type;
 598   typedef typename Seq::iterator seq_iterator;
 599
 600   typedef typename Order::const_iterator order_const_iterator;
 601   typedef typename Order::difference_type order_diff_type;
 602   typedef typename Order::value_type order_value_type;
 603   typedef typename Order::size_type order_size_type;
 604   typedef typename Order::iterator order_iterator;
 605
 606   BOOST_STATIC_ASSERT((is_same<order_value_type, edge_descriptor>::value));
 607   BOOST_CONCEPT_ASSERT((Convertible<order_size_type, edges_size_type>));
 608
 609   BOOST_CONCEPT_ASSERT((Convertible<seq_size_type, edges_size_type>));
 610   BOOST_STATIC_ASSERT((is_same<seq_value_type, bool>::value));
 611
 612   BOOST_STATIC_ASSERT((is_same<directed_category, undirected_tag>::value));
 613
 614   if(num_vertices(iG) != num_vertices(vG))
 615     return;
 616
 617   if(inL.size() != num_edges(iG)
 618       || inL.size() != num_edges(vG))
 619     return;
 620
 621   if(iG_map.size() != num_edges(iG)
 622       || vG_map.size() != num_edges(vG))
 623     return;
 624
 625   typedef bimaps::bimap<
 626       bimaps::set_of< int >,
 627       bimaps::set_of< order_value_type >
 628     > bimap_type;
 629   typedef typename bimap_type::value_type bimap_value;
 630
 631   bimap_type iG_bimap, vG_bimap;
 632   for(order_size_type i = 0; i < iG_map.size(); ++i)
 633     iG_bimap.insert(bimap_value(i, iG_map[i]));
 634   for(order_size_type i = 0; i < vG_map.size(); ++i)
 635     vG_bimap.insert(bimap_value(i, vG_map[i]));
 636
 637   edge_iterator current, last;
 638   boost::tuples::tie(current, last) = edges(iG);
 639   for(; current != last; ++current)
 640     if(iG_bimap.right.find(*current) == iG_bimap.right.end())
 641       return;
 642   boost::tuples::tie(current, last) = edges(vG);
 643   for(; current != last; ++current)
 644     if(vG_bimap.right.find(*current) == vG_bimap.right.end())
 645       return;
 646
 647   std::stack<edge_descriptor> iG_buf, vG_buf;
 648
 649   std::map<vertex_descriptor, edge_descriptor> tree_map;
 650   std::map<vertex_descriptor, vertex_descriptor> pred_map;
 651   std::map<vertex_descriptor, int> dist_map, low_map;
 652
 653   detail::bridges_visitor<
 654       associative_property_map<
 655           std::map<vertex_descriptor, edge_descriptor>
 656         >,
 657       associative_property_map<
 658           std::map<vertex_descriptor, vertex_descriptor>
 659         >,
 660       associative_property_map< std::map<vertex_descriptor, int> >,
 661       associative_property_map< std::map<vertex_descriptor, int> >,
 662       std::stack<edge_descriptor>
 663     >
 664   iG_vis(
 665       associative_property_map<
 666         std::map< vertex_descriptor, edge_descriptor> >(tree_map),
 667       associative_property_map<
 668         std::map< vertex_descriptor, vertex_descriptor> >(pred_map),
 669       associative_property_map<std::map< vertex_descriptor, int> >(dist_map),
 670       associative_property_map<std::map< vertex_descriptor, int> >(low_map),
 671       iG_buf
 672     ),
 673   vG_vis(
 674       associative_property_map<
 675         std::map< vertex_descriptor, edge_descriptor> >(tree_map),
 676       associative_property_map<
 677         std::map< vertex_descriptor, vertex_descriptor> >(pred_map),
 678       associative_property_map<std::map< vertex_descriptor, int> >(dist_map),
 679       associative_property_map<std::map< vertex_descriptor, int> >(low_map),
 680       vG_buf
 681     );
 682
 683   std::map<vertex_descriptor, default_color_type> vertex_color;
 684   std::map<edge_descriptor, default_color_type> edge_color;
 685
 686   undirected_dfs(iG, iG_vis,
 687       associative_property_map<
 688         std::map<vertex_descriptor, default_color_type> >(vertex_color),
 689       associative_property_map<
 690         std::map<edge_descriptor, default_color_type> >(edge_color)
 691     );
 692   undirected_dfs(vG, vG_vis,
 693       associative_property_map<
 694         std::map<vertex_descriptor, default_color_type> >(vertex_color),
 695       associative_property_map<
 696         std::map<edge_descriptor, default_color_type> >(edge_color)
 697     );
 698
 699   while(!iG_buf.empty()) {
 700     inL[iG_bimap.right.at(iG_buf.top())] = true;
 701     iG_buf.pop();
 702   }
 703   while(!vG_buf.empty()) {
 704     inL[vG_bimap.right.at(vG_buf.top())] = true;
 705     vG_buf.pop();
 706   }
 707
 708   std::map<edge_descriptor, bool> iG_inL, vG_inL;
 709   associative_property_map< std::map<edge_descriptor, bool> >
 710     aiG_inL(iG_inL), avG_inL(vG_inL);
 711
 712   for(seq_size_type i = 0; i < inL.size(); ++i)
 713   {
 714     if(inL[i]) {
 715       put(aiG_inL, iG_bimap.left.at(i), true);
 716       put(avG_inL, vG_bimap.left.at(i), true);
 717     } else {
 718       put(aiG_inL, iG_bimap.left.at(i), false);
 719       put(avG_inL, vG_bimap.left.at(i), false);
 720     }
 721   }
 722
 723   undirected_dfs(
 724       make_filtered_graph(iG,
 725         detail::inL_edge_status< associative_property_map<
 726           std::map<edge_descriptor, bool> > >(aiG_inL)),
 727       make_dfs_visitor(
 728         detail::cycle_finder< std::stack<edge_descriptor> > (&iG_buf)),
 729       associative_property_map<
 730         std::map<vertex_descriptor, default_color_type> >(vertex_color),
 731       associative_property_map<
 732         std::map<edge_descriptor, default_color_type> >(edge_color)
 733     );
 734   undirected_dfs(
 735       make_filtered_graph(vG,
 736         detail::inL_edge_status< associative_property_map<
 737           std::map<edge_descriptor, bool> > >(avG_inL)),
 738       make_dfs_visitor(
 739         detail::cycle_finder< std::stack<edge_descriptor> > (&vG_buf)),
 740       associative_property_map<
 741         std::map<vertex_descriptor, default_color_type> >(vertex_color),
 742       associative_property_map<
 743         std::map<edge_descriptor, default_color_type> >(edge_color)
 744     );
 745
 746   if(iG_buf.empty() && vG_buf.empty()) {
 747
 748     std::map<edge_descriptor, bool> iG_deleted, vG_deleted;
 749     associative_property_map< std::map<edge_descriptor, bool> > diG(iG_deleted);
 750     associative_property_map< std::map<edge_descriptor, bool> > dvG(vG_deleted);
 751
 752     boost::tuples::tie(current, last) = edges(iG);
 753     for(; current != last; ++current)
 754       put(diG, *current, false);
 755     boost::tuples::tie(current, last) = edges(vG);
 756     for(; current != last; ++current)
 757       put(dvG, *current, false);
 758
 759     for(seq_size_type j = 0; j < inL.size(); ++j) {
 760       if(!inL[j]) {
 761         put(aiG_inL, iG_bimap.left.at(j), true);
 762         put(avG_inL, vG_bimap.left.at(j), true);
 763
 764         undirected_dfs(
 765             make_filtered_graph(iG,
 766               detail::inL_edge_status< associative_property_map<
 767                 std::map<edge_descriptor, bool> > >(aiG_inL)),
 768             make_dfs_visitor(
 769               detail::cycle_finder< std::stack<edge_descriptor> > (&iG_buf)),
 770             associative_property_map<
 771               std::map<vertex_descriptor, default_color_type> >(vertex_color),
 772             associative_property_map<
 773               std::map<edge_descriptor, default_color_type> >(edge_color)
 774           );
 775         undirected_dfs(
 776             make_filtered_graph(vG,
 777               detail::inL_edge_status< associative_property_map<
 778                 std::map<edge_descriptor, bool> > >(avG_inL)),
 779             make_dfs_visitor(
 780               detail::cycle_finder< std::stack<edge_descriptor> > (&vG_buf)),
 781             associative_property_map<
 782               std::map<vertex_descriptor, default_color_type> >(vertex_color),
 783             associative_property_map<
 784               std::map<edge_descriptor, default_color_type> >(edge_color)
 785           );
 786
 787         if(!iG_buf.empty() || !vG_buf.empty()) {
 788           while(!iG_buf.empty()) iG_buf.pop();
 789           while(!vG_buf.empty()) vG_buf.pop();
 790           put(diG, iG_bimap.left.at(j), true);
 791           put(dvG, vG_bimap.left.at(j), true);
 792         }
 793
 794         put(aiG_inL, iG_bimap.left.at(j), false);
 795         put(avG_inL, vG_bimap.left.at(j), false);
 796       }
 797     }
 798
 799     int cc = 0;
 800
 801     std::map<vertex_descriptor, int> com_map;
 802     cc += connected_components(
 803         make_filtered_graph(iG,
 804           detail::deleted_edge_status<associative_property_map<
 805             std::map<edge_descriptor, bool> > >(diG)),
 806         associative_property_map<std::map<vertex_descriptor, int> >(com_map)
 807       );
 808     cc += connected_components(
 809         make_filtered_graph(vG,
 810           detail::deleted_edge_status<associative_property_map<
 811             std::map<edge_descriptor, bool> > >(dvG)),
 812         associative_property_map< std::map<vertex_descriptor, int> >(com_map)
 813       );
 814
 815     if(cc != 2)
 816       return;
 817
 818     // REC
 819     detail::rec_two_graphs_common_spanning_trees<Graph, Func, Seq,
 820         associative_property_map< std::map<edge_descriptor, bool> > >
 821       (iG, iG_bimap, aiG_inL, diG, vG, vG_bimap, aiG_inL, dvG, func, inL);
 822
 823   }
 824
 825 }
 826
 827
 828 template <
 829   typename Graph,
 830   typename Func,
 831   typename Seq
 832 >
 833 BOOST_CONCEPT_REQUIRES(
 834   ((IncidenceGraphConcept<Graph>))
 835   ((EdgeListGraphConcept<Graph>)),
 836   (void)
 837 )
 838 two_graphs_common_spanning_trees
 839   (
 840     const Graph& iG,
 841     const Graph& vG,
 842     Func func,
 843     Seq inL
 844   )
 845 {
 846   typedef graph_traits<Graph> GraphTraits;
 847
 848   typedef typename GraphTraits::edge_descriptor edge_descriptor;
 849   typedef typename GraphTraits::edges_size_type edges_size_type;
 850   typedef typename GraphTraits::edge_iterator edge_iterator;
 851
 852   std::vector<edge_descriptor> iGO, vGO;
 853   edge_iterator curr, last;
 854
 855   boost::tuples::tie(curr, last) = edges(iG);
 856   for(; curr != last; ++curr)
 857     iGO.push_back(*curr);
 858
 859   boost::tuples::tie(curr, last) = edges(vG);
 860   for(; curr != last; ++curr)
 861     vGO.push_back(*curr);
 862
 863   two_graphs_common_spanning_trees(iG, iGO, vG, vGO, func, inL);
 864 }
 865
 866
 867 } // namespace boost
 868
 869
 870 #endif // BOOST_GRAPH_TWO_GRAPHS_COMMON_SPANNING_TREES_HPP