COIN-OR::LEMON - Graph Library

source: lemon/lemon/grid_graph.h @ 349:560e4b6d020d

Last change on this file since 349:560e4b6d020d was 348:052cecabcb71, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Fixes and improvements related to GridGraph?

File size: 18.5 KB
RevLine 
[346]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>
[347]23#include <lemon/bits/graph_extender.h>
24#include <lemon/dim2.h>
[346]25#include <lemon/assert.h>
26
27///\ingroup graphs
28///\file
29///\brief GridGraph class.
30
31namespace lemon {
32
33  class GridGraphBase {
34
35  public:
36
37    typedef GridGraphBase Graph;
38
39    class Node;
[347]40    class Edge;
[346]41    class Arc;
42
43  public:
44
45    GridGraphBase() {}
46
47  protected:
48
[347]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;
[346]54    }
55
56  public:
57
58    Node operator()(int i, int j) const {
[347]59      LEMON_DEBUG(0 <= i && i < _width &&
60                  0 <= j  && j < _height, "Index out of range");
[346]61      return Node(i + j * _width);
62    }
63
[347]64    int col(Node n) const {
65      return n._id % _width;
[346]66    }
67
[347]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));
[346]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
[347]87    int nodeNum() const { return _node_num; }
88    int edgeNum() const { return _edge_num; }
89    int arcNum() const { return 2 * _edge_num; }
[346]90
[347]91    Node u(Edge edge) const {
92      if (edge._id < _edge_limit) {
93        return edge._id;
[346]94      } else {
[347]95        return (edge._id - _edge_limit) % (_width - 1) +
96          (edge._id - _edge_limit) / (_width - 1) * _width;
[346]97      }
98    }
99
[347]100    Node v(Edge edge) const {
101      if (edge._id < _edge_limit) {
102        return edge._id + _width;
[346]103      } else {
[347]104        return (edge._id - _edge_limit) % (_width - 1) +
105          (edge._id - _edge_limit) / (_width - 1) * _width + 1;
[346]106      }
107    }
108
[347]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; }
[346]124
125    static Node nodeFromId(int id) { return Node(id);}
[347]126    static Edge edgeFromId(int id) { return Edge(id);}
[346]127    static Arc arcFromId(int id) { return Arc(id);}
128
[347]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    }
[346]150
151    Arc findArc(Node u, Node v, Arc prev = INVALID) const {
152      if (prev != INVALID) return INVALID;
[347]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        }
[346]167      }
168      return INVALID;
169    }
170
171    class Node {
172      friend class GridGraphBase;
173
174    protected:
[347]175      int _id;
176      Node(int id) : _id(id) {}
[346]177    public:
178      Node() {}
[347]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;
[348]187      friend class Arc;
[347]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;}
[346]200    };
201
202    class Arc {
203      friend class GridGraphBase;
204
205    protected:
[347]206      int _id;
207
208      Arc(int id) : _id(id) {}
209
[346]210    public:
211      Arc() {}
[347]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;}
[346]217    };
218
[347]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
[346]227    void first(Node& node) const {
[347]228      node._id = _node_num - 1;
[346]229    }
230
231    static void next(Node& node) {
[347]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;
[346]241    }
242
243    void first(Arc& arc) const {
[347]244      arc._id = 2 * _edge_num - 1;
[346]245    }
246
247    static void next(Arc& arc) {
[347]248      --arc._id;
[346]249    }
250
251    void firstOut(Arc& arc, const Node& node) const {
[347]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        }
[346]293      } else {
[347]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;
[346]430      }
431    }
432
[347]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);
[346]437      } else {
[347]438        return INVALID;
[346]439      }
440    }
441
[347]442    Arc up(Node n) const {
443      if (n._id < _edge_limit) {
444        return Arc((n._id << 1) | 1);
[346]445      } else {
[347]446        return INVALID;
[346]447      }
448    }
449
[347]450    Arc down(Node n) const {
451      if (n._id >= _width) {
452        return Arc((n._id - _width) << 1);
[346]453      } else {
[347]454        return INVALID;
[346]455      }
456    }
457
458  private:
459    int _width, _height;
[347]460    int _node_num, _edge_num;
461    int _edge_limit;
[346]462  };
463
[347]464
465  typedef GraphExtender<GridGraphBase> ExtendedGridGraphBase;
[346]466
467  /// \ingroup graphs
468  ///
469  /// \brief Grid graph class
470  ///
471  /// This class implements a special graph type. The nodes of the
[347]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
[348]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
[347]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.
[346]482  ///
483  /// \image html grid_graph.png
[348]484  /// \image latex grid_graph.eps "Grid graph" row_num=\textrow_num
[346]485  ///
[347]486  /// A short example about the basic usage:
[346]487  ///\code
[347]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;
[346]493  ///   }
494  /// }
495  ///\endcode
496  ///
[348]497  /// This graph type is fully conform to the \ref concepts::Graph
[347]498  /// "Graph" concept, and it also has an important extra feature
[348]499  /// that its maps are real \ref concepts::ReferenceMap
500  /// "reference map"s.
[346]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:
[347]511      /// \brief The key type of the map
[346]512      typedef GridGraph::Node Key;
[347]513      /// \brief The value type of the map
[346]514      typedef dim2::Point<int> Value;
515
[347]516      /// \brief Constructor
517      ///
[346]518      /// Constructor
519      IndexMap(const GridGraph& graph) : _graph(graph) {}
520
[347]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);
[346]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:
[347]563      /// \brief The key type of the map
[346]564      typedef GridGraph::Node Key;
[347]565      /// \brief The value type of the map
[346]566      typedef int Value;
567
[347]568      /// \brief Constructor
569      ///
[346]570      /// Constructor
571      RowMap(const GridGraph& graph) : _graph(graph) {}
572
[347]573      /// \brief The subscript operator
574      ///
575      /// The subscript operator.
576      Value operator[](Key key) const {
[346]577        return _graph.row(key);
578      }
579
580    private:
581      const GridGraph& _graph;
582    };
583
584    /// \brief Constructor
585    ///
[347]586    /// Construct a grid graph with given size.
[346]587    GridGraph(int width, int height) { construct(width, height); }
588
589    /// \brief Resize the graph
590    ///
[347]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.
[346]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
[347]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
[346]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
[347]626    /// \brief Gives back the position of the node.
[346]627    ///
[347]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);
[346]631    }
632
[347]633    /// \brief Gives back the number of the columns.
[346]634    ///
[347]635    /// Gives back the number of the columns.
[346]636    int width() const {
637      return Parent::width();
638    }
639
[347]640    /// \brief Gives back the number of the rows.
[346]641    ///
[347]642    /// Gives back the number of the rows.
[346]643    int height() const {
644      return Parent::height();
645    }
646
[347]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
[346]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
[347]674    /// outgoing arc then it gives back INVALID.
[346]675    Arc down(Node n) const {
[347]676      return Parent::down(n);
[346]677    }
678
[347]679    /// \brief Index map of the grid graph
[346]680    ///
[347]681    /// Just returns an IndexMap for the grid graph.
682    IndexMap indexMap() const {
683      return IndexMap(*this);
[346]684    }
685
[347]686    /// \brief Row map of the grid graph
[346]687    ///
[347]688    /// Just returns a RowMap for the grid graph.
689    RowMap rowMap() const {
690      return RowMap(*this);
[346]691    }
692
[347]693    /// \brief Column map of the grid graph
[346]694    ///
[347]695    /// Just returns a ColMap for the grid graph.
696    ColMap colMap() const {
697      return ColMap(*this);
[346]698    }
699
[347]700  };
[346]701
702}
[347]703#endif
Note: See TracBrowser for help on using the repository browser.