epoc32/include/stdapis/boost/graph/isomorphism.hpp
branchSymbian2
changeset 2 2fe1408b6811
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/epoc32/include/stdapis/boost/graph/isomorphism.hpp	Tue Mar 16 16:12:26 2010 +0000
     1.3 @@ -0,0 +1,467 @@
     1.4 +// Copyright (C) 2001 Jeremy Siek, Douglas Gregor, Brian Osman
     1.5 +//
     1.6 +// Distributed under the Boost Software License, Version 1.0. (See
     1.7 +// accompanying file LICENSE_1_0.txt or copy at
     1.8 +// http://www.boost.org/LICENSE_1_0.txt)
     1.9 +#ifndef BOOST_GRAPH_ISOMORPHISM_HPP
    1.10 +#define BOOST_GRAPH_ISOMORPHISM_HPP
    1.11 +
    1.12 +#include <utility>
    1.13 +#include <vector>
    1.14 +#include <iterator>
    1.15 +#include <algorithm>
    1.16 +#include <boost/config.hpp>
    1.17 +#include <boost/graph/depth_first_search.hpp>
    1.18 +#include <boost/utility.hpp>
    1.19 +#include <boost/detail/algorithm.hpp>
    1.20 +#include <boost/pending/indirect_cmp.hpp> // for make_indirect_pmap
    1.21 +
    1.22 +#ifndef BOOST_GRAPH_ITERATION_MACROS_HPP
    1.23 +#define BOOST_ISO_INCLUDED_ITER_MACROS // local macro, see bottom of file
    1.24 +#include <boost/graph/iteration_macros.hpp>
    1.25 +#endif
    1.26 +
    1.27 +namespace boost {
    1.28 +
    1.29 +  namespace detail {
    1.30 +
    1.31 +    template <typename Graph1, typename Graph2, typename IsoMapping,
    1.32 +      typename Invariant1, typename Invariant2,
    1.33 +      typename IndexMap1, typename IndexMap2>
    1.34 +    class isomorphism_algo
    1.35 +    {
    1.36 +      typedef typename graph_traits<Graph1>::vertex_descriptor vertex1_t;
    1.37 +      typedef typename graph_traits<Graph2>::vertex_descriptor vertex2_t;
    1.38 +      typedef typename graph_traits<Graph1>::edge_descriptor edge1_t;
    1.39 +      typedef typename graph_traits<Graph1>::vertices_size_type size_type;
    1.40 +      typedef typename Invariant1::result_type invar1_value;
    1.41 +      typedef typename Invariant2::result_type invar2_value;
    1.42 +    
    1.43 +      const Graph1& G1;
    1.44 +      const Graph2& G2;
    1.45 +      IsoMapping f;
    1.46 +      Invariant1 invariant1;
    1.47 +      Invariant2 invariant2;
    1.48 +      std::size_t max_invariant;
    1.49 +      IndexMap1 index_map1;
    1.50 +      IndexMap2 index_map2;
    1.51 +    
    1.52 +      std::vector<vertex1_t> dfs_vertices;
    1.53 +      typedef typename std::vector<vertex1_t>::iterator vertex_iter;
    1.54 +      std::vector<int> dfs_num_vec;
    1.55 +      typedef safe_iterator_property_map<typename std::vector<int>::iterator,
    1.56 +                                         IndexMap1
    1.57 +#ifdef BOOST_NO_STD_ITERATOR_TRAITS
    1.58 +                                         , int, int&
    1.59 +#endif /* BOOST_NO_STD_ITERATOR_TRAITS */
    1.60 +                                         > DFSNumMap;
    1.61 +      DFSNumMap dfs_num;
    1.62 +      std::vector<edge1_t> ordered_edges;
    1.63 +      typedef typename std::vector<edge1_t>::iterator edge_iter;
    1.64 +    
    1.65 +      std::vector<char> in_S_vec;
    1.66 +      typedef safe_iterator_property_map<typename std::vector<char>::iterator,
    1.67 +                                         IndexMap2
    1.68 +#ifdef BOOST_NO_STD_ITERATOR_TRAITS
    1.69 +                                         , char, char&
    1.70 +#endif /* BOOST_NO_STD_ITERATOR_TRAITS */
    1.71 +                                         > InSMap;
    1.72 +      InSMap in_S;
    1.73 +    
    1.74 +      int num_edges_on_k;
    1.75 +    
    1.76 +      friend struct compare_multiplicity;
    1.77 +      struct compare_multiplicity
    1.78 +      {
    1.79 +        compare_multiplicity(Invariant1 invariant1, size_type* multiplicity)
    1.80 +          : invariant1(invariant1), multiplicity(multiplicity) { }
    1.81 +        bool operator()(const vertex1_t& x, const vertex1_t& y) const {
    1.82 +          return multiplicity[invariant1(x)] < multiplicity[invariant1(y)];
    1.83 +        }
    1.84 +        Invariant1 invariant1;
    1.85 +        size_type* multiplicity;
    1.86 +      };
    1.87 +    
    1.88 +      struct record_dfs_order : default_dfs_visitor
    1.89 +      {
    1.90 +        record_dfs_order(std::vector<vertex1_t>& v, std::vector<edge1_t>& e) 
    1.91 +          : vertices(v), edges(e) { }
    1.92 +    
    1.93 +        void discover_vertex(vertex1_t v, const Graph1&) const {
    1.94 +          vertices.push_back(v);
    1.95 +        }
    1.96 +        void examine_edge(edge1_t e, const Graph1& G1) const {
    1.97 +          edges.push_back(e);
    1.98 +        }
    1.99 +        std::vector<vertex1_t>& vertices;
   1.100 +        std::vector<edge1_t>& edges;
   1.101 +      };
   1.102 +    
   1.103 +      struct edge_cmp {
   1.104 +        edge_cmp(const Graph1& G1, DFSNumMap dfs_num)
   1.105 +          : G1(G1), dfs_num(dfs_num) { }
   1.106 +        bool operator()(const edge1_t& e1, const edge1_t& e2) const {
   1.107 +          using namespace std;
   1.108 +          int u1 = dfs_num[source(e1,G1)], v1 = dfs_num[target(e1,G1)];
   1.109 +          int u2 = dfs_num[source(e2,G1)], v2 = dfs_num[target(e2,G1)];
   1.110 +          int m1 = (max)(u1, v1);
   1.111 +          int m2 = (max)(u2, v2);
   1.112 +          // lexicographical comparison 
   1.113 +          return std::make_pair(m1, std::make_pair(u1, v1))
   1.114 +            < std::make_pair(m2, std::make_pair(u2, v2));
   1.115 +        }
   1.116 +        const Graph1& G1;
   1.117 +        DFSNumMap dfs_num;
   1.118 +      };
   1.119 +    
   1.120 +    public:
   1.121 +      isomorphism_algo(const Graph1& G1, const Graph2& G2, IsoMapping f,
   1.122 +                       Invariant1 invariant1, Invariant2 invariant2, std::size_t max_invariant,
   1.123 +                       IndexMap1 index_map1, IndexMap2 index_map2)
   1.124 +        : G1(G1), G2(G2), f(f), invariant1(invariant1), invariant2(invariant2),
   1.125 +          max_invariant(max_invariant),
   1.126 +          index_map1(index_map1), index_map2(index_map2)
   1.127 +      {
   1.128 +        in_S_vec.resize(num_vertices(G1));
   1.129 +        in_S = make_safe_iterator_property_map
   1.130 +          (in_S_vec.begin(), in_S_vec.size(), index_map2
   1.131 +#ifdef BOOST_NO_STD_ITERATOR_TRAITS
   1.132 +           , in_S_vec.front()
   1.133 +#endif /* BOOST_NO_STD_ITERATOR_TRAITS */
   1.134 +           );
   1.135 +      }
   1.136 +    
   1.137 +      bool test_isomorphism()
   1.138 +      {
   1.139 +        {
   1.140 +          std::vector<invar1_value> invar1_array;
   1.141 +          BGL_FORALL_VERTICES_T(v, G1, Graph1)
   1.142 +            invar1_array.push_back(invariant1(v));
   1.143 +          sort(invar1_array);
   1.144 +        
   1.145 +          std::vector<invar2_value> invar2_array;
   1.146 +          BGL_FORALL_VERTICES_T(v, G2, Graph2)
   1.147 +            invar2_array.push_back(invariant2(v));
   1.148 +          sort(invar2_array);
   1.149 +          if (! equal(invar1_array, invar2_array))
   1.150 +            return false;
   1.151 +        }
   1.152 +        
   1.153 +        std::vector<vertex1_t> V_mult;
   1.154 +        BGL_FORALL_VERTICES_T(v, G1, Graph1)
   1.155 +          V_mult.push_back(v);
   1.156 +        {
   1.157 +          std::vector<size_type> multiplicity(max_invariant, 0);
   1.158 +          BGL_FORALL_VERTICES_T(v, G1, Graph1)
   1.159 +            ++multiplicity[invariant1(v)];
   1.160 +          sort(V_mult, compare_multiplicity(invariant1, &multiplicity[0]));
   1.161 +        }
   1.162 +        
   1.163 +        std::vector<default_color_type> color_vec(num_vertices(G1));
   1.164 +        safe_iterator_property_map<std::vector<default_color_type>::iterator,
   1.165 +                                   IndexMap1
   1.166 +#ifdef BOOST_NO_STD_ITERATOR_TRAITS
   1.167 +                                   , default_color_type, default_color_type&
   1.168 +#endif /* BOOST_NO_STD_ITERATOR_TRAITS */
   1.169 +                                   >
   1.170 +          color_map(color_vec.begin(), color_vec.size(), index_map1);
   1.171 +        record_dfs_order dfs_visitor(dfs_vertices, ordered_edges);
   1.172 +        typedef color_traits<default_color_type> Color;
   1.173 +        for (vertex_iter u = V_mult.begin(); u != V_mult.end(); ++u) {
   1.174 +          if (color_map[*u] == Color::white()) {
   1.175 +            dfs_visitor.start_vertex(*u, G1);
   1.176 +            depth_first_visit(G1, *u, dfs_visitor, color_map);
   1.177 +          }
   1.178 +        }
   1.179 +        // Create the dfs_num array and dfs_num_map
   1.180 +        dfs_num_vec.resize(num_vertices(G1));
   1.181 +        dfs_num = make_safe_iterator_property_map(dfs_num_vec.begin(),
   1.182 +                                                  dfs_num_vec.size(), 
   1.183 +                                                  index_map1
   1.184 +#ifdef BOOST_NO_STD_ITERATOR_TRAITS
   1.185 +                                                  , dfs_num_vec.front()
   1.186 +#endif /* BOOST_NO_STD_ITERATOR_TRAITS */
   1.187 +                                                  );
   1.188 +        size_type n = 0;
   1.189 +        for (vertex_iter v = dfs_vertices.begin(); v != dfs_vertices.end(); ++v)
   1.190 +          dfs_num[*v] = n++;
   1.191 +        
   1.192 +        sort(ordered_edges, edge_cmp(G1, dfs_num));
   1.193 +        
   1.194 +    
   1.195 +        int dfs_num_k = -1;
   1.196 +        return this->match(ordered_edges.begin(), dfs_num_k);
   1.197 +      }
   1.198 +    
   1.199 +    private:
   1.200 +      bool match(edge_iter iter, int dfs_num_k)
   1.201 +      {
   1.202 +        if (iter != ordered_edges.end()) {
   1.203 +          vertex1_t i = source(*iter, G1), j = target(*iter, G2);
   1.204 +          if (dfs_num[i] > dfs_num_k) {
   1.205 +            vertex1_t kp1 = dfs_vertices[dfs_num_k + 1];
   1.206 +            BGL_FORALL_VERTICES_T(u, G2, Graph2) {
   1.207 +              if (invariant1(kp1) == invariant2(u) && in_S[u] == false) {
   1.208 +                f[kp1] = u;
   1.209 +                in_S[u] = true;
   1.210 +                num_edges_on_k = 0;
   1.211 +                
   1.212 +                if (match(iter, dfs_num_k + 1))
   1.213 +#if 0
   1.214 +                    // dwa 2003/7/11 -- this *HAS* to be a bug!
   1.215 +                    ;
   1.216 +#endif 
   1.217 +                    return true;
   1.218 +                    
   1.219 +                in_S[u] = false;
   1.220 +              }
   1.221 +            }
   1.222 +               
   1.223 +          }
   1.224 +          else if (dfs_num[j] > dfs_num_k) {
   1.225 +            vertex1_t k = dfs_vertices[dfs_num_k];
   1.226 +            num_edges_on_k -= 
   1.227 +              count_if(adjacent_vertices(f[k], G2), make_indirect_pmap(in_S));
   1.228 +                
   1.229 +            for (int jj = 0; jj < dfs_num_k; ++jj) {
   1.230 +              vertex1_t j = dfs_vertices[jj];
   1.231 +              num_edges_on_k -= count(adjacent_vertices(f[j], G2), f[k]);
   1.232 +            }
   1.233 +                
   1.234 +            if (num_edges_on_k != 0)
   1.235 +              return false;
   1.236 +            BGL_FORALL_ADJ_T(f[i], v, G2, Graph2)
   1.237 +              if (invariant2(v) == invariant1(j) && in_S[v] == false) {
   1.238 +                f[j] = v;
   1.239 +                in_S[v] = true;
   1.240 +                num_edges_on_k = 1;
   1.241 +                BOOST_USING_STD_MAX();
   1.242 +                int next_k = max BOOST_PREVENT_MACRO_SUBSTITUTION(dfs_num_k, max BOOST_PREVENT_MACRO_SUBSTITUTION(dfs_num[i], dfs_num[j]));
   1.243 +                if (match(next(iter), next_k))
   1.244 +                  return true;
   1.245 +                in_S[v] = false;
   1.246 +              }
   1.247 +                
   1.248 +                
   1.249 +          }
   1.250 +          else {
   1.251 +            if (contains(adjacent_vertices(f[i], G2), f[j])) {
   1.252 +              ++num_edges_on_k;
   1.253 +              if (match(next(iter), dfs_num_k))
   1.254 +                return true;
   1.255 +            }
   1.256 +                
   1.257 +          }
   1.258 +        } else 
   1.259 +          return true;
   1.260 +        return false;
   1.261 +      }
   1.262 +    
   1.263 +    };
   1.264 +
   1.265 +    
   1.266 +    template <typename Graph, typename InDegreeMap>
   1.267 +    void compute_in_degree(const Graph& g, InDegreeMap in_degree_map)
   1.268 +    {
   1.269 +      BGL_FORALL_VERTICES_T(v, g, Graph)
   1.270 +        put(in_degree_map, v, 0);
   1.271 +
   1.272 +      BGL_FORALL_VERTICES_T(u, g, Graph)
   1.273 +        BGL_FORALL_ADJ_T(u, v, g, Graph)
   1.274 +        put(in_degree_map, v, get(in_degree_map, v) + 1);
   1.275 +    }
   1.276 +
   1.277 +  } // namespace detail
   1.278 +
   1.279 +
   1.280 +  template <typename InDegreeMap, typename Graph>
   1.281 +  class degree_vertex_invariant
   1.282 +  {
   1.283 +    typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
   1.284 +    typedef typename graph_traits<Graph>::degree_size_type size_type;
   1.285 +  public:
   1.286 +    typedef vertex_t argument_type;
   1.287 +    typedef size_type result_type;
   1.288 +
   1.289 +    degree_vertex_invariant(const InDegreeMap& in_degree_map, const Graph& g)
   1.290 +      : m_in_degree_map(in_degree_map), m_g(g) { }
   1.291 +
   1.292 +    size_type operator()(vertex_t v) const {
   1.293 +      return (num_vertices(m_g) + 1) * out_degree(v, m_g)
   1.294 +        + get(m_in_degree_map, v);
   1.295 +    }
   1.296 +    // The largest possible vertex invariant number
   1.297 +    size_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { 
   1.298 +      return num_vertices(m_g) * num_vertices(m_g) + num_vertices(m_g);
   1.299 +    }
   1.300 +  private:
   1.301 +    InDegreeMap m_in_degree_map;
   1.302 +    const Graph& m_g;
   1.303 +  };
   1.304 +
   1.305 +
   1.306 +  template <typename Graph1, typename Graph2, typename IsoMapping, 
   1.307 +    typename Invariant1, typename Invariant2,
   1.308 +    typename IndexMap1, typename IndexMap2>
   1.309 +  bool isomorphism(const Graph1& G1, const Graph2& G2, IsoMapping f, 
   1.310 +                   Invariant1 invariant1, Invariant2 invariant2, 
   1.311 +                   std::size_t max_invariant,
   1.312 +                   IndexMap1 index_map1, IndexMap2 index_map2)
   1.313 +
   1.314 +  {
   1.315 +    // Graph requirements
   1.316 +    function_requires< VertexListGraphConcept<Graph1> >();
   1.317 +    function_requires< EdgeListGraphConcept<Graph1> >();
   1.318 +    function_requires< VertexListGraphConcept<Graph2> >();
   1.319 +    function_requires< BidirectionalGraphConcept<Graph2> >();
   1.320 +    
   1.321 +    typedef typename graph_traits<Graph1>::vertex_descriptor vertex1_t;
   1.322 +    typedef typename graph_traits<Graph2>::vertex_descriptor vertex2_t;
   1.323 +    typedef typename graph_traits<Graph1>::vertices_size_type size_type;
   1.324 +    
   1.325 +    // Vertex invariant requirement
   1.326 +    function_requires< AdaptableUnaryFunctionConcept<Invariant1,
   1.327 +      size_type, vertex1_t> >();
   1.328 +    function_requires< AdaptableUnaryFunctionConcept<Invariant2,
   1.329 +      size_type, vertex2_t> >();
   1.330 +    
   1.331 +    // Property map requirements
   1.332 +    function_requires< ReadWritePropertyMapConcept<IsoMapping, vertex1_t> >();
   1.333 +    typedef typename property_traits<IsoMapping>::value_type IsoMappingValue;
   1.334 +    BOOST_STATIC_ASSERT((is_same<IsoMappingValue, vertex2_t>::value));
   1.335 +    
   1.336 +    function_requires< ReadablePropertyMapConcept<IndexMap1, vertex1_t> >();
   1.337 +    typedef typename property_traits<IndexMap1>::value_type IndexMap1Value;
   1.338 +    BOOST_STATIC_ASSERT((is_convertible<IndexMap1Value, size_type>::value));
   1.339 +    
   1.340 +    function_requires< ReadablePropertyMapConcept<IndexMap2, vertex2_t> >();
   1.341 +    typedef typename property_traits<IndexMap2>::value_type IndexMap2Value;
   1.342 +    BOOST_STATIC_ASSERT((is_convertible<IndexMap2Value, size_type>::value));
   1.343 +    
   1.344 +    if (num_vertices(G1) != num_vertices(G2))
   1.345 +      return false;
   1.346 +    if (num_vertices(G1) == 0 && num_vertices(G2) == 0)
   1.347 +      return true;
   1.348 +    
   1.349 +    detail::isomorphism_algo<Graph1, Graph2, IsoMapping, Invariant1,
   1.350 +      Invariant2, IndexMap1, IndexMap2> 
   1.351 +      algo(G1, G2, f, invariant1, invariant2, max_invariant, 
   1.352 +           index_map1, index_map2);
   1.353 +    return algo.test_isomorphism();
   1.354 +  }
   1.355 +
   1.356 +
   1.357 +  namespace detail {
   1.358 +  
   1.359 +    template <typename Graph1, typename Graph2, 
   1.360 +      typename IsoMapping, 
   1.361 +      typename IndexMap1, typename IndexMap2,
   1.362 +      typename P, typename T, typename R>
   1.363 +    bool isomorphism_impl(const Graph1& G1, const Graph2& G2, 
   1.364 +                          IsoMapping f, IndexMap1 index_map1, IndexMap2 index_map2,
   1.365 +                          const bgl_named_params<P,T,R>& params)
   1.366 +    {
   1.367 +      std::vector<std::size_t> in_degree1_vec(num_vertices(G1));
   1.368 +      typedef safe_iterator_property_map<std::vector<std::size_t>::iterator,
   1.369 +                                         IndexMap1
   1.370 +#ifdef BOOST_NO_STD_ITERATOR_TRAITS
   1.371 +                                         , std::size_t, std::size_t&
   1.372 +#endif /* BOOST_NO_STD_ITERATOR_TRAITS */
   1.373 +                                         > InDeg1;
   1.374 +      InDeg1 in_degree1(in_degree1_vec.begin(), in_degree1_vec.size(), index_map1);
   1.375 +      compute_in_degree(G1, in_degree1);
   1.376 +
   1.377 +      std::vector<std::size_t> in_degree2_vec(num_vertices(G2));
   1.378 +      typedef safe_iterator_property_map<std::vector<std::size_t>::iterator, 
   1.379 +                                         IndexMap2
   1.380 +#ifdef BOOST_NO_STD_ITERATOR_TRAITS
   1.381 +                                         , std::size_t, std::size_t&
   1.382 +#endif /* BOOST_NO_STD_ITERATOR_TRAITS */
   1.383 +                                         > InDeg2;
   1.384 +      InDeg2 in_degree2(in_degree2_vec.begin(), in_degree2_vec.size(), index_map2);
   1.385 +      compute_in_degree(G2, in_degree2);
   1.386 +
   1.387 +      degree_vertex_invariant<InDeg1, Graph1> invariant1(in_degree1, G1);
   1.388 +      degree_vertex_invariant<InDeg2, Graph2> invariant2(in_degree2, G2);
   1.389 +
   1.390 +      return isomorphism(G1, G2, f,
   1.391 +                         choose_param(get_param(params, vertex_invariant1_t()), invariant1),
   1.392 +                         choose_param(get_param(params, vertex_invariant2_t()), invariant2),
   1.393 +                         choose_param(get_param(params, vertex_max_invariant_t()), (invariant2.max)()),
   1.394 +                         index_map1, index_map2
   1.395 +                         );  
   1.396 +    }  
   1.397 +   
   1.398 +  } // namespace detail
   1.399 +
   1.400 +
   1.401 +  // Named parameter interface
   1.402 +  template <typename Graph1, typename Graph2, class P, class T, class R>
   1.403 +  bool isomorphism(const Graph1& g1,
   1.404 +                   const Graph2& g2,
   1.405 +                   const bgl_named_params<P,T,R>& params)
   1.406 +  {
   1.407 +    typedef typename graph_traits<Graph2>::vertex_descriptor vertex2_t;
   1.408 +    typename std::vector<vertex2_t>::size_type n = num_vertices(g1);
   1.409 +    std::vector<vertex2_t> f(n);
   1.410 +    return detail::isomorphism_impl
   1.411 +      (g1, g2, 
   1.412 +       choose_param(get_param(params, vertex_isomorphism_t()),
   1.413 +                    make_safe_iterator_property_map(f.begin(), f.size(),
   1.414 +                                                    choose_const_pmap(get_param(params, vertex_index1),
   1.415 +                                                                      g1, vertex_index), vertex2_t())),
   1.416 +       choose_const_pmap(get_param(params, vertex_index1), g1, vertex_index),
   1.417 +       choose_const_pmap(get_param(params, vertex_index2), g2, vertex_index),
   1.418 +       params
   1.419 +       );
   1.420 +  }
   1.421 +
   1.422 +  // All defaults interface
   1.423 +  template <typename Graph1, typename Graph2>
   1.424 +  bool isomorphism(const Graph1& g1, const Graph2& g2)
   1.425 +  {
   1.426 +    return isomorphism(g1, g2,
   1.427 +                       bgl_named_params<int, buffer_param_t>(0));// bogus named param
   1.428 +  }
   1.429 +
   1.430 +
   1.431 +  // Verify that the given mapping iso_map from the vertices of g1 to the
   1.432 +  // vertices of g2 describes an isomorphism.
   1.433 +  // Note: this could be made much faster by specializing based on the graph
   1.434 +  // concepts modeled, but since we're verifying an O(n^(lg n)) algorithm,
   1.435 +  // O(n^4) won't hurt us.
   1.436 +  template<typename Graph1, typename Graph2, typename IsoMap>
   1.437 +  inline bool verify_isomorphism(const Graph1& g1, const Graph2& g2, IsoMap iso_map)
   1.438 +  {
   1.439 +#if 0
   1.440 +    // problematic for filtered_graph!
   1.441 +    if (num_vertices(g1) != num_vertices(g2) || num_edges(g1) != num_edges(g2))
   1.442 +      return false;
   1.443 +#endif
   1.444 +  
   1.445 +    for (typename graph_traits<Graph1>::edge_iterator e1 = edges(g1).first;
   1.446 +         e1 != edges(g1).second; ++e1) {
   1.447 +      bool found_edge = false;
   1.448 +      for (typename graph_traits<Graph2>::edge_iterator e2 = edges(g2).first;
   1.449 +           e2 != edges(g2).second && !found_edge; ++e2) {
   1.450 +        if (source(*e2, g2) == get(iso_map, source(*e1, g1)) &&
   1.451 +            target(*e2, g2) == get(iso_map, target(*e1, g1))) {
   1.452 +          found_edge = true;
   1.453 +        }
   1.454 +      }
   1.455 +    
   1.456 +      if (!found_edge)
   1.457 +        return false;
   1.458 +    }
   1.459 +  
   1.460 +    return true;
   1.461 +  }
   1.462 +
   1.463 +} // namespace boost
   1.464 +
   1.465 +#ifdef BOOST_ISO_INCLUDED_ITER_MACROS
   1.466 +#undef BOOST_ISO_INCLUDED_ITER_MACROS
   1.467 +#include <boost/graph/iteration_macros_undef.hpp>
   1.468 +#endif
   1.469 +
   1.470 +#endif // BOOST_GRAPH_ISOMORPHISM_HPP