COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/grid_graph.h @ 1956:a055123339d5

Last change on this file since 1956:a055123339d5 was 1956:a055123339d5, checked in by Alpar Juttner, 14 years ago

Unified copyright notices

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