grid_graph.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  *
00003  * This file is a part of LEMON, a generic C++ optimization library
00004  *
00005  * Copyright (C) 2003-2006
00006  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00007  * (Egervary Research Group on Combinatorial Optimization, EGRES).
00008  *
00009  * Permission to use, modify and distribute this software is granted
00010  * provided that this copyright notice appears in all copies. For
00011  * precise terms see the accompanying LICENSE file.
00012  *
00013  * This software is provided "AS IS" with no warranty of any kind,
00014  * express or implied, and with no claim as to its suitability for any
00015  * purpose.
00016  *
00017  */
00018 
00019 #ifndef GRID_GRAPH_H
00020 #define GRID_GRAPH_H
00021 
00022 #include <iostream>
00023 #include <lemon/invalid.h>
00024 #include <lemon/utility.h>
00025 
00026 #include <lemon/bits/iterable_graph_extender.h>
00027 #include <lemon/bits/alteration_notifier.h>
00028 #include <lemon/bits/static_map.h>
00029 #include <lemon/bits/graph_extender.h>
00030 
00031 #include <lemon/xy.h>
00032 
00036 
00037 namespace lemon {
00038 
00046   class GridGraphBase {
00047 
00048   public:
00049 
00050     typedef GridGraphBase Graph;
00051 
00052     class Node;
00053     class Edge;
00054 
00055   public:
00056 
00057     GridGraphBase() {}
00058 
00059   protected:
00060 
00064     void construct(int width, int height) {
00065       _height = height; _width = width;
00066       _nodeNum = height * width; _edgeNum = 2 * _nodeNum - width - height;
00067       _edgeLimit = _nodeNum - width;
00068     }
00069 
00074     Edge _down(Node n) const {
00075       if (n.id < _nodeNum - _width) {
00076         return Edge(n.id);
00077       } else {
00078         return INVALID;
00079       }
00080     }
00081 
00086     Edge _up(Node n) const {
00087       if (n.id >= _width) {
00088         return Edge(n.id - _width);
00089       } else {
00090         return INVALID;
00091       }
00092     }
00093 
00098     Edge _right(Node n) const {
00099       if (n.id % _width < _width - 1) {
00100         return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1);
00101       } else {
00102         return INVALID;
00103       }
00104     }
00105 
00110     Edge _left(Node n) const {
00111       if (n.id % _width > 0) {
00112         return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1) - 1;
00113       } else {
00114         return INVALID;
00115       }
00116     }
00117 
00118 
00119   public:
00120     
00124     Node operator()(int i, int j) const {
00125       return Node(i + j * _width);
00126     }
00127 
00131     int row(Node n) const {
00132       return n.id / _width;
00133     }
00134     
00138     int col(Node n) const {
00139       return n.id % _width;    
00140     }
00141 
00145     int width() const {
00146       return _width;
00147     }
00148 
00152     int height() const {
00153       return _height;
00154     }
00155 
00156     typedef True NodeNumTag;
00157     typedef True EdgeNumTag;
00158 
00160     int nodeNum() const { return _nodeNum; }
00162     int edgeNum() const { return _edgeNum; }
00163 
00165     
00168     int maxNodeId() const { return nodeNum() - 1; }
00170     
00173     int maxEdgeId() const { return edgeNum() - 1; }
00174 
00178     Node source(Edge e) const {
00179       if (e.id < _edgeLimit) {
00180         return e.id;
00181       } else {
00182         return (e.id - _edgeLimit) % (_width - 1) +
00183           (e.id - _edgeLimit) / (_width - 1) * _width;
00184       }
00185     }
00186 
00190     Node target(Edge e) const {
00191       if (e.id < _edgeLimit) {
00192         return e.id + _width;
00193       } else {
00194         return (e.id - _edgeLimit) % (_width - 1) +
00195           (e.id - _edgeLimit) / (_width - 1) * _width + 1;
00196       }
00197     }
00198 
00200     
00207 
00208     static int id(Node v) { return v.id; }
00210     
00217     static int id(Edge e) { return e.id; }
00218 
00219     static Node nodeFromId(int id) { return Node(id);}
00220     
00221     static Edge edgeFromId(int id) { return Edge(id);}
00222 
00223     typedef True FindEdgeTag;
00224 
00226     
00233     Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
00234       if (prev != INVALID) return INVALID;
00235       if (v.id - u.id == _width) return Edge(u.id);
00236       if (v.id - u.id == 1 && u.id % _width < _width - 1) {
00237         return Edge(u.id / _width * (_width - 1) +
00238                     u.id % _width + _edgeLimit);
00239       }
00240       return INVALID;
00241     }
00242     
00243       
00244     class Node {
00245       friend class GridGraphBase;
00246 
00247     protected:
00248       int id;
00249       Node(int _id) { id = _id;}
00250     public:
00251       Node() {}
00252       Node (Invalid) { id = -1; }
00253       bool operator==(const Node node) const {return id == node.id;}
00254       bool operator!=(const Node node) const {return id != node.id;}
00255       bool operator<(const Node node) const {return id < node.id;}
00256     };
00257     
00258 
00259 
00260     class Edge {
00261       friend class GridGraphBase;
00262       
00263     protected:
00264       int id; 
00265 
00266       Edge(int _id) : id(_id) {}
00267 
00268     public:
00269       Edge() { }
00270       Edge (Invalid) { id = -1; }
00271       bool operator==(const Edge edge) const {return id == edge.id;}
00272       bool operator!=(const Edge edge) const {return id != edge.id;}
00273       bool operator<(const Edge edge) const {return id < edge.id;}
00274     };
00275 
00276     void first(Node& node) const {
00277       node.id = nodeNum() - 1;
00278     }
00279 
00280     static void next(Node& node) {
00281       --node.id;
00282     }
00283 
00284     void first(Edge& edge) const {
00285       edge.id = edgeNum() - 1;
00286     }
00287 
00288     static void next(Edge& edge) {
00289       --edge.id;
00290     }
00291 
00292     void firstOut(Edge& edge, const Node& node) const {
00293       if (node.id < _nodeNum - _width) {
00294         edge.id = node.id;
00295       } else if (node.id % _width < _width - 1) {
00296         edge.id = _edgeLimit + node.id % _width +
00297           (node.id / _width) * (_width - 1);
00298       } else {
00299         edge.id = -1;
00300       }
00301     }
00302 
00303     void nextOut(Edge& edge) const {
00304       if (edge.id >= _edgeLimit) {
00305         edge.id = -1;
00306       } else if (edge.id % _width < _width - 1) {
00307         edge.id = _edgeLimit + edge.id % _width +
00308           (edge.id / _width) * (_width - 1);
00309       } else {
00310         edge.id = -1;
00311       }
00312     }
00313 
00314     void firstIn(Edge& edge, const Node& node) const {
00315       if (node.id >= _width) {
00316         edge.id = node.id - _width;
00317       } else if (node.id % _width > 0) {
00318         edge.id = _edgeLimit + node.id % _width +
00319           (node.id / _width) * (_width - 1) - 1;
00320       } else {
00321         edge.id = -1;
00322       }
00323     }
00324     
00325     void nextIn(Edge& edge) const {
00326       if (edge.id >= _edgeLimit) {
00327         edge.id = -1;
00328       } else if (edge.id % _width > 0) {
00329         edge.id = _edgeLimit + edge.id % _width +
00330           (edge.id / _width + 1) * (_width - 1) - 1;
00331       } else {
00332         edge.id = -1;
00333       }
00334     }
00335 
00336   private:
00337     int _width, _height;
00338     int _nodeNum, _edgeNum;
00339     int _edgeLimit;
00340   };
00341 
00342 
00343   typedef StaticMappableUGraphExtender<
00344     IterableUGraphExtender<
00345     AlterableUGraphExtender<
00346     UGraphExtender<GridGraphBase> > > > ExtendedGridGraphBase;
00347 
00374   class GridGraph : public ExtendedGridGraphBase {
00375   public:
00376 
00380     class IndexMap {
00381     public:
00382       typedef True NeedCopy;
00384       typedef GridGraph::Node Key;
00386       typedef xy<int> Value;
00387 
00391       IndexMap(const GridGraph& _graph) : graph(_graph) {}
00392 
00396       Value operator[](Key key) const {
00397         return xy<int>(graph.row(key), graph.col(key));
00398       }
00399 
00400     private:
00401       const GridGraph& graph;
00402     };
00403 
00407     class RowMap {
00408     public:
00409       typedef True NeedCopy;
00411       typedef GridGraph::Node Key;
00413       typedef int Value;
00414 
00418       RowMap(const GridGraph& _graph) : graph(_graph) {}
00419 
00423       Value operator[](Key key) const {
00424         return graph.row(key);
00425       }
00426 
00427     private:
00428       const GridGraph& graph;
00429     };
00430 
00434     class ColMap {
00435     public:
00436       typedef True NeedCopy;
00438       typedef GridGraph::Node Key;
00440       typedef int Value;
00441 
00445       ColMap(const GridGraph& _graph) : graph(_graph) {}
00446 
00450       Value operator[](Key key) const {
00451         return graph.col(key);
00452       }
00453 
00454     private:
00455       const GridGraph& graph;
00456     };
00457 
00461     GridGraph(int n, int m) { construct(n, m); }
00462     
00467     Edge down(Node n) const {
00468       UEdge ue = _down(n);
00469       return ue != INVALID ? direct(ue, true) : INVALID;
00470     }
00471     
00476     Edge up(Node n) const {
00477       UEdge ue = _up(n);
00478       return ue != INVALID ? direct(ue, false) : INVALID;
00479     }
00480 
00485     Edge right(Node n) const {
00486       UEdge ue = _right(n);
00487       return ue != INVALID ? direct(ue, true) : INVALID;
00488     }
00489 
00494     Edge left(Node n) const {
00495       UEdge ue = _left(n);
00496       return ue != INVALID ? direct(ue, false) : INVALID;
00497     }
00498     
00499   };
00500 
00504   GridGraph::IndexMap indexMap(const GridGraph& graph) {
00505     return GridGraph::IndexMap(graph);
00506   }
00507 
00511   GridGraph::RowMap rowMap(const GridGraph& graph) {
00512     return GridGraph::RowMap(graph);
00513   }
00514 
00518   GridGraph::ColMap colMap(const GridGraph& graph) {
00519     return GridGraph::ColMap(graph);
00520   }
00521 }
00522 #endif

Generated on Fri Feb 3 18:37:43 2006 for LEMON by  doxygen 1.4.6