Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-01-18 09:37:30 

0001 // Copyright (C) 2001 Jeremy Siek, Douglas Gregor, Brian Osman
0002 //
0003 // Distributed under the Boost Software License, Version 1.0. (See
0004 // accompanying file LICENSE_1_0.txt or copy at
0005 // http://www.boost.org/LICENSE_1_0.txt)
0006 #ifndef BOOST_GRAPH_ISOMORPHISM_HPP
0007 #define BOOST_GRAPH_ISOMORPHISM_HPP
0008 
0009 #include <utility>
0010 #include <vector>
0011 #include <iterator>
0012 #include <algorithm>
0013 #include <boost/config.hpp>
0014 #include <boost/assert.hpp>
0015 #include <boost/smart_ptr.hpp>
0016 #include <boost/graph/depth_first_search.hpp>
0017 #include <boost/detail/algorithm.hpp>
0018 #include <boost/pending/indirect_cmp.hpp> // for make_indirect_pmap
0019 #include <boost/concept/assert.hpp>
0020 
0021 #ifndef BOOST_GRAPH_ITERATION_MACROS_HPP
0022 #define BOOST_ISO_INCLUDED_ITER_MACROS // local macro, see bottom of file
0023 #include <boost/graph/iteration_macros.hpp>
0024 #endif
0025 
0026 namespace boost
0027 {
0028 
0029 namespace detail
0030 {
0031 
0032     template < typename Graph1, typename Graph2, typename IsoMapping,
0033         typename Invariant1, typename Invariant2, typename IndexMap1,
0034         typename IndexMap2 >
0035     class isomorphism_algo
0036     {
0037         typedef typename graph_traits< Graph1 >::vertex_descriptor vertex1_t;
0038         typedef typename graph_traits< Graph2 >::vertex_descriptor vertex2_t;
0039         typedef typename graph_traits< Graph1 >::edge_descriptor edge1_t;
0040         typedef typename graph_traits< Graph1 >::vertices_size_type size_type;
0041         typedef typename Invariant1::result_type invar1_value;
0042         typedef typename Invariant2::result_type invar2_value;
0043 
0044         const Graph1& G1;
0045         const Graph2& G2;
0046         IsoMapping f;
0047         Invariant1 invariant1;
0048         Invariant2 invariant2;
0049         std::size_t max_invariant;
0050         IndexMap1 index_map1;
0051         IndexMap2 index_map2;
0052 
0053         std::vector< vertex1_t > dfs_vertices;
0054         typedef typename std::vector< vertex1_t >::iterator vertex_iter;
0055         std::vector< int > dfs_num_vec;
0056         typedef safe_iterator_property_map<
0057             typename std::vector< int >::iterator, IndexMap1
0058 #ifdef BOOST_NO_STD_ITERATOR_TRAITS
0059             ,
0060             int, int&
0061 #endif /* BOOST_NO_STD_ITERATOR_TRAITS */
0062             >
0063             DFSNumMap;
0064         DFSNumMap dfs_num;
0065         std::vector< edge1_t > ordered_edges;
0066         typedef typename std::vector< edge1_t >::iterator edge_iter;
0067 
0068         std::vector< char > in_S_vec;
0069         typedef safe_iterator_property_map<
0070             typename std::vector< char >::iterator, IndexMap2
0071 #ifdef BOOST_NO_STD_ITERATOR_TRAITS
0072             ,
0073             char, char&
0074 #endif /* BOOST_NO_STD_ITERATOR_TRAITS */
0075             >
0076             InSMap;
0077         InSMap in_S;
0078 
0079         int num_edges_on_k;
0080 
0081         friend struct compare_multiplicity;
0082         struct compare_multiplicity
0083         {
0084             compare_multiplicity(Invariant1 invariant1, size_type* multiplicity)
0085             : invariant1(invariant1), multiplicity(multiplicity)
0086             {
0087             }
0088             bool operator()(const vertex1_t& x, const vertex1_t& y) const
0089             {
0090                 return multiplicity[invariant1(x)]
0091                     < multiplicity[invariant1(y)];
0092             }
0093             Invariant1 invariant1;
0094             size_type* multiplicity;
0095         };
0096 
0097         struct record_dfs_order : default_dfs_visitor
0098         {
0099             record_dfs_order(
0100                 std::vector< vertex1_t >& v, std::vector< edge1_t >& e)
0101             : vertices(v), edges(e)
0102             {
0103             }
0104 
0105             void discover_vertex(vertex1_t v, const Graph1&) const
0106             {
0107                 vertices.push_back(v);
0108             }
0109             void examine_edge(edge1_t e, const Graph1&) const
0110             {
0111                 edges.push_back(e);
0112             }
0113             std::vector< vertex1_t >& vertices;
0114             std::vector< edge1_t >& edges;
0115         };
0116 
0117         struct edge_cmp
0118         {
0119             edge_cmp(const Graph1& G1, DFSNumMap dfs_num)
0120             : G1(G1), dfs_num(dfs_num)
0121             {
0122             }
0123             bool operator()(const edge1_t& e1, const edge1_t& e2) const
0124             {
0125                 using namespace std;
0126                 int u1 = dfs_num[source(e1, G1)], v1 = dfs_num[target(e1, G1)];
0127                 int u2 = dfs_num[source(e2, G1)], v2 = dfs_num[target(e2, G1)];
0128                 int m1 = (max)(u1, v1);
0129                 int m2 = (max)(u2, v2);
0130                 // lexicographical comparison
0131                 return std::make_pair(m1, std::make_pair(u1, v1))
0132                     < std::make_pair(m2, std::make_pair(u2, v2));
0133             }
0134             const Graph1& G1;
0135             DFSNumMap dfs_num;
0136         };
0137 
0138     public:
0139         isomorphism_algo(const Graph1& G1, const Graph2& G2, IsoMapping f,
0140             Invariant1 invariant1, Invariant2 invariant2,
0141             std::size_t max_invariant, IndexMap1 index_map1,
0142             IndexMap2 index_map2)
0143         : G1(G1)
0144         , G2(G2)
0145         , f(f)
0146         , invariant1(invariant1)
0147         , invariant2(invariant2)
0148         , max_invariant(max_invariant)
0149         , index_map1(index_map1)
0150         , index_map2(index_map2)
0151         {
0152             in_S_vec.resize(num_vertices(G1));
0153             in_S = make_safe_iterator_property_map(
0154                 in_S_vec.begin(), in_S_vec.size(), index_map2
0155 #ifdef BOOST_NO_STD_ITERATOR_TRAITS
0156                 ,
0157                 in_S_vec.front()
0158 #endif /* BOOST_NO_STD_ITERATOR_TRAITS */
0159             );
0160         }
0161 
0162         bool test_isomorphism()
0163         {
0164             // reset isomapping
0165             BGL_FORALL_VERTICES_T(v, G1, Graph1)
0166             f[v] = graph_traits< Graph2 >::null_vertex();
0167 
0168             {
0169                 std::vector< invar1_value > invar1_array;
0170                 BGL_FORALL_VERTICES_T(v, G1, Graph1)
0171                 invar1_array.push_back(invariant1(v));
0172                 sort(invar1_array);
0173 
0174                 std::vector< invar2_value > invar2_array;
0175                 BGL_FORALL_VERTICES_T(v, G2, Graph2)
0176                 invar2_array.push_back(invariant2(v));
0177                 sort(invar2_array);
0178                 if (!equal(invar1_array, invar2_array))
0179                     return false;
0180             }
0181 
0182             std::vector< vertex1_t > V_mult;
0183             BGL_FORALL_VERTICES_T(v, G1, Graph1)
0184             V_mult.push_back(v);
0185             {
0186                 std::vector< size_type > multiplicity(max_invariant, 0);
0187                 BGL_FORALL_VERTICES_T(v, G1, Graph1)
0188                 ++multiplicity.at(invariant1(v));
0189                 sort(
0190                     V_mult, compare_multiplicity(invariant1, &multiplicity[0]));
0191             }
0192 
0193             std::vector< default_color_type > color_vec(num_vertices(G1));
0194             safe_iterator_property_map<
0195                 std::vector< default_color_type >::iterator, IndexMap1
0196 #ifdef BOOST_NO_STD_ITERATOR_TRAITS
0197                 ,
0198                 default_color_type, default_color_type&
0199 #endif /* BOOST_NO_STD_ITERATOR_TRAITS */
0200                 >
0201                 color_map(color_vec.begin(), color_vec.size(), index_map1);
0202             record_dfs_order dfs_visitor(dfs_vertices, ordered_edges);
0203             typedef color_traits< default_color_type > Color;
0204             for (vertex_iter u = V_mult.begin(); u != V_mult.end(); ++u)
0205             {
0206                 if (color_map[*u] == Color::white())
0207                 {
0208                     dfs_visitor.start_vertex(*u, G1);
0209                     depth_first_visit(G1, *u, dfs_visitor, color_map);
0210                 }
0211             }
0212             // Create the dfs_num array and dfs_num_map
0213             dfs_num_vec.resize(num_vertices(G1));
0214             dfs_num = make_safe_iterator_property_map(
0215                 dfs_num_vec.begin(), dfs_num_vec.size(), index_map1
0216 #ifdef BOOST_NO_STD_ITERATOR_TRAITS
0217                 ,
0218                 dfs_num_vec.front()
0219 #endif /* BOOST_NO_STD_ITERATOR_TRAITS */
0220             );
0221             size_type n = 0;
0222             for (vertex_iter v = dfs_vertices.begin(); v != dfs_vertices.end();
0223                  ++v)
0224                 dfs_num[*v] = n++;
0225 
0226             sort(ordered_edges, edge_cmp(G1, dfs_num));
0227 
0228             int dfs_num_k = -1;
0229             return this->match(ordered_edges.begin(), dfs_num_k);
0230         }
0231 
0232     private:
0233         struct match_continuation
0234         {
0235             enum
0236             {
0237                 pos_G2_vertex_loop,
0238                 pos_fi_adj_loop,
0239                 pos_dfs_num
0240             } position;
0241             typedef typename graph_traits< Graph2 >::vertex_iterator
0242                 vertex_iterator;
0243             std::pair< vertex_iterator, vertex_iterator > G2_verts;
0244             typedef typename graph_traits< Graph2 >::adjacency_iterator
0245                 adjacency_iterator;
0246             std::pair< adjacency_iterator, adjacency_iterator > fi_adj;
0247             edge_iter iter;
0248             int dfs_num_k;
0249         };
0250 
0251         bool match(edge_iter iter, int dfs_num_k)
0252         {
0253             std::vector< match_continuation > k;
0254             typedef typename graph_traits< Graph2 >::vertex_iterator
0255                 vertex_iterator;
0256             std::pair< vertex_iterator, vertex_iterator > G2_verts(
0257                 vertices(G2));
0258             typedef typename graph_traits< Graph2 >::adjacency_iterator
0259                 adjacency_iterator;
0260             std::pair< adjacency_iterator, adjacency_iterator > fi_adj;
0261             vertex1_t i, j;
0262 
0263         recur:
0264             if (iter != ordered_edges.end())
0265             {
0266                 i = source(*iter, G1);
0267                 j = target(*iter, G1);
0268                 if (dfs_num[i] > dfs_num_k)
0269                 {
0270                     G2_verts = vertices(G2);
0271                     while (G2_verts.first != G2_verts.second)
0272                     {
0273                         {
0274                             vertex2_t u = *G2_verts.first;
0275                             vertex1_t kp1 = dfs_vertices[dfs_num_k + 1];
0276                             if (invariant1(kp1) == invariant2(u)
0277                                 && in_S[u] == false)
0278                             {
0279                                 {
0280                                     f[kp1] = u;
0281                                     in_S[u] = true;
0282                                     num_edges_on_k = 0;
0283 
0284                                     match_continuation new_k;
0285                                     new_k.position = match_continuation::
0286                                         pos_G2_vertex_loop;
0287                                     new_k.G2_verts = G2_verts;
0288                                     new_k.iter = iter;
0289                                     new_k.dfs_num_k = dfs_num_k;
0290                                     k.push_back(new_k);
0291                                     ++dfs_num_k;
0292                                     goto recur;
0293                                 }
0294                             }
0295                         }
0296                     G2_loop_k:
0297                         ++G2_verts.first;
0298                     }
0299                 }
0300                 else if (dfs_num[j] > dfs_num_k)
0301                 {
0302                     {
0303                         vertex1_t vk = dfs_vertices[dfs_num_k];
0304                         num_edges_on_k -= count_if(adjacent_vertices(f[vk], G2),
0305                             make_indirect_pmap(in_S));
0306 
0307                         for (int jj = 0; jj < dfs_num_k; ++jj)
0308                         {
0309                             vertex1_t j = dfs_vertices[jj];
0310                             num_edges_on_k
0311                                 -= count(adjacent_vertices(f[j], G2), f[vk]);
0312                         }
0313                     }
0314 
0315                     if (num_edges_on_k != 0)
0316                         goto return_point_false;
0317                     fi_adj = adjacent_vertices(f[i], G2);
0318                     while (fi_adj.first != fi_adj.second)
0319                     {
0320                         {
0321                             vertex2_t v = *fi_adj.first;
0322                             if (invariant2(v) == invariant1(j)
0323                                 && in_S[v] == false)
0324                             {
0325                                 f[j] = v;
0326                                 in_S[v] = true;
0327                                 num_edges_on_k = 1;
0328                                 BOOST_USING_STD_MAX();
0329                                 int next_k
0330                                     = max BOOST_PREVENT_MACRO_SUBSTITUTION(
0331                                         dfs_num_k,
0332                                         max BOOST_PREVENT_MACRO_SUBSTITUTION(
0333                                             dfs_num[i], dfs_num[j]));
0334                                 match_continuation new_k;
0335                                 new_k.position
0336                                     = match_continuation::pos_fi_adj_loop;
0337                                 new_k.fi_adj = fi_adj;
0338                                 new_k.iter = iter;
0339                                 new_k.dfs_num_k = dfs_num_k;
0340                                 ++iter;
0341                                 dfs_num_k = next_k;
0342                                 k.push_back(new_k);
0343                                 goto recur;
0344                             }
0345                         }
0346                     fi_adj_loop_k:
0347                         ++fi_adj.first;
0348                     }
0349                 }
0350                 else
0351                 {
0352                     if (container_contains(adjacent_vertices(f[i], G2), f[j]))
0353                     {
0354                         ++num_edges_on_k;
0355                         match_continuation new_k;
0356                         new_k.position = match_continuation::pos_dfs_num;
0357                         k.push_back(new_k);
0358                         ++iter;
0359                         goto recur;
0360                     }
0361                 }
0362             }
0363             else
0364                 goto return_point_true;
0365             goto return_point_false;
0366 
0367             {
0368             return_point_true:
0369                 return true;
0370 
0371             return_point_false:
0372                 if (k.empty())
0373                     return false;
0374                 const match_continuation& this_k = k.back();
0375                 switch (this_k.position)
0376                 {
0377                 case match_continuation::pos_G2_vertex_loop:
0378                 {
0379                     G2_verts = this_k.G2_verts;
0380                     iter = this_k.iter;
0381                     dfs_num_k = this_k.dfs_num_k;
0382                     k.pop_back();
0383                     in_S[*G2_verts.first] = false;
0384                     i = source(*iter, G1);
0385                     j = target(*iter, G1);
0386                     goto G2_loop_k;
0387                 }
0388                 case match_continuation::pos_fi_adj_loop:
0389                 {
0390                     fi_adj = this_k.fi_adj;
0391                     iter = this_k.iter;
0392                     dfs_num_k = this_k.dfs_num_k;
0393                     k.pop_back();
0394                     in_S[*fi_adj.first] = false;
0395                     i = source(*iter, G1);
0396                     j = target(*iter, G1);
0397                     goto fi_adj_loop_k;
0398                 }
0399                 case match_continuation::pos_dfs_num:
0400                 {
0401                     k.pop_back();
0402                     goto return_point_false;
0403                 }
0404                 default:
0405                 {
0406                     BOOST_ASSERT(!"Bad position");
0407 #ifdef UNDER_CE
0408                     exit(-1);
0409 #else
0410                     abort();
0411 #endif
0412                 }
0413                 }
0414             }
0415         }
0416     };
0417 
0418     template < typename Graph, typename InDegreeMap >
0419     void compute_in_degree(const Graph& g, InDegreeMap in_degree_map)
0420     {
0421         BGL_FORALL_VERTICES_T(v, g, Graph)
0422         put(in_degree_map, v, 0);
0423 
0424         BGL_FORALL_VERTICES_T(u, g, Graph)
0425         BGL_FORALL_ADJ_T(u, v, g, Graph)
0426         put(in_degree_map, v, get(in_degree_map, v) + 1);
0427     }
0428 
0429 } // namespace detail
0430 
0431 template < typename InDegreeMap, typename Graph > class degree_vertex_invariant
0432 {
0433     typedef typename graph_traits< Graph >::vertex_descriptor vertex_t;
0434     typedef typename graph_traits< Graph >::degree_size_type size_type;
0435 
0436 public:
0437     typedef vertex_t argument_type;
0438     typedef size_type result_type;
0439 
0440     degree_vertex_invariant(const InDegreeMap& in_degree_map, const Graph& g)
0441     : m_in_degree_map(in_degree_map)
0442     , m_max_vertex_in_degree(0)
0443     , m_max_vertex_out_degree(0)
0444     , m_g(g)
0445     {
0446         BGL_FORALL_VERTICES_T(v, g, Graph)
0447         {
0448             m_max_vertex_in_degree
0449                 = (std::max)(m_max_vertex_in_degree, get(m_in_degree_map, v));
0450             m_max_vertex_out_degree
0451                 = (std::max)(m_max_vertex_out_degree, out_degree(v, g));
0452         }
0453     }
0454 
0455     size_type operator()(vertex_t v) const
0456     {
0457         return (m_max_vertex_in_degree + 1) * out_degree(v, m_g)
0458             + get(m_in_degree_map, v);
0459     }
0460     // The largest possible vertex invariant number
0461     size_type max BOOST_PREVENT_MACRO_SUBSTITUTION() const
0462     {
0463         return (m_max_vertex_in_degree + 1) * (m_max_vertex_out_degree + 1);
0464     }
0465 
0466 private:
0467     InDegreeMap m_in_degree_map;
0468     size_type m_max_vertex_in_degree;
0469     size_type m_max_vertex_out_degree;
0470     const Graph& m_g;
0471 };
0472 
0473 // Count actual number of vertices, even in filtered graphs.
0474 template < typename Graph > size_t count_vertices(const Graph& g)
0475 {
0476     size_t n = 0;
0477     BGL_FORALL_VERTICES_T(v, g, Graph)
0478     {
0479         (void)v;
0480         ++n;
0481     }
0482     return n;
0483 }
0484 
0485 template < typename Graph1, typename Graph2, typename IsoMapping,
0486     typename Invariant1, typename Invariant2, typename IndexMap1,
0487     typename IndexMap2 >
0488 bool isomorphism(const Graph1& G1, const Graph2& G2, IsoMapping f,
0489     Invariant1 invariant1, Invariant2 invariant2, std::size_t max_invariant,
0490     IndexMap1 index_map1, IndexMap2 index_map2)
0491 
0492 {
0493     // Graph requirements
0494     BOOST_CONCEPT_ASSERT((VertexListGraphConcept< Graph1 >));
0495     BOOST_CONCEPT_ASSERT((EdgeListGraphConcept< Graph1 >));
0496     BOOST_CONCEPT_ASSERT((VertexListGraphConcept< Graph2 >));
0497     // BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<Graph2> ));
0498 
0499     typedef typename graph_traits< Graph1 >::vertex_descriptor vertex1_t;
0500     typedef typename graph_traits< Graph2 >::vertex_descriptor vertex2_t;
0501     typedef typename graph_traits< Graph1 >::vertices_size_type size_type;
0502 
0503     // Vertex invariant requirement
0504     BOOST_CONCEPT_ASSERT(
0505         (AdaptableUnaryFunctionConcept< Invariant1, size_type, vertex1_t >));
0506     BOOST_CONCEPT_ASSERT(
0507         (AdaptableUnaryFunctionConcept< Invariant2, size_type, vertex2_t >));
0508 
0509     // Property map requirements
0510     BOOST_CONCEPT_ASSERT(
0511         (ReadWritePropertyMapConcept< IsoMapping, vertex1_t >));
0512     typedef typename property_traits< IsoMapping >::value_type IsoMappingValue;
0513     BOOST_STATIC_ASSERT((is_convertible< IsoMappingValue, vertex2_t >::value));
0514 
0515     BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept< IndexMap1, vertex1_t >));
0516     typedef typename property_traits< IndexMap1 >::value_type IndexMap1Value;
0517     BOOST_STATIC_ASSERT((is_convertible< IndexMap1Value, size_type >::value));
0518 
0519     BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept< IndexMap2, vertex2_t >));
0520     typedef typename property_traits< IndexMap2 >::value_type IndexMap2Value;
0521     BOOST_STATIC_ASSERT((is_convertible< IndexMap2Value, size_type >::value));
0522 
0523     if (count_vertices(G1) != count_vertices(G2))
0524         return false;
0525     if (count_vertices(G1) == 0 && count_vertices(G2) == 0)
0526         return true;
0527 
0528     detail::isomorphism_algo< Graph1, Graph2, IsoMapping, Invariant1,
0529         Invariant2, IndexMap1, IndexMap2 >
0530         algo(G1, G2, f, invariant1, invariant2, max_invariant, index_map1,
0531             index_map2);
0532     return algo.test_isomorphism();
0533 }
0534 
0535 namespace detail
0536 {
0537 
0538     template < typename Graph1, typename Graph2, typename IsoMapping,
0539         typename IndexMap1, typename IndexMap2, typename P, typename T,
0540         typename R >
0541     bool isomorphism_impl(const Graph1& G1, const Graph2& G2, IsoMapping f,
0542         IndexMap1 index_map1, IndexMap2 index_map2,
0543         const bgl_named_params< P, T, R >& params)
0544     {
0545         std::vector< std::size_t > in_degree1_vec(num_vertices(G1));
0546         typedef safe_iterator_property_map<
0547             std::vector< std::size_t >::iterator, IndexMap1
0548 #ifdef BOOST_NO_STD_ITERATOR_TRAITS
0549             ,
0550             std::size_t, std::size_t&
0551 #endif /* BOOST_NO_STD_ITERATOR_TRAITS */
0552             >
0553             InDeg1;
0554         InDeg1 in_degree1(
0555             in_degree1_vec.begin(), in_degree1_vec.size(), index_map1);
0556         compute_in_degree(G1, in_degree1);
0557 
0558         std::vector< std::size_t > in_degree2_vec(num_vertices(G2));
0559         typedef safe_iterator_property_map<
0560             std::vector< std::size_t >::iterator, IndexMap2
0561 #ifdef BOOST_NO_STD_ITERATOR_TRAITS
0562             ,
0563             std::size_t, std::size_t&
0564 #endif /* BOOST_NO_STD_ITERATOR_TRAITS */
0565             >
0566             InDeg2;
0567         InDeg2 in_degree2(
0568             in_degree2_vec.begin(), in_degree2_vec.size(), index_map2);
0569         compute_in_degree(G2, in_degree2);
0570 
0571         degree_vertex_invariant< InDeg1, Graph1 > invariant1(in_degree1, G1);
0572         degree_vertex_invariant< InDeg2, Graph2 > invariant2(in_degree2, G2);
0573 
0574         return isomorphism(G1, G2, f,
0575             choose_param(get_param(params, vertex_invariant1_t()), invariant1),
0576             choose_param(get_param(params, vertex_invariant2_t()), invariant2),
0577             choose_param(get_param(params, vertex_max_invariant_t()),
0578                 (invariant2.max)()),
0579             index_map1, index_map2);
0580     }
0581 
0582     template < typename G, typename Index > struct make_degree_invariant
0583     {
0584         const G& g;
0585         const Index& index;
0586         make_degree_invariant(const G& g, const Index& index)
0587         : g(g), index(index)
0588         {
0589         }
0590         typedef typename boost::graph_traits< G >::degree_size_type
0591             degree_size_type;
0592         typedef shared_array_property_map< degree_size_type, Index >
0593             prop_map_type;
0594         typedef degree_vertex_invariant< prop_map_type, G > result_type;
0595         result_type operator()() const
0596         {
0597             prop_map_type pm = make_shared_array_property_map(
0598                 num_vertices(g), degree_size_type(), index);
0599             compute_in_degree(g, pm);
0600             return result_type(pm, g);
0601         }
0602     };
0603 
0604 } // namespace detail
0605 
0606 namespace graph
0607 {
0608     namespace detail
0609     {
0610         template < typename Graph1, typename Graph2 > struct isomorphism_impl
0611         {
0612             typedef bool result_type;
0613             typedef result_type type;
0614             template < typename ArgPack >
0615             bool operator()(const Graph1& g1, const Graph2& g2,
0616                 const ArgPack& arg_pack) const
0617             {
0618                 using namespace boost::graph::keywords;
0619                 typedef typename boost::detail::override_const_property_result<
0620                     ArgPack, tag::vertex_index1_map, boost::vertex_index_t,
0621                     Graph1 >::type index1_map_type;
0622                 typedef typename boost::detail::override_const_property_result<
0623                     ArgPack, tag::vertex_index2_map, boost::vertex_index_t,
0624                     Graph2 >::type index2_map_type;
0625                 index1_map_type index1_map
0626                     = boost::detail::override_const_property(
0627                         arg_pack, _vertex_index1_map, g1, boost::vertex_index);
0628                 index2_map_type index2_map
0629                     = boost::detail::override_const_property(
0630                         arg_pack, _vertex_index2_map, g2, boost::vertex_index);
0631                 typedef typename graph_traits< Graph2 >::vertex_descriptor
0632                     vertex2_t;
0633                 typename std::vector< vertex2_t >::size_type n
0634                     = (typename std::vector< vertex2_t >::size_type)
0635                         num_vertices(g1);
0636                 std::vector< vertex2_t > f(n);
0637                 typename boost::parameter::lazy_binding< ArgPack,
0638                     tag::vertex_invariant1,
0639                     boost::detail::make_degree_invariant< Graph1,
0640                         index1_map_type > >::type invariant1
0641                     = arg_pack[_vertex_invariant1
0642                         || boost::detail::make_degree_invariant< Graph1,
0643                             index1_map_type >(g1, index1_map)];
0644                 typename boost::parameter::lazy_binding< ArgPack,
0645                     tag::vertex_invariant2,
0646                     boost::detail::make_degree_invariant< Graph2,
0647                         index2_map_type > >::type invariant2
0648                     = arg_pack[_vertex_invariant2
0649                         || boost::detail::make_degree_invariant< Graph2,
0650                             index2_map_type >(g2, index2_map)];
0651                 return boost::isomorphism(g1, g2,
0652                     choose_param(
0653                         arg_pack[_isomorphism_map | boost::param_not_found()],
0654                         make_shared_array_property_map(
0655                             num_vertices(g1), vertex2_t(), index1_map)),
0656                     invariant1, invariant2,
0657                     arg_pack[_vertex_max_invariant | (invariant2.max)()],
0658                     index1_map, index2_map);
0659             }
0660         };
0661     }
0662     BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(isomorphism, 2, 6)
0663 }
0664 
0665 // Named parameter interface
0666 BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(isomorphism, 2)
0667 
0668 // Verify that the given mapping iso_map from the vertices of g1 to the
0669 // vertices of g2 describes an isomorphism.
0670 // Note: this could be made much faster by specializing based on the graph
0671 // concepts modeled, but since we're verifying an O(n^(lg n)) algorithm,
0672 // O(n^4) won't hurt us.
0673 template < typename Graph1, typename Graph2, typename IsoMap >
0674 inline bool verify_isomorphism(
0675     const Graph1& g1, const Graph2& g2, IsoMap iso_map)
0676 {
0677 #if 0
0678     // problematic for filtered_graph!
0679     if (num_vertices(g1) != num_vertices(g2) || num_edges(g1) != num_edges(g2))
0680       return false;
0681 #endif
0682 
0683     BGL_FORALL_EDGES_T(e1, g1, Graph1)
0684     {
0685         bool found_edge = false;
0686         BGL_FORALL_EDGES_T(e2, g2, Graph2)
0687         {
0688             if (source(e2, g2) == get(iso_map, source(e1, g1))
0689                 && target(e2, g2) == get(iso_map, target(e1, g1)))
0690             {
0691                 found_edge = true;
0692             }
0693         }
0694 
0695         if (!found_edge)
0696             return false;
0697     }
0698 
0699     return true;
0700 }
0701 
0702 } // namespace boost
0703 
0704 #ifdef BOOST_ISO_INCLUDED_ITER_MACROS
0705 #undef BOOST_ISO_INCLUDED_ITER_MACROS
0706 #include <boost/graph/iteration_macros_undef.hpp>
0707 #endif
0708 
0709 #endif // BOOST_GRAPH_ISOMORPHISM_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!