COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/grid_ugraph.h @ 1980:a954b780e3ab

Last change on this file since 1980:a954b780e3ab was 1979:c2992fd74dad, checked in by Balazs Dezso, 18 years ago

Mergeing extendermerge branch
Changes:

the extender system
resize for static size graph
UGraphExtender => UndirectGraphExtender?

UGraphExtenders with changed meaning

Some UGraphExtender /SubUGraphExtenders, DirectUGraphExtender/
GridGraph? => GridUGraph
radix sort to ansi compatible

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