lemon/grid_graph.h
author Alpar Juttner <alpar@cs.elte.hu>
Mon, 01 Dec 2008 14:18:40 +0000
changeset 404 59d3aa4f921f
parent 338 b77fb8c32707
child 440 88ed40ad0d4f
permissions -rw-r--r--
Merge
     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 <lemon/core.h>
    23 #include <lemon/bits/graph_extender.h>
    24 #include <lemon/dim2.h>
    25 #include <lemon/assert.h>
    26 
    27 ///\ingroup graphs
    28 ///\file
    29 ///\brief GridGraph class.
    30 
    31 namespace lemon {
    32 
    33   class GridGraphBase {
    34 
    35   public:
    36 
    37     typedef GridGraphBase Graph;
    38 
    39     class Node;
    40     class Edge;
    41     class Arc;
    42 
    43   public:
    44 
    45     GridGraphBase() {}
    46 
    47   protected:
    48 
    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;
    54     }
    55 
    56   public:
    57 
    58     Node operator()(int i, int j) const {
    59       LEMON_DEBUG(0 <= i && i < _width &&
    60                   0 <= j  && j < _height, "Index out of range");
    61       return Node(i + j * _width);
    62     }
    63 
    64     int col(Node n) const {
    65       return n._id % _width;
    66     }
    67 
    68     int row(Node n) const {
    69       return n._id / _width;
    70     }
    71 
    72     dim2::Point<int> pos(Node n) const {
    73       return dim2::Point<int>(col(n), row(n));
    74     }
    75 
    76     int width() const {
    77       return _width;
    78     }
    79 
    80     int height() const {
    81       return _height;
    82     }
    83 
    84     typedef True NodeNumTag;
    85     typedef True EdgeNumTag;
    86     typedef True ArcNumTag;
    87 
    88     int nodeNum() const { return _node_num; }
    89     int edgeNum() const { return _edge_num; }
    90     int arcNum() const { return 2 * _edge_num; }
    91 
    92     Node u(Edge edge) const {
    93       if (edge._id < _edge_limit) {
    94         return edge._id;
    95       } else {
    96         return (edge._id - _edge_limit) % (_width - 1) +
    97           (edge._id - _edge_limit) / (_width - 1) * _width;
    98       }
    99     }
   100 
   101     Node v(Edge edge) const {
   102       if (edge._id < _edge_limit) {
   103         return edge._id + _width;
   104       } else {
   105         return (edge._id - _edge_limit) % (_width - 1) +
   106           (edge._id - _edge_limit) / (_width - 1) * _width + 1;
   107       }
   108     }
   109 
   110     Node source(Arc arc) const {
   111       return (arc._id & 1) == 1 ? u(arc) : v(arc);
   112     }
   113 
   114     Node target(Arc arc) const {
   115       return (arc._id & 1) == 1 ? v(arc) : u(arc);
   116     }
   117 
   118     static int id(Node node) { return node._id; }
   119     static int id(Edge edge) { return edge._id; }
   120     static int id(Arc arc) { return arc._id; }
   121 
   122     int maxNodeId() const { return _node_num - 1; }
   123     int maxEdgeId() const { return _edge_num - 1; }
   124     int maxArcId() const { return 2 * _edge_num - 1; }
   125 
   126     static Node nodeFromId(int id) { return Node(id);}
   127     static Edge edgeFromId(int id) { return Edge(id);}
   128     static Arc arcFromId(int id) { return Arc(id);}
   129 
   130     typedef True FindEdgeTag;
   131     typedef True FindArcTag;
   132 
   133     Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
   134       if (prev != INVALID) return INVALID;
   135       if (v._id > u._id) {
   136         if (v._id - u._id == _width)
   137           return Edge(u._id);
   138         if (v._id - u._id == 1 && u._id % _width < _width - 1) {
   139           return Edge(u._id / _width * (_width - 1) +
   140                       u._id % _width + _edge_limit);
   141         }
   142       } else {
   143         if (u._id - v._id == _width)
   144           return Edge(v._id);
   145         if (u._id - v._id == 1 && v._id % _width < _width - 1) {
   146           return Edge(v._id / _width * (_width - 1) +
   147                       v._id % _width + _edge_limit);
   148         }
   149       }
   150       return INVALID;
   151     }
   152 
   153     Arc findArc(Node u, Node v, Arc prev = INVALID) const {
   154       if (prev != INVALID) return INVALID;
   155       if (v._id > u._id) {
   156         if (v._id - u._id == _width)
   157           return Arc((u._id << 1) | 1);
   158         if (v._id - u._id == 1 && u._id % _width < _width - 1) {
   159           return Arc(((u._id / _width * (_width - 1) +
   160                        u._id % _width + _edge_limit) << 1) | 1);
   161         }
   162       } else {
   163         if (u._id - v._id == _width)
   164           return Arc(v._id << 1);
   165         if (u._id - v._id == 1 && v._id % _width < _width - 1) {
   166           return Arc((v._id / _width * (_width - 1) +
   167                        v._id % _width + _edge_limit) << 1);
   168         }
   169       }
   170       return INVALID;
   171     }
   172 
   173     class Node {
   174       friend class GridGraphBase;
   175 
   176     protected:
   177       int _id;
   178       Node(int id) : _id(id) {}
   179     public:
   180       Node() {}
   181       Node (Invalid) : _id(-1) {}
   182       bool operator==(const Node node) const {return _id == node._id;}
   183       bool operator!=(const Node node) const {return _id != node._id;}
   184       bool operator<(const Node node) const {return _id < node._id;}
   185     };
   186 
   187     class Edge {
   188       friend class GridGraphBase;
   189       friend class Arc;
   190 
   191     protected:
   192       int _id;
   193 
   194       Edge(int id) : _id(id) {}
   195 
   196     public:
   197       Edge() {}
   198       Edge (Invalid) : _id(-1) {}
   199       bool operator==(const Edge edge) const {return _id == edge._id;}
   200       bool operator!=(const Edge edge) const {return _id != edge._id;}
   201       bool operator<(const Edge edge) const {return _id < edge._id;}
   202     };
   203 
   204     class Arc {
   205       friend class GridGraphBase;
   206 
   207     protected:
   208       int _id;
   209 
   210       Arc(int id) : _id(id) {}
   211 
   212     public:
   213       Arc() {}
   214       Arc (Invalid) : _id(-1) {}
   215       operator Edge() const { return _id != -1 ? Edge(_id >> 1) : INVALID; }
   216       bool operator==(const Arc arc) const {return _id == arc._id;}
   217       bool operator!=(const Arc arc) const {return _id != arc._id;}
   218       bool operator<(const Arc arc) const {return _id < arc._id;}
   219     };
   220 
   221     static bool direction(Arc arc) {
   222       return (arc._id & 1) == 1;
   223     }
   224 
   225     static Arc direct(Edge edge, bool dir) {
   226       return Arc((edge._id << 1) | (dir ? 1 : 0));
   227     }
   228 
   229     void first(Node& node) const {
   230       node._id = _node_num - 1;
   231     }
   232 
   233     static void next(Node& node) {
   234       --node._id;
   235     }
   236 
   237     void first(Edge& edge) const {
   238       edge._id = _edge_num - 1;
   239     }
   240 
   241     static void next(Edge& edge) {
   242       --edge._id;
   243     }
   244 
   245     void first(Arc& arc) const {
   246       arc._id = 2 * _edge_num - 1;
   247     }
   248 
   249     static void next(Arc& arc) {
   250       --arc._id;
   251     }
   252 
   253     void firstOut(Arc& arc, const Node& node) const {
   254       if (node._id % _width < _width - 1) {
   255         arc._id = (_edge_limit + node._id % _width +
   256                    (node._id / _width) * (_width - 1)) << 1 | 1;
   257         return;
   258       }
   259       if (node._id < _node_num - _width) {
   260         arc._id = node._id << 1 | 1;
   261         return;
   262       }
   263       if (node._id % _width > 0) {
   264         arc._id = (_edge_limit + node._id % _width +
   265                    (node._id / _width) * (_width - 1) - 1) << 1;
   266         return;
   267       }
   268       if (node._id >= _width) {
   269         arc._id = (node._id - _width) << 1;
   270         return;
   271       }
   272       arc._id = -1;
   273     }
   274 
   275     void nextOut(Arc& arc) const {
   276       int nid = arc._id >> 1;
   277       if ((arc._id & 1) == 1) {
   278         if (nid >= _edge_limit) {
   279           nid = (nid - _edge_limit) % (_width - 1) +
   280             (nid - _edge_limit) / (_width - 1) * _width;
   281           if (nid < _node_num - _width) {
   282             arc._id = nid << 1 | 1;
   283             return;
   284           }
   285         }
   286         if (nid % _width > 0) {
   287           arc._id = (_edge_limit + nid % _width +
   288                      (nid / _width) * (_width - 1) - 1) << 1;
   289           return;
   290         }
   291         if (nid >= _width) {
   292           arc._id = (nid - _width) << 1;
   293           return;
   294         }
   295       } else {
   296         if (nid >= _edge_limit) {
   297           nid = (nid - _edge_limit) % (_width - 1) +
   298             (nid - _edge_limit) / (_width - 1) * _width + 1;
   299           if (nid >= _width) {
   300             arc._id = (nid - _width) << 1;
   301             return;
   302           }
   303         }
   304       }
   305       arc._id = -1;
   306     }
   307 
   308     void firstIn(Arc& arc, const Node& node) const {
   309       if (node._id % _width < _width - 1) {
   310         arc._id = (_edge_limit + node._id % _width +
   311                    (node._id / _width) * (_width - 1)) << 1;
   312         return;
   313       }
   314       if (node._id < _node_num - _width) {
   315         arc._id = node._id << 1;
   316         return;
   317       }
   318       if (node._id % _width > 0) {
   319         arc._id = (_edge_limit + node._id % _width +
   320                    (node._id / _width) * (_width - 1) - 1) << 1 | 1;
   321         return;
   322       }
   323       if (node._id >= _width) {
   324         arc._id = (node._id - _width) << 1 | 1;
   325         return;
   326       }
   327       arc._id = -1;
   328     }
   329 
   330     void nextIn(Arc& arc) const {
   331       int nid = arc._id >> 1;
   332       if ((arc._id & 1) == 0) {
   333         if (nid >= _edge_limit) {
   334           nid = (nid - _edge_limit) % (_width - 1) +
   335             (nid - _edge_limit) / (_width - 1) * _width;
   336           if (nid < _node_num - _width) {
   337             arc._id = nid << 1;
   338             return;
   339           }
   340         }
   341         if (nid % _width > 0) {
   342           arc._id = (_edge_limit + nid % _width +
   343                      (nid / _width) * (_width - 1) - 1) << 1 | 1;
   344           return;
   345         }
   346         if (nid >= _width) {
   347           arc._id = (nid - _width) << 1 | 1;
   348           return;
   349         }
   350       } else {
   351         if (nid >= _edge_limit) {
   352           nid = (nid - _edge_limit) % (_width - 1) +
   353             (nid - _edge_limit) / (_width - 1) * _width + 1;
   354           if (nid >= _width) {
   355             arc._id = (nid - _width) << 1 | 1;
   356             return;
   357           }
   358         }
   359       }
   360       arc._id = -1;
   361     }
   362 
   363     void firstInc(Edge& edge, bool& dir, const Node& node) const {
   364       if (node._id % _width < _width - 1) {
   365         edge._id = _edge_limit + node._id % _width +
   366           (node._id / _width) * (_width - 1);
   367         dir = true;
   368         return;
   369       }
   370       if (node._id < _node_num - _width) {
   371         edge._id = node._id;
   372         dir = true;
   373         return;
   374       }
   375       if (node._id % _width > 0) {
   376         edge._id = _edge_limit + node._id % _width +
   377           (node._id / _width) * (_width - 1) - 1;
   378         dir = false;
   379         return;
   380       }
   381       if (node._id >= _width) {
   382         edge._id = node._id - _width;
   383         dir = false;
   384         return;
   385       }
   386       edge._id = -1;
   387       dir = true;
   388     }
   389 
   390     void nextInc(Edge& edge, bool& dir) const {
   391       int nid = edge._id;
   392       if (dir) {
   393         if (nid >= _edge_limit) {
   394           nid = (nid - _edge_limit) % (_width - 1) +
   395             (nid - _edge_limit) / (_width - 1) * _width;
   396           if (nid < _node_num - _width) {
   397             edge._id = nid;
   398             return;
   399           }
   400         }
   401         if (nid % _width > 0) {
   402           edge._id = _edge_limit + nid % _width +
   403             (nid / _width) * (_width - 1) - 1;
   404           dir = false;
   405           return;
   406         }
   407         if (nid >= _width) {
   408           edge._id = nid - _width;
   409           dir = false;
   410           return;
   411         }
   412       } else {
   413         if (nid >= _edge_limit) {
   414           nid = (nid - _edge_limit) % (_width - 1) +
   415             (nid - _edge_limit) / (_width - 1) * _width + 1;
   416           if (nid >= _width) {
   417             edge._id = nid - _width;
   418             return;
   419           }
   420         }
   421       }
   422       edge._id = -1;
   423       dir = true;
   424     }
   425 
   426     Arc right(Node n) const {
   427       if (n._id % _width < _width - 1) {
   428         return Arc(((_edge_limit + n._id % _width +
   429                     (n._id / _width) * (_width - 1)) << 1) | 1);
   430       } else {
   431         return INVALID;
   432       }
   433     }
   434 
   435     Arc left(Node n) const {
   436       if (n._id % _width > 0) {
   437         return Arc((_edge_limit + n._id % _width +
   438                      (n._id / _width) * (_width - 1) - 1) << 1);
   439       } else {
   440         return INVALID;
   441       }
   442     }
   443 
   444     Arc up(Node n) const {
   445       if (n._id < _edge_limit) {
   446         return Arc((n._id << 1) | 1);
   447       } else {
   448         return INVALID;
   449       }
   450     }
   451 
   452     Arc down(Node n) const {
   453       if (n._id >= _width) {
   454         return Arc((n._id - _width) << 1);
   455       } else {
   456         return INVALID;
   457       }
   458     }
   459 
   460   private:
   461     int _width, _height;
   462     int _node_num, _edge_num;
   463     int _edge_limit;
   464   };
   465 
   466 
   467   typedef GraphExtender<GridGraphBase> ExtendedGridGraphBase;
   468 
   469   /// \ingroup graphs
   470   ///
   471   /// \brief Grid graph class
   472   ///
   473   /// This class implements a special graph type. The nodes of the
   474   /// graph can be indexed by two integer \c (i,j) value where \c i is
   475   /// in the \c [0..width()-1] range and j is in the \c
   476   /// [0..height()-1] range.  Two nodes are connected in the graph if
   477   /// the indexes differ exactly on one position and exactly one is
   478   /// the difference. The nodes of the graph can be indexed by position
   479   /// with the \c operator()() function. The positions of the nodes can be
   480   /// get with \c pos(), \c col() and \c row() members. The outgoing
   481   /// arcs can be retrieved with the \c right(), \c up(), \c left()
   482   /// and \c down() functions, where the bottom-left corner is the
   483   /// origin.
   484   ///
   485   /// \image html grid_graph.png
   486   /// \image latex grid_graph.eps "Grid graph" width=\textwidth
   487   ///
   488   /// A short example about the basic usage:
   489   ///\code
   490   /// GridGraph graph(rows, cols);
   491   /// GridGraph::NodeMap<int> val(graph);
   492   /// for (int i = 0; i < graph.width(); ++i) {
   493   ///   for (int j = 0; j < graph.height(); ++j) {
   494   ///     val[graph(i, j)] = i + j;
   495   ///   }
   496   /// }
   497   ///\endcode
   498   ///
   499   /// This graph type is fully conform to the \ref concepts::Graph
   500   /// "Graph" concept, and it also has an important extra feature
   501   /// that its maps are real \ref concepts::ReferenceMap
   502   /// "reference map"s.
   503   class GridGraph : public ExtendedGridGraphBase {
   504   public:
   505 
   506     typedef ExtendedGridGraphBase Parent;
   507 
   508     /// \brief Map to get the indices of the nodes as dim2::Point<int>.
   509     ///
   510     /// Map to get the indices of the nodes as dim2::Point<int>.
   511     class IndexMap {
   512     public:
   513       /// \brief The key type of the map
   514       typedef GridGraph::Node Key;
   515       /// \brief The value type of the map
   516       typedef dim2::Point<int> Value;
   517 
   518       /// \brief Constructor
   519       ///
   520       /// Constructor
   521       IndexMap(const GridGraph& graph) : _graph(graph) {}
   522 
   523       /// \brief The subscript operator
   524       ///
   525       /// The subscript operator.
   526       Value operator[](Key key) const {
   527         return _graph.pos(key);
   528       }
   529 
   530     private:
   531       const GridGraph& _graph;
   532     };
   533 
   534     /// \brief Map to get the column of the nodes.
   535     ///
   536     /// Map to get the column of the nodes.
   537     class ColMap {
   538     public:
   539       /// \brief The key type of the map
   540       typedef GridGraph::Node Key;
   541       /// \brief The value type of the map
   542       typedef int Value;
   543 
   544       /// \brief Constructor
   545       ///
   546       /// Constructor
   547       ColMap(const GridGraph& graph) : _graph(graph) {}
   548 
   549       /// \brief The subscript operator
   550       ///
   551       /// The subscript operator.
   552       Value operator[](Key key) const {
   553         return _graph.col(key);
   554       }
   555 
   556     private:
   557       const GridGraph& _graph;
   558     };
   559 
   560     /// \brief Map to get the row of the nodes.
   561     ///
   562     /// Map to get the row of the nodes.
   563     class RowMap {
   564     public:
   565       /// \brief The key type of the map
   566       typedef GridGraph::Node Key;
   567       /// \brief The value type of the map
   568       typedef int Value;
   569 
   570       /// \brief Constructor
   571       ///
   572       /// Constructor
   573       RowMap(const GridGraph& graph) : _graph(graph) {}
   574 
   575       /// \brief The subscript operator
   576       ///
   577       /// The subscript operator.
   578       Value operator[](Key key) const {
   579         return _graph.row(key);
   580       }
   581 
   582     private:
   583       const GridGraph& _graph;
   584     };
   585 
   586     /// \brief Constructor
   587     ///
   588     /// Construct a grid graph with given size.
   589     GridGraph(int width, int height) { construct(width, height); }
   590 
   591     /// \brief Resize the graph
   592     ///
   593     /// Resize the graph. The function will fully destroy and rebuild
   594     /// the graph.  This cause that the maps of the graph will
   595     /// reallocated automatically and the previous values will be
   596     /// lost.
   597     void resize(int width, int height) {
   598       Parent::notifier(Arc()).clear();
   599       Parent::notifier(Edge()).clear();
   600       Parent::notifier(Node()).clear();
   601       construct(width, height);
   602       Parent::notifier(Node()).build();
   603       Parent::notifier(Edge()).build();
   604       Parent::notifier(Arc()).build();
   605     }
   606 
   607     /// \brief The node on the given position.
   608     ///
   609     /// Gives back the node on the given position.
   610     Node operator()(int i, int j) const {
   611       return Parent::operator()(i, j);
   612     }
   613 
   614     /// \brief Gives back the column index of the node.
   615     ///
   616     /// Gives back the column index of the node.
   617     int col(Node n) const {
   618       return Parent::col(n);
   619     }
   620 
   621     /// \brief Gives back the row index of the node.
   622     ///
   623     /// Gives back the row index of the node.
   624     int row(Node n) const {
   625       return Parent::row(n);
   626     }
   627 
   628     /// \brief Gives back the position of the node.
   629     ///
   630     /// Gives back the position of the node, ie. the <tt>(col,row)</tt> pair.
   631     dim2::Point<int> pos(Node n) const {
   632       return Parent::pos(n);
   633     }
   634 
   635     /// \brief Gives back the number of the columns.
   636     ///
   637     /// Gives back the number of the columns.
   638     int width() const {
   639       return Parent::width();
   640     }
   641 
   642     /// \brief Gives back the number of the rows.
   643     ///
   644     /// Gives back the number of the rows.
   645     int height() const {
   646       return Parent::height();
   647     }
   648 
   649     /// \brief Gives back the arc goes right from the node.
   650     ///
   651     /// Gives back the arc goes right from the node. If there is not
   652     /// outgoing arc then it gives back INVALID.
   653     Arc right(Node n) const {
   654       return Parent::right(n);
   655     }
   656 
   657     /// \brief Gives back the arc goes left from the node.
   658     ///
   659     /// Gives back the arc goes left from the node. If there is not
   660     /// outgoing arc then it gives back INVALID.
   661     Arc left(Node n) const {
   662       return Parent::left(n);
   663     }
   664 
   665     /// \brief Gives back the arc goes up from the node.
   666     ///
   667     /// Gives back the arc goes up from the node. If there is not
   668     /// outgoing arc then it gives back INVALID.
   669     Arc up(Node n) const {
   670       return Parent::up(n);
   671     }
   672 
   673     /// \brief Gives back the arc goes down from the node.
   674     ///
   675     /// Gives back the arc goes down from the node. If there is not
   676     /// outgoing arc then it gives back INVALID.
   677     Arc down(Node n) const {
   678       return Parent::down(n);
   679     }
   680 
   681     /// \brief Index map of the grid graph
   682     ///
   683     /// Just returns an IndexMap for the grid graph.
   684     IndexMap indexMap() const {
   685       return IndexMap(*this);
   686     }
   687 
   688     /// \brief Row map of the grid graph
   689     ///
   690     /// Just returns a RowMap for the grid graph.
   691     RowMap rowMap() const {
   692       return RowMap(*this);
   693     }
   694 
   695     /// \brief Column map of the grid graph
   696     ///
   697     /// Just returns a ColMap for the grid graph.
   698     ColMap colMap() const {
   699       return ColMap(*this);
   700     }
   701 
   702   };
   703 
   704 }
   705 #endif