COIN-OR::LEMON - Graph Library

Changeset 1680:4f8b9cee576b in lemon-0.x for lemon/grid_graph.h


Ignore:
Timestamp:
09/12/05 11:19:52 (14 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2199
Message:

Fixing and improving GridGraph?

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/grid_graph.h

    r1623 r1680  
    4848    ///
    4949    /// Creates a grid graph with the given size.
    50     void construct(int height, int width) {
     50    void construct(int width, int height) {
    5151      _height = height; _width = width;
    5252      _nodeNum = height * width; _edgeNum = 2 * _nodeNum - width - height;
    5353      _edgeLimit = _nodeNum - width;
    5454    }
     55
     56    /// \brief Gives back the edge goes down from the node.
     57    ///
     58    /// Gives back the edge goes down from the node. If there is not
     59    /// outgoing edge then it gives back INVALID.
     60    Edge _down(Node n) const {
     61      if (n.id < _nodeNum - _width) {
     62        return Edge(n.id);
     63      } else {
     64        return INVALID;
     65      }
     66    }
     67
     68    /// \brief Gives back the edge comes from up into the node.
     69    ///
     70    /// Gives back the edge comes from up into the node. If there is not
     71    /// incoming edge then it gives back INVALID.
     72    Edge _up(Node n) const {
     73      if (n.id >= _width) {
     74        return Edge(n.id - _width);
     75      } else {
     76        return INVALID;
     77      }
     78    }
     79
     80    /// \brief Gives back the edge goes right from the node.
     81    ///
     82    /// Gives back the edge goes right from the node. If there is not
     83    /// outgoing edge then it gives back INVALID.
     84    Edge _right(Node n) const {
     85      if (n.id % _width < _width - 1) {
     86        return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1);
     87      } else {
     88        return INVALID;
     89      }
     90    }
     91
     92    /// \brief Gives back the edge comes from left into the node.
     93    ///
     94    /// Gives back the edge comes left up into the node. If there is not
     95    /// incoming edge then it gives back INVALID.
     96    Edge _left(Node n) const {
     97      if (n.id % _width > 0) {
     98        return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1) - 1;
     99      } else {
     100        return INVALID;
     101      }
     102    }
     103
    55104
    56105  public:
     
    60109    /// Gives back the node on the given position.
    61110    Node operator()(int i, int j) const {
    62       return Node(i * _width + j);
     111      return Node(i + j * _width);
    63112    }
    64113
     
    73122    ///
    74123    /// Gives back the coloumn index of the node.
    75     int col(Node node) const {
     124    int col(Node n) const {
    76125      return n.id % _width;   
    77126    }
     
    278327
    279328
    280   typedef UndirGraphExtender<GridGraphBase>
    281   UndirGridGraphBase;
    282   typedef AlterableUndirGraphExtender<UndirGridGraphBase>
    283   AlterableGridGraphBase;
    284   typedef IterableUndirGraphExtender<AlterableGridGraphBase>
    285   IterableGridGraphBase;
    286   typedef MappableUndirGraphExtender<IterableGridGraphBase>
    287   MappableGridGraphBase;
     329  typedef MappableUndirGraphExtender<
     330    IterableUndirGraphExtender<
     331    AlterableUndirGraphExtender<
     332    UndirGraphExtender<GridGraphBase> > > > ExtendedGridGraphBase;
    288333
    289334  /// \ingroup graphs
     
    312357  ///
    313358  /// \author Balazs Dezso
    314   class GridGraph : public MappableGridGraphBase {
     359  class GridGraph : public ExtendedGridGraphBase {
    315360  public:
    316361   
    317     GridGraph(int m, int n) { construct(m, n); }
     362    GridGraph(int n, int m) { construct(n, m); }
     363   
     364    /// \brief Gives back the edge goes down from the node.
     365    ///
     366    /// Gives back the edge goes down from the node. If there is not
     367    /// outgoing edge then it gives back INVALID.
     368    Edge down(Node n) const {
     369      UndirEdge ue = _down(n);
     370      return ue != INVALID ? direct(ue, true) : INVALID;
     371    }
     372   
     373    /// \brief Gives back the edge goes up from the node.
     374    ///
     375    /// Gives back the edge goes up from the node. If there is not
     376    /// outgoing edge then it gives back INVALID.
     377    Edge up(Node n) const {
     378      UndirEdge ue = _up(n);
     379      return ue != INVALID ? direct(ue, false) : INVALID;
     380    }
     381
     382    /// \brief Gives back the edge goes right from the node.
     383    ///
     384    /// Gives back the edge goes right from the node. If there is not
     385    /// outgoing edge then it gives back INVALID.
     386    Edge right(Node n) const {
     387      UndirEdge ue = _right(n);
     388      return ue != INVALID ? direct(ue, true) : INVALID;
     389    }
     390
     391    /// \brief Gives back the edge goes left from the node.
     392    ///
     393    /// Gives back the edge goes left from the node. If there is not
     394    /// outgoing edge then it gives back INVALID.
     395    Edge left(Node n) const {
     396      UndirEdge ue = _left(n);
     397      return ue != INVALID ? direct(ue, false) : INVALID;
     398    }
     399   
    318400  };
    319401}
Note: See TracChangeset for help on using the changeset viewer.