COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/grid_graph.h @ 1623:c3defc3590aa

Last change on this file since 1623:c3defc3590aa was 1623:c3defc3590aa, checked in by Balazs Dezso, 14 years ago

Matrix graph renamed to grid graph
Some usefull function and documentation

File size: 8.4 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 height, int width) {
51      _height = height; _width = width;
52      _nodeNum = height * width; _edgeNum = 2 * _nodeNum - width - height;
53      _edgeLimit = _nodeNum - width;
54    }
55
56  public:
57   
58    /// \brief The node on the given position.
59    ///
60    /// Gives back the node on the given position.
61    Node operator()(int i, int j) const {
62      return Node(i * _width + j);
63    }
64
65    /// \brief Gives back the row index of the node.
66    ///
67    /// Gives back the row index of the node.
68    int row(Node n) const {
69      return n.id / _width;
70    }
71   
72    /// \brief Gives back the coloumn index of the node.
73    ///
74    /// Gives back the coloumn index of the node.
75    int col(Node node) const {
76      return n.id % _width;   
77    }
78
79    /// \brief Gives back the width of the graph.
80    ///
81    /// Gives back the width of the graph.
82    int width() const {
83      return _width;
84    }
85
86    /// \brief Gives back the height of the graph.
87    ///
88    /// Gives back the height of the graph.
89    int height() const {
90      return _height;
91    }
92
93    typedef True NodeNumTag;
94    typedef True EdgeNumTag;
95
96    ///Number of nodes.
97    int nodeNum() const { return _nodeNum; }
98    ///Number of edges.
99    int edgeNum() const { return _edgeNum; }
100
101    /// Maximum node ID.
102   
103    /// Maximum node ID.
104    ///\sa id(Node)
105    int maxId(Node = INVALID) const { return nodeNum() - 1; }
106    /// Maximum edge ID.
107   
108    /// Maximum edge ID.
109    ///\sa id(Edge)
110    int maxId(Edge = INVALID) const { return edgeNum() - 1; }
111
112    /// \brief Gives back the source node of an edge.
113    ///   
114    /// Gives back the source node of an edge.
115    Node source(Edge e) const {
116      if (e.id < _edgeLimit) {
117        return e.id;
118      } else {
119        return (e.id - _edgeLimit) % (_width - 1) +
120          (e.id - _edgeLimit) / (_width - 1) * _width;
121      }
122    }
123
124    /// \brief Gives back the target node of an edge.
125    ///   
126    /// Gives back the target node of an edge.
127    Node target(Edge e) const {
128      if (e.id < _edgeLimit) {
129        return e.id + _width;
130      } else {
131        return (e.id - _edgeLimit) % (_width - 1) +
132          (e.id - _edgeLimit) / (_width - 1) * _width + 1;
133      }
134    }
135
136    /// Node ID.
137   
138    /// The ID of a valid Node is a nonnegative integer not greater than
139    /// \ref maxNodeId(). The range of the ID's is not surely continuous
140    /// and the greatest node ID can be actually less then \ref maxNodeId().
141    ///
142    /// The ID of the \ref INVALID node is -1.
143    ///\return The ID of the node \c v.
144
145    static int id(Node v) { return v.id; }
146    /// Edge ID.
147   
148    /// The ID of a valid Edge is a nonnegative integer not greater than
149    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
150    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
151    ///
152    /// The ID of the \ref INVALID edge is -1.
153    ///\return The ID of the edge \c e.
154    static int id(Edge e) { return e.id; }
155
156    static Node fromId(int id, Node) { return Node(id);}
157   
158    static Edge fromId(int id, Edge) { return Edge(id);}
159
160    typedef True FindEdgeTag;
161
162    /// Finds an edge between two nodes.
163   
164    /// Finds an edge from node \c u to node \c v.
165    ///
166    /// If \c prev is \ref INVALID (this is the default value), then
167    /// It finds the first edge from \c u to \c v. Otherwise it looks for
168    /// the next edge from \c u to \c v after \c prev.
169    /// \return The found edge or INVALID if there is no such an edge.
170    Edge findEdge(Node u, Node v, Edge prev = INVALID) {
171      if (prev != INVALID) return INVALID;
172      if (v.id - u.id == _width) return Edge(u.id);
173      if (v.id - u.id == 1 && u.id % _width < _width - 1) {
174        return Edge(u.id / _width * (_width - 1) +
175                    u.id % _width + _edgeLimit);
176      }
177      return INVALID;
178    }
179   
180     
181    class Node {
182      friend class GridGraphBase;
183
184    protected:
185      int id;
186      Node(int _id) { id = _id;}
187    public:
188      Node() {}
189      Node (Invalid) { id = -1; }
190      bool operator==(const Node node) const {return id == node.id;}
191      bool operator!=(const Node node) const {return id != node.id;}
192      bool operator<(const Node node) const {return id < node.id;}
193    };
194   
195
196
197    class Edge {
198      friend class GridGraphBase;
199     
200    protected:
201      int id;
202
203      Edge(int _id) : id(_id) {}
204
205    public:
206      Edge() { }
207      Edge (Invalid) { id = -1; }
208      bool operator==(const Edge edge) const {return id == edge.id;}
209      bool operator!=(const Edge edge) const {return id != edge.id;}
210      bool operator<(const Edge edge) const {return id < edge.id;}
211    };
212
213    void first(Node& node) const {
214      node.id = nodeNum() - 1;
215    }
216
217    static void next(Node& node) {
218      --node.id;
219    }
220
221    void first(Edge& edge) const {
222      edge.id = edgeNum() - 1;
223    }
224
225    static void next(Edge& edge) {
226      --edge.id;
227    }
228
229    void firstOut(Edge& edge, const Node& node) const {
230      if (node.id < _nodeNum - _width) {
231        edge.id = node.id;
232      } else if (node.id % _width < _width - 1) {
233        edge.id = _edgeLimit + node.id % _width +
234          (node.id / _width) * (_width - 1);
235      } else {
236        edge.id = -1;
237      }
238    }
239
240    void nextOut(Edge& edge) const {
241      if (edge.id >= _edgeLimit) {
242        edge.id = -1;
243      } else if (edge.id % _width < _width - 1) {
244        edge.id = _edgeLimit + edge.id % _width +
245          (edge.id / _width) * (_width - 1);
246      } else {
247        edge.id = -1;
248      }
249    }
250
251    void firstIn(Edge& edge, const Node& node) const {
252      if (node.id >= _width) {
253        edge.id = node.id - _width;
254      } else if (node.id % _width > 0) {
255        edge.id = _edgeLimit + node.id % _width +
256          (node.id / _width) * (_width - 1) - 1;
257      } else {
258        edge.id = -1;
259      }
260    }
261   
262    void nextIn(Edge& edge) const {
263      if (edge.id >= _edgeLimit) {
264        edge.id = -1;
265      } else if (edge.id % _width > 0) {
266        edge.id = _edgeLimit + edge.id % _width +
267          (edge.id / _width + 1) * (_width - 1) - 1;
268      } else {
269        edge.id = -1;
270      }
271    }
272
273  private:
274    int _width, _height;
275    int _nodeNum, _edgeNum;
276    int _edgeLimit;
277  };
278
279
280  typedef UndirGraphExtender<GridGraphBase>
281  UndirGridGraphBase;
282  typedef AlterableUndirGraphExtender<UndirGridGraphBase>
283  AlterableGridGraphBase;
284  typedef IterableUndirGraphExtender<AlterableGridGraphBase>
285  IterableGridGraphBase;
286  typedef MappableUndirGraphExtender<IterableGridGraphBase>
287  MappableGridGraphBase;
288
289  /// \ingroup graphs
290  ///
291  /// \brief Grid graph class
292  ///
293  /// This class implements a special graph type. The nodes of the
294  /// graph can be indiced by two integer \c (i,j) value where \c i
295  /// is in the \c [0,height) range and j is in the [0, width) range.
296  /// Two nodes are connected in the graph if the indices differ only
297  /// on one position and only one is the difference.
298  ///
299  /// The graph can be indiced in the following way:
300  /// \code
301  /// GridGraph graph(h, w);
302  /// GridGraph::NodeMap<int> val(graph);
303  /// for (int i = 0; i < graph.height(); ++i) {
304  ///   for (int j = 0; j < graph.width(); ++j) {
305  ///     val[graph(i, j)] = i + j;
306  ///   }
307  /// }
308  /// \endcode
309  ///
310  /// The graph type is fully conform to the \ref concept::UndirGraph
311  /// "Undirected Graph" concept.
312  ///
313  /// \author Balazs Dezso
314  class GridGraph : public MappableGridGraphBase {
315  public:
316   
317    GridGraph(int m, int n) { construct(m, n); }
318  };
319}
320#endif
Note: See TracBrowser for help on using the repository browser.