Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-01-30 09:43:09 

0001 //          Copyright (C) 2012, Michele Caini.
0002 // Distributed under the Boost Software License, Version 1.0.
0003 //    (See accompanying file LICENSE_1_0.txt or copy at
0004 //          http://www.boost.org/LICENSE_1_0.txt)
0005 
0006 //          Two Graphs Common Spanning Trees Algorithm
0007 //      Based on academic article of Mint, Read and Tarjan
0008 //     Efficient Algorithm for Common Spanning Tree Problem
0009 // Electron. Lett., 28 April 1983, Volume 19, Issue 9, p.346-347
0010 
0011 #ifndef BOOST_GRAPH_TWO_GRAPHS_COMMON_SPANNING_TREES_HPP
0012 #define BOOST_GRAPH_TWO_GRAPHS_COMMON_SPANNING_TREES_HPP
0013 
0014 #include <boost/config.hpp>
0015 
0016 #include <boost/bimap.hpp>
0017 #include <boost/type_traits.hpp>
0018 #include <boost/concept/requires.hpp>
0019 #include <boost/graph/graph_traits.hpp>
0020 #include <boost/graph/undirected_dfs.hpp>
0021 #include <boost/graph/connected_components.hpp>
0022 #include <boost/graph/filtered_graph.hpp>
0023 #include <vector>
0024 #include <stack>
0025 #include <map>
0026 
0027 namespace boost
0028 {
0029 
0030 namespace detail
0031 {
0032 
0033     template < typename TreeMap, typename PredMap, typename DistMap,
0034         typename LowMap, typename Buffer >
0035     struct bridges_visitor : public default_dfs_visitor
0036     {
0037         bridges_visitor(TreeMap tree, PredMap pred, DistMap dist, LowMap low,
0038             Buffer& buffer)
0039         : mTree(tree), mPred(pred), mDist(dist), mLow(low), mBuffer(buffer)
0040         {
0041             mNum = -1;
0042         }
0043 
0044         template < typename Vertex, typename Graph >
0045         void initialize_vertex(const Vertex& u, const Graph& g)
0046         {
0047             put(mPred, u, u);
0048             put(mDist, u, -1);
0049         }
0050 
0051         template < typename Vertex, typename Graph >
0052         void discover_vertex(const Vertex& u, const Graph& g)
0053         {
0054             put(mDist, u, ++mNum);
0055             put(mLow, u, get(mDist, u));
0056         }
0057 
0058         template < typename Edge, typename Graph >
0059         void tree_edge(const Edge& e, const Graph& g)
0060         {
0061             put(mPred, target(e, g), source(e, g));
0062             put(mTree, target(e, g), e);
0063         }
0064 
0065         template < typename Edge, typename Graph >
0066         void back_edge(const Edge& e, const Graph& g)
0067         {
0068             put(mLow, source(e, g),
0069                 (std::min)(get(mLow, source(e, g)), get(mDist, target(e, g))));
0070         }
0071 
0072         template < typename Vertex, typename Graph >
0073         void finish_vertex(const Vertex& u, const Graph& g)
0074         {
0075             Vertex parent = get(mPred, u);
0076             if (get(mLow, u) > get(mDist, parent))
0077                 mBuffer.push(get(mTree, u));
0078             put(mLow, parent, (std::min)(get(mLow, parent), get(mLow, u)));
0079         }
0080 
0081         TreeMap mTree;
0082         PredMap mPred;
0083         DistMap mDist;
0084         LowMap mLow;
0085         Buffer& mBuffer;
0086         int mNum;
0087     };
0088 
0089     template < typename Buffer >
0090     struct cycle_finder : public base_visitor< cycle_finder< Buffer > >
0091     {
0092         typedef on_back_edge event_filter;
0093         cycle_finder() : mBuffer(0) {}
0094         cycle_finder(Buffer* buffer) : mBuffer(buffer) {}
0095         template < typename Edge, typename Graph >
0096         void operator()(const Edge& e, const Graph& g)
0097         {
0098             if (mBuffer)
0099                 mBuffer->push(e);
0100         }
0101         Buffer* mBuffer;
0102     };
0103 
0104     template < typename DeletedMap > struct deleted_edge_status
0105     {
0106         deleted_edge_status() {}
0107         deleted_edge_status(DeletedMap map) : mMap(map) {}
0108         template < typename Edge > bool operator()(const Edge& e) const
0109         {
0110             return (!get(mMap, e));
0111         }
0112         DeletedMap mMap;
0113     };
0114 
0115     template < typename InLMap > struct inL_edge_status
0116     {
0117         inL_edge_status() {}
0118         inL_edge_status(InLMap map) : mMap(map) {}
0119         template < typename Edge > bool operator()(const Edge& e) const
0120         {
0121             return get(mMap, e);
0122         }
0123         InLMap mMap;
0124     };
0125 
0126     template < typename Graph, typename Func, typename Seq, typename Map >
0127     void rec_two_graphs_common_spanning_trees(const Graph& iG,
0128         bimap< bimaps::set_of< int >,
0129             bimaps::set_of< typename graph_traits< Graph >::edge_descriptor > >
0130             iG_bimap,
0131         Map aiG_inL, Map diG, const Graph& vG,
0132         bimap< bimaps::set_of< int >,
0133             bimaps::set_of< typename graph_traits< Graph >::edge_descriptor > >
0134             vG_bimap,
0135         Map avG_inL, Map dvG, Func func, Seq inL)
0136     {
0137         typedef graph_traits< Graph > GraphTraits;
0138 
0139         typedef typename GraphTraits::vertex_descriptor vertex_descriptor;
0140         typedef typename GraphTraits::edge_descriptor edge_descriptor;
0141 
0142         typedef typename Seq::size_type seq_size_type;
0143 
0144         int edges = num_vertices(iG) - 1;
0145         //
0146         //  [ Michele Caini ]
0147         //
0148         //  Using the condition (edges != 0) leads to the accidental submission
0149         //  of
0150         //    sub-graphs ((V-1+1)-fake-tree, named here fat-tree).
0151         //  Remove this condition is a workaround for the problem of fat-trees.
0152         //  Please do not add that condition, even if it improves performance.
0153         //
0154         //  Here is proposed the previous guard (that was wrong):
0155         //     for(seq_size_type i = 0; (i < inL.size()) && (edges != 0); ++i)
0156         //
0157         {
0158             for (seq_size_type i = 0; i < inL.size(); ++i)
0159                 if (inL[i])
0160                     --edges;
0161 
0162             if (edges < 0)
0163                 return;
0164         }
0165 
0166         bool is_tree = (edges == 0);
0167         if (is_tree)
0168         {
0169             func(inL);
0170         }
0171         else
0172         {
0173             std::map< vertex_descriptor, default_color_type > vertex_color;
0174             std::map< edge_descriptor, default_color_type > edge_color;
0175 
0176             std::stack< edge_descriptor > iG_buf, vG_buf;
0177             bool found = false;
0178 
0179             seq_size_type m;
0180             for (seq_size_type j = 0; j < inL.size() && !found; ++j)
0181             {
0182                 if (!inL[j] && !get(diG, iG_bimap.left.at(j))
0183                     && !get(dvG, vG_bimap.left.at(j)))
0184                 {
0185                     put(aiG_inL, iG_bimap.left.at(j), true);
0186                     put(avG_inL, vG_bimap.left.at(j), true);
0187 
0188                     undirected_dfs(
0189                         make_filtered_graph(iG,
0190                             detail::inL_edge_status< associative_property_map<
0191                                 std::map< edge_descriptor, bool > > >(aiG_inL)),
0192                         make_dfs_visitor(detail::cycle_finder<
0193                             std::stack< edge_descriptor > >(&iG_buf)),
0194                         associative_property_map<
0195                             std::map< vertex_descriptor, default_color_type > >(
0196                             vertex_color),
0197                         associative_property_map<
0198                             std::map< edge_descriptor, default_color_type > >(
0199                             edge_color));
0200                     undirected_dfs(
0201                         make_filtered_graph(vG,
0202                             detail::inL_edge_status< associative_property_map<
0203                                 std::map< edge_descriptor, bool > > >(avG_inL)),
0204                         make_dfs_visitor(detail::cycle_finder<
0205                             std::stack< edge_descriptor > >(&vG_buf)),
0206                         associative_property_map<
0207                             std::map< vertex_descriptor, default_color_type > >(
0208                             vertex_color),
0209                         associative_property_map<
0210                             std::map< edge_descriptor, default_color_type > >(
0211                             edge_color));
0212 
0213                     if (iG_buf.empty() && vG_buf.empty())
0214                     {
0215                         inL[j] = true;
0216                         found = true;
0217                         m = j;
0218                     }
0219                     else
0220                     {
0221                         while (!iG_buf.empty())
0222                             iG_buf.pop();
0223                         while (!vG_buf.empty())
0224                             vG_buf.pop();
0225                         put(aiG_inL, iG_bimap.left.at(j), false);
0226                         put(avG_inL, vG_bimap.left.at(j), false);
0227                     }
0228                 }
0229             }
0230 
0231             if (found)
0232             {
0233 
0234                 std::stack< edge_descriptor > iG_buf_copy, vG_buf_copy;
0235                 for (seq_size_type j = 0; j < inL.size(); ++j)
0236                 {
0237                     if (!inL[j] && !get(diG, iG_bimap.left.at(j))
0238                         && !get(dvG, vG_bimap.left.at(j)))
0239                     {
0240 
0241                         put(aiG_inL, iG_bimap.left.at(j), true);
0242                         put(avG_inL, vG_bimap.left.at(j), true);
0243 
0244                         undirected_dfs(
0245                             make_filtered_graph(iG,
0246                                 detail::inL_edge_status<
0247                                     associative_property_map<
0248                                         std::map< edge_descriptor, bool > > >(
0249                                     aiG_inL)),
0250                             make_dfs_visitor(detail::cycle_finder<
0251                                 std::stack< edge_descriptor > >(&iG_buf)),
0252                             associative_property_map< std::map<
0253                                 vertex_descriptor, default_color_type > >(
0254                                 vertex_color),
0255                             associative_property_map< std::map< edge_descriptor,
0256                                 default_color_type > >(edge_color));
0257                         undirected_dfs(
0258                             make_filtered_graph(vG,
0259                                 detail::inL_edge_status<
0260                                     associative_property_map<
0261                                         std::map< edge_descriptor, bool > > >(
0262                                     avG_inL)),
0263                             make_dfs_visitor(detail::cycle_finder<
0264                                 std::stack< edge_descriptor > >(&vG_buf)),
0265                             associative_property_map< std::map<
0266                                 vertex_descriptor, default_color_type > >(
0267                                 vertex_color),
0268                             associative_property_map< std::map< edge_descriptor,
0269                                 default_color_type > >(edge_color));
0270 
0271                         if (!iG_buf.empty() || !vG_buf.empty())
0272                         {
0273                             while (!iG_buf.empty())
0274                                 iG_buf.pop();
0275                             while (!vG_buf.empty())
0276                                 vG_buf.pop();
0277                             put(diG, iG_bimap.left.at(j), true);
0278                             put(dvG, vG_bimap.left.at(j), true);
0279                             iG_buf_copy.push(iG_bimap.left.at(j));
0280                             vG_buf_copy.push(vG_bimap.left.at(j));
0281                         }
0282 
0283                         put(aiG_inL, iG_bimap.left.at(j), false);
0284                         put(avG_inL, vG_bimap.left.at(j), false);
0285                     }
0286                 }
0287 
0288                 // REC
0289                 detail::rec_two_graphs_common_spanning_trees< Graph, Func, Seq,
0290                     Map >(iG, iG_bimap, aiG_inL, diG, vG, vG_bimap, aiG_inL,
0291                     dvG, func, inL);
0292 
0293                 while (!iG_buf_copy.empty())
0294                 {
0295                     put(diG, iG_buf_copy.top(), false);
0296                     put(dvG,
0297                         vG_bimap.left.at(iG_bimap.right.at(iG_buf_copy.top())),
0298                         false);
0299                     iG_buf_copy.pop();
0300                 }
0301                 while (!vG_buf_copy.empty())
0302                 {
0303                     put(dvG, vG_buf_copy.top(), false);
0304                     put(diG,
0305                         iG_bimap.left.at(vG_bimap.right.at(vG_buf_copy.top())),
0306                         false);
0307                     vG_buf_copy.pop();
0308                 }
0309 
0310                 inL[m] = false;
0311                 put(aiG_inL, iG_bimap.left.at(m), false);
0312                 put(avG_inL, vG_bimap.left.at(m), false);
0313 
0314                 put(diG, iG_bimap.left.at(m), true);
0315                 put(dvG, vG_bimap.left.at(m), true);
0316 
0317                 std::map< vertex_descriptor, edge_descriptor > tree_map;
0318                 std::map< vertex_descriptor, vertex_descriptor > pred_map;
0319                 std::map< vertex_descriptor, int > dist_map, low_map;
0320 
0321                 detail::bridges_visitor<
0322                     associative_property_map<
0323                         std::map< vertex_descriptor, edge_descriptor > >,
0324                     associative_property_map<
0325                         std::map< vertex_descriptor, vertex_descriptor > >,
0326                     associative_property_map<
0327                         std::map< vertex_descriptor, int > >,
0328                     associative_property_map<
0329                         std::map< vertex_descriptor, int > >,
0330                     std::stack< edge_descriptor > >
0331                 iG_vis(associative_property_map<
0332                            std::map< vertex_descriptor, edge_descriptor > >(
0333                            tree_map),
0334                     associative_property_map<
0335                         std::map< vertex_descriptor, vertex_descriptor > >(
0336                         pred_map),
0337                     associative_property_map<
0338                         std::map< vertex_descriptor, int > >(dist_map),
0339                     associative_property_map<
0340                         std::map< vertex_descriptor, int > >(low_map),
0341                     iG_buf),
0342                     vG_vis(associative_property_map<
0343                                std::map< vertex_descriptor, edge_descriptor > >(
0344                                tree_map),
0345                         associative_property_map<
0346                             std::map< vertex_descriptor, vertex_descriptor > >(
0347                             pred_map),
0348                         associative_property_map<
0349                             std::map< vertex_descriptor, int > >(dist_map),
0350                         associative_property_map<
0351                             std::map< vertex_descriptor, int > >(low_map),
0352                         vG_buf);
0353 
0354                 undirected_dfs(
0355                     make_filtered_graph(iG,
0356                         detail::deleted_edge_status< associative_property_map<
0357                             std::map< edge_descriptor, bool > > >(diG)),
0358                     iG_vis,
0359                     associative_property_map<
0360                         std::map< vertex_descriptor, default_color_type > >(
0361                         vertex_color),
0362                     associative_property_map<
0363                         std::map< edge_descriptor, default_color_type > >(
0364                         edge_color));
0365                 undirected_dfs(
0366                     make_filtered_graph(vG,
0367                         detail::deleted_edge_status< associative_property_map<
0368                             std::map< edge_descriptor, bool > > >(dvG)),
0369                     vG_vis,
0370                     associative_property_map<
0371                         std::map< vertex_descriptor, default_color_type > >(
0372                         vertex_color),
0373                     associative_property_map<
0374                         std::map< edge_descriptor, default_color_type > >(
0375                         edge_color));
0376 
0377                 found = false;
0378                 std::stack< edge_descriptor > iG_buf_tmp, vG_buf_tmp;
0379                 while (!iG_buf.empty() && !found)
0380                 {
0381                     if (!inL[iG_bimap.right.at(iG_buf.top())])
0382                     {
0383                         put(aiG_inL, iG_buf.top(), true);
0384                         put(avG_inL,
0385                             vG_bimap.left.at(iG_bimap.right.at(iG_buf.top())),
0386                             true);
0387 
0388                         undirected_dfs(
0389                             make_filtered_graph(iG,
0390                                 detail::inL_edge_status<
0391                                     associative_property_map<
0392                                         std::map< edge_descriptor, bool > > >(
0393                                     aiG_inL)),
0394                             make_dfs_visitor(detail::cycle_finder<
0395                                 std::stack< edge_descriptor > >(&iG_buf_tmp)),
0396                             associative_property_map< std::map<
0397                                 vertex_descriptor, default_color_type > >(
0398                                 vertex_color),
0399                             associative_property_map< std::map< edge_descriptor,
0400                                 default_color_type > >(edge_color));
0401                         undirected_dfs(
0402                             make_filtered_graph(vG,
0403                                 detail::inL_edge_status<
0404                                     associative_property_map<
0405                                         std::map< edge_descriptor, bool > > >(
0406                                     avG_inL)),
0407                             make_dfs_visitor(detail::cycle_finder<
0408                                 std::stack< edge_descriptor > >(&vG_buf_tmp)),
0409                             associative_property_map< std::map<
0410                                 vertex_descriptor, default_color_type > >(
0411                                 vertex_color),
0412                             associative_property_map< std::map< edge_descriptor,
0413                                 default_color_type > >(edge_color));
0414 
0415                         if (!iG_buf_tmp.empty() || !vG_buf_tmp.empty())
0416                         {
0417                             found = true;
0418                         }
0419                         else
0420                         {
0421                             while (!iG_buf_tmp.empty())
0422                                 iG_buf_tmp.pop();
0423                             while (!vG_buf_tmp.empty())
0424                                 vG_buf_tmp.pop();
0425                             iG_buf_copy.push(iG_buf.top());
0426                         }
0427 
0428                         put(aiG_inL, iG_buf.top(), false);
0429                         put(avG_inL,
0430                             vG_bimap.left.at(iG_bimap.right.at(iG_buf.top())),
0431                             false);
0432                     }
0433                     iG_buf.pop();
0434                 }
0435                 while (!vG_buf.empty() && !found)
0436                 {
0437                     if (!inL[vG_bimap.right.at(vG_buf.top())])
0438                     {
0439                         put(avG_inL, vG_buf.top(), true);
0440                         put(aiG_inL,
0441                             iG_bimap.left.at(vG_bimap.right.at(vG_buf.top())),
0442                             true);
0443 
0444                         undirected_dfs(
0445                             make_filtered_graph(iG,
0446                                 detail::inL_edge_status<
0447                                     associative_property_map<
0448                                         std::map< edge_descriptor, bool > > >(
0449                                     aiG_inL)),
0450                             make_dfs_visitor(detail::cycle_finder<
0451                                 std::stack< edge_descriptor > >(&iG_buf_tmp)),
0452                             associative_property_map< std::map<
0453                                 vertex_descriptor, default_color_type > >(
0454                                 vertex_color),
0455                             associative_property_map< std::map< edge_descriptor,
0456                                 default_color_type > >(edge_color));
0457                         undirected_dfs(
0458                             make_filtered_graph(vG,
0459                                 detail::inL_edge_status<
0460                                     associative_property_map<
0461                                         std::map< edge_descriptor, bool > > >(
0462                                     avG_inL)),
0463                             make_dfs_visitor(detail::cycle_finder<
0464                                 std::stack< edge_descriptor > >(&vG_buf_tmp)),
0465                             associative_property_map< std::map<
0466                                 vertex_descriptor, default_color_type > >(
0467                                 vertex_color),
0468                             associative_property_map< std::map< edge_descriptor,
0469                                 default_color_type > >(edge_color));
0470 
0471                         if (!iG_buf_tmp.empty() || !vG_buf_tmp.empty())
0472                         {
0473                             found = true;
0474                         }
0475                         else
0476                         {
0477                             while (!iG_buf_tmp.empty())
0478                                 iG_buf_tmp.pop();
0479                             while (!vG_buf_tmp.empty())
0480                                 vG_buf_tmp.pop();
0481                             vG_buf_copy.push(vG_buf.top());
0482                         }
0483 
0484                         put(avG_inL, vG_buf.top(), false);
0485                         put(aiG_inL,
0486                             iG_bimap.left.at(vG_bimap.right.at(vG_buf.top())),
0487                             false);
0488                     }
0489                     vG_buf.pop();
0490                 }
0491 
0492                 if (!found)
0493                 {
0494 
0495                     while (!iG_buf_copy.empty())
0496                     {
0497                         inL[iG_bimap.right.at(iG_buf_copy.top())] = true;
0498                         put(aiG_inL, iG_buf_copy.top(), true);
0499                         put(avG_inL,
0500                             vG_bimap.left.at(
0501                                 iG_bimap.right.at(iG_buf_copy.top())),
0502                             true);
0503                         iG_buf.push(iG_buf_copy.top());
0504                         iG_buf_copy.pop();
0505                     }
0506                     while (!vG_buf_copy.empty())
0507                     {
0508                         inL[vG_bimap.right.at(vG_buf_copy.top())] = true;
0509                         put(avG_inL, vG_buf_copy.top(), true);
0510                         put(aiG_inL,
0511                             iG_bimap.left.at(
0512                                 vG_bimap.right.at(vG_buf_copy.top())),
0513                             true);
0514                         vG_buf.push(vG_buf_copy.top());
0515                         vG_buf_copy.pop();
0516                     }
0517 
0518                     // REC
0519                     detail::rec_two_graphs_common_spanning_trees< Graph, Func,
0520                         Seq, Map >(iG, iG_bimap, aiG_inL, diG, vG, vG_bimap,
0521                         aiG_inL, dvG, func, inL);
0522 
0523                     while (!iG_buf.empty())
0524                     {
0525                         inL[iG_bimap.right.at(iG_buf.top())] = false;
0526                         put(aiG_inL, iG_buf.top(), false);
0527                         put(avG_inL,
0528                             vG_bimap.left.at(iG_bimap.right.at(iG_buf.top())),
0529                             false);
0530                         iG_buf.pop();
0531                     }
0532                     while (!vG_buf.empty())
0533                     {
0534                         inL[vG_bimap.right.at(vG_buf.top())] = false;
0535                         put(avG_inL, vG_buf.top(), false);
0536                         put(aiG_inL,
0537                             iG_bimap.left.at(vG_bimap.right.at(vG_buf.top())),
0538                             false);
0539                         vG_buf.pop();
0540                     }
0541                 }
0542 
0543                 put(diG, iG_bimap.left.at(m), false);
0544                 put(dvG, vG_bimap.left.at(m), false);
0545             }
0546         }
0547     }
0548 
0549 } // namespace detail
0550 
0551 template < typename Coll, typename Seq > struct tree_collector
0552 {
0553 
0554 public:
0555     BOOST_CONCEPT_ASSERT((BackInsertionSequence< Coll >));
0556     BOOST_CONCEPT_ASSERT((RandomAccessContainer< Seq >));
0557     BOOST_CONCEPT_ASSERT((CopyConstructible< Seq >));
0558 
0559     typedef typename Coll::value_type coll_value_type;
0560     typedef typename Seq::value_type seq_value_type;
0561 
0562     BOOST_STATIC_ASSERT((is_same< coll_value_type, Seq >::value));
0563     BOOST_STATIC_ASSERT((is_same< seq_value_type, bool >::value));
0564 
0565     tree_collector(Coll& seqs) : mSeqs(seqs) {}
0566 
0567     inline void operator()(Seq seq) { mSeqs.push_back(seq); }
0568 
0569 private:
0570     Coll& mSeqs;
0571 };
0572 
0573 template < typename Graph, typename Order, typename Func, typename Seq >
0574 BOOST_CONCEPT_REQUIRES(
0575     ((RandomAccessContainer< Order >))((IncidenceGraphConcept< Graph >))(
0576         (UnaryFunction< Func, void, Seq >))(
0577         (Mutable_RandomAccessContainer< Seq >))(
0578         (VertexAndEdgeListGraphConcept< Graph >)),
0579     (void))
0580 two_graphs_common_spanning_trees(const Graph& iG, Order iG_map, const Graph& vG,
0581     Order vG_map, Func func, Seq inL)
0582 {
0583     typedef graph_traits< Graph > GraphTraits;
0584 
0585     typedef typename GraphTraits::directed_category directed_category;
0586     typedef typename GraphTraits::vertex_descriptor vertex_descriptor;
0587     typedef typename GraphTraits::edge_descriptor edge_descriptor;
0588 
0589     typedef typename GraphTraits::edges_size_type edges_size_type;
0590     typedef typename GraphTraits::edge_iterator edge_iterator;
0591 
0592     typedef typename Seq::value_type seq_value_type;
0593     typedef typename Seq::size_type seq_size_type;
0594 
0595     typedef typename Order::value_type order_value_type;
0596     typedef typename Order::size_type order_size_type;
0597 
0598     BOOST_STATIC_ASSERT((is_same< order_value_type, edge_descriptor >::value));
0599     BOOST_CONCEPT_ASSERT((Convertible< order_size_type, edges_size_type >));
0600 
0601     BOOST_CONCEPT_ASSERT((Convertible< seq_size_type, edges_size_type >));
0602     BOOST_STATIC_ASSERT((is_same< seq_value_type, bool >::value));
0603 
0604     BOOST_STATIC_ASSERT((is_same< directed_category, undirected_tag >::value));
0605 
0606     if (num_vertices(iG) != num_vertices(vG))
0607         return;
0608 
0609     if (inL.size() != num_edges(iG) || inL.size() != num_edges(vG))
0610         return;
0611 
0612     if (iG_map.size() != num_edges(iG) || vG_map.size() != num_edges(vG))
0613         return;
0614 
0615     typedef bimaps::bimap< bimaps::set_of< int >,
0616         bimaps::set_of< order_value_type > >
0617         bimap_type;
0618     typedef typename bimap_type::value_type bimap_value;
0619 
0620     bimap_type iG_bimap, vG_bimap;
0621     for (order_size_type i = 0; i < iG_map.size(); ++i)
0622         iG_bimap.insert(bimap_value(i, iG_map[i]));
0623     for (order_size_type i = 0; i < vG_map.size(); ++i)
0624         vG_bimap.insert(bimap_value(i, vG_map[i]));
0625 
0626     edge_iterator current, last;
0627     boost::tuples::tie(current, last) = edges(iG);
0628     for (; current != last; ++current)
0629         if (iG_bimap.right.find(*current) == iG_bimap.right.end())
0630             return;
0631     boost::tuples::tie(current, last) = edges(vG);
0632     for (; current != last; ++current)
0633         if (vG_bimap.right.find(*current) == vG_bimap.right.end())
0634             return;
0635 
0636     std::stack< edge_descriptor > iG_buf, vG_buf;
0637 
0638     std::map< vertex_descriptor, edge_descriptor > tree_map;
0639     std::map< vertex_descriptor, vertex_descriptor > pred_map;
0640     std::map< vertex_descriptor, int > dist_map, low_map;
0641 
0642     detail::bridges_visitor< associative_property_map< std::map<
0643                                  vertex_descriptor, edge_descriptor > >,
0644         associative_property_map<
0645             std::map< vertex_descriptor, vertex_descriptor > >,
0646         associative_property_map< std::map< vertex_descriptor, int > >,
0647         associative_property_map< std::map< vertex_descriptor, int > >,
0648         std::stack< edge_descriptor > >
0649     iG_vis(associative_property_map<
0650                std::map< vertex_descriptor, edge_descriptor > >(tree_map),
0651         associative_property_map<
0652             std::map< vertex_descriptor, vertex_descriptor > >(pred_map),
0653         associative_property_map< std::map< vertex_descriptor, int > >(
0654             dist_map),
0655         associative_property_map< std::map< vertex_descriptor, int > >(low_map),
0656         iG_buf),
0657         vG_vis(associative_property_map<
0658                    std::map< vertex_descriptor, edge_descriptor > >(tree_map),
0659             associative_property_map<
0660                 std::map< vertex_descriptor, vertex_descriptor > >(pred_map),
0661             associative_property_map< std::map< vertex_descriptor, int > >(
0662                 dist_map),
0663             associative_property_map< std::map< vertex_descriptor, int > >(
0664                 low_map),
0665             vG_buf);
0666 
0667     std::map< vertex_descriptor, default_color_type > vertex_color;
0668     std::map< edge_descriptor, default_color_type > edge_color;
0669 
0670     undirected_dfs(iG, iG_vis,
0671         associative_property_map<
0672             std::map< vertex_descriptor, default_color_type > >(vertex_color),
0673         associative_property_map<
0674             std::map< edge_descriptor, default_color_type > >(edge_color));
0675     undirected_dfs(vG, vG_vis,
0676         associative_property_map<
0677             std::map< vertex_descriptor, default_color_type > >(vertex_color),
0678         associative_property_map<
0679             std::map< edge_descriptor, default_color_type > >(edge_color));
0680 
0681     while (!iG_buf.empty())
0682     {
0683         inL[iG_bimap.right.at(iG_buf.top())] = true;
0684         iG_buf.pop();
0685     }
0686     while (!vG_buf.empty())
0687     {
0688         inL[vG_bimap.right.at(vG_buf.top())] = true;
0689         vG_buf.pop();
0690     }
0691 
0692     std::map< edge_descriptor, bool > iG_inL, vG_inL;
0693     associative_property_map< std::map< edge_descriptor, bool > > aiG_inL(
0694         iG_inL),
0695         avG_inL(vG_inL);
0696 
0697     for (seq_size_type i = 0; i < inL.size(); ++i)
0698     {
0699         if (inL[i])
0700         {
0701             put(aiG_inL, iG_bimap.left.at(i), true);
0702             put(avG_inL, vG_bimap.left.at(i), true);
0703         }
0704         else
0705         {
0706             put(aiG_inL, iG_bimap.left.at(i), false);
0707             put(avG_inL, vG_bimap.left.at(i), false);
0708         }
0709     }
0710 
0711     undirected_dfs(
0712         make_filtered_graph(iG,
0713             detail::inL_edge_status<
0714                 associative_property_map< std::map< edge_descriptor, bool > > >(
0715                 aiG_inL)),
0716         make_dfs_visitor(
0717             detail::cycle_finder< std::stack< edge_descriptor > >(&iG_buf)),
0718         associative_property_map<
0719             std::map< vertex_descriptor, default_color_type > >(vertex_color),
0720         associative_property_map<
0721             std::map< edge_descriptor, default_color_type > >(edge_color));
0722     undirected_dfs(
0723         make_filtered_graph(vG,
0724             detail::inL_edge_status<
0725                 associative_property_map< std::map< edge_descriptor, bool > > >(
0726                 avG_inL)),
0727         make_dfs_visitor(
0728             detail::cycle_finder< std::stack< edge_descriptor > >(&vG_buf)),
0729         associative_property_map<
0730             std::map< vertex_descriptor, default_color_type > >(vertex_color),
0731         associative_property_map<
0732             std::map< edge_descriptor, default_color_type > >(edge_color));
0733 
0734     if (iG_buf.empty() && vG_buf.empty())
0735     {
0736 
0737         std::map< edge_descriptor, bool > iG_deleted, vG_deleted;
0738         associative_property_map< std::map< edge_descriptor, bool > > diG(
0739             iG_deleted);
0740         associative_property_map< std::map< edge_descriptor, bool > > dvG(
0741             vG_deleted);
0742 
0743         boost::tuples::tie(current, last) = edges(iG);
0744         for (; current != last; ++current)
0745             put(diG, *current, false);
0746         boost::tuples::tie(current, last) = edges(vG);
0747         for (; current != last; ++current)
0748             put(dvG, *current, false);
0749 
0750         for (seq_size_type j = 0; j < inL.size(); ++j)
0751         {
0752             if (!inL[j])
0753             {
0754                 put(aiG_inL, iG_bimap.left.at(j), true);
0755                 put(avG_inL, vG_bimap.left.at(j), true);
0756 
0757                 undirected_dfs(
0758                     make_filtered_graph(iG,
0759                         detail::inL_edge_status< associative_property_map<
0760                             std::map< edge_descriptor, bool > > >(aiG_inL)),
0761                     make_dfs_visitor(
0762                         detail::cycle_finder< std::stack< edge_descriptor > >(
0763                             &iG_buf)),
0764                     associative_property_map<
0765                         std::map< vertex_descriptor, default_color_type > >(
0766                         vertex_color),
0767                     associative_property_map<
0768                         std::map< edge_descriptor, default_color_type > >(
0769                         edge_color));
0770                 undirected_dfs(
0771                     make_filtered_graph(vG,
0772                         detail::inL_edge_status< associative_property_map<
0773                             std::map< edge_descriptor, bool > > >(avG_inL)),
0774                     make_dfs_visitor(
0775                         detail::cycle_finder< std::stack< edge_descriptor > >(
0776                             &vG_buf)),
0777                     associative_property_map<
0778                         std::map< vertex_descriptor, default_color_type > >(
0779                         vertex_color),
0780                     associative_property_map<
0781                         std::map< edge_descriptor, default_color_type > >(
0782                         edge_color));
0783 
0784                 if (!iG_buf.empty() || !vG_buf.empty())
0785                 {
0786                     while (!iG_buf.empty())
0787                         iG_buf.pop();
0788                     while (!vG_buf.empty())
0789                         vG_buf.pop();
0790                     put(diG, iG_bimap.left.at(j), true);
0791                     put(dvG, vG_bimap.left.at(j), true);
0792                 }
0793 
0794                 put(aiG_inL, iG_bimap.left.at(j), false);
0795                 put(avG_inL, vG_bimap.left.at(j), false);
0796             }
0797         }
0798 
0799         int cc = 0;
0800 
0801         std::map< vertex_descriptor, int > com_map;
0802         cc += connected_components(
0803             make_filtered_graph(iG,
0804                 detail::deleted_edge_status< associative_property_map<
0805                     std::map< edge_descriptor, bool > > >(diG)),
0806             associative_property_map< std::map< vertex_descriptor, int > >(
0807                 com_map));
0808         cc += connected_components(
0809             make_filtered_graph(vG,
0810                 detail::deleted_edge_status< associative_property_map<
0811                     std::map< edge_descriptor, bool > > >(dvG)),
0812             associative_property_map< std::map< vertex_descriptor, int > >(
0813                 com_map));
0814 
0815         if (cc != 2)
0816             return;
0817 
0818         // REC
0819         detail::rec_two_graphs_common_spanning_trees< Graph, Func, Seq,
0820             associative_property_map< std::map< edge_descriptor, bool > > >(
0821             iG, iG_bimap, aiG_inL, diG, vG, vG_bimap, aiG_inL, dvG, func, inL);
0822     }
0823 }
0824 
0825 template < typename Graph, typename Func, typename Seq >
0826 BOOST_CONCEPT_REQUIRES(
0827     ((IncidenceGraphConcept< Graph >))((EdgeListGraphConcept< Graph >)), (void))
0828 two_graphs_common_spanning_trees(
0829     const Graph& iG, const Graph& vG, Func func, Seq inL)
0830 {
0831     typedef graph_traits< Graph > GraphTraits;
0832 
0833     typedef typename GraphTraits::edge_descriptor edge_descriptor;
0834     typedef typename GraphTraits::edge_iterator edge_iterator;
0835 
0836     std::vector< edge_descriptor > iGO, vGO;
0837     edge_iterator curr, last;
0838 
0839     boost::tuples::tie(curr, last) = edges(iG);
0840     for (; curr != last; ++curr)
0841         iGO.push_back(*curr);
0842 
0843     boost::tuples::tie(curr, last) = edges(vG);
0844     for (; curr != last; ++curr)
0845         vGO.push_back(*curr);
0846 
0847     two_graphs_common_spanning_trees(iG, iGO, vG, vGO, func, inL);
0848 }
0849 
0850 } // namespace boost
0851 
0852 #endif // BOOST_GRAPH_TWO_GRAPHS_COMMON_SPANNING_TREES_HPP
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!