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