COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/grid_graph.h @ 1680:4f8b9cee576b

Last change on this file since 1680:4f8b9cee576b was 1680:4f8b9cee576b, checked in by Balazs Dezso, 14 years ago

Fixing and improving GridGraph?

File size: 10.8 KB
Line 
1/* -*- C++ -*-
2 * lemon/grid_graph.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2005 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/default_map.h>
27
28#include <lemon/bits/undir_graph_extender.h>
29
30namespace lemon {
31
32  class GridGraphBase {
33
34  public:
35
36    typedef GridGraphBase Graph;
37
38    class Node;
39    class Edge;
40
41  public:
42
43    GridGraphBase() {}
44
45  protected:
46
47    /// \brief Creates a grid graph with the given size.
48    ///
49    /// Creates a grid graph with the given size.
50    void construct(int width, int height) {
51      _height = height; _width = width;
52      _nodeNum = height * width; _edgeNum = 2 * _nodeNum - width - height;
53      _edgeLimit = _nodeNum - width;
54    }
55
56    /// \brief Gives back the edge goes down from the node.
57    ///
58    /// Gives back the edge goes down from the node. If there is not
59    /// outgoing edge then it gives back INVALID.
60    Edge _down(Node n) const {
61      if (n.id < _nodeNum - _width) {
62        return Edge(n.id);
63      } else {
64        return INVALID;
65      }
66    }
67
68    /// \brief Gives back the edge comes from up into the node.
69    ///
70    /// Gives back the edge comes from up into the node. If there is not
71    /// incoming edge then it gives back INVALID.
72    Edge _up(Node n) const {
73      if (n.id >= _width) {
74        return Edge(n.id - _width);
75      } else {
76        return INVALID;
77      }
78    }
79
80    /// \brief Gives back the edge goes right from the node.
81    ///
82    /// Gives back the edge goes right from the node. If there is not
83    /// outgoing edge then it gives back INVALID.
84    Edge _right(Node n) const {
85      if (n.id % _width < _width - 1) {
86        return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1);
87      } else {
88        return INVALID;
89      }
90    }
91
92    /// \brief Gives back the edge comes from left into the node.
93    ///
94    /// Gives back the edge comes left up into the node. If there is not
95    /// incoming edge then it gives back INVALID.
96    Edge _left(Node n) const {
97      if (n.id % _width > 0) {
98        return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1) - 1;
99      } else {
100        return INVALID;
101      }
102    }
103
104
105  public:
106   
107    /// \brief The node on the given position.
108    ///
109    /// Gives back the node on the given position.
110    Node operator()(int i, int j) const {
111      return Node(i + j * _width);
112    }
113
114    /// \brief Gives back the row index of the node.
115    ///
116    /// Gives back the row index of the node.
117    int row(Node n) const {
118      return n.id / _width;
119    }
120   
121    /// \brief Gives back the coloumn index of the node.
122    ///
123    /// Gives back the coloumn index of the node.
124    int col(Node n) const {
125      return n.id % _width;   
126    }
127
128    /// \brief Gives back the width of the graph.
129    ///
130    /// Gives back the width of the graph.
131    int width() const {
132      return _width;
133    }
134
135    /// \brief Gives back the height of the graph.
136    ///
137    /// Gives back the height of the graph.
138    int height() const {
139      return _height;
140    }
141
142    typedef True NodeNumTag;
143    typedef True EdgeNumTag;
144
145    ///Number of nodes.
146    int nodeNum() const { return _nodeNum; }
147    ///Number of edges.
148    int edgeNum() const { return _edgeNum; }
149
150    /// Maximum node ID.
151   
152    /// Maximum node ID.
153    ///\sa id(Node)
154    int maxId(Node = INVALID) const { return nodeNum() - 1; }
155    /// Maximum edge ID.
156   
157    /// Maximum edge ID.
158    ///\sa id(Edge)
159    int maxId(Edge = INVALID) const { return edgeNum() - 1; }
160
161    /// \brief Gives back the source node of an edge.
162    ///   
163    /// Gives back the source node of an edge.
164    Node source(Edge e) const {
165      if (e.id < _edgeLimit) {
166        return e.id;
167      } else {
168        return (e.id - _edgeLimit) % (_width - 1) +
169          (e.id - _edgeLimit) / (_width - 1) * _width;
170      }
171    }
172
173    /// \brief Gives back the target node of an edge.
174    ///   
175    /// Gives back the target node of an edge.
176    Node target(Edge e) const {
177      if (e.id < _edgeLimit) {
178        return e.id + _width;
179      } else {
180        return (e.id - _edgeLimit) % (_width - 1) +
181          (e.id - _edgeLimit) / (_width - 1) * _width + 1;
182      }
183    }
184
185    /// Node ID.
186   
187    /// The ID of a valid Node is a nonnegative integer not greater than
188    /// \ref maxNodeId(). The range of the ID's is not surely continuous
189    /// and the greatest node ID can be actually less then \ref maxNodeId().
190    ///
191    /// The ID of the \ref INVALID node is -1.
192    ///\return The ID of the node \c v.
193
194    static int id(Node v) { return v.id; }
195    /// Edge ID.
196   
197    /// The ID of a valid Edge is a nonnegative integer not greater than
198    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
199    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
200    ///
201    /// The ID of the \ref INVALID edge is -1.
202    ///\return The ID of the edge \c e.
203    static int id(Edge e) { return e.id; }
204
205    static Node fromId(int id, Node) { return Node(id);}
206   
207    static Edge fromId(int id, Edge) { return Edge(id);}
208
209    typedef True FindEdgeTag;
210
211    /// Finds an edge between two nodes.
212   
213    /// Finds an edge from node \c u to node \c v.
214    ///
215    /// If \c prev is \ref INVALID (this is the default value), then
216    /// It finds the first edge from \c u to \c v. Otherwise it looks for
217    /// the next edge from \c u to \c v after \c prev.
218    /// \return The found edge or INVALID if there is no such an edge.
219    Edge findEdge(Node u, Node v, Edge prev = INVALID) {
220      if (prev != INVALID) return INVALID;
221      if (v.id - u.id == _width) return Edge(u.id);
222      if (v.id - u.id == 1 && u.id % _width < _width - 1) {
223        return Edge(u.id / _width * (_width - 1) +
224                    u.id % _width + _edgeLimit);
225      }
226      return INVALID;
227    }
228   
229     
230    class Node {
231      friend class GridGraphBase;
232
233    protected:
234      int id;
235      Node(int _id) { id = _id;}
236    public:
237      Node() {}
238      Node (Invalid) { id = -1; }
239      bool operator==(const Node node) const {return id == node.id;}
240      bool operator!=(const Node node) const {return id != node.id;}
241      bool operator<(const Node node) const {return id < node.id;}
242    };
243   
244
245
246    class Edge {
247      friend class GridGraphBase;
248     
249    protected:
250      int id;
251
252      Edge(int _id) : id(_id) {}
253
254    public:
255      Edge() { }
256      Edge (Invalid) { id = -1; }
257      bool operator==(const Edge edge) const {return id == edge.id;}
258      bool operator!=(const Edge edge) const {return id != edge.id;}
259      bool operator<(const Edge edge) const {return id < edge.id;}
260    };
261
262    void first(Node& node) const {
263      node.id = nodeNum() - 1;
264    }
265
266    static void next(Node& node) {
267      --node.id;
268    }
269
270    void first(Edge& edge) const {
271      edge.id = edgeNum() - 1;
272    }
273
274    static void next(Edge& edge) {
275      --edge.id;
276    }
277
278    void firstOut(Edge& edge, const Node& node) const {
279      if (node.id < _nodeNum - _width) {
280        edge.id = node.id;
281      } else if (node.id % _width < _width - 1) {
282        edge.id = _edgeLimit + node.id % _width +
283          (node.id / _width) * (_width - 1);
284      } else {
285        edge.id = -1;
286      }
287    }
288
289    void nextOut(Edge& edge) const {
290      if (edge.id >= _edgeLimit) {
291        edge.id = -1;
292      } else if (edge.id % _width < _width - 1) {
293        edge.id = _edgeLimit + edge.id % _width +
294          (edge.id / _width) * (_width - 1);
295      } else {
296        edge.id = -1;
297      }
298    }
299
300    void firstIn(Edge& edge, const Node& node) const {
301      if (node.id >= _width) {
302        edge.id = node.id - _width;
303      } else if (node.id % _width > 0) {
304        edge.id = _edgeLimit + node.id % _width +
305          (node.id / _width) * (_width - 1) - 1;
306      } else {
307        edge.id = -1;
308      }
309    }
310   
311    void nextIn(Edge& edge) const {
312      if (edge.id >= _edgeLimit) {
313        edge.id = -1;
314      } else if (edge.id % _width > 0) {
315        edge.id = _edgeLimit + edge.id % _width +
316          (edge.id / _width + 1) * (_width - 1) - 1;
317      } else {
318        edge.id = -1;
319      }
320    }
321
322  private:
323    int _width, _height;
324    int _nodeNum, _edgeNum;
325    int _edgeLimit;
326  };
327
328
329  typedef MappableUndirGraphExtender<
330    IterableUndirGraphExtender<
331    AlterableUndirGraphExtender<
332    UndirGraphExtender<GridGraphBase> > > > ExtendedGridGraphBase;
333
334  /// \ingroup graphs
335  ///
336  /// \brief Grid graph class
337  ///
338  /// This class implements a special graph type. The nodes of the
339  /// graph can be indiced by two integer \c (i,j) value where \c i
340  /// is in the \c [0,height) range and j is in the [0, width) range.
341  /// Two nodes are connected in the graph if the indices differ only
342  /// on one position and only one is the difference.
343  ///
344  /// The graph can be indiced in the following way:
345  /// \code
346  /// GridGraph graph(h, w);
347  /// GridGraph::NodeMap<int> val(graph);
348  /// for (int i = 0; i < graph.height(); ++i) {
349  ///   for (int j = 0; j < graph.width(); ++j) {
350  ///     val[graph(i, j)] = i + j;
351  ///   }
352  /// }
353  /// \endcode
354  ///
355  /// The graph type is fully conform to the \ref concept::UndirGraph
356  /// "Undirected Graph" concept.
357  ///
358  /// \author Balazs Dezso
359  class GridGraph : public ExtendedGridGraphBase {
360  public:
361   
362    GridGraph(int n, int m) { construct(n, m); }
363   
364    /// \brief Gives back the edge goes down from the node.
365    ///
366    /// Gives back the edge goes down from the node. If there is not
367    /// outgoing edge then it gives back INVALID.
368    Edge down(Node n) const {
369      UndirEdge ue = _down(n);
370      return ue != INVALID ? direct(ue, true) : INVALID;
371    }
372   
373    /// \brief Gives back the edge goes up from the node.
374    ///
375    /// Gives back the edge goes up from the node. If there is not
376    /// outgoing edge then it gives back INVALID.
377    Edge up(Node n) const {
378      UndirEdge ue = _up(n);
379      return ue != INVALID ? direct(ue, false) : INVALID;
380    }
381
382    /// \brief Gives back the edge goes right from the node.
383    ///
384    /// Gives back the edge goes right from the node. If there is not
385    /// outgoing edge then it gives back INVALID.
386    Edge right(Node n) const {
387      UndirEdge ue = _right(n);
388      return ue != INVALID ? direct(ue, true) : INVALID;
389    }
390
391    /// \brief Gives back the edge goes left from the node.
392    ///
393    /// Gives back the edge goes left from the node. If there is not
394    /// outgoing edge then it gives back INVALID.
395    Edge left(Node n) const {
396      UndirEdge ue = _left(n);
397      return ue != INVALID ? direct(ue, false) : INVALID;
398    }
399   
400  };
401}
402#endif
Note: See TracBrowser for help on using the repository browser.