COIN-OR::LEMON - Graph Library

Changeset 335:160bf92c7cdc in lemon-1.2


Ignore:
Timestamp:
10/20/08 12:36:02 (11 years ago)
Author:
Balazs Dezso <deba@…>
Branch:
default
Phase:
public
Message:

Improvement on grid graphs

  • The indexing of matrix is changed according to integer points of the plane.
  • The graph type does not depend on the UndirGraphExtender?.
  • Improving documentation.
  • Improved image generation.
Files:
1 added
4 edited

Legend:

Unmodified
Added
Removed
  • doc/CMakeLists.txt

    r225 r335  
    1414      COMMAND rm -rf gen-images
    1515      COMMAND mkdir gen-images
     16      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
    1617      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
    1718      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
  • doc/Makefile.am

    r227 r335  
    1212
    1313DOC_EPS_IMAGES18 = \
     14        grid_graph.eps \
    1415        nodeshape_0.eps \
    1516        nodeshape_1.eps \
  • lemon/grid_graph.h

    r334 r335  
    2020#define GRID_GRAPH_H
    2121
    22 #include <iostream>
    2322#include <lemon/core.h>
     23#include <lemon/bits/graph_extender.h>
     24#include <lemon/dim2.h>
    2425#include <lemon/assert.h>
    25 
    26 #include <lemon/bits/base_extender.h>
    27 #include <lemon/bits/graph_extender.h>
    28 
    29 #include <lemon/dim2.h>
    3026
    3127///\ingroup graphs
     
    4238
    4339    class Node;
     40    class Edge;
    4441    class Arc;
    4542
     
    5047  protected:
    5148
    52     void construct(int w, int h) {
    53       _height = h; _width = w;
    54       _nodeNum = h * w; _arcNum = 2 * _nodeNum - w - h;
    55       _arcLimit = _nodeNum - w;
    56     }
    57 
    58     Arc _down(Node n) const {
    59       if (n.id < _nodeNum - _width) {
    60         return Arc(n.id);
    61       } else {
    62         return INVALID;
    63       }
    64     }
    65 
    66     Arc _up(Node n) const {
    67       if (n.id >= _width) {
    68         return Arc(n.id - _width);
    69       } else {
    70         return INVALID;
    71       }
    72     }
    73 
    74     Arc _right(Node n) const {
    75       if (n.id % _width < _width - 1) {
    76         return _arcLimit + n.id % _width + (n.id / _width) * (_width - 1);
    77       } else {
    78         return INVALID;
    79       }
    80     }
    81 
    82     Arc _left(Node n) const {
    83       if (n.id % _width > 0) {
    84         return _arcLimit + n.id % _width + (n.id / _width) * (_width - 1) - 1;
    85       } else {
    86         return INVALID;
    87       }
     49    void construct(int width, int height) {
     50       _width = width; _height = height;
     51      _node_num = width * height;
     52      _edge_num = 2 * _node_num - width - height;
     53      _edge_limit = _node_num - _width;
    8854    }
    8955
     
    9157
    9258    Node operator()(int i, int j) const {
    93       LEMON_ASSERT(0 <= i && i < width() &&
    94                    0 <= j && j < height(), "lemon::GridGraph::IndexError");
     59      LEMON_DEBUG(0 <= i && i < _width &&
     60                  0 <= j  && j < _height, "Index out of range");
    9561      return Node(i + j * _width);
    9662    }
    9763
     64    int col(Node n) const {
     65      return n._id % _width;
     66    }
     67
    9868    int row(Node n) const {
    99       return n.id / _width;
    100     }
    101 
    102     int col(Node n) const {
    103       return n.id % _width;
     69      return n._id / _width;
     70    }
     71
     72    dim2::Point<int> pos(Node n) const {
     73      return dim2::Point<int>(col(n), row(n));
    10474    }
    10575
     
    11585    typedef True ArcNumTag;
    11686
    117     int nodeNum() const { return _nodeNum; }
    118     int arcNum() const { return _arcNum; }
    119 
    120     int maxNodeId() const { return nodeNum() - 1; }
    121     int maxArcId() const { return arcNum() - 1; }
    122 
    123     Node source(Arc e) const {
    124       if (e.id < _arcLimit) {
    125         return e.id;
    126       } else {
    127         return (e.id - _arcLimit) % (_width - 1) +
    128           (e.id - _arcLimit) / (_width - 1) * _width;
    129       }
    130     }
    131 
    132     Node target(Arc e) const {
    133       if (e.id < _arcLimit) {
    134         return e.id + _width;
    135       } else {
    136         return (e.id - _arcLimit) % (_width - 1) +
    137           (e.id - _arcLimit) / (_width - 1) * _width + 1;
    138       }
    139     }
    140 
    141     static int id(Node v) { return v.id; }
    142     static int id(Arc e) { return e.id; }
     87    int nodeNum() const { return _node_num; }
     88    int edgeNum() const { return _edge_num; }
     89    int arcNum() const { return 2 * _edge_num; }
     90
     91    Node u(Edge edge) const {
     92      if (edge._id < _edge_limit) {
     93        return edge._id;
     94      } else {
     95        return (edge._id - _edge_limit) % (_width - 1) +
     96          (edge._id - _edge_limit) / (_width - 1) * _width;
     97      }
     98    }
     99
     100    Node v(Edge edge) const {
     101      if (edge._id < _edge_limit) {
     102        return edge._id + _width;
     103      } else {
     104        return (edge._id - _edge_limit) % (_width - 1) +
     105          (edge._id - _edge_limit) / (_width - 1) * _width + 1;
     106      }
     107    }
     108
     109    Node source(Arc arc) const {
     110      return (arc._id & 1) == 1 ? u(arc) : v(arc);
     111    }
     112
     113    Node target(Arc arc) const {
     114      return (arc._id & 1) == 1 ? v(arc) : u(arc);
     115    }
     116
     117    static int id(Node node) { return node._id; }
     118    static int id(Edge edge) { return edge._id; }
     119    static int id(Arc arc) { return arc._id; }
     120
     121    int maxNodeId() const { return _node_num - 1; }
     122    int maxEdgeId() const { return _edge_num - 1; }
     123    int maxArcId() const { return 2 * _edge_num - 1; }
    143124
    144125    static Node nodeFromId(int id) { return Node(id);}
    145 
     126    static Edge edgeFromId(int id) { return Edge(id);}
    146127    static Arc arcFromId(int id) { return Arc(id);}
    147128
    148     typedef True FindArcTag;
     129    typedef True FindEdgeTag;
     130
     131    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
     132      if (prev != INVALID) return INVALID;
     133      if (v._id > u._id) {
     134        if (v._id - u._id == _width)
     135          return Edge(u._id);
     136        if (v._id - u._id == 1 && u._id % _width < _width - 1) {
     137          return Edge(u._id / _width * (_width - 1) +
     138                      u._id % _width + _edge_limit);
     139        }
     140      } else {
     141        if (u._id - v._id == _width)
     142          return Edge(v._id);
     143        if (u._id - v._id == 1 && v._id % _width < _width - 1) {
     144          return Edge(v._id / _width * (_width - 1) +
     145                      v._id % _width + _edge_limit);
     146        }
     147      }
     148      return INVALID;
     149    }
    149150
    150151    Arc findArc(Node u, Node v, Arc prev = INVALID) const {
    151152      if (prev != INVALID) return INVALID;
    152       if (v.id - u.id == _width) return Arc(u.id);
    153       if (v.id - u.id == 1 && u.id % _width < _width - 1) {
    154         return Arc(u.id / _width * (_width - 1) +
    155                    u.id % _width + _arcLimit);
     153      if (v._id > u._id) {
     154        if (v._id - u._id == _width)
     155          return Arc((u._id << 1) | 1);
     156        if (v._id - u._id == 1 && u._id % _width < _width - 1) {
     157          return Arc(((u._id / _width * (_width - 1) +
     158                       u._id % _width + _edge_limit) << 1) | 1);
     159        }
     160      } else {
     161        if (u._id - v._id == _width)
     162          return Arc(v._id << 1);
     163        if (u._id - v._id == 1 && v._id % _width < _width - 1) {
     164          return Arc((v._id / _width * (_width - 1) +
     165                       v._id % _width + _edge_limit) << 1);
     166        }
    156167      }
    157168      return INVALID;
     
    162173
    163174    protected:
    164       int id;
    165       Node(int _id) : id(_id) {}
     175      int _id;
     176      Node(int id) : _id(id) {}
    166177    public:
    167178      Node() {}
    168       Node (Invalid) { id = -1; }
    169       bool operator==(const Node node) const { return id == node.id; }
    170       bool operator!=(const Node node) const { return id != node.id; }
    171       bool operator<(const Node node) const { return id < node.id; }
     179      Node (Invalid) : _id(-1) {}
     180      bool operator==(const Node node) const {return _id == node._id;}
     181      bool operator!=(const Node node) const {return _id != node._id;}
     182      bool operator<(const Node node) const {return _id < node._id;}
     183    };
     184
     185    class Edge {
     186      friend class GridGraphBase;
     187
     188    protected:
     189      int _id;
     190
     191      Edge(int id) : _id(id) {}
     192
     193    public:
     194      Edge() {}
     195      Edge (Invalid) : _id(-1) {}
     196      bool operator==(const Edge edge) const {return _id == edge._id;}
     197      bool operator!=(const Edge edge) const {return _id != edge._id;}
     198      bool operator<(const Edge edge) const {return _id < edge._id;}
    172199    };
    173200
     
    176203
    177204    protected:
    178       int id;
    179       Arc(int _id) : id(_id) {}
     205      int _id;
     206
     207      Arc(int id) : _id(id) {}
     208
    180209    public:
    181210      Arc() {}
    182       Arc (Invalid) { id = -1; }
    183       bool operator==(const Arc arc) const { return id == arc.id; }
    184       bool operator!=(const Arc arc) const { return id != arc.id; }
    185       bool operator<(const Arc arc) const { return id < arc.id; }
     211      Arc (Invalid) : _id(-1) {}
     212      operator Edge() const { return _id != -1 ? Edge(_id >> 1) : INVALID; }
     213      bool operator==(const Arc arc) const {return _id == arc._id;}
     214      bool operator!=(const Arc arc) const {return _id != arc._id;}
     215      bool operator<(const Arc arc) const {return _id < arc._id;}
    186216    };
    187217
     218    static bool direction(Arc arc) {
     219      return (arc._id & 1) == 1;
     220    }
     221
     222    static Arc direct(Edge edge, bool dir) {
     223      return Arc((edge._id << 1) | (dir ? 1 : 0));
     224    }
     225
    188226    void first(Node& node) const {
    189       node.id = nodeNum() - 1;
     227      node._id = _node_num - 1;
    190228    }
    191229
    192230    static void next(Node& node) {
    193       --node.id;
     231      --node._id;
     232    }
     233
     234    void first(Edge& edge) const {
     235      edge._id = _edge_num - 1;
     236    }
     237
     238    static void next(Edge& edge) {
     239      --edge._id;
    194240    }
    195241
    196242    void first(Arc& arc) const {
    197       arc.id = arcNum() - 1;
     243      arc._id = 2 * _edge_num - 1;
    198244    }
    199245
    200246    static void next(Arc& arc) {
    201       --arc.id;
     247      --arc._id;
    202248    }
    203249
    204250    void firstOut(Arc& arc, const Node& node) const {
    205       if (node.id < _nodeNum - _width) {
    206         arc.id = node.id;
    207       } else if (node.id % _width < _width - 1) {
    208         arc.id = _arcLimit + node.id % _width +
    209           (node.id / _width) * (_width - 1);
    210       } else {
    211         arc.id = -1;
    212       }
     251      if (node._id % _width < _width - 1) {
     252        arc._id = (_edge_limit + node._id % _width +
     253                   (node._id / _width) * (_width - 1)) << 1 | 1;
     254        return;
     255      }
     256      if (node._id < _node_num - _width) {
     257        arc._id = node._id << 1 | 1;
     258        return;
     259      }
     260      if (node._id % _width > 0) {
     261        arc._id = (_edge_limit + node._id % _width +
     262                   (node._id / _width) * (_width - 1) - 1) << 1;
     263        return;
     264      }
     265      if (node._id >= _width) {
     266        arc._id = (node._id - _width) << 1;
     267        return;
     268      }
     269      arc._id = -1;
    213270    }
    214271
    215272    void nextOut(Arc& arc) const {
    216       if (arc.id >= _arcLimit) {
    217         arc.id = -1;
    218       } else if (arc.id % _width < _width - 1) {
    219         arc.id = _arcLimit + arc.id % _width +
    220           (arc.id / _width) * (_width - 1);
    221       } else {
    222         arc.id = -1;
    223       }
     273      int nid = arc._id >> 1;
     274      if ((arc._id & 1) == 1) {
     275        if (nid >= _edge_limit) {
     276          nid = (nid - _edge_limit) % (_width - 1) +
     277            (nid - _edge_limit) / (_width - 1) * _width;
     278          if (nid < _node_num - _width) {
     279            arc._id = nid << 1 | 1;
     280            return;
     281          }
     282        }
     283        if (nid % _width > 0) {
     284          arc._id = (_edge_limit + nid % _width +
     285                     (nid / _width) * (_width - 1) - 1) << 1;
     286          return;
     287        }
     288        if (nid >= _width) {
     289          arc._id = (nid - _width) << 1;
     290          return;
     291        }
     292      } else {
     293        if (nid >= _edge_limit) {
     294          nid = (nid - _edge_limit) % (_width - 1) +
     295            (nid - _edge_limit) / (_width - 1) * _width + 1;
     296          if (nid >= _width) {
     297            arc._id = (nid - _width) << 1;
     298            return;
     299          }
     300        }
     301      }
     302      arc._id = -1;
    224303    }
    225304
    226305    void firstIn(Arc& arc, const Node& node) const {
    227       if (node.id >= _width) {
    228         arc.id = node.id - _width;
    229       } else if (node.id % _width > 0) {
    230         arc.id = _arcLimit + node.id % _width +
    231           (node.id / _width) * (_width - 1) - 1;
    232       } else {
    233         arc.id = -1;
    234       }
     306      if (node._id % _width < _width - 1) {
     307        arc._id = (_edge_limit + node._id % _width +
     308                   (node._id / _width) * (_width - 1)) << 1;
     309        return;
     310      }
     311      if (node._id < _node_num - _width) {
     312        arc._id = node._id << 1;
     313        return;
     314      }
     315      if (node._id % _width > 0) {
     316        arc._id = (_edge_limit + node._id % _width +
     317                   (node._id / _width) * (_width - 1) - 1) << 1 | 1;
     318        return;
     319      }
     320      if (node._id >= _width) {
     321        arc._id = (node._id - _width) << 1 | 1;
     322        return;
     323      }
     324      arc._id = -1;
    235325    }
    236326
    237327    void nextIn(Arc& arc) const {
    238       if (arc.id >= _arcLimit) {
    239         arc.id = -1;
    240       } else if (arc.id % _width > 0) {
    241         arc.id = _arcLimit + arc.id % _width +
    242           (arc.id / _width + 1) * (_width - 1) - 1;
    243       } else {
    244         arc.id = -1;
     328      int nid = arc._id >> 1;
     329      if ((arc._id & 1) == 0) {
     330        if (nid >= _edge_limit) {
     331          nid = (nid - _edge_limit) % (_width - 1) +
     332            (nid - _edge_limit) / (_width - 1) * _width;
     333          if (nid < _node_num - _width) {
     334            arc._id = nid << 1;
     335            return;
     336          }
     337        }
     338        if (nid % _width > 0) {
     339          arc._id = (_edge_limit + nid % _width +
     340                     (nid / _width) * (_width - 1) - 1) << 1 | 1;
     341          return;
     342        }
     343        if (nid >= _width) {
     344          arc._id = (nid - _width) << 1 | 1;
     345          return;
     346        }
     347      } else {
     348        if (nid >= _edge_limit) {
     349          nid = (nid - _edge_limit) % (_width - 1) +
     350            (nid - _edge_limit) / (_width - 1) * _width + 1;
     351          if (nid >= _width) {
     352            arc._id = (nid - _width) << 1 | 1;
     353            return;
     354          }
     355        }
     356      }
     357      arc._id = -1;
     358    }
     359
     360    void firstInc(Edge& edge, bool& dir, const Node& node) const {
     361      if (node._id % _width < _width - 1) {
     362        edge._id = _edge_limit + node._id % _width +
     363          (node._id / _width) * (_width - 1);
     364        dir = true;
     365        return;
     366      }
     367      if (node._id < _node_num - _width) {
     368        edge._id = node._id;
     369        dir = true;
     370        return;
     371      }
     372      if (node._id % _width > 0) {
     373        edge._id = _edge_limit + node._id % _width +
     374          (node._id / _width) * (_width - 1) - 1;
     375        dir = false;
     376        return;
     377      }
     378      if (node._id >= _width) {
     379        edge._id = node._id - _width;
     380        dir = false;
     381        return;
     382      }
     383      edge._id = -1;
     384      dir = true;
     385    }
     386
     387    void nextInc(Edge& edge, bool& dir) const {
     388      int nid = edge._id;
     389      if (dir) {
     390        if (nid >= _edge_limit) {
     391          nid = (nid - _edge_limit) % (_width - 1) +
     392            (nid - _edge_limit) / (_width - 1) * _width;
     393          if (nid < _node_num - _width) {
     394            edge._id = nid;
     395            return;
     396          }
     397        }
     398        if (nid % _width > 0) {
     399          edge._id = _edge_limit + nid % _width +
     400            (nid / _width) * (_width - 1) - 1;
     401          dir = false;
     402          return;
     403        }
     404        if (nid >= _width) {
     405          edge._id = nid - _width;
     406          dir = false;
     407          return;
     408        }
     409      } else {
     410        if (nid >= _edge_limit) {
     411          nid = (nid - _edge_limit) % (_width - 1) +
     412            (nid - _edge_limit) / (_width - 1) * _width + 1;
     413          if (nid >= _width) {
     414            edge._id = nid - _width;
     415            return;
     416          }
     417        }
     418      }
     419      edge._id = -1;
     420      dir = true;
     421    }
     422
     423    Arc right(Node n) const {
     424      if (n._id % _width < _width - 1) {
     425        return Arc(((_edge_limit + n._id % _width +
     426                    (n._id / _width) * (_width - 1)) << 1) | 1);
     427      } else {
     428        return INVALID;
     429      }
     430    }
     431
     432    Arc left(Node n) const {
     433      if (n._id % _width > 0) {
     434        return Arc((_edge_limit + n._id % _width +
     435                     (n._id / _width) * (_width - 1) - 1) << 1);
     436      } else {
     437        return INVALID;
     438      }
     439    }
     440
     441    Arc up(Node n) const {
     442      if (n._id < _edge_limit) {
     443        return Arc((n._id << 1) | 1);
     444      } else {
     445        return INVALID;
     446      }
     447    }
     448
     449    Arc down(Node n) const {
     450      if (n._id >= _width) {
     451        return Arc((n._id - _width) << 1);
     452      } else {
     453        return INVALID;
    245454      }
    246455    }
     
    248457  private:
    249458    int _width, _height;
    250     int _nodeNum, _arcNum;
    251     int _arcLimit;
     459    int _node_num, _edge_num;
     460    int _edge_limit;
    252461  };
    253462
    254   typedef GraphExtender<UndirDigraphExtender<GridGraphBase> >
    255     ExtendedGridGraphBase;
     463
     464  typedef GraphExtender<GridGraphBase> ExtendedGridGraphBase;
    256465
    257466  /// \ingroup graphs
     
    260469  ///
    261470  /// This class implements a special graph type. The nodes of the
    262   /// graph can be indiced by two integer \c (i,j) value where \c i
    263   /// is in the \c [0,width) range and j is in the [0, height) range.
    264   /// Two nodes are connected in the graph if the indices differ only
    265   /// on one position and only one is the difference.
     471  /// graph can be indexed by two integer \c (i,j) value where \c i is
     472  /// in the \c [0..width()-1] range and j is in the \c
     473  /// [0..height()-1] range.  Two nodes are connected in the graph if
     474  /// the indexes differ exactly on one position and exactly one is
     475  /// the difference. The nodes of the graph be indexed by position
     476  /// with \c operator()() function. The positions of the nodes can be
     477  /// get with \c pos(), \c col() and \c row() members. The outgoing
     478  /// arcs can be retrieved with the \c right(), \c up(), \c left()
     479  /// and \c down() functions, where the bottom-left corner is the
     480  /// origin.
    266481  ///
    267482  /// \image html grid_graph.png
    268   /// \image latex grid_graph.eps "Grid graph" width=\textwidth
     483  /// \image latex grid_graph.eps "Grid digraph" row_num=\textrow_num
    269484  ///
    270   /// The graph can be indiced in the following way:
     485  /// A short example about the basic usage:
    271486  ///\code
    272   /// GridGraph gr(w, h);
    273   /// GridGraph::NodeMap<int> val(gr);
    274   /// for (int i = 0; i < gr.width(); ++i) {
    275   ///   for (int j = 0; j < gr.height(); ++j) {
    276   ///     val[gr(i, j)] = i + j;
     487  /// GridGraph graph(rows, cols);
     488  /// GridGraph::NodeMap<int> val(graph);
     489  /// for (int i = 0; i < graph.width(); ++i) {
     490  ///   for (int j = 0; j < graph.height(); ++j) {
     491  ///     val[graph(i, j)] = i + j;
    277492  ///   }
    278493  /// }
    279494  ///\endcode
    280495  ///
    281   /// This graph type is fully conform to the \ref concepts::Graph
    282   /// "Undirected Graph" concept, and it also has an important extra
    283   /// feature that its maps are real \ref concepts::ReferenceMap
    284   /// "reference map"s.
     496  /// The graph type is fully conform to the \ref concepts::Graph
     497  /// "Graph" concept, and it also has an important extra feature
     498  /// that its maps are real \ref concepts::ReferenceMap "reference
     499  /// map"s.
    285500  class GridGraph : public ExtendedGridGraphBase {
    286501  public:
     
    293508    class IndexMap {
    294509    public:
    295       /// The key type of the map
     510      /// \brief The key type of the map
    296511      typedef GridGraph::Node Key;
    297       /// The value type of the map
     512      /// \brief The value type of the map
    298513      typedef dim2::Point<int> Value;
    299514
     515      /// \brief Constructor
     516      ///
    300517      /// Constructor
    301518      IndexMap(const GridGraph& graph) : _graph(graph) {}
    302519
    303       /// The subscript operator
    304       Value operator[](const Key& key) const {
    305         return dim2::Point<int>(_graph.row(key), _graph.col(key));
     520      /// \brief The subscript operator
     521      ///
     522      /// The subscript operator.
     523      Value operator[](Key key) const {
     524        return _graph.pos(key);
    306525      }
    307526
     
    310529    };
    311530
     531    /// \brief Map to get the column of the nodes.
     532    ///
     533    /// Map to get the column of the nodes.
     534    class ColMap {
     535    public:
     536      /// \brief The key type of the map
     537      typedef GridGraph::Node Key;
     538      /// \brief The value type of the map
     539      typedef int Value;
     540
     541      /// \brief Constructor
     542      ///
     543      /// Constructor
     544      ColMap(const GridGraph& graph) : _graph(graph) {}
     545
     546      /// \brief The subscript operator
     547      ///
     548      /// The subscript operator.
     549      Value operator[](Key key) const {
     550        return _graph.col(key);
     551      }
     552
     553    private:
     554      const GridGraph& _graph;
     555    };
     556
    312557    /// \brief Map to get the row of the nodes.
    313558    ///
     
    315560    class RowMap {
    316561    public:
    317       /// The key type of the map
     562      /// \brief The key type of the map
    318563      typedef GridGraph::Node Key;
    319       /// The value type of the map
     564      /// \brief The value type of the map
    320565      typedef int Value;
    321566
     567      /// \brief Constructor
     568      ///
    322569      /// Constructor
    323570      RowMap(const GridGraph& graph) : _graph(graph) {}
    324571
    325       /// The subscript operator
    326       Value operator[](const Key& key) const {
     572      /// \brief The subscript operator
     573      ///
     574      /// The subscript operator.
     575      Value operator[](Key key) const {
    327576        return _graph.row(key);
    328577      }
     
    332581    };
    333582
    334     /// \brief Map to get the column of the nodes.
    335     ///
    336     /// Map to get the column of the nodes.
    337     class ColMap {
    338     public:
    339       /// The key type of the map
    340       typedef GridGraph::Node Key;
    341       /// The value type of the map
    342       typedef int Value;
    343 
    344       /// Constructor
    345       ColMap(const GridGraph& graph) : _graph(graph) {}
    346 
    347       /// The subscript operator
    348       Value operator[](const Key& key) const {
    349         return _graph.col(key);
    350       }
    351 
    352     private:
    353       const GridGraph& _graph;
    354     };
    355 
    356583    /// \brief Constructor
    357584    ///
    358     /// Constructor.
    359     /// \param width The width of the grid.
    360     /// \param height The height of the grid.
     585    /// Construct a grid graph with given size.
    361586    GridGraph(int width, int height) { construct(width, height); }
    362587
    363588    /// \brief Resize the graph
    364589    ///
    365     /// Resize the grid.
     590    /// Resize the graph. The function will fully destroy and rebuild
     591    /// the graph.  This cause that the maps of the graph will
     592    /// reallocated automatically and the previous values will be
     593    /// lost.
    366594    void resize(int width, int height) {
    367595      Parent::notifier(Arc()).clear();
     
    381609    }
    382610
     611    /// \brief Gives back the column index of the node.
     612    ///
     613    /// Gives back the column index of the node.
     614    int col(Node n) const {
     615      return Parent::col(n);
     616    }
     617
    383618    /// \brief Gives back the row index of the node.
    384619    ///
     
    388623    }
    389624
    390     /// \brief Gives back the column index of the node.
    391     ///
    392     /// Gives back the column index of the node.
    393     int col(Node n) const {
    394       return Parent::col(n);
    395     }
    396 
    397     /// \brief Gives back the width of the grid.
    398     ///
    399     /// Gives back the width of the grid.
     625    /// \brief Gives back the position of the node.
     626    ///
     627    /// Gives back the position of the node, ie. the <tt>(col,row)</tt> pair.
     628    dim2::Point<int> pos(Node n) const {
     629      return Parent::pos(n);
     630    }
     631
     632    /// \brief Gives back the number of the columns.
     633    ///
     634    /// Gives back the number of the columns.
    400635    int width() const {
    401636      return Parent::width();
    402637    }
    403638
    404     /// \brief Gives back the height of the grid.
    405     ///
    406     /// Gives back the height of the grid.
     639    /// \brief Gives back the number of the rows.
     640    ///
     641    /// Gives back the number of the rows.
    407642    int height() const {
    408643      return Parent::height();
    409644    }
    410645
     646    /// \brief Gives back the arc goes right from the node.
     647    ///
     648    /// Gives back the arc goes right from the node. If there is not
     649    /// outgoing arc then it gives back INVALID.
     650    Arc right(Node n) const {
     651      return Parent::right(n);
     652    }
     653
     654    /// \brief Gives back the arc goes left from the node.
     655    ///
     656    /// Gives back the arc goes left from the node. If there is not
     657    /// outgoing arc then it gives back INVALID.
     658    Arc left(Node n) const {
     659      return Parent::left(n);
     660    }
     661
     662    /// \brief Gives back the arc goes up from the node.
     663    ///
     664    /// Gives back the arc goes up from the node. If there is not
     665    /// outgoing arc then it gives back INVALID.
     666    Arc up(Node n) const {
     667      return Parent::up(n);
     668    }
     669
    411670    /// \brief Gives back the arc goes down from the node.
    412671    ///
    413672    /// Gives back the arc goes down from the node. If there is not
    414     /// outgoing arc then it gives back \c INVALID.
     673    /// outgoing arc then it gives back INVALID.
    415674    Arc down(Node n) const {
    416       Edge e = _down(n);
    417       return e != INVALID ? direct(e, true) : INVALID;
    418     }
    419 
    420     /// \brief Gives back the arc goes up from the node.
    421     ///
    422     /// Gives back the arc goes up from the node. If there is not
    423     /// outgoing arc then it gives back \c INVALID.
    424     Arc up(Node n) const {
    425       Edge e = _up(n);
    426       return e != INVALID ? direct(e, false) : INVALID;
    427     }
    428 
    429     /// \brief Gives back the arc goes right from the node.
    430     ///
    431     /// Gives back the arc goes right from the node. If there is not
    432     /// outgoing arc then it gives back \c INVALID.
    433     Arc right(Node n) const {
    434       Edge e = _right(n);
    435       return e != INVALID ? direct(e, true) : INVALID;
    436     }
    437 
    438     /// \brief Gives back the arc goes left from the node.
    439     ///
    440     /// Gives back the arc goes left from the node. If there is not
    441     /// outgoing arc then it gives back \c INVALID.
    442     Arc left(Node n) const {
    443       Edge e = _left(n);
    444       return e != INVALID ? direct(e, false) : INVALID;
    445     }
    446 
    447   }; // class GridGraph
    448 
    449   /// \brief Index map of the grid graph
    450   ///
    451   /// Just returns an IndexMap for the grid graph.
    452   inline GridGraph::IndexMap indexMap(const GridGraph& graph) {
    453     return GridGraph::IndexMap(graph);
    454   }
    455 
    456   /// \brief Row map of the grid graph
    457   ///
    458   /// Just returns a RowMap for the grid graph.
    459   inline GridGraph::RowMap rowMap(const GridGraph& graph) {
    460     return GridGraph::RowMap(graph);
    461   }
    462 
    463   /// \brief Column map of the grid graph
    464   ///
    465   /// Just returns a ColMap for the grid graph.
    466   inline GridGraph::ColMap colMap(const GridGraph& graph) {
    467     return GridGraph::ColMap(graph);
    468   }
     675      return Parent::down(n);
     676    }
     677
     678    /// \brief Index map of the grid graph
     679    ///
     680    /// Just returns an IndexMap for the grid graph.
     681    IndexMap indexMap() const {
     682      return IndexMap(*this);
     683    }
     684
     685    /// \brief Row map of the grid graph
     686    ///
     687    /// Just returns a RowMap for the grid graph.
     688    RowMap rowMap() const {
     689      return RowMap(*this);
     690    }
     691
     692    /// \brief Column map of the grid graph
     693    ///
     694    /// Just returns a ColMap for the grid graph.
     695    ColMap colMap() const {
     696      return ColMap(*this);
     697    }
     698
     699  };
     700
    469701}
    470 
    471 #endif // GRID_GRAPH_H
     702#endif
  • test/graph_test.cc

    r334 r335  
    127127//  { // Checking FullGraph
    128128//    checkConcept<Graph, FullGraph>();
     129//    checkGraphIterators<FullGraph>();
    129130//  }
    130131  { // Checking GridGraph
     
    187188}
    188189
    189 void checkGridGraph(const GridGraph& g, int w, int h) {
    190   check(g.width() == w, "Wrong width");
    191   check(g.height() == h, "Wrong height");
    192 
    193   for (int i = 0; i < w; ++i) {
    194     for (int j = 0; j < h; ++j) {
    195       check(g.col(g(i, j)) == i, "Wrong col");
    196       check(g.row(g(i, j)) == j, "Wrong row");
    197     }
    198   }
    199 
    200   for (int i = 0; i < w; ++i) {
    201     for (int j = 0; j < h - 1; ++j) {
    202       check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down");
    203       check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down");
    204     }
    205     check(g.down(g(i, h - 1)) == INVALID, "Wrong down");
    206   }
    207 
    208   for (int i = 0; i < w; ++i) {
    209     for (int j = 1; j < h; ++j) {
    210       check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up");
    211       check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up");
    212     }
    213     check(g.up(g(i, 0)) == INVALID, "Wrong up");
    214   }
    215 
    216   for (int j = 0; j < h; ++j) {
    217     for (int i = 0; i < w - 1; ++i) {
    218       check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right");
    219       check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right");
    220     }
    221     check(g.right(g(w - 1, j)) == INVALID, "Wrong right");
    222   }
    223 
    224   for (int j = 0; j < h; ++j) {
    225     for (int i = 1; i < w; ++i) {
    226       check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left");
    227       check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left");
    228     }
    229     check(g.left(g(0, j)) == INVALID, "Wrong left");
    230   }
    231 
    232   checkGraphNodeList(g, w*h);
    233   checkGraphArcList(g, 2*(2*w*h-w-h));
    234   checkGraphEdgeList(g, 2*w*h-w-h);
    235 
    236   checkGraphOutArcList(g, g(0,0), 2);
    237   checkGraphOutArcList(g, g(0,1), 3);
    238   checkGraphOutArcList(g, g(w-2,h-2), 4);
    239 
    240   checkGraphInArcList(g, g(0,0), 2);
    241   checkGraphInArcList(g, g(0,1), 3);
    242   checkGraphInArcList(g, g(w-2,h-2), 4);
    243 
    244   checkGraphIncEdgeList(g, g(0,0), 2);
    245   checkGraphIncEdgeList(g, g(0,1), 3);
    246   checkGraphIncEdgeList(g, g(w-2,h-2), 4);
    247 
    248   checkGraphConArcList(g, 2*(2*w*h-w-h));
    249   checkGraphConEdgeList(g, 2*w*h-w-h);
    250 
    251   checkArcDirections(g);
    252 
    253   checkNodeIds(g);
    254   checkArcIds(g);
    255   checkEdgeIds(g);
    256   checkGraphNodeMap(g);
    257   checkGraphArcMap(g);
    258   checkGraphEdgeMap(g);
     190void checkGridGraph(int width, int height) {
     191  typedef GridGraph Graph;
     192  GRAPH_TYPEDEFS(Graph);
     193  Graph G(width, height);
     194
     195  check(G.width() == width, "Wrong row number");
     196  check(G.height() == height, "Wrong column number");
     197
     198  for (int i = 0; i < width; ++i) {
     199    for (int j = 0; j < height; ++j) {
     200      check(G.col(G(i, j)) == i, "Wrong column");
     201      check(G.row(G(i, j)) == j, "Wrong row");
     202      check(G.pos(G(i, j)).x == i, "Wrong column");
     203      check(G.pos(G(i, j)).y == j, "Wrong row");
     204    }
     205  }
     206
     207  for (int j = 0; j < height; ++j) {
     208    for (int i = 0; i < width - 1; ++i) {
     209      check(G.source(G.right(G(i, j))) == G(i, j), "Wrong right");
     210      check(G.target(G.right(G(i, j))) == G(i + 1, j), "Wrong right");
     211    }
     212    check(G.right(G(width - 1, j)) == INVALID, "Wrong right");
     213  }
     214
     215  for (int j = 0; j < height; ++j) {
     216    for (int i = 1; i < width; ++i) {
     217      check(G.source(G.left(G(i, j))) == G(i, j), "Wrong left");
     218      check(G.target(G.left(G(i, j))) == G(i - 1, j), "Wrong left");
     219    }
     220    check(G.left(G(0, j)) == INVALID, "Wrong left");
     221  }
     222
     223  for (int i = 0; i < width; ++i) {
     224    for (int j = 0; j < height - 1; ++j) {
     225      check(G.source(G.up(G(i, j))) == G(i, j), "Wrong up");
     226      check(G.target(G.up(G(i, j))) == G(i, j + 1), "Wrong up");
     227    }
     228    check(G.up(G(i, height - 1)) == INVALID, "Wrong up");
     229  }
     230
     231  for (int i = 0; i < width; ++i) {
     232    for (int j = 1; j < height; ++j) {
     233      check(G.source(G.down(G(i, j))) == G(i, j), "Wrong down");
     234      check(G.target(G.down(G(i, j))) == G(i, j - 1), "Wrong down");
     235    }
     236    check(G.down(G(i, 0)) == INVALID, "Wrong down");
     237  }
     238
     239  checkGraphNodeList(G, width * height);
     240  checkGraphEdgeList(G, width * (height - 1) + (width - 1) * height);
     241  checkGraphArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
     242
     243  for (NodeIt n(G); n != INVALID; ++n) {
     244    int nb = 4;
     245    if (G.col(n) == 0) --nb;
     246    if (G.col(n) == width - 1) --nb;
     247    if (G.row(n) == 0) --nb;
     248    if (G.row(n) == height - 1) --nb;
     249
     250    checkGraphOutArcList(G, n, nb);
     251    checkGraphInArcList(G, n, nb);
     252    checkGraphIncEdgeList(G, n, nb);
     253  }
     254
     255  checkArcDirections(G);
     256
     257  checkGraphConArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
     258  checkGraphConEdgeList(G, width * (height - 1) + (width - 1) * height);
     259
     260  checkNodeIds(G);
     261  checkArcIds(G);
     262  checkEdgeIds(G);
     263  checkGraphNodeMap(G);
     264  checkGraphArcMap(G);
     265  checkGraphEdgeMap(G);
     266
    259267}
    260268
     
    274282//   }
    275283  { // Checking GridGraph
    276     GridGraph g(5, 6);
    277     checkGridGraph(g, 5, 6);
     284    checkGridGraph(5, 8);
     285    checkGridGraph(8, 5);
     286    checkGridGraph(5, 5);
     287    checkGridGraph(0, 0);
     288    checkGridGraph(1, 1);
    278289  }
    279290}
Note: See TracChangeset for help on using the changeset viewer.