1.1 --- a/demo/Makefile.am Mon Sep 12 09:15:59 2005 +0000
1.2 +++ b/demo/Makefile.am Mon Sep 12 09:19:52 2005 +0000
1.3 @@ -14,7 +14,8 @@
1.4 hello_lemon \
1.5 sub_graph_adaptor_demo \
1.6 descriptor_map_demo \
1.7 - coloring
1.8 + coloring \
1.9 + grid_graph_demo
1.10
1.11 if HAVE_GLPK
1.12 noinst_PROGRAMS += lp_demo lp_maxflow_demo
1.13 @@ -37,6 +38,8 @@
1.14
1.15 graph_to_eps_demo_SOURCES = graph_to_eps_demo.cc
1.16
1.17 +grid_graph_demo_SOURCES = grid_graph_demo.cc
1.18 +
1.19 graph_orientation_SOURCES = graph_orientation.cc
1.20
1.21 min_route_SOURCES = min_route.cc
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/demo/grid_graph_demo.cc Mon Sep 12 09:19:52 2005 +0000
2.3 @@ -0,0 +1,29 @@
2.4 +#include <lemon/grid_graph.h>
2.5 +#include <lemon/graph_adaptor.h>
2.6 +#include <lemon/graph_to_eps.h>
2.7 +#include <lemon/xy.h>
2.8 +
2.9 +#include <iostream>
2.10 +#include <fstream>
2.11 +
2.12 +using namespace lemon;
2.13 +using namespace std;
2.14 +
2.15 +int main() {
2.16 + GridGraph graph(5, 7);
2.17 + GridGraph::NodeMap<xy<double> > coord(graph);
2.18 + for (int i = 0; i < graph.width(); ++i) {
2.19 + for (int j = 0; j < graph.height(); ++j) {
2.20 + coord[graph(i, j)] = xy<double>(i * 10.0, j * 10.0);
2.21 + }
2.22 + }
2.23 + graphToEps(graph, "grid_graph.eps").scaleToA4().
2.24 + title("Grid graph").
2.25 + copyright("(C) 2005 LEMON Project").
2.26 + coords(coord).
2.27 + enableParallel().
2.28 + nodeScale(.45).
2.29 + drawArrows().
2.30 + run();
2.31 + return 0;
2.32 +}
3.1 --- a/lemon/grid_graph.h Mon Sep 12 09:15:59 2005 +0000
3.2 +++ b/lemon/grid_graph.h Mon Sep 12 09:19:52 2005 +0000
3.3 @@ -47,19 +47,68 @@
3.4 /// \brief Creates a grid graph with the given size.
3.5 ///
3.6 /// Creates a grid graph with the given size.
3.7 - void construct(int height, int width) {
3.8 + void construct(int width, int height) {
3.9 _height = height; _width = width;
3.10 _nodeNum = height * width; _edgeNum = 2 * _nodeNum - width - height;
3.11 _edgeLimit = _nodeNum - width;
3.12 }
3.13
3.14 + /// \brief Gives back the edge goes down from the node.
3.15 + ///
3.16 + /// Gives back the edge goes down from the node. If there is not
3.17 + /// outgoing edge then it gives back INVALID.
3.18 + Edge _down(Node n) const {
3.19 + if (n.id < _nodeNum - _width) {
3.20 + return Edge(n.id);
3.21 + } else {
3.22 + return INVALID;
3.23 + }
3.24 + }
3.25 +
3.26 + /// \brief Gives back the edge comes from up into the node.
3.27 + ///
3.28 + /// Gives back the edge comes from up into the node. If there is not
3.29 + /// incoming edge then it gives back INVALID.
3.30 + Edge _up(Node n) const {
3.31 + if (n.id >= _width) {
3.32 + return Edge(n.id - _width);
3.33 + } else {
3.34 + return INVALID;
3.35 + }
3.36 + }
3.37 +
3.38 + /// \brief Gives back the edge goes right from the node.
3.39 + ///
3.40 + /// Gives back the edge goes right from the node. If there is not
3.41 + /// outgoing edge then it gives back INVALID.
3.42 + Edge _right(Node n) const {
3.43 + if (n.id % _width < _width - 1) {
3.44 + return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1);
3.45 + } else {
3.46 + return INVALID;
3.47 + }
3.48 + }
3.49 +
3.50 + /// \brief Gives back the edge comes from left into the node.
3.51 + ///
3.52 + /// Gives back the edge comes left up into the node. If there is not
3.53 + /// incoming edge then it gives back INVALID.
3.54 + Edge _left(Node n) const {
3.55 + if (n.id % _width > 0) {
3.56 + return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1) - 1;
3.57 + } else {
3.58 + return INVALID;
3.59 + }
3.60 + }
3.61 +
3.62 +
3.63 public:
3.64
3.65 /// \brief The node on the given position.
3.66 ///
3.67 /// Gives back the node on the given position.
3.68 Node operator()(int i, int j) const {
3.69 - return Node(i * _width + j);
3.70 + return Node(i + j * _width);
3.71 }
3.72
3.73 /// \brief Gives back the row index of the node.
3.74 @@ -72,7 +121,7 @@
3.75 /// \brief Gives back the coloumn index of the node.
3.76 ///
3.77 /// Gives back the coloumn index of the node.
3.78 - int col(Node node) const {
3.79 + int col(Node n) const {
3.80 return n.id % _width;
3.81 }
3.82
3.83 @@ -277,14 +326,10 @@
3.84 };
3.85
3.86
3.87 - typedef UndirGraphExtender<GridGraphBase>
3.88 - UndirGridGraphBase;
3.89 - typedef AlterableUndirGraphExtender<UndirGridGraphBase>
3.90 - AlterableGridGraphBase;
3.91 - typedef IterableUndirGraphExtender<AlterableGridGraphBase>
3.92 - IterableGridGraphBase;
3.93 - typedef MappableUndirGraphExtender<IterableGridGraphBase>
3.94 - MappableGridGraphBase;
3.95 + typedef MappableUndirGraphExtender<
3.96 + IterableUndirGraphExtender<
3.97 + AlterableUndirGraphExtender<
3.98 + UndirGraphExtender<GridGraphBase> > > > ExtendedGridGraphBase;
3.99
3.100 /// \ingroup graphs
3.101 ///
3.102 @@ -311,10 +356,47 @@
3.103 /// "Undirected Graph" concept.
3.104 ///
3.105 /// \author Balazs Dezso
3.106 - class GridGraph : public MappableGridGraphBase {
3.107 + class GridGraph : public ExtendedGridGraphBase {
3.108 public:
3.109
3.110 - GridGraph(int m, int n) { construct(m, n); }
3.111 + GridGraph(int n, int m) { construct(n, m); }
3.112 +
3.113 + /// \brief Gives back the edge goes down from the node.
3.114 + ///
3.115 + /// Gives back the edge goes down from the node. If there is not
3.116 + /// outgoing edge then it gives back INVALID.
3.117 + Edge down(Node n) const {
3.118 + UndirEdge ue = _down(n);
3.119 + return ue != INVALID ? direct(ue, true) : INVALID;
3.120 + }
3.121 +
3.122 + /// \brief Gives back the edge goes up from the node.
3.123 + ///
3.124 + /// Gives back the edge goes up from the node. If there is not
3.125 + /// outgoing edge then it gives back INVALID.
3.126 + Edge up(Node n) const {
3.127 + UndirEdge ue = _up(n);
3.128 + return ue != INVALID ? direct(ue, false) : INVALID;
3.129 + }
3.130 +
3.131 + /// \brief Gives back the edge goes right from the node.
3.132 + ///
3.133 + /// Gives back the edge goes right from the node. If there is not
3.134 + /// outgoing edge then it gives back INVALID.
3.135 + Edge right(Node n) const {
3.136 + UndirEdge ue = _right(n);
3.137 + return ue != INVALID ? direct(ue, true) : INVALID;
3.138 + }
3.139 +
3.140 + /// \brief Gives back the edge goes left from the node.
3.141 + ///
3.142 + /// Gives back the edge goes left from the node. If there is not
3.143 + /// outgoing edge then it gives back INVALID.
3.144 + Edge left(Node n) const {
3.145 + UndirEdge ue = _left(n);
3.146 + return ue != INVALID ? direct(ue, false) : INVALID;
3.147 + }
3.148 +
3.149 };
3.150 }
3.151 #endif
4.1 --- a/test/undir_graph_test.cc Mon Sep 12 09:15:59 2005 +0000
4.2 +++ b/test/undir_graph_test.cc Mon Sep 12 09:19:52 2005 +0000
4.3 @@ -5,6 +5,7 @@
4.4 #include <lemon/list_graph.h>
4.5 #include <lemon/smart_graph.h>
4.6 #include <lemon/full_graph.h>
4.7 +#include <lemon/grid_graph.h>
4.8
4.9 #include <lemon/graph_utils.h>
4.10
4.11 @@ -43,12 +44,35 @@
4.12 checkConcept<UndirGraph, UndirFullGraph>();
4.13
4.14 checkConcept<UndirGraph, UndirGraph>();
4.15 +
4.16 + checkConcept<UndirGraph, GridGraph>();
4.17 }
4.18
4.19 template <typename Graph>
4.20 void check_item_counts(Graph &g, int n, int e) {
4.21 - check(countNodes(g)==n, "Wrong node number.");
4.22 - check(countEdges(g)==2*e, "Wrong edge number.");
4.23 + int nn = 0;
4.24 + for (typename Graph::NodeIt it(g); it != INVALID; ++it) {
4.25 + ++nn;
4.26 + }
4.27 +
4.28 + check(nn == n, "Wrong node number.");
4.29 + check(countNodes(g) == n, "Wrong node number.");
4.30 +
4.31 + int ee = 0;
4.32 + for (typename Graph::EdgeIt it(g); it != INVALID; ++it) {
4.33 + ++ee;
4.34 + }
4.35 +
4.36 + check(ee == 2*e, "Wrong edge number.");
4.37 + check(countEdges(g) == 2*e, "Wrong edge number.");
4.38 +
4.39 + int uee = 0;
4.40 + for (typename Graph::UndirEdgeIt it(g); it != INVALID; ++it) {
4.41 + ++uee;
4.42 + }
4.43 +
4.44 + check(uee == e, "Wrong undir edge number.");
4.45 + check(countUndirEdges(g) == e, "Wrong undir edge number.");
4.46 }
4.47
4.48 template <typename Graph>
4.49 @@ -108,8 +132,50 @@
4.50 // print_items(g);
4.51
4.52 check_item_counts(g,3,2);
4.53 +}
4.54
4.55 +void checkGridGraph(const GridGraph& g, int w, int h) {
4.56 + check(g.width() == w, "Wrong width");
4.57 + check(g.height() == h, "Wrong height");
4.58
4.59 + for (int i = 0; i < w; ++i) {
4.60 + for (int j = 0; j < h; ++j) {
4.61 + check(g.col(g(i, j)) == i, "Wrong col");
4.62 + check(g.row(g(i, j)) == j, "Wrong row");
4.63 + }
4.64 + }
4.65 +
4.66 + for (int i = 0; i < w; ++i) {
4.67 + for (int j = 0; j < h - 1; ++j) {
4.68 + check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down");
4.69 + check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down");
4.70 + }
4.71 + check(g.down(g(i, h - 1)) == INVALID, "Wrong down");
4.72 + }
4.73 +
4.74 + for (int i = 0; i < w; ++i) {
4.75 + for (int j = 1; j < h; ++j) {
4.76 + check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up");
4.77 + check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up");
4.78 + }
4.79 + check(g.up(g(i, 0)) == INVALID, "Wrong up");
4.80 + }
4.81 +
4.82 + for (int j = 0; j < h; ++j) {
4.83 + for (int i = 0; i < w - 1; ++i) {
4.84 + check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right");
4.85 + check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right");
4.86 + }
4.87 + check(g.right(g(w - 1, j)) == INVALID, "Wrong right");
4.88 + }
4.89 +
4.90 + for (int j = 0; j < h; ++j) {
4.91 + for (int i = 1; i < w; ++i) {
4.92 + check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left");
4.93 + check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left");
4.94 + }
4.95 + check(g.left(g(0, j)) == INVALID, "Wrong left");
4.96 + }
4.97 }
4.98
4.99 int main() {
4.100 @@ -123,5 +189,13 @@
4.101 check_item_counts(g, 5, 10);
4.102 }
4.103
4.104 + {
4.105 + GridGraph g(5, 6);
4.106 + check_item_counts(g, 30, 49);
4.107 + checkGridGraph(g, 5, 6);
4.108 + }
4.109 +
4.110 + std::cout << __FILE__ ": All tests passed.\n";
4.111 +
4.112 return 0;
4.113 }