lemon/grid_graph.h
changeset 334 ada5f74d1c9e
child 335 160bf92c7cdc
equal deleted inserted replaced
-1:000000000000 0:52c0d1db35dd
       
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
       
     2  *
       
     3  * This file is a part of LEMON, a generic C++ optimization library.
       
     4  *
       
     5  * Copyright (C) 2003-2008
       
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
       
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
       
     8  *
       
     9  * Permission to use, modify and distribute this software is granted
       
    10  * provided that this copyright notice appears in all copies. For
       
    11  * precise terms see the accompanying LICENSE file.
       
    12  *
       
    13  * This software is provided "AS IS" with no warranty of any kind,
       
    14  * express or implied, and with no claim as to its suitability for any
       
    15  * purpose.
       
    16  *
       
    17  */
       
    18 
       
    19 #ifndef GRID_GRAPH_H
       
    20 #define GRID_GRAPH_H
       
    21 
       
    22 #include <iostream>
       
    23 #include <lemon/core.h>
       
    24 #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>
       
    30 
       
    31 ///\ingroup graphs
       
    32 ///\file
       
    33 ///\brief GridGraph class.
       
    34 
       
    35 namespace lemon {
       
    36 
       
    37   class GridGraphBase {
       
    38 
       
    39   public:
       
    40 
       
    41     typedef GridGraphBase Graph;
       
    42 
       
    43     class Node;
       
    44     class Arc;
       
    45 
       
    46   public:
       
    47 
       
    48     GridGraphBase() {}
       
    49 
       
    50   protected:
       
    51 
       
    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       }
       
    88     }
       
    89 
       
    90   public:
       
    91 
       
    92     Node operator()(int i, int j) const {
       
    93       LEMON_ASSERT(0 <= i && i < width() &&
       
    94                    0 <= j && j < height(), "lemon::GridGraph::IndexError");
       
    95       return Node(i + j * _width);
       
    96     }
       
    97 
       
    98     int row(Node n) const {
       
    99       return n.id / _width;
       
   100     }
       
   101 
       
   102     int col(Node n) const {
       
   103       return n.id % _width;
       
   104     }
       
   105 
       
   106     int width() const {
       
   107       return _width;
       
   108     }
       
   109 
       
   110     int height() const {
       
   111       return _height;
       
   112     }
       
   113 
       
   114     typedef True NodeNumTag;
       
   115     typedef True ArcNumTag;
       
   116 
       
   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; }
       
   143 
       
   144     static Node nodeFromId(int id) { return Node(id);}
       
   145 
       
   146     static Arc arcFromId(int id) { return Arc(id);}
       
   147 
       
   148     typedef True FindArcTag;
       
   149 
       
   150     Arc findArc(Node u, Node v, Arc prev = INVALID) const {
       
   151       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);
       
   156       }
       
   157       return INVALID;
       
   158     }
       
   159 
       
   160     class Node {
       
   161       friend class GridGraphBase;
       
   162 
       
   163     protected:
       
   164       int id;
       
   165       Node(int _id) : id(_id) {}
       
   166     public:
       
   167       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; }
       
   172     };
       
   173 
       
   174     class Arc {
       
   175       friend class GridGraphBase;
       
   176 
       
   177     protected:
       
   178       int id;
       
   179       Arc(int _id) : id(_id) {}
       
   180     public:
       
   181       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; }
       
   186     };
       
   187 
       
   188     void first(Node& node) const {
       
   189       node.id = nodeNum() - 1;
       
   190     }
       
   191 
       
   192     static void next(Node& node) {
       
   193       --node.id;
       
   194     }
       
   195 
       
   196     void first(Arc& arc) const {
       
   197       arc.id = arcNum() - 1;
       
   198     }
       
   199 
       
   200     static void next(Arc& arc) {
       
   201       --arc.id;
       
   202     }
       
   203 
       
   204     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       }
       
   213     }
       
   214 
       
   215     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       }
       
   224     }
       
   225 
       
   226     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       }
       
   235     }
       
   236 
       
   237     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;
       
   245       }
       
   246     }
       
   247 
       
   248   private:
       
   249     int _width, _height;
       
   250     int _nodeNum, _arcNum;
       
   251     int _arcLimit;
       
   252   };
       
   253 
       
   254   typedef GraphExtender<UndirDigraphExtender<GridGraphBase> >
       
   255     ExtendedGridGraphBase;
       
   256 
       
   257   /// \ingroup graphs
       
   258   ///
       
   259   /// \brief Grid graph class
       
   260   ///
       
   261   /// 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.
       
   266   ///
       
   267   /// \image html grid_graph.png
       
   268   /// \image latex grid_graph.eps "Grid graph" width=\textwidth
       
   269   ///
       
   270   /// The graph can be indiced in the following way:
       
   271   ///\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;
       
   277   ///   }
       
   278   /// }
       
   279   ///\endcode
       
   280   ///
       
   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.
       
   285   class GridGraph : public ExtendedGridGraphBase {
       
   286   public:
       
   287 
       
   288     typedef ExtendedGridGraphBase Parent;
       
   289 
       
   290     /// \brief Map to get the indices of the nodes as dim2::Point<int>.
       
   291     ///
       
   292     /// Map to get the indices of the nodes as dim2::Point<int>.
       
   293     class IndexMap {
       
   294     public:
       
   295       /// The key type of the map
       
   296       typedef GridGraph::Node Key;
       
   297       /// The value type of the map
       
   298       typedef dim2::Point<int> Value;
       
   299 
       
   300       /// Constructor
       
   301       IndexMap(const GridGraph& graph) : _graph(graph) {}
       
   302 
       
   303       /// The subscript operator
       
   304       Value operator[](const Key& key) const {
       
   305         return dim2::Point<int>(_graph.row(key), _graph.col(key));
       
   306       }
       
   307 
       
   308     private:
       
   309       const GridGraph& _graph;
       
   310     };
       
   311 
       
   312     /// \brief Map to get the row of the nodes.
       
   313     ///
       
   314     /// Map to get the row of the nodes.
       
   315     class RowMap {
       
   316     public:
       
   317       /// The key type of the map
       
   318       typedef GridGraph::Node Key;
       
   319       /// The value type of the map
       
   320       typedef int Value;
       
   321 
       
   322       /// Constructor
       
   323       RowMap(const GridGraph& graph) : _graph(graph) {}
       
   324 
       
   325       /// The subscript operator
       
   326       Value operator[](const Key& key) const {
       
   327         return _graph.row(key);
       
   328       }
       
   329 
       
   330     private:
       
   331       const GridGraph& _graph;
       
   332     };
       
   333 
       
   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 
       
   356     /// \brief Constructor
       
   357     ///
       
   358     /// Constructor.
       
   359     /// \param width The width of the grid.
       
   360     /// \param height The height of the grid.
       
   361     GridGraph(int width, int height) { construct(width, height); }
       
   362 
       
   363     /// \brief Resize the graph
       
   364     ///
       
   365     /// Resize the grid.
       
   366     void resize(int width, int height) {
       
   367       Parent::notifier(Arc()).clear();
       
   368       Parent::notifier(Edge()).clear();
       
   369       Parent::notifier(Node()).clear();
       
   370       construct(width, height);
       
   371       Parent::notifier(Node()).build();
       
   372       Parent::notifier(Edge()).build();
       
   373       Parent::notifier(Arc()).build();
       
   374     }
       
   375 
       
   376     /// \brief The node on the given position.
       
   377     ///
       
   378     /// Gives back the node on the given position.
       
   379     Node operator()(int i, int j) const {
       
   380       return Parent::operator()(i, j);
       
   381     }
       
   382 
       
   383     /// \brief Gives back the row index of the node.
       
   384     ///
       
   385     /// Gives back the row index of the node.
       
   386     int row(Node n) const {
       
   387       return Parent::row(n);
       
   388     }
       
   389 
       
   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.
       
   400     int width() const {
       
   401       return Parent::width();
       
   402     }
       
   403 
       
   404     /// \brief Gives back the height of the grid.
       
   405     ///
       
   406     /// Gives back the height of the grid.
       
   407     int height() const {
       
   408       return Parent::height();
       
   409     }
       
   410 
       
   411     /// \brief Gives back the arc goes down from the node.
       
   412     ///
       
   413     /// Gives back the arc goes down from the node. If there is not
       
   414     /// outgoing arc then it gives back \c INVALID.
       
   415     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   }
       
   469 }
       
   470 
       
   471 #endif // GRID_GRAPH_H