COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/grid_graph.h @ 1882:2c3f6c7e01b4

Last change on this file since 1882:2c3f6c7e01b4 was 1875:98698b69a902, checked in by Alpar Juttner, 18 years ago

Happy new year to LEMON

File size: 13.6 KB
Line 
1/* -*- C++ -*-
2 * lemon/grid_graph.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
16
17#ifndef GRID_GRAPH_H
18#define GRID_GRAPH_H
19
20#include <iostream>
21#include <lemon/invalid.h>
22#include <lemon/utility.h>
23
24#include <lemon/bits/iterable_graph_extender.h>
25#include <lemon/bits/alteration_notifier.h>
26#include <lemon/bits/static_map.h>
27#include <lemon/bits/graph_extender.h>
28
29#include <lemon/xy.h>
30
31///\ingroup graphs
32///\file
33///\brief GridGraph class.
34
35namespace lemon {
36
37  /// \brief Base graph for GridGraph.
38  ///
39  /// Base graph for grid graph. It describes some member functions
40  /// which can be used in the GridGraph.
41  ///
42  /// \warning Always use the GridGraph instead of this.
43  /// \see GridGraph
44  class GridGraphBase {
45
46  public:
47
48    typedef GridGraphBase Graph;
49
50    class Node;
51    class Edge;
52
53  public:
54
55    GridGraphBase() {}
56
57  protected:
58
59    /// \brief Creates a grid graph with the given size.
60    ///
61    /// Creates a grid graph with the given size.
62    void construct(int width, int height) {
63      _height = height; _width = width;
64      _nodeNum = height * width; _edgeNum = 2 * _nodeNum - width - height;
65      _edgeLimit = _nodeNum - width;
66    }
67
68    /// \brief Gives back the edge goes down from the node.
69    ///
70    /// Gives back the edge goes down from the node. If there is not
71    /// outgoing edge then it gives back INVALID.
72    Edge _down(Node n) const {
73      if (n.id < _nodeNum - _width) {
74        return Edge(n.id);
75      } else {
76        return INVALID;
77      }
78    }
79
80    /// \brief Gives back the edge comes from up into the node.
81    ///
82    /// Gives back the edge comes from up into the node. If there is not
83    /// incoming edge then it gives back INVALID.
84    Edge _up(Node n) const {
85      if (n.id >= _width) {
86        return Edge(n.id - _width);
87      } else {
88        return INVALID;
89      }
90    }
91
92    /// \brief Gives back the edge goes right from the node.
93    ///
94    /// Gives back the edge goes right from the node. If there is not
95    /// outgoing edge then it gives back INVALID.
96    Edge _right(Node n) const {
97      if (n.id % _width < _width - 1) {
98        return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1);
99      } else {
100        return INVALID;
101      }
102    }
103
104    /// \brief Gives back the edge comes from left into the node.
105    ///
106    /// Gives back the edge comes left up into the node. If there is not
107    /// incoming edge then it gives back INVALID.
108    Edge _left(Node n) const {
109      if (n.id % _width > 0) {
110        return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1) - 1;
111      } else {
112        return INVALID;
113      }
114    }
115
116
117  public:
118   
119    /// \brief The node on the given position.
120    ///
121    /// Gives back the node on the given position.
122    Node operator()(int i, int j) const {
123      return Node(i + j * _width);
124    }
125
126    /// \brief Gives back the row index of the node.
127    ///
128    /// Gives back the row index of the node.
129    int row(Node n) const {
130      return n.id / _width;
131    }
132   
133    /// \brief Gives back the coloumn index of the node.
134    ///
135    /// Gives back the coloumn index of the node.
136    int col(Node n) const {
137      return n.id % _width;   
138    }
139
140    /// \brief Gives back the width of the graph.
141    ///
142    /// Gives back the width of the graph.
143    int width() const {
144      return _width;
145    }
146
147    /// \brief Gives back the height of the graph.
148    ///
149    /// Gives back the height of the graph.
150    int height() const {
151      return _height;
152    }
153
154    typedef True NodeNumTag;
155    typedef True EdgeNumTag;
156
157    ///Number of nodes.
158    int nodeNum() const { return _nodeNum; }
159    ///Number of edges.
160    int edgeNum() const { return _edgeNum; }
161
162    /// Maximum node ID.
163   
164    /// Maximum node ID.
165    ///\sa id(Node)
166    int maxNodeId() const { return nodeNum() - 1; }
167    /// Maximum edge ID.
168   
169    /// Maximum edge ID.
170    ///\sa id(Edge)
171    int maxEdgeId() const { return edgeNum() - 1; }
172
173    /// \brief Gives back the source node of an edge.
174    ///   
175    /// Gives back the source node of an edge.
176    Node source(Edge e) const {
177      if (e.id < _edgeLimit) {
178        return e.id;
179      } else {
180        return (e.id - _edgeLimit) % (_width - 1) +
181          (e.id - _edgeLimit) / (_width - 1) * _width;
182      }
183    }
184
185    /// \brief Gives back the target node of an edge.
186    ///   
187    /// Gives back the target node of an edge.
188    Node target(Edge e) const {
189      if (e.id < _edgeLimit) {
190        return e.id + _width;
191      } else {
192        return (e.id - _edgeLimit) % (_width - 1) +
193          (e.id - _edgeLimit) / (_width - 1) * _width + 1;
194      }
195    }
196
197    /// Node ID.
198   
199    /// The ID of a valid Node is a nonnegative integer not greater than
200    /// \ref maxNodeId(). The range of the ID's is not surely continuous
201    /// and the greatest node ID can be actually less then \ref maxNodeId().
202    ///
203    /// The ID of the \ref INVALID node is -1.
204    ///\return The ID of the node \c v.
205
206    static int id(Node v) { return v.id; }
207    /// Edge ID.
208   
209    /// The ID of a valid Edge is a nonnegative integer not greater than
210    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
211    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
212    ///
213    /// The ID of the \ref INVALID edge is -1.
214    ///\return The ID of the edge \c e.
215    static int id(Edge e) { return e.id; }
216
217    static Node nodeFromId(int id) { return Node(id);}
218   
219    static Edge edgeFromId(int id) { return Edge(id);}
220
221    typedef True FindEdgeTag;
222
223    /// Finds an edge between two nodes.
224   
225    /// Finds an edge from node \c u to node \c v.
226    ///
227    /// If \c prev is \ref INVALID (this is the default value), then
228    /// It finds the first edge from \c u to \c v. Otherwise it looks for
229    /// the next edge from \c u to \c v after \c prev.
230    /// \return The found edge or INVALID if there is no such an edge.
231    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
232      if (prev != INVALID) return INVALID;
233      if (v.id - u.id == _width) return Edge(u.id);
234      if (v.id - u.id == 1 && u.id % _width < _width - 1) {
235        return Edge(u.id / _width * (_width - 1) +
236                    u.id % _width + _edgeLimit);
237      }
238      return INVALID;
239    }
240   
241     
242    class Node {
243      friend class GridGraphBase;
244
245    protected:
246      int id;
247      Node(int _id) { id = _id;}
248    public:
249      Node() {}
250      Node (Invalid) { id = -1; }
251      bool operator==(const Node node) const {return id == node.id;}
252      bool operator!=(const Node node) const {return id != node.id;}
253      bool operator<(const Node node) const {return id < node.id;}
254    };
255   
256
257
258    class Edge {
259      friend class GridGraphBase;
260     
261    protected:
262      int id;
263
264      Edge(int _id) : id(_id) {}
265
266    public:
267      Edge() { }
268      Edge (Invalid) { id = -1; }
269      bool operator==(const Edge edge) const {return id == edge.id;}
270      bool operator!=(const Edge edge) const {return id != edge.id;}
271      bool operator<(const Edge edge) const {return id < edge.id;}
272    };
273
274    void first(Node& node) const {
275      node.id = nodeNum() - 1;
276    }
277
278    static void next(Node& node) {
279      --node.id;
280    }
281
282    void first(Edge& edge) const {
283      edge.id = edgeNum() - 1;
284    }
285
286    static void next(Edge& edge) {
287      --edge.id;
288    }
289
290    void firstOut(Edge& edge, const Node& node) const {
291      if (node.id < _nodeNum - _width) {
292        edge.id = node.id;
293      } else if (node.id % _width < _width - 1) {
294        edge.id = _edgeLimit + node.id % _width +
295          (node.id / _width) * (_width - 1);
296      } else {
297        edge.id = -1;
298      }
299    }
300
301    void nextOut(Edge& edge) const {
302      if (edge.id >= _edgeLimit) {
303        edge.id = -1;
304      } else if (edge.id % _width < _width - 1) {
305        edge.id = _edgeLimit + edge.id % _width +
306          (edge.id / _width) * (_width - 1);
307      } else {
308        edge.id = -1;
309      }
310    }
311
312    void firstIn(Edge& edge, const Node& node) const {
313      if (node.id >= _width) {
314        edge.id = node.id - _width;
315      } else if (node.id % _width > 0) {
316        edge.id = _edgeLimit + node.id % _width +
317          (node.id / _width) * (_width - 1) - 1;
318      } else {
319        edge.id = -1;
320      }
321    }
322   
323    void nextIn(Edge& edge) const {
324      if (edge.id >= _edgeLimit) {
325        edge.id = -1;
326      } else if (edge.id % _width > 0) {
327        edge.id = _edgeLimit + edge.id % _width +
328          (edge.id / _width + 1) * (_width - 1) - 1;
329      } else {
330        edge.id = -1;
331      }
332    }
333
334  private:
335    int _width, _height;
336    int _nodeNum, _edgeNum;
337    int _edgeLimit;
338  };
339
340
341  typedef StaticMappableUndirGraphExtender<
342    IterableUndirGraphExtender<
343    AlterableUndirGraphExtender<
344    UndirGraphExtender<GridGraphBase> > > > ExtendedGridGraphBase;
345
346  /// \ingroup graphs
347  ///
348  /// \brief Grid graph class
349  ///
350  /// This class implements a special graph type. The nodes of the
351  /// graph can be indiced by two integer \c (i,j) value where \c i
352  /// is in the \c [0,width) range and j is in the [0, height) range.
353  /// Two nodes are connected in the graph if the indices differ only
354  /// on one position and only one is the difference.
355  ///
356  /// The graph can be indiced in the following way:
357  /// \code
358  /// GridGraph graph(w, h);
359  /// GridGraph::NodeMap<int> val(graph);
360  /// for (int i = 0; i < graph.width(); ++i) {
361  ///   for (int j = 0; j < graph.height(); ++j) {
362  ///     val[graph(i, j)] = i + j;
363  ///   }
364  /// }
365  /// \endcode
366  ///
367  /// The graph type is fully conform to the \ref concept::UndirGraph
368  /// "Undirected Graph" concept.
369  ///
370  /// \author Balazs Dezso
371  /// \see GridGraphBase
372  class GridGraph : public ExtendedGridGraphBase {
373  public:
374
375    /// \brief Map to get the indices of the nodes as xy<int>.
376    ///
377    /// Map to get the indices of the nodes as xy<int>.
378    class IndexMap {
379    public:
380      typedef True NeedCopy;
381      /// \brief The key type of the map
382      typedef GridGraph::Node Key;
383      /// \brief The value type of the map
384      typedef xy<int> Value;
385
386      /// \brief Constructor
387      ///
388      /// Constructor
389      IndexMap(const GridGraph& _graph) : graph(_graph) {}
390
391      /// \brief The subscript operator
392      ///
393      /// The subscript operator.
394      Value operator[](Key key) const {
395        return xy<int>(graph.row(key), graph.col(key));
396      }
397
398    private:
399      const GridGraph& graph;
400    };
401
402    /// \brief Map to get the row of the nodes.
403    ///
404    /// Map to get the row of the nodes.
405    class RowMap {
406    public:
407      typedef True NeedCopy;
408      /// \brief The key type of the map
409      typedef GridGraph::Node Key;
410      /// \brief The value type of the map
411      typedef int Value;
412
413      /// \brief Constructor
414      ///
415      /// Constructor
416      RowMap(const GridGraph& _graph) : graph(_graph) {}
417
418      /// \brief The subscript operator
419      ///
420      /// The subscript operator.
421      Value operator[](Key key) const {
422        return graph.row(key);
423      }
424
425    private:
426      const GridGraph& graph;
427    };
428
429    /// \brief Map to get the column of the nodes.
430    ///
431    /// Map to get the column of the nodes.
432    class ColMap {
433    public:
434      typedef True NeedCopy;
435      /// \brief The key type of the map
436      typedef GridGraph::Node Key;
437      /// \brief The value type of the map
438      typedef int Value;
439
440      /// \brief Constructor
441      ///
442      /// Constructor
443      ColMap(const GridGraph& _graph) : graph(_graph) {}
444
445      /// \brief The subscript operator
446      ///
447      /// The subscript operator.
448      Value operator[](Key key) const {
449        return graph.col(key);
450      }
451
452    private:
453      const GridGraph& graph;
454    };
455
456    /// \brief Constructor
457    ///
458    ///
459    GridGraph(int n, int m) { construct(n, m); }
460   
461    /// \brief Gives back the edge goes down from the node.
462    ///
463    /// Gives back the edge goes down from the node. If there is not
464    /// outgoing edge then it gives back INVALID.
465    Edge down(Node n) const {
466      UndirEdge ue = _down(n);
467      return ue != INVALID ? direct(ue, true) : INVALID;
468    }
469   
470    /// \brief Gives back the edge goes up from the node.
471    ///
472    /// Gives back the edge goes up from the node. If there is not
473    /// outgoing edge then it gives back INVALID.
474    Edge up(Node n) const {
475      UndirEdge ue = _up(n);
476      return ue != INVALID ? direct(ue, false) : INVALID;
477    }
478
479    /// \brief Gives back the edge goes right from the node.
480    ///
481    /// Gives back the edge goes right from the node. If there is not
482    /// outgoing edge then it gives back INVALID.
483    Edge right(Node n) const {
484      UndirEdge ue = _right(n);
485      return ue != INVALID ? direct(ue, true) : INVALID;
486    }
487
488    /// \brief Gives back the edge goes left from the node.
489    ///
490    /// Gives back the edge goes left from the node. If there is not
491    /// outgoing edge then it gives back INVALID.
492    Edge left(Node n) const {
493      UndirEdge ue = _left(n);
494      return ue != INVALID ? direct(ue, false) : INVALID;
495    }
496   
497  };
498
499  /// \brief Index map of the grid graph
500  ///
501  /// Just returns an IndexMap for the grid graph.
502  GridGraph::IndexMap indexMap(const GridGraph& graph) {
503    return GridGraph::IndexMap(graph);
504  }
505
506  /// \brief Row map of the grid graph
507  ///
508  /// Just returns a RowMap for the grid graph.
509  GridGraph::RowMap rowMap(const GridGraph& graph) {
510    return GridGraph::RowMap(graph);
511  }
512
513  /// \brief Column map of the grid graph
514  ///
515  /// Just returns a ColMap for the grid graph.
516  GridGraph::ColMap colMap(const GridGraph& graph) {
517    return GridGraph::ColMap(graph);
518  }
519}
520#endif
Note: See TracBrowser for help on using the repository browser.