COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/grid_ugraph.h @ 2553:bfced05fa852

Last change on this file since 2553:bfced05fa852 was 2553:bfced05fa852, checked in by Alpar Juttner, 17 years ago

Happy New Year to LEMON (+ better update-copyright-header script)

File size: 12.0 KB
Line 
1/* -*- C++ -*-
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_UGRAPH_H
20#define GRID_UGRAPH_H
21
22#include <iostream>
23#include <lemon/bits/invalid.h>
24#include <lemon/bits/utility.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 GridUGraph class.
34
35namespace lemon {
36
37  class GridUGraphBase {
38
39  public:
40
41    typedef GridUGraphBase UGraph;
42
43    class Node;
44    class Edge;
45
46  public:
47
48    GridUGraphBase() {}
49
50  protected:
51
52    void construct(int w, int h) {
53      _height = h; _width = w;
54      _nodeNum = h * w; _edgeNum = 2 * _nodeNum - w - h;
55      _edgeLimit = _nodeNum - w;
56    }
57
58    Edge _down(Node n) const {
59      if (n.id < _nodeNum - _width) {
60        return Edge(n.id);
61      } else {
62        return INVALID;
63      }
64    }
65
66    Edge _up(Node n) const {
67      if (n.id >= _width) {
68        return Edge(n.id - _width);
69      } else {
70        return INVALID;
71      }
72    }
73
74    Edge _right(Node n) const {
75      if (n.id % _width < _width - 1) {
76        return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1);
77      } else {
78        return INVALID;
79      }
80    }
81
82    Edge _left(Node n) const {
83      if (n.id % _width > 0) {
84        return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1) - 1;
85      } else {
86        return INVALID;
87      }
88    }
89
90  public:
91
92    class IndexError : public RuntimeError {
93    public:
94      virtual const char* what() const throw() {
95        return "lemon::GridUGraph::IndexError";
96      } 
97    };
98
99   
100    Node operator()(int i, int j) const {
101      LEMON_ASSERT(0 <= i && i < width() && 0 <= j  &&
102                   j < height(), IndexError());
103      return Node(i + j * _width);
104    }
105
106    int row(Node n) const {
107      return n.id / _width;
108    }
109   
110    int col(Node n) const {
111      return n.id % _width;   
112    }
113
114    int width() const {
115      return _width;
116    }
117
118    int height() const {
119      return _height;
120    }
121
122    typedef True NodeNumTag;
123    typedef True EdgeNumTag;
124
125    int nodeNum() const { return _nodeNum; }
126    int edgeNum() const { return _edgeNum; }
127
128    int maxNodeId() const { return nodeNum() - 1; }
129    int maxEdgeId() const { return edgeNum() - 1; }
130
131    Node source(Edge e) const {
132      if (e.id < _edgeLimit) {
133        return e.id;
134      } else {
135        return (e.id - _edgeLimit) % (_width - 1) +
136          (e.id - _edgeLimit) / (_width - 1) * _width;
137      }
138    }
139
140    Node target(Edge e) const {
141      if (e.id < _edgeLimit) {
142        return e.id + _width;
143      } else {
144        return (e.id - _edgeLimit) % (_width - 1) +
145          (e.id - _edgeLimit) / (_width - 1) * _width + 1;
146      }
147    }
148
149    static int id(Node v) { return v.id; }
150    static int id(Edge e) { return e.id; }
151
152    static Node nodeFromId(int id) { return Node(id);}
153   
154    static Edge edgeFromId(int id) { return Edge(id);}
155
156    typedef True FindEdgeTag;
157
158    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
159      if (prev != INVALID) return INVALID;
160      if (v.id - u.id == _width) return Edge(u.id);
161      if (v.id - u.id == 1 && u.id % _width < _width - 1) {
162        return Edge(u.id / _width * (_width - 1) +
163                    u.id % _width + _edgeLimit);
164      }
165      return INVALID;
166    }
167   
168     
169    class Node {
170      friend class GridUGraphBase;
171
172    protected:
173      int id;
174      Node(int _id) { id = _id;}
175    public:
176      Node() {}
177      Node (Invalid) { id = -1; }
178      bool operator==(const Node node) const {return id == node.id;}
179      bool operator!=(const Node node) const {return id != node.id;}
180      bool operator<(const Node node) const {return id < node.id;}
181    };
182   
183
184
185    class Edge {
186      friend class GridUGraphBase;
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    void first(Node& node) const {
202      node.id = nodeNum() - 1;
203    }
204
205    static void next(Node& node) {
206      --node.id;
207    }
208
209    void first(Edge& edge) const {
210      edge.id = edgeNum() - 1;
211    }
212
213    static void next(Edge& edge) {
214      --edge.id;
215    }
216
217    void firstOut(Edge& edge, const Node& node) const {
218      if (node.id < _nodeNum - _width) {
219        edge.id = node.id;
220      } else if (node.id % _width < _width - 1) {
221        edge.id = _edgeLimit + node.id % _width +
222          (node.id / _width) * (_width - 1);
223      } else {
224        edge.id = -1;
225      }
226    }
227
228    void nextOut(Edge& edge) const {
229      if (edge.id >= _edgeLimit) {
230        edge.id = -1;
231      } else if (edge.id % _width < _width - 1) {
232        edge.id = _edgeLimit + edge.id % _width +
233          (edge.id / _width) * (_width - 1);
234      } else {
235        edge.id = -1;
236      }
237    }
238
239    void firstIn(Edge& edge, const Node& node) const {
240      if (node.id >= _width) {
241        edge.id = node.id - _width;
242      } else if (node.id % _width > 0) {
243        edge.id = _edgeLimit + node.id % _width +
244          (node.id / _width) * (_width - 1) - 1;
245      } else {
246        edge.id = -1;
247      }
248    }
249   
250    void nextIn(Edge& edge) const {
251      if (edge.id >= _edgeLimit) {
252        edge.id = -1;
253      } else if (edge.id % _width > 0) {
254        edge.id = _edgeLimit + edge.id % _width +
255          (edge.id / _width + 1) * (_width - 1) - 1;
256      } else {
257        edge.id = -1;
258      }
259    }
260
261  private:
262    int _width, _height;
263    int _nodeNum, _edgeNum;
264    int _edgeLimit;
265  };
266
267
268  typedef UGraphExtender<UndirGraphExtender<GridUGraphBase> >
269  ExtendedGridUGraphBase;
270
271  /// \ingroup graphs
272  ///
273  /// \brief Grid graph class
274  ///
275  /// This class implements a special graph type. The nodes of the
276  /// graph can be indiced by two integer \c (i,j) value where \c i
277  /// is in the \c [0,width) range and j is in the [0, height) range.
278  /// Two nodes are connected in the graph if the indices differ only
279  /// on one position and only one is the difference.
280  ///
281  /// \image html grid_ugraph.png
282  /// \image latex grid_ugraph.eps "Grid graph" width=\textwidth
283  ///
284  /// The graph can be indiced in the following way:
285  ///\code
286  /// GridUGraph graph(w, h);
287  /// GridUGraph::NodeMap<int> val(graph);
288  /// for (int i = 0; i < graph.width(); ++i) {
289  ///   for (int j = 0; j < graph.height(); ++j) {
290  ///     val[graph(i, j)] = i + j;
291  ///   }
292  /// }
293  ///\endcode
294  ///
295  /// The graph type is fully conform to the \ref concepts::UGraph
296  /// "Undirected Graph" concept,  and it also has an
297  ///important extra feature that
298  ///its maps are real \ref concepts::ReferenceMap "reference map"s.
299  ///
300  ///
301  /// \author Balazs Dezso
302  class GridUGraph : public ExtendedGridUGraphBase {
303  public:
304
305    typedef ExtendedGridUGraphBase Parent;
306
307    /// \brief Map to get the indices of the nodes as dim2::Point<int>.
308    ///
309    /// Map to get the indices of the nodes as dim2::Point<int>.
310    class IndexMap {
311    public:
312      /// \brief The key type of the map
313      typedef GridUGraph::Node Key;
314      /// \brief The value type of the map
315      typedef dim2::Point<int> Value;
316
317      /// \brief Constructor
318      ///
319      /// Constructor
320      IndexMap(const GridUGraph& _graph) : graph(_graph) {}
321
322      /// \brief The subscript operator
323      ///
324      /// The subscript operator.
325      Value operator[](Key key) const {
326        return dim2::Point<int>(graph.row(key), graph.col(key));
327      }
328
329    private:
330      const GridUGraph& graph;
331    };
332
333    /// \brief Map to get the row of the nodes.
334    ///
335    /// Map to get the row of the nodes.
336    class RowMap {
337    public:
338      /// \brief The key type of the map
339      typedef GridUGraph::Node Key;
340      /// \brief The value type of the map
341      typedef int Value;
342
343      /// \brief Constructor
344      ///
345      /// Constructor
346      RowMap(const GridUGraph& _graph) : graph(_graph) {}
347
348      /// \brief The subscript operator
349      ///
350      /// The subscript operator.
351      Value operator[](Key key) const {
352        return graph.row(key);
353      }
354
355    private:
356      const GridUGraph& graph;
357    };
358
359    /// \brief Map to get the column of the nodes.
360    ///
361    /// Map to get the column of the nodes.
362    class ColMap {
363    public:
364      /// \brief The key type of the map
365      typedef GridUGraph::Node Key;
366      /// \brief The value type of the map
367      typedef int Value;
368
369      /// \brief Constructor
370      ///
371      /// Constructor
372      ColMap(const GridUGraph& _graph) : graph(_graph) {}
373
374      /// \brief The subscript operator
375      ///
376      /// The subscript operator.
377      Value operator[](Key key) const {
378        return graph.col(key);
379      }
380
381    private:
382      const GridUGraph& graph;
383    };
384
385    /// \brief Constructor
386    ///
387    ///
388    GridUGraph(int n, int m) { construct(n, m); }
389
390    /// \brief Resize the graph
391    ///
392    void resize(int n, int m) {
393      Parent::notifier(Edge()).clear();
394      Parent::notifier(UEdge()).clear();
395      Parent::notifier(Node()).clear();
396      construct(n, m);
397      Parent::notifier(Node()).build();
398      Parent::notifier(UEdge()).build();
399      Parent::notifier(Edge()).build();
400    }
401   
402    /// \brief The node on the given position.
403    ///
404    /// Gives back the node on the given position.
405    Node operator()(int i, int j) const {
406      return Parent::operator()(i, j);
407    }
408
409    /// \brief Gives back the row index of the node.
410    ///
411    /// Gives back the row index of the node.
412    int row(Node n) const {
413      return Parent::row(n);
414    }
415   
416    /// \brief Gives back the coloumn index of the node.
417    ///
418    /// Gives back the coloumn index of the node.
419    int col(Node n) const {
420      return Parent::col(n);
421    }
422
423    /// \brief Gives back the width of the graph.
424    ///
425    /// Gives back the width of the graph.
426    int width() const {
427      return Parent::width();
428    }
429
430    /// \brief Gives back the height of the graph.
431    ///
432    /// Gives back the height of the graph.
433    int height() const {
434      return Parent::height();
435    }
436
437    /// \brief Gives back the edge goes down from the node.
438    ///
439    /// Gives back the edge goes down from the node. If there is not
440    /// outgoing edge then it gives back INVALID.
441    Edge down(Node n) const {
442      UEdge ue = _down(n);
443      return ue != INVALID ? direct(ue, true) : INVALID;
444    }
445   
446    /// \brief Gives back the edge goes up from the node.
447    ///
448    /// Gives back the edge goes up from the node. If there is not
449    /// outgoing edge then it gives back INVALID.
450    Edge up(Node n) const {
451      UEdge ue = _up(n);
452      return ue != INVALID ? direct(ue, false) : INVALID;
453    }
454
455    /// \brief Gives back the edge goes right from the node.
456    ///
457    /// Gives back the edge goes right from the node. If there is not
458    /// outgoing edge then it gives back INVALID.
459    Edge right(Node n) const {
460      UEdge ue = _right(n);
461      return ue != INVALID ? direct(ue, true) : INVALID;
462    }
463
464    /// \brief Gives back the edge goes left from the node.
465    ///
466    /// Gives back the edge goes left from the node. If there is not
467    /// outgoing edge then it gives back INVALID.
468    Edge left(Node n) const {
469      UEdge ue = _left(n);
470      return ue != INVALID ? direct(ue, false) : INVALID;
471    }
472   
473  };
474
475  /// \brief Index map of the grid graph
476  ///
477  /// Just returns an IndexMap for the grid graph.
478  GridUGraph::IndexMap indexMap(const GridUGraph& graph) {
479    return GridUGraph::IndexMap(graph);
480  }
481
482  /// \brief Row map of the grid graph
483  ///
484  /// Just returns a RowMap for the grid graph.
485  GridUGraph::RowMap rowMap(const GridUGraph& graph) {
486    return GridUGraph::RowMap(graph);
487  }
488
489  /// \brief Column map of the grid graph
490  ///
491  /// Just returns a ColMap for the grid graph.
492  GridUGraph::ColMap colMap(const GridUGraph& graph) {
493    return GridUGraph::ColMap(graph);
494  }
495}
496#endif
Note: See TracBrowser for help on using the repository browser.