boost/graph/mesh_graph_generator.hpp

0001 // Copyright 2004, 2005 The Trustees of Indiana University.
0002
0003 // Use, modification and distribution is subject to the Boost Software
0004 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0005 // http://www.boost.org/LICENSE_1_0.txt)
0006
0007 //  Authors: Nick Edmonds
0008 //           Andrew Lumsdaine
0009 #ifndef BOOST_GRAPH_MESH_GENERATOR_HPP
0010 #define BOOST_GRAPH_MESH_GENERATOR_HPP
0011
0012 #include <iterator>
0013 #include <utility>
0014 #include <boost/assert.hpp>
0015 #include <boost/graph/graph_traits.hpp>
0016 #include <boost/type_traits/is_base_and_derived.hpp>
0017 #include <boost/type_traits/is_same.hpp>
0018
0019 namespace boost
0020 {
0021
0022 template < typename Graph > class mesh_iterator
0023 {
0024     typedef typename graph_traits< Graph >::directed_category directed_category;
0025     typedef
0026         typename graph_traits< Graph >::vertices_size_type vertices_size_type;
0027
0028     BOOST_STATIC_CONSTANT(bool,
0029         is_undirected
0030         = (is_base_and_derived< undirected_tag, directed_category >::value
0031             || is_same< undirected_tag, directed_category >::value));
0032
0033 public:
0034     typedef std::input_iterator_tag iterator_category;
0035     typedef std::pair< vertices_size_type, vertices_size_type > value_type;
0036     typedef const value_type& reference;
0037     typedef const value_type* pointer;
0038     typedef void difference_type;
0039
0040     mesh_iterator() : x(0), y(0), done(true) {}
0041
0042     // Vertices are numbered in row-major order
0043     // Assumes directed
0044     mesh_iterator(
0045         vertices_size_type x, vertices_size_type y, bool toroidal = true)
0046     : x(x)
0047     , y(y)
0048     , n(x * y)
0049     , source(0)
0050     , target(1)
0051     , current(0, 1)
0052     , toroidal(toroidal)
0053     , done(false)
0054     {
0055         BOOST_ASSERT(x > 1 && y > 1);
0056     }
0057
0058     reference operator*() const { return current; }
0059     pointer operator->() const { return &current; }
0060
0061     mesh_iterator& operator++()
0062     {
0063         if (is_undirected)
0064         {
0065             if (!toroidal)
0066             {
0067                 if (target == source + 1)
0068                     if (source < x * (y - 1))
0069                         target = source + x;
0070                     else
0071                     {
0072                         source++;
0073                         target = (source % x) < x - 1 ? source + 1 : source + x;
0074                         if (target > n)
0075                             done = true;
0076                     }
0077                 else if (target == source + x)
0078                 {
0079                     source++;
0080                     target = (source % x) < x - 1 ? source + 1 : source + x;
0081                 }
0082             }
0083             else
0084             {
0085                 if (target == source + 1 || target == source - (source % x))
0086                     target = (source + x) % n;
0087                 else if (target == (source + x) % n)
0088                 {
0089                     if (source == n - 1)
0090                         done = true;
0091                     else
0092                     {
0093                         source++;
0094                         target = (source % x) < (x - 1) ? source + 1
0095                                                         : source - (source % x);
0096                     }
0097                 }
0098             }
0099         }
0100         else
0101         { // Directed
0102             if (!toroidal)
0103             {
0104                 if (target == source - x)
0105                     target = source % x > 0 ? source - 1 : source + 1;
0106                 else if (target == source - 1)
0107                     if ((source % x) < (x - 1))
0108                         target = source + 1;
0109                     else if (source < x * (y - 1))
0110                         target = source + x;
0111                     else
0112                     {
0113                         done = true;
0114                     }
0115                 else if (target == source + 1)
0116                     if (source < x * (y - 1))
0117                         target = source + x;
0118                     else
0119                     {
0120                         source++;
0121                         target = source - x;
0122                     }
0123                 else if (target == source + x)
0124                 {
0125                     source++;
0126                     target = (source >= x) ? source - x : source - 1;
0127                 }
0128             }
0129             else
0130             {
0131                 if (source == n - 1 && target == (source + x) % n)
0132                     done = true;
0133                 else if (target == source - 1 || target == source + x - 1)
0134                     target = (source + x) % n;
0135                 else if (target == source + 1
0136                     || target == source - (source % x))
0137                     target = (source - x + n) % n;
0138                 else if (target == (source - x + n) % n)
0139                     target = (source % x > 0) ? source - 1 : source + x - 1;
0140                 else if (target == (source + x) % n)
0141                 {
0142                     source++;
0143                     target = (source % x) < (x - 1) ? source + 1
0144                                                     : source - (source % x);
0145                 }
0146             }
0147         }
0148
0149         current.first = source;
0150         current.second = target;
0151
0152         return *this;
0153     }
0154
0155     mesh_iterator operator++(int)
0156     {
0157         mesh_iterator temp(*this);
0158         ++(*this);
0159         return temp;
0160     }
0161
0162     bool operator==(const mesh_iterator& other) const
0163     {
0164         return done == other.done;
0165     }
0166
0167     bool operator!=(const mesh_iterator& other) const
0168     {
0169         return !(*this == other);
0170     }
0171
0172 private:
0173     vertices_size_type x, y;
0174     vertices_size_type n;
0175     vertices_size_type source;
0176     vertices_size_type target;
0177     value_type current;
0178     bool toroidal;
0179     bool done;
0180 };
0181
0182 } // end namespace boost
0183
0184 #endif // BOOST_GRAPH_MESH_GENERATOR_HPP