COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/grid_graph.h @ 335:160bf92c7cdc

Last change on this file since 335:160bf92c7cdc was 335:160bf92c7cdc, checked in by Balazs Dezso <deba@…>, 15 years ago

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.
File size: 18.5 KB
Line 
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
31namespace 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
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;}
199    };
200
201    class Arc {
202      friend class GridGraphBase;
203
204    protected:
205      int _id;
206
207      Arc(int id) : _id(id) {}
208
209    public:
210      Arc() {}
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;}
216    };
217
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
226    void first(Node& node) const {
227      node._id = _node_num - 1;
228    }
229
230    static void next(Node& node) {
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;
240    }
241
242    void first(Arc& arc) const {
243      arc._id = 2 * _edge_num - 1;
244    }
245
246    static void next(Arc& arc) {
247      --arc._id;
248    }
249
250    void firstOut(Arc& arc, const Node& node) const {
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;
270    }
271
272    void nextOut(Arc& arc) const {
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;
303    }
304
305    void firstIn(Arc& arc, const Node& node) const {
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;
325    }
326
327    void nextIn(Arc& arc) const {
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;
454      }
455    }
456
457  private:
458    int _width, _height;
459    int _node_num, _edge_num;
460    int _edge_limit;
461  };
462
463
464  typedef GraphExtender<GridGraphBase> ExtendedGridGraphBase;
465
466  /// \ingroup graphs
467  ///
468  /// \brief Grid graph class
469  ///
470  /// This class implements a special graph type. The nodes of the
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.
481  ///
482  /// \image html grid_graph.png
483  /// \image latex grid_graph.eps "Grid digraph" row_num=\textrow_num
484  ///
485  /// A short example about the basic usage:
486  ///\code
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;
492  ///   }
493  /// }
494  ///\endcode
495  ///
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.
500  class GridGraph : public ExtendedGridGraphBase {
501  public:
502
503    typedef ExtendedGridGraphBase Parent;
504
505    /// \brief Map to get the indices of the nodes as dim2::Point<int>.
506    ///
507    /// Map to get the indices of the nodes as dim2::Point<int>.
508    class IndexMap {
509    public:
510      /// \brief The key type of the map
511      typedef GridGraph::Node Key;
512      /// \brief The value type of the map
513      typedef dim2::Point<int> Value;
514
515      /// \brief Constructor
516      ///
517      /// Constructor
518      IndexMap(const GridGraph& graph) : _graph(graph) {}
519
520      /// \brief The subscript operator
521      ///
522      /// The subscript operator.
523      Value operator[](Key key) const {
524        return _graph.pos(key);
525      }
526
527    private:
528      const GridGraph& _graph;
529    };
530
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
557    /// \brief Map to get the row of the nodes.
558    ///
559    /// Map to get the row of the nodes.
560    class RowMap {
561    public:
562      /// \brief The key type of the map
563      typedef GridGraph::Node Key;
564      /// \brief The value type of the map
565      typedef int Value;
566
567      /// \brief Constructor
568      ///
569      /// Constructor
570      RowMap(const GridGraph& graph) : _graph(graph) {}
571
572      /// \brief The subscript operator
573      ///
574      /// The subscript operator.
575      Value operator[](Key key) const {
576        return _graph.row(key);
577      }
578
579    private:
580      const GridGraph& _graph;
581    };
582
583    /// \brief Constructor
584    ///
585    /// Construct a grid graph with given size.
586    GridGraph(int width, int height) { construct(width, height); }
587
588    /// \brief Resize the graph
589    ///
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.
594    void resize(int width, int height) {
595      Parent::notifier(Arc()).clear();
596      Parent::notifier(Edge()).clear();
597      Parent::notifier(Node()).clear();
598      construct(width, height);
599      Parent::notifier(Node()).build();
600      Parent::notifier(Edge()).build();
601      Parent::notifier(Arc()).build();
602    }
603
604    /// \brief The node on the given position.
605    ///
606    /// Gives back the node on the given position.
607    Node operator()(int i, int j) const {
608      return Parent::operator()(i, j);
609    }
610
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
618    /// \brief Gives back the row index of the node.
619    ///
620    /// Gives back the row index of the node.
621    int row(Node n) const {
622      return Parent::row(n);
623    }
624
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.
635    int width() const {
636      return Parent::width();
637    }
638
639    /// \brief Gives back the number of the rows.
640    ///
641    /// Gives back the number of the rows.
642    int height() const {
643      return Parent::height();
644    }
645
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
670    /// \brief Gives back the arc goes down from the node.
671    ///
672    /// Gives back the arc goes down from the node. If there is not
673    /// outgoing arc then it gives back INVALID.
674    Arc down(Node n) const {
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
701}
702#endif
Note: See TracBrowser for help on using the repository browser.