COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/grid_ugraph.h @ 2229:4dbb6dd2dd4b

Last change on this file since 2229:4dbb6dd2dd4b was 2223:590c1b663a27, checked in by Balazs Dezso, 18 years ago

Exporting interface to the Graph class
Some documentation improvements

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-2006
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 width, int height) {
53      _height = height; _width = width;
54      _nodeNum = height * width; _edgeNum = 2 * _nodeNum - width - height;
55      _edgeLimit = _nodeNum - width;
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 concept::UGraph
296  /// "Undirected Graph" concept.
297  ///
298  /// \author Balazs Dezso
299  class GridUGraph : public ExtendedGridUGraphBase {
300  public:
301
302    typedef ExtendedGridUGraphBase Parent;
303
304    /// \brief Map to get the indices of the nodes as dim2::Point<int>.
305    ///
306    /// Map to get the indices of the nodes as dim2::Point<int>.
307    class IndexMap {
308    public:
309      /// \brief The key type of the map
310      typedef GridUGraph::Node Key;
311      /// \brief The value type of the map
312      typedef dim2::Point<int> Value;
313
314      /// \brief Constructor
315      ///
316      /// Constructor
317      IndexMap(const GridUGraph& _graph) : graph(_graph) {}
318
319      /// \brief The subscript operator
320      ///
321      /// The subscript operator.
322      Value operator[](Key key) const {
323        return dim2::Point<int>(graph.row(key), graph.col(key));
324      }
325
326    private:
327      const GridUGraph& graph;
328    };
329
330    /// \brief Map to get the row of the nodes.
331    ///
332    /// Map to get the row of the nodes.
333    class RowMap {
334    public:
335      /// \brief The key type of the map
336      typedef GridUGraph::Node Key;
337      /// \brief The value type of the map
338      typedef int Value;
339
340      /// \brief Constructor
341      ///
342      /// Constructor
343      RowMap(const GridUGraph& _graph) : graph(_graph) {}
344
345      /// \brief The subscript operator
346      ///
347      /// The subscript operator.
348      Value operator[](Key key) const {
349        return graph.row(key);
350      }
351
352    private:
353      const GridUGraph& graph;
354    };
355
356    /// \brief Map to get the column of the nodes.
357    ///
358    /// Map to get the column of the nodes.
359    class ColMap {
360    public:
361      /// \brief The key type of the map
362      typedef GridUGraph::Node Key;
363      /// \brief The value type of the map
364      typedef int Value;
365
366      /// \brief Constructor
367      ///
368      /// Constructor
369      ColMap(const GridUGraph& _graph) : graph(_graph) {}
370
371      /// \brief The subscript operator
372      ///
373      /// The subscript operator.
374      Value operator[](Key key) const {
375        return graph.col(key);
376      }
377
378    private:
379      const GridUGraph& graph;
380    };
381
382    /// \brief Constructor
383    ///
384    ///
385    GridUGraph(int n, int m) { construct(n, m); }
386
387    /// \brief Resize the graph
388    ///
389    void resize(int n, int m) {
390      Parent::getNotifier(Edge()).clear();
391      Parent::getNotifier(UEdge()).clear();
392      Parent::getNotifier(Node()).clear();
393      construct(n, m);
394      Parent::getNotifier(Node()).build();
395      Parent::getNotifier(UEdge()).build();
396      Parent::getNotifier(Edge()).build();
397    }
398   
399    /// \brief The node on the given position.
400    ///
401    /// Gives back the node on the given position.
402    Node operator()(int i, int j) const {
403      return Parent::operator()(i, j);
404    }
405
406    /// \brief Gives back the row index of the node.
407    ///
408    /// Gives back the row index of the node.
409    int row(Node n) const {
410      return Parent::row(n);
411    }
412   
413    /// \brief Gives back the coloumn index of the node.
414    ///
415    /// Gives back the coloumn index of the node.
416    int col(Node n) const {
417      return Parent::col(n);
418    }
419
420    /// \brief Gives back the width of the graph.
421    ///
422    /// Gives back the width of the graph.
423    int width() const {
424      return Parent::width();
425    }
426
427    /// \brief Gives back the height of the graph.
428    ///
429    /// Gives back the height of the graph.
430    int height() const {
431      return Parent::height();
432    }
433
434    /// \brief Gives back the edge goes down from the node.
435    ///
436    /// Gives back the edge goes down from the node. If there is not
437    /// outgoing edge then it gives back INVALID.
438    Edge down(Node n) const {
439      UEdge ue = _down(n);
440      return ue != INVALID ? direct(ue, true) : INVALID;
441    }
442   
443    /// \brief Gives back the edge goes up from the node.
444    ///
445    /// Gives back the edge goes up from the node. If there is not
446    /// outgoing edge then it gives back INVALID.
447    Edge up(Node n) const {
448      UEdge ue = _up(n);
449      return ue != INVALID ? direct(ue, false) : INVALID;
450    }
451
452    /// \brief Gives back the edge goes right from the node.
453    ///
454    /// Gives back the edge goes right from the node. If there is not
455    /// outgoing edge then it gives back INVALID.
456    Edge right(Node n) const {
457      UEdge ue = _right(n);
458      return ue != INVALID ? direct(ue, true) : INVALID;
459    }
460
461    /// \brief Gives back the edge goes left from the node.
462    ///
463    /// Gives back the edge goes left from the node. If there is not
464    /// outgoing edge then it gives back INVALID.
465    Edge left(Node n) const {
466      UEdge ue = _left(n);
467      return ue != INVALID ? direct(ue, false) : INVALID;
468    }
469   
470  };
471
472  /// \brief Index map of the grid graph
473  ///
474  /// Just returns an IndexMap for the grid graph.
475  GridUGraph::IndexMap indexMap(const GridUGraph& graph) {
476    return GridUGraph::IndexMap(graph);
477  }
478
479  /// \brief Row map of the grid graph
480  ///
481  /// Just returns a RowMap for the grid graph.
482  GridUGraph::RowMap rowMap(const GridUGraph& graph) {
483    return GridUGraph::RowMap(graph);
484  }
485
486  /// \brief Column map of the grid graph
487  ///
488  /// Just returns a ColMap for the grid graph.
489  GridUGraph::ColMap colMap(const GridUGraph& graph) {
490    return GridUGraph::ColMap(graph);
491  }
492}
493#endif
Note: See TracBrowser for help on using the repository browser.