lemon-0.x: lemon/grid_ugraph.h@e4f8367beb41

     1 /* -*- C++ -*-

     2  *

     3  * This file is a part of LEMON, a generic C++ optimization library

     4  *

     5  * Copyright (C) 2003-2007

     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  */

    19 #ifndef GRID_UGRAPH_H

    20 #define GRID_UGRAPH_H

    22 #include <iostream>

    23 #include <lemon/bits/invalid.h>

    24 #include <lemon/bits/utility.h>

    26 #include <lemon/bits/base_extender.h>

    27 #include <lemon/bits/graph_extender.h>

    29 #include <lemon/dim2.h>

    31 ///\ingroup graphs

    32 ///\file

    33 ///\brief GridUGraph class.

    35 namespace lemon {

    37   class GridUGraphBase {

    39   public:

    41     typedef GridUGraphBase UGraph;

    43     class Node;

    44     class Edge;

    46   public:

    48     GridUGraphBase() {}

    50   protected:

    52     void construct(int w, int h) {

    53       _height = h; _width = w;

    54       _nodeNum = h * w; _edgeNum = 2 * _nodeNum - w - h;

    55       _edgeLimit = _nodeNum - w;

    56     }

    58     Edge _down(Node n) const {

    59       if (n.id < _nodeNum - _width) {

    60 	return Edge(n.id);

    61       } else {

    62 	return INVALID;

    63       }

    64     }

    66     Edge _up(Node n) const {

    67       if (n.id >= _width) {

    68 	return Edge(n.id - _width);

    69       } else {

    70 	return INVALID;

    71       }

    72     }

    74     Edge _right(Node n) const {

    75       if (n.id % _width < _width - 1) {

    76 	return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1);

    77       } else {

    78 	return INVALID;

    79       }

    80     }

    82     Edge _left(Node n) const {

    83       if (n.id % _width > 0) {

    84 	return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1) - 1;

    85       } else {

    86 	return INVALID;

    87       }

    88     }

    90   public:

    92     class IndexError : public RuntimeError {

    93     public:

    94       virtual const char* what() const throw() {

    95         return "lemon::GridUGraph::IndexError";

    96       }

    97     };

   100     Node operator()(int i, int j) const {

   101       LEMON_ASSERT(0 <= i && i < width() && 0 <= j  &&

   102                    j < height(), IndexError());

   103       return Node(i + j * _width);

   104     }

   106     int row(Node n) const {

   107       return n.id / _width;

   108     }

   110     int col(Node n) const {

   111       return n.id % _width;

   112     }

   114     int width() const {

   115       return _width;

   116     }

   118     int height() const {

   119       return _height;

   120     }

   122     typedef True NodeNumTag;

   123     typedef True EdgeNumTag;

   125     int nodeNum() const { return _nodeNum; }

   126     int edgeNum() const { return _edgeNum; }

   128     int maxNodeId() const { return nodeNum() - 1; }

   129     int maxEdgeId() const { return edgeNum() - 1; }

   131     Node source(Edge e) const {

   132       if (e.id < _edgeLimit) {

   133 	return e.id;

   134       } else {

   135 	return (e.id - _edgeLimit) % (_width - 1) +

   136 	  (e.id - _edgeLimit) / (_width - 1) * _width;

   137       }

   138     }

   140     Node target(Edge e) const {

   141       if (e.id < _edgeLimit) {

   142 	return e.id + _width;

   143       } else {

   144 	return (e.id - _edgeLimit) % (_width - 1) +

   145 	  (e.id - _edgeLimit) / (_width - 1) * _width + 1;

   146       }

   147     }

   149     static int id(Node v) { return v.id; }

   150     static int id(Edge e) { return e.id; }

   152     static Node nodeFromId(int id) { return Node(id);}

   154     static Edge edgeFromId(int id) { return Edge(id);}

   156     typedef True FindEdgeTag;

   158     Edge findEdge(Node u, Node v, Edge prev = INVALID) const {

   159       if (prev != INVALID) return INVALID;

   160       if (v.id - u.id == _width) return Edge(u.id);

   161       if (v.id - u.id == 1 && u.id % _width < _width - 1) {

   162 	return Edge(u.id / _width * (_width - 1) +

   163 		    u.id % _width + _edgeLimit);

   164       }

   165       return INVALID;

   166     }

   169     class Node {

   170       friend class GridUGraphBase;

   172     protected:

   173       int id;

   174       Node(int _id) { id = _id;}

   175     public:

   176       Node() {}

   177       Node (Invalid) { id = -1; }

   178       bool operator==(const Node node) const {return id == node.id;}

   179       bool operator!=(const Node node) const {return id != node.id;}

   180       bool operator<(const Node node) const {return id < node.id;}

   181     };

   185     class Edge {

   186       friend class GridUGraphBase;

   188     protected:

   189       int id;

   191       Edge(int _id) : id(_id) {}

   193     public:

   194       Edge() { }

   195       Edge (Invalid) { id = -1; }

   196       bool operator==(const Edge edge) const {return id == edge.id;}

   197       bool operator!=(const Edge edge) const {return id != edge.id;}

   198       bool operator<(const Edge edge) const {return id < edge.id;}

   199     };

   201     void first(Node& node) const {

   202       node.id = nodeNum() - 1;

   203     }

   205     static void next(Node& node) {

   206       --node.id;

   207     }

   209     void first(Edge& edge) const {

   210       edge.id = edgeNum() - 1;

   211     }

   213     static void next(Edge& edge) {

   214       --edge.id;

   215     }

   217     void firstOut(Edge& edge, const Node& node) const {

   218       if (node.id < _nodeNum - _width) {

   219 	edge.id = node.id;

   220       } else if (node.id % _width < _width - 1) {

   221 	edge.id = _edgeLimit + node.id % _width +

   222 	  (node.id / _width) * (_width - 1);

   223       } else {

   224 	edge.id = -1;

   225       }

   226     }

   228     void nextOut(Edge& edge) const {

   229       if (edge.id >= _edgeLimit) {

   230 	edge.id = -1;

   231       } else if (edge.id % _width < _width - 1) {

   232 	edge.id = _edgeLimit + edge.id % _width +

   233 	  (edge.id / _width) * (_width - 1);

   234       } else {

   235 	edge.id = -1;

   236       }

   237     }

   239     void firstIn(Edge& edge, const Node& node) const {

   240       if (node.id >= _width) {

   241 	edge.id = node.id - _width;

   242       } else if (node.id % _width > 0) {

   243 	edge.id = _edgeLimit + node.id % _width +

   244 	  (node.id / _width) * (_width - 1) - 1;

   245       } else {

   246 	edge.id = -1;

   247       }

   248     }

   250     void nextIn(Edge& edge) const {

   251       if (edge.id >= _edgeLimit) {

   252 	edge.id = -1;

   253       } else if (edge.id % _width > 0) {

   254 	edge.id = _edgeLimit + edge.id % _width +

   255 	  (edge.id / _width + 1) * (_width - 1) - 1;

   256       } else {

   257 	edge.id = -1;

   258       }

   259     }

   261   private:

   262     int _width, _height;

   263     int _nodeNum, _edgeNum;

   264     int _edgeLimit;

   265   };

   268   typedef UGraphExtender<UndirGraphExtender<GridUGraphBase> >

   269   ExtendedGridUGraphBase;

   271   /// \ingroup graphs

   272   ///

   273   /// \brief Grid graph class

   274   ///

   275   /// This class implements a special graph type. The nodes of the

   276   /// graph can be indiced by two integer \c (i,j) value where \c i

   277   /// is in the \c [0,width) range and j is in the [0, height) range.

   278   /// Two nodes are connected in the graph if the indices differ only

   279   /// on one position and only one is the difference.

   280   ///

   281   /// \image html grid_ugraph.png

   282   /// \image latex grid_ugraph.eps "Grid graph" width=\textwidth

   283   ///

   284   /// The graph can be indiced in the following way:

   285   ///\code

   286   /// GridUGraph graph(w, h);

   287   /// GridUGraph::NodeMap<int> val(graph);

   288   /// for (int i = 0; i < graph.width(); ++i) {

   289   ///   for (int j = 0; j < graph.height(); ++j) {

   290   ///     val[graph(i, j)] = i + j;

   291   ///   }

   292   /// }

   293   ///\endcode

   294   ///

   295   /// The graph type is fully conform to the \ref concepts::UGraph

   296   /// "Undirected Graph" concept,  and it also has an

   297   ///important extra feature that

   298   ///its maps are real \ref concepts::ReferenceMap "reference map"s.

   299   ///

   300   ///

   301   /// \author Balazs Dezso

   302   class GridUGraph : public ExtendedGridUGraphBase {

   303   public:

   305     typedef ExtendedGridUGraphBase Parent;

   307     /// \brief Map to get the indices of the nodes as dim2::Point<int>.

   308     ///

   309     /// Map to get the indices of the nodes as dim2::Point<int>.

   310     class IndexMap {

   311     public:

   312       /// \brief The key type of the map

   313       typedef GridUGraph::Node Key;

   314       /// \brief The value type of the map

   315       typedef dim2::Point<int> Value;

   317       /// \brief Constructor

   318       ///

   319       /// Constructor

   320       IndexMap(const GridUGraph& _graph) : graph(_graph) {}

   322       /// \brief The subscript operator

   323       ///

   324       /// The subscript operator.

   325       Value operator[](Key key) const {

   326 	return dim2::Point<int>(graph.row(key), graph.col(key));

   327       }

   329     private:

   330       const GridUGraph& graph;

   331     };

   333     /// \brief Map to get the row of the nodes.

   334     ///

   335     /// Map to get the row of the nodes.

   336     class RowMap {

   337     public:

   338       /// \brief The key type of the map

   339       typedef GridUGraph::Node Key;

   340       /// \brief The value type of the map

   341       typedef int Value;

   343       /// \brief Constructor

   344       ///

   345       /// Constructor

   346       RowMap(const GridUGraph& _graph) : graph(_graph) {}

   348       /// \brief The subscript operator

   349       ///

   350       /// The subscript operator.

   351       Value operator[](Key key) const {

   352 	return graph.row(key);

   353       }

   355     private:

   356       const GridUGraph& graph;

   357     };

   359     /// \brief Map to get the column of the nodes.

   360     ///

   361     /// Map to get the column of the nodes.

   362     class ColMap {

   363     public:

   364       /// \brief The key type of the map

   365       typedef GridUGraph::Node Key;

   366       /// \brief The value type of the map

   367       typedef int Value;

   369       /// \brief Constructor

   370       ///

   371       /// Constructor

   372       ColMap(const GridUGraph& _graph) : graph(_graph) {}

   374       /// \brief The subscript operator

   375       ///

   376       /// The subscript operator.

   377       Value operator[](Key key) const {

   378 	return graph.col(key);

   379       }

   381     private:

   382       const GridUGraph& graph;

   383     };

   385     /// \brief Constructor

   386     ///

   387     ///

   388     GridUGraph(int n, int m) { construct(n, m); }

   390     /// \brief Resize the graph

   391     ///

   392     void resize(int n, int m) {

   393       Parent::notifier(Edge()).clear();

   394       Parent::notifier(UEdge()).clear();

   395       Parent::notifier(Node()).clear();

   396       construct(n, m);

   397       Parent::notifier(Node()).build();

   398       Parent::notifier(UEdge()).build();

   399       Parent::notifier(Edge()).build();

   400     }

   402     /// \brief The node on the given position.

   403     ///

   404     /// Gives back the node on the given position.

   405     Node operator()(int i, int j) const {

   406       return Parent::operator()(i, j);

   407     }

   409     /// \brief Gives back the row index of the node.

   410     ///

   411     /// Gives back the row index of the node.

   412     int row(Node n) const {

   413       return Parent::row(n);

   414     }

   416     /// \brief Gives back the coloumn index of the node.

   417     ///

   418     /// Gives back the coloumn index of the node.

   419     int col(Node n) const {

   420       return Parent::col(n);

   421     }

   423     /// \brief Gives back the width of the graph.

   424     ///

   425     /// Gives back the width of the graph.

   426     int width() const {

   427       return Parent::width();

   428     }

   430     /// \brief Gives back the height of the graph.

   431     ///

   432     /// Gives back the height of the graph.

   433     int height() const {

   434       return Parent::height();

   435     }

   437     /// \brief Gives back the edge goes down from the node.

   438     ///

   439     /// Gives back the edge goes down from the node. If there is not

   440     /// outgoing edge then it gives back INVALID.

   441     Edge down(Node n) const {

   442       UEdge ue = _down(n);

   443       return ue != INVALID ? direct(ue, true) : INVALID;

   444     }

   446     /// \brief Gives back the edge goes up from the node.

   447     ///

   448     /// Gives back the edge goes up from the node. If there is not

   449     /// outgoing edge then it gives back INVALID.

   450     Edge up(Node n) const {

   451       UEdge ue = _up(n);

   452       return ue != INVALID ? direct(ue, false) : INVALID;

   453     }

   455     /// \brief Gives back the edge goes right from the node.

   456     ///

   457     /// Gives back the edge goes right from the node. If there is not

   458     /// outgoing edge then it gives back INVALID.

   459     Edge right(Node n) const {

   460       UEdge ue = _right(n);

   461       return ue != INVALID ? direct(ue, true) : INVALID;

   462     }

   464     /// \brief Gives back the edge goes left from the node.

   465     ///

   466     /// Gives back the edge goes left from the node. If there is not

   467     /// outgoing edge then it gives back INVALID.

   468     Edge left(Node n) const {

   469       UEdge ue = _left(n);

   470       return ue != INVALID ? direct(ue, false) : INVALID;

   471     }

   473   };

   475   /// \brief Index map of the grid graph

   476   ///

   477   /// Just returns an IndexMap for the grid graph.

   478   GridUGraph::IndexMap indexMap(const GridUGraph& graph) {

   479     return GridUGraph::IndexMap(graph);

   480   }

   482   /// \brief Row map of the grid graph

   483   ///

   484   /// Just returns a RowMap for the grid graph.

   485   GridUGraph::RowMap rowMap(const GridUGraph& graph) {

   486     return GridUGraph::RowMap(graph);

   487   }

   489   /// \brief Column map of the grid graph

   490   ///

   491   /// Just returns a ColMap for the grid graph.

   492   GridUGraph::ColMap colMap(const GridUGraph& graph) {

   493     return GridUGraph::ColMap(graph);

   494   }

   495 }

   496 #endif

author	ladanyi
	Sat, 13 Oct 2007 08:48:07 +0000
changeset 2495	e4f8367beb41
parent 2386	81b47fc5c444
child 2553	bfced05fa852
permissions	-rw-r--r--