Changeset 1680:4f8b9cee576b in lemon-0.x
- Timestamp:
- 09/12/05 11:19:52 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2199
- Files:
-
- 1 added
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
demo/Makefile.am
r1678 r1680 15 15 sub_graph_adaptor_demo \ 16 16 descriptor_map_demo \ 17 coloring 17 coloring \ 18 grid_graph_demo 18 19 19 20 if HAVE_GLPK … … 38 39 graph_to_eps_demo_SOURCES = graph_to_eps_demo.cc 39 40 41 grid_graph_demo_SOURCES = grid_graph_demo.cc 42 40 43 graph_orientation_SOURCES = graph_orientation.cc 41 44 -
lemon/grid_graph.h
r1623 r1680 48 48 /// 49 49 /// Creates a grid graph with the given size. 50 void construct(int height, int width) {50 void construct(int width, int height) { 51 51 _height = height; _width = width; 52 52 _nodeNum = height * width; _edgeNum = 2 * _nodeNum - width - height; 53 53 _edgeLimit = _nodeNum - width; 54 54 } 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 55 104 56 105 public: … … 60 109 /// Gives back the node on the given position. 61 110 Node operator()(int i, int j) const { 62 return Node(i * _width + j);111 return Node(i + j * _width); 63 112 } 64 113 … … 73 122 /// 74 123 /// Gives back the coloumn index of the node. 75 int col(Node n ode) const {124 int col(Node n) const { 76 125 return n.id % _width; 77 126 } … … 278 327 279 328 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; 288 333 289 334 /// \ingroup graphs … … 312 357 /// 313 358 /// \author Balazs Dezso 314 class GridGraph : public MappableGridGraphBase {359 class GridGraph : public ExtendedGridGraphBase { 315 360 public: 316 361 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 318 400 }; 319 401 } -
test/undir_graph_test.cc
r1568 r1680 6 6 #include <lemon/smart_graph.h> 7 7 #include <lemon/full_graph.h> 8 #include <lemon/grid_graph.h> 8 9 9 10 #include <lemon/graph_utils.h> … … 44 45 45 46 checkConcept<UndirGraph, UndirGraph>(); 47 48 checkConcept<UndirGraph, GridGraph>(); 46 49 } 47 50 48 51 template <typename Graph> 49 52 void 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."); 52 76 } 53 77 … … 109 133 110 134 check_item_counts(g,3,2); 111 112 135 } 136 137 void 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 } 113 179 } 114 180 … … 124 190 } 125 191 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 126 200 return 0; 127 201 }
Note: See TracChangeset
for help on using the changeset viewer.