COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/grid_ugraph.h @ 1988:875fe3f689e0

Last change on this file since 1988:875fe3f689e0 was 1986:9b56cca61e2e, checked in by Balazs Dezso, 18 years ago

An additional simplier interface for static size graphs.
Node operator()(int) for getting node by index
int index(Node node) for getting index by node

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