COIN-OR::LEMON - Graph Library

source: lemon/lemon/grid_graph.h @ 346:ada5f74d1c9e

Last change on this file since 346:ada5f74d1c9e was 346:ada5f74d1c9e, checked in by Peter Kovacs <kpeter@…>, 16 years ago

Port grid graph structure from SVN 3503 (ticket #57)

File size: 11.8 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 <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
35namespace 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
Note: See TracBrowser for help on using the repository browser.