COIN-OR::LEMON - Graph Library

Changeset 1680:4f8b9cee576b in lemon-0.x


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?

Files:
1 added
3 edited

Legend:

Unmodified
Added
Removed
  • demo/Makefile.am

    r1678 r1680  
    1515        sub_graph_adaptor_demo \
    1616        descriptor_map_demo \
    17         coloring
     17        coloring \
     18        grid_graph_demo
    1819
    1920if HAVE_GLPK
     
    3839graph_to_eps_demo_SOURCES = graph_to_eps_demo.cc
    3940
     41grid_graph_demo_SOURCES = grid_graph_demo.cc
     42
    4043graph_orientation_SOURCES = graph_orientation.cc
    4144
  • 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}
  • test/undir_graph_test.cc

    r1568 r1680  
    66#include <lemon/smart_graph.h>
    77#include <lemon/full_graph.h>
     8#include <lemon/grid_graph.h>
    89
    910#include <lemon/graph_utils.h>
     
    4445
    4546  checkConcept<UndirGraph, UndirGraph>();
     47
     48  checkConcept<UndirGraph, GridGraph>();
    4649}
    4750
    4851template <typename Graph>
    4952void check_item_counts(Graph &g, int n, int e) {
    50   check(countNodes(g)==n, "Wrong node number.");
    51   check(countEdges(g)==2*e, "Wrong edge number.");
     53  int nn = 0;
     54  for (typename Graph::NodeIt it(g); it != INVALID; ++it) {
     55    ++nn;
     56  }
     57
     58  check(nn == n, "Wrong node number.");
     59  check(countNodes(g) == n, "Wrong node number.");
     60
     61  int ee = 0;
     62  for (typename Graph::EdgeIt it(g); it != INVALID; ++it) {
     63    ++ee;
     64  }
     65
     66  check(ee == 2*e, "Wrong edge number.");
     67  check(countEdges(g) == 2*e, "Wrong edge number.");
     68
     69  int uee = 0;
     70  for (typename Graph::UndirEdgeIt it(g); it != INVALID; ++it) {
     71    ++uee;
     72  }
     73
     74  check(uee == e, "Wrong undir edge number.");
     75  check(countUndirEdges(g) == e, "Wrong undir edge number.");
    5276}
    5377
     
    109133
    110134  check_item_counts(g,3,2);
    111 
    112 
     135}
     136
     137void checkGridGraph(const GridGraph& g, int w, int h) {
     138  check(g.width() == w, "Wrong width");
     139  check(g.height() == h, "Wrong height");
     140
     141  for (int i = 0; i < w; ++i) {
     142    for (int j = 0; j < h; ++j) {
     143      check(g.col(g(i, j)) == i, "Wrong col");
     144      check(g.row(g(i, j)) == j, "Wrong row");
     145    }
     146  }
     147 
     148  for (int i = 0; i < w; ++i) {
     149    for (int j = 0; j < h - 1; ++j) {
     150      check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down");
     151      check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down");
     152    }
     153    check(g.down(g(i, h - 1)) == INVALID, "Wrong down");
     154  }
     155
     156  for (int i = 0; i < w; ++i) {
     157    for (int j = 1; j < h; ++j) {
     158      check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up");
     159      check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up");
     160    }
     161    check(g.up(g(i, 0)) == INVALID, "Wrong up");
     162  }
     163
     164  for (int j = 0; j < h; ++j) {
     165    for (int i = 0; i < w - 1; ++i) {
     166      check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right");
     167      check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right");     
     168    }
     169    check(g.right(g(w - 1, j)) == INVALID, "Wrong right");   
     170  }
     171
     172  for (int j = 0; j < h; ++j) {
     173    for (int i = 1; i < w; ++i) {
     174      check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left");
     175      check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left");     
     176    }
     177    check(g.left(g(0, j)) == INVALID, "Wrong left");   
     178  }
    113179}
    114180
     
    124190  }
    125191
     192  {
     193    GridGraph g(5, 6);
     194    check_item_counts(g, 30, 49);
     195    checkGridGraph(g, 5, 6);
     196  }
     197
     198  std::cout << __FILE__ ": All tests passed.\n";
     199
    126200  return 0;
    127201}
Note: See TracChangeset for help on using the changeset viewer.