diff --git a/doc/CMakeLists.txt b/doc/CMakeLists.txt --- a/doc/CMakeLists.txt +++ b/doc/CMakeLists.txt @@ -13,6 +13,7 @@ ADD_CUSTOM_TARGET(html COMMAND rm -rf gen-images COMMAND mkdir gen-images + COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps diff --git a/doc/Makefile.am b/doc/Makefile.am --- a/doc/Makefile.am +++ b/doc/Makefile.am @@ -11,6 +11,7 @@ doc/CMakeLists.txt DOC_EPS_IMAGES18 = \ + grid_graph.eps \ nodeshape_0.eps \ nodeshape_1.eps \ nodeshape_2.eps \ diff --git a/doc/images/grid_graph.eps b/doc/images/grid_graph.eps new file mode 100644 --- /dev/null +++ b/doc/images/grid_graph.eps @@ -0,0 +1,286 @@ +%!PS-Adobe-2.0 EPSF-2.0 +%%Title: Grid undirected graph +%%Copyright: (C) 2006 LEMON Project +%%Creator: LEMON, graphToEps() +%%CreationDate: Fri Sep 29 11:55:56 2006 +%%BoundingBox: 0 0 985 1144 +%%EndComments +/lb { setlinewidth setrgbcolor newpath moveto + 4 2 roll 1 index 1 index curveto stroke } bind def +/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def +/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def +/sq { newpath 2 index 1 index add 2 index 2 index add moveto + 2 index 1 index sub 2 index 2 index add lineto + 2 index 1 index sub 2 index 2 index sub lineto + 2 index 1 index add 2 index 2 index sub lineto + closepath pop pop pop} bind def +/di { newpath 2 index 1 index add 2 index moveto + 2 index 2 index 2 index add lineto + 2 index 1 index sub 2 index lineto + 2 index 2 index 2 index sub lineto + closepath pop pop pop} bind def +/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill + setrgbcolor 1.1 div c fill + } bind def +/arrl 1 def +/arrw 0.3 def +/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def +/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def + /w exch def /len exch def + newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto + len w sub arrl sub dx dy lrl + arrw dy dx neg lrl + dx arrl w add mul dy w 2 div arrw add mul sub + dy arrl w add mul dx w 2 div arrw add mul add rlineto + dx arrl w add mul neg dy w 2 div arrw add mul sub + dy arrl w add mul neg dx w 2 div arrw add mul add rlineto + arrw dy dx neg lrl + len w sub arrl sub neg dx dy lrl + closepath fill } bind def +/cshow { 2 index 2 index moveto dup stringwidth pop + neg 2 div fosi .35 mul neg rmoveto show pop pop} def + +gsave +2 2 scale +50 40 translate +5.5000 5.5000 scale +% 1.14018 1.14018 translate +%Edges: +gsave +70 80 70 90 0 0 0 0.5000 l +70 70 70 80 0 0 0 0.5000 l +70 60 70 70 0 0 0 0.5000 l +70 50 70 60 0 0 0 0.5000 l +70 40 70 50 0 0 0 0.5000 l +70 30 70 40 0 0 0 0.5000 l +70 20 70 30 0 0 0 0.5000 l +70 10 70 20 0 0 0 0.5000 l +70 0 70 10 0 0 0 0.5000 l +60 80 60 90 0 0 0 0.5000 l +60 70 60 80 0 0 0 0.5000 l +60 60 60 70 0 0 0 0.5000 l +60 50 60 60 0 0 0 0.5000 l +60 40 60 50 0 0 0 0.5000 l +60 30 60 40 0 0 0 0.5000 l +60 20 60 30 0 0 0 0.5000 l +60 10 60 20 0 0 0 0.5000 l +60 0 60 10 0 0 0 0.5000 l +50 80 50 90 0 0 0 0.5000 l +50 70 50 80 0 0 0 0.5000 l +50 60 50 70 0 0 0 0.5000 l +50 50 50 60 0 0 0 0.5000 l +50 40 50 50 0 0 0 0.5000 l +50 30 50 40 0 0 0 0.5000 l +50 20 50 30 0 0 0 0.5000 l +50 10 50 20 0 0 0 0.5000 l +50 0 50 10 0 0 0 0.5000 l +40 80 40 90 0 0 0 0.5000 l +40 70 40 80 0 0 0 0.5000 l +40 60 40 70 0 0 0 0.5000 l +40 50 40 60 0 0 0 0.5000 l +40 40 40 50 0 0 0 0.5000 l +40 30 40 40 0 0 0 0.5000 l +40 20 40 30 0 0 0 0.5000 l +40 10 40 20 0 0 0 0.5000 l +40 0 40 10 0 0 0 0.5000 l +30 80 30 90 0 0 0 0.5000 l +30 70 30 80 0 0 0 0.5000 l +30 60 30 70 0 0 0 0.5000 l +30 50 30 60 0 0 0 0.5000 l +30 40 30 50 0 0 0 0.5000 l +30 30 30 40 0 0 0 0.5000 l +30 20 30 30 0 0 0 0.5000 l +30 10 30 20 0 0 0 0.5000 l +30 0 30 10 0 0 0 0.5000 l +20 80 20 90 0 0 0 0.5000 l +20 70 20 80 0 0 0 0.5000 l +20 60 20 70 0 0 0 0.5000 l +20 50 20 60 0 0 0 0.5000 l +20 40 20 50 0 0 0 0.5000 l +20 30 20 40 0 0 0 0.5000 l +20 20 20 30 0 0 0 0.5000 l +20 10 20 20 0 0 0 0.5000 l +20 0 20 10 0 0 0 0.5000 l +10 80 10 90 0 0 0 0.5000 l +10 70 10 80 0 0 0 0.5000 l +10 60 10 70 0 0 0 0.5000 l +10 50 10 60 0 0 0 0.5000 l +10 40 10 50 0 0 0 0.5000 l +10 30 10 40 0 0 0 0.5000 l +10 20 10 30 0 0 0 0.5000 l +10 10 10 20 0 0 0 0.5000 l +10 0 10 10 0 0 0 0.5000 l +0 80 0 90 0 0 0 0.5000 l +0 70 0 80 0 0 0 0.5000 l +0 60 0 70 0 0 0 0.5000 l +0 50 0 60 0 0 0 0.5000 l +0 40 0 50 0 0 0 0.5000 l +0 30 0 40 0 0 0 0.5000 l +0 20 0 30 0 0 0 0.5000 l +0 10 0 20 0 0 0 0.5000 l +0 0 0 10 0 0 0 0.5000 l +60 90 70 90 0 0 0 0.5000 l +60 80 70 80 0 0 0 0.5000 l +60 70 70 70 0 0 0 0.5000 l +60 60 70 60 0 0 0 0.5000 l +60 50 70 50 0 0 0 0.5000 l +60 40 70 40 0 0 0 0.5000 l +60 30 70 30 0 0 0 0.5000 l +60 20 70 20 0 0 0 0.5000 l +60 10 70 10 0 0 0 0.5000 l +60 0 70 0 0 0 0 0.5000 l +50 90 60 90 0 0 0 0.5000 l +50 80 60 80 0 0 0 0.5000 l +50 70 60 70 0 0 0 0.5000 l +50 60 60 60 0 0 0 0.5000 l +50 50 60 50 0 0 0 0.5000 l +50 40 60 40 0 0 0 0.5000 l +50 30 60 30 0 0 0 0.5000 l +50 20 60 20 0 0 0 0.5000 l +50 10 60 10 0 0 0 0.5000 l +50 0 60 0 0 0 0 0.5000 l +40 90 50 90 0 0 0 0.5000 l +40 80 50 80 0 0 0 0.5000 l +40 70 50 70 0 0 0 0.5000 l +40 60 50 60 0 0 0 0.5000 l +40 50 50 50 0 0 0 0.5000 l +40 40 50 40 0 0 0 0.5000 l +40 30 50 30 0 0 0 0.5000 l +40 20 50 20 0 0 0 0.5000 l +40 10 50 10 0 0 0 0.5000 l +40 0 50 0 0 0 0 0.5000 l +30 90 40 90 0 0 0 0.5000 l +30 80 40 80 0 0 0 0.5000 l +30 70 40 70 0 0 0 0.5000 l +30 60 40 60 0 0 0 0.5000 l +30 50 40 50 0 0 0 0.5000 l +30 40 40 40 0 0 0 0.5000 l +30 30 40 30 0 0 0 0.5000 l +30 20 40 20 0 0 0 0.5000 l +30 10 40 10 0 0 0 0.5000 l +30 0 40 0 0 0 0 0.5000 l +20 90 30 90 0 0 0 0.5000 l +20 80 30 80 0 0 0 0.5000 l +20 70 30 70 0 0 0 0.5000 l +20 60 30 60 0 0 0 0.5000 l +20 50 30 50 0 0 0 0.5000 l +20 40 30 40 0 0 0 0.5000 l +20 30 30 30 0 0 0 0.5000 l +20 20 30 20 0 0 0 0.5000 l +20 10 30 10 0 0 0 0.5000 l +20 0 30 0 0 0 0 0.5000 l +10 90 20 90 0 0 0 0.5000 l +10 80 20 80 0 0 0 0.5000 l +10 70 20 70 0 0 0 0.5000 l +10 60 20 60 0 0 0 0.5000 l +10 50 20 50 0 0 0 0.5000 l +10 40 20 40 0 0 0 0.5000 l +10 30 20 30 0 0 0 0.5000 l +10 20 20 20 0 0 0 0.5000 l +10 10 20 10 0 0 0 0.5000 l +10 0 20 0 0 0 0 0.5000 l +0 90 10 90 0 0 0 0.5000 l +0 80 10 80 0 0 0 0.5000 l +0 70 10 70 0 0 0 0.5000 l +0 60 10 60 0 0 0 0.5000 l +0 50 10 50 0 0 0 0.5000 l +0 40 10 40 0 0 0 0.5000 l +0 30 10 30 0 0 0 0.5000 l +0 20 10 20 0 0 0 0.5000 l +0 10 10 10 0 0 0 0.5000 l +0 0 10 0 0 0 0 0.5000 l +grestore +%Nodes: +gsave +70 90 1.4000 0 0 0 nc +70 80 1.4000 1 1 1 nc +70 70 1.4000 1 1 1 nc +70 60 1.4000 1 1 1 nc +70 50 1.4000 1 1 1 nc +70 40 1.4000 1 1 1 nc +70 30 1.4000 1 1 1 nc +70 20 1.4000 1 1 1 nc +70 10 1.4000 1 1 1 nc +70 0 1.4000 0 0 0 nc +60 90 1.4000 1 1 1 nc +60 80 1.4000 1 1 1 nc +60 70 1.4000 1 1 1 nc +60 60 1.4000 1 1 1 nc +60 50 1.4000 1 1 1 nc +60 40 1.4000 1 1 1 nc +60 30 1.4000 1 1 1 nc +60 20 1.4000 1 1 1 nc +60 10 1.4000 1 1 1 nc +60 0 1.4000 1 1 1 nc +50 90 1.4000 1 1 1 nc +50 80 1.4000 1 1 1 nc +50 70 1.4000 1 1 1 nc +50 60 1.4000 1 1 1 nc +50 50 1.4000 1 1 1 nc +50 40 1.4000 1 1 1 nc +50 30 1.4000 1 1 1 nc +50 20 1.4000 1 1 1 nc +50 10 1.4000 1 1 1 nc +50 0 1.4000 1 1 1 nc +40 90 1.4000 1 1 1 nc +40 80 1.4000 1 1 1 nc +40 70 1.4000 1 1 1 nc +40 60 1.4000 1 1 1 nc +40 50 1.4000 1 1 1 nc +40 40 1.4000 1 1 1 nc +40 30 1.4000 1 1 1 nc +40 20 1.4000 1 1 1 nc +40 10 1.4000 1 1 1 nc +40 0 1.4000 1 1 1 nc +30 90 1.4000 1 1 1 nc +30 80 1.4000 1 1 1 nc +30 70 1.4000 1 1 1 nc +30 60 1.4000 1 1 1 nc +30 50 1.4000 1 1 1 nc +30 40 1.4000 1 1 1 nc +30 30 1.4000 1 1 1 nc +30 20 1.4000 1 1 1 nc +30 10 1.4000 1 1 1 nc +30 0 1.4000 1 1 1 nc +20 90 1.4000 1 1 1 nc +20 80 1.4000 1 1 1 nc +20 70 1.4000 1 1 1 nc +20 60 1.4000 1 1 1 nc +20 50 1.4000 1 1 1 nc +20 40 1.4000 1 1 1 nc +20 30 1.4000 1 1 1 nc +20 20 1.4000 1 1 1 nc +20 10 1.4000 1 1 1 nc +20 0 1.4000 1 1 1 nc +10 90 1.4000 1 1 1 nc +10 80 1.4000 1 1 1 nc +10 70 1.4000 1 1 1 nc +10 60 1.4000 1 1 1 nc +10 50 1.4000 1 1 1 nc +10 40 1.4000 1 1 1 nc +10 30 1.4000 1 1 1 nc +10 20 1.4000 1 1 1 nc +10 10 1.4000 1 1 1 nc +10 0 1.4000 1 1 1 nc +0 90 1.4000 0 0 0 nc +0 80 1.4000 1 1 1 nc +0 70 1.4000 1 1 1 nc +0 60 1.4000 1 1 1 nc +0 50 1.4000 1 1 1 nc +0 40 1.4000 1 1 1 nc +0 30 1.4000 1 1 1 nc +0 20 1.4000 1 1 1 nc +0 10 1.4000 1 1 1 nc +0 0 1.4000 0 0 0 nc +grestore +gsave +/fosi 3.5 def +(Helvetica) findfont fosi scalefont setfont +0 0 0 setrgbcolor +0 95 ((0,height-1)) cshow +67 95 ((width-1,height-1)) cshow +0 -5 ((0,0)) cshow +70 -5 ((width-1,0)) cshow +grestore +grestore +showpage diff --git a/lemon/grid_graph.h b/lemon/grid_graph.h --- a/lemon/grid_graph.h +++ b/lemon/grid_graph.h @@ -19,15 +19,11 @@ #ifndef GRID_GRAPH_H #define GRID_GRAPH_H -#include #include +#include +#include #include -#include -#include - -#include - ///\ingroup graphs ///\file ///\brief GridGraph class. @@ -41,6 +37,7 @@ typedef GridGraphBase Graph; class Node; + class Edge; class Arc; public: @@ -49,58 +46,31 @@ protected: - void construct(int w, int h) { - _height = h; _width = w; - _nodeNum = h * w; _arcNum = 2 * _nodeNum - w - h; - _arcLimit = _nodeNum - w; - } - - Arc _down(Node n) const { - if (n.id < _nodeNum - _width) { - return Arc(n.id); - } else { - return INVALID; - } - } - - Arc _up(Node n) const { - if (n.id >= _width) { - return Arc(n.id - _width); - } else { - return INVALID; - } - } - - Arc _right(Node n) const { - if (n.id % _width < _width - 1) { - return _arcLimit + n.id % _width + (n.id / _width) * (_width - 1); - } else { - return INVALID; - } - } - - Arc _left(Node n) const { - if (n.id % _width > 0) { - return _arcLimit + n.id % _width + (n.id / _width) * (_width - 1) - 1; - } else { - return INVALID; - } + void construct(int width, int height) { + _width = width; _height = height; + _node_num = width * height; + _edge_num = 2 * _node_num - width - height; + _edge_limit = _node_num - _width; } public: Node operator()(int i, int j) const { - LEMON_ASSERT(0 <= i && i < width() && - 0 <= j && j < height(), "lemon::GridGraph::IndexError"); + LEMON_DEBUG(0 <= i && i < _width && + 0 <= j && j < _height, "Index out of range"); return Node(i + j * _width); } - int row(Node n) const { - return n.id / _width; + int col(Node n) const { + return n._id % _width; } - int col(Node n) const { - return n.id % _width; + int row(Node n) const { + return n._id / _width; + } + + dim2::Point pos(Node n) const { + return dim2::Point(col(n), row(n)); } int width() const { @@ -114,45 +84,86 @@ typedef True NodeNumTag; typedef True ArcNumTag; - int nodeNum() const { return _nodeNum; } - int arcNum() const { return _arcNum; } + int nodeNum() const { return _node_num; } + int edgeNum() const { return _edge_num; } + int arcNum() const { return 2 * _edge_num; } - int maxNodeId() const { return nodeNum() - 1; } - int maxArcId() const { return arcNum() - 1; } - - Node source(Arc e) const { - if (e.id < _arcLimit) { - return e.id; + Node u(Edge edge) const { + if (edge._id < _edge_limit) { + return edge._id; } else { - return (e.id - _arcLimit) % (_width - 1) + - (e.id - _arcLimit) / (_width - 1) * _width; + return (edge._id - _edge_limit) % (_width - 1) + + (edge._id - _edge_limit) / (_width - 1) * _width; } } - Node target(Arc e) const { - if (e.id < _arcLimit) { - return e.id + _width; + Node v(Edge edge) const { + if (edge._id < _edge_limit) { + return edge._id + _width; } else { - return (e.id - _arcLimit) % (_width - 1) + - (e.id - _arcLimit) / (_width - 1) * _width + 1; + return (edge._id - _edge_limit) % (_width - 1) + + (edge._id - _edge_limit) / (_width - 1) * _width + 1; } } - static int id(Node v) { return v.id; } - static int id(Arc e) { return e.id; } + Node source(Arc arc) const { + return (arc._id & 1) == 1 ? u(arc) : v(arc); + } + + Node target(Arc arc) const { + return (arc._id & 1) == 1 ? v(arc) : u(arc); + } + + static int id(Node node) { return node._id; } + static int id(Edge edge) { return edge._id; } + static int id(Arc arc) { return arc._id; } + + int maxNodeId() const { return _node_num - 1; } + int maxEdgeId() const { return _edge_num - 1; } + int maxArcId() const { return 2 * _edge_num - 1; } static Node nodeFromId(int id) { return Node(id);} - + static Edge edgeFromId(int id) { return Edge(id);} static Arc arcFromId(int id) { return Arc(id);} - typedef True FindArcTag; + typedef True FindEdgeTag; + + Edge findEdge(Node u, Node v, Edge prev = INVALID) const { + if (prev != INVALID) return INVALID; + if (v._id > u._id) { + if (v._id - u._id == _width) + return Edge(u._id); + if (v._id - u._id == 1 && u._id % _width < _width - 1) { + return Edge(u._id / _width * (_width - 1) + + u._id % _width + _edge_limit); + } + } else { + if (u._id - v._id == _width) + return Edge(v._id); + if (u._id - v._id == 1 && v._id % _width < _width - 1) { + return Edge(v._id / _width * (_width - 1) + + v._id % _width + _edge_limit); + } + } + return INVALID; + } Arc findArc(Node u, Node v, Arc prev = INVALID) const { if (prev != INVALID) return INVALID; - if (v.id - u.id == _width) return Arc(u.id); - if (v.id - u.id == 1 && u.id % _width < _width - 1) { - return Arc(u.id / _width * (_width - 1) + - u.id % _width + _arcLimit); + if (v._id > u._id) { + if (v._id - u._id == _width) + return Arc((u._id << 1) | 1); + if (v._id - u._id == 1 && u._id % _width < _width - 1) { + return Arc(((u._id / _width * (_width - 1) + + u._id % _width + _edge_limit) << 1) | 1); + } + } else { + if (u._id - v._id == _width) + return Arc(v._id << 1); + if (u._id - v._id == 1 && v._id % _width < _width - 1) { + return Arc((v._id / _width * (_width - 1) + + v._id % _width + _edge_limit) << 1); + } } return INVALID; } @@ -161,127 +172,331 @@ friend class GridGraphBase; protected: - int id; - Node(int _id) : id(_id) {} + int _id; + Node(int id) : _id(id) {} public: Node() {} - Node (Invalid) { id = -1; } - bool operator==(const Node node) const { return id == node.id; } - bool operator!=(const Node node) const { return id != node.id; } - bool operator<(const Node node) const { return id < node.id; } + Node (Invalid) : _id(-1) {} + bool operator==(const Node node) const {return _id == node._id;} + bool operator!=(const Node node) const {return _id != node._id;} + bool operator<(const Node node) const {return _id < node._id;} + }; + + class Edge { + friend class GridGraphBase; + + protected: + int _id; + + Edge(int id) : _id(id) {} + + public: + Edge() {} + Edge (Invalid) : _id(-1) {} + bool operator==(const Edge edge) const {return _id == edge._id;} + bool operator!=(const Edge edge) const {return _id != edge._id;} + bool operator<(const Edge edge) const {return _id < edge._id;} }; class Arc { friend class GridGraphBase; protected: - int id; - Arc(int _id) : id(_id) {} + int _id; + + Arc(int id) : _id(id) {} + public: Arc() {} - Arc (Invalid) { id = -1; } - bool operator==(const Arc arc) const { return id == arc.id; } - bool operator!=(const Arc arc) const { return id != arc.id; } - bool operator<(const Arc arc) const { return id < arc.id; } + Arc (Invalid) : _id(-1) {} + operator Edge() const { return _id != -1 ? Edge(_id >> 1) : INVALID; } + bool operator==(const Arc arc) const {return _id == arc._id;} + bool operator!=(const Arc arc) const {return _id != arc._id;} + bool operator<(const Arc arc) const {return _id < arc._id;} }; + static bool direction(Arc arc) { + return (arc._id & 1) == 1; + } + + static Arc direct(Edge edge, bool dir) { + return Arc((edge._id << 1) | (dir ? 1 : 0)); + } + void first(Node& node) const { - node.id = nodeNum() - 1; + node._id = _node_num - 1; } static void next(Node& node) { - --node.id; + --node._id; + } + + void first(Edge& edge) const { + edge._id = _edge_num - 1; + } + + static void next(Edge& edge) { + --edge._id; } void first(Arc& arc) const { - arc.id = arcNum() - 1; + arc._id = 2 * _edge_num - 1; } static void next(Arc& arc) { - --arc.id; + --arc._id; } void firstOut(Arc& arc, const Node& node) const { - if (node.id < _nodeNum - _width) { - arc.id = node.id; - } else if (node.id % _width < _width - 1) { - arc.id = _arcLimit + node.id % _width + - (node.id / _width) * (_width - 1); + if (node._id % _width < _width - 1) { + arc._id = (_edge_limit + node._id % _width + + (node._id / _width) * (_width - 1)) << 1 | 1; + return; + } + if (node._id < _node_num - _width) { + arc._id = node._id << 1 | 1; + return; + } + if (node._id % _width > 0) { + arc._id = (_edge_limit + node._id % _width + + (node._id / _width) * (_width - 1) - 1) << 1; + return; + } + if (node._id >= _width) { + arc._id = (node._id - _width) << 1; + return; + } + arc._id = -1; + } + + void nextOut(Arc& arc) const { + int nid = arc._id >> 1; + if ((arc._id & 1) == 1) { + if (nid >= _edge_limit) { + nid = (nid - _edge_limit) % (_width - 1) + + (nid - _edge_limit) / (_width - 1) * _width; + if (nid < _node_num - _width) { + arc._id = nid << 1 | 1; + return; + } + } + if (nid % _width > 0) { + arc._id = (_edge_limit + nid % _width + + (nid / _width) * (_width - 1) - 1) << 1; + return; + } + if (nid >= _width) { + arc._id = (nid - _width) << 1; + return; + } } else { - arc.id = -1; + if (nid >= _edge_limit) { + nid = (nid - _edge_limit) % (_width - 1) + + (nid - _edge_limit) / (_width - 1) * _width + 1; + if (nid >= _width) { + arc._id = (nid - _width) << 1; + return; + } + } + } + arc._id = -1; + } + + void firstIn(Arc& arc, const Node& node) const { + if (node._id % _width < _width - 1) { + arc._id = (_edge_limit + node._id % _width + + (node._id / _width) * (_width - 1)) << 1; + return; + } + if (node._id < _node_num - _width) { + arc._id = node._id << 1; + return; + } + if (node._id % _width > 0) { + arc._id = (_edge_limit + node._id % _width + + (node._id / _width) * (_width - 1) - 1) << 1 | 1; + return; + } + if (node._id >= _width) { + arc._id = (node._id - _width) << 1 | 1; + return; + } + arc._id = -1; + } + + void nextIn(Arc& arc) const { + int nid = arc._id >> 1; + if ((arc._id & 1) == 0) { + if (nid >= _edge_limit) { + nid = (nid - _edge_limit) % (_width - 1) + + (nid - _edge_limit) / (_width - 1) * _width; + if (nid < _node_num - _width) { + arc._id = nid << 1; + return; + } + } + if (nid % _width > 0) { + arc._id = (_edge_limit + nid % _width + + (nid / _width) * (_width - 1) - 1) << 1 | 1; + return; + } + if (nid >= _width) { + arc._id = (nid - _width) << 1 | 1; + return; + } + } else { + if (nid >= _edge_limit) { + nid = (nid - _edge_limit) % (_width - 1) + + (nid - _edge_limit) / (_width - 1) * _width + 1; + if (nid >= _width) { + arc._id = (nid - _width) << 1 | 1; + return; + } + } + } + arc._id = -1; + } + + void firstInc(Edge& edge, bool& dir, const Node& node) const { + if (node._id % _width < _width - 1) { + edge._id = _edge_limit + node._id % _width + + (node._id / _width) * (_width - 1); + dir = true; + return; + } + if (node._id < _node_num - _width) { + edge._id = node._id; + dir = true; + return; + } + if (node._id % _width > 0) { + edge._id = _edge_limit + node._id % _width + + (node._id / _width) * (_width - 1) - 1; + dir = false; + return; + } + if (node._id >= _width) { + edge._id = node._id - _width; + dir = false; + return; + } + edge._id = -1; + dir = true; + } + + void nextInc(Edge& edge, bool& dir) const { + int nid = edge._id; + if (dir) { + if (nid >= _edge_limit) { + nid = (nid - _edge_limit) % (_width - 1) + + (nid - _edge_limit) / (_width - 1) * _width; + if (nid < _node_num - _width) { + edge._id = nid; + return; + } + } + if (nid % _width > 0) { + edge._id = _edge_limit + nid % _width + + (nid / _width) * (_width - 1) - 1; + dir = false; + return; + } + if (nid >= _width) { + edge._id = nid - _width; + dir = false; + return; + } + } else { + if (nid >= _edge_limit) { + nid = (nid - _edge_limit) % (_width - 1) + + (nid - _edge_limit) / (_width - 1) * _width + 1; + if (nid >= _width) { + edge._id = nid - _width; + return; + } + } + } + edge._id = -1; + dir = true; + } + + Arc right(Node n) const { + if (n._id % _width < _width - 1) { + return Arc(((_edge_limit + n._id % _width + + (n._id / _width) * (_width - 1)) << 1) | 1); + } else { + return INVALID; } } - void nextOut(Arc& arc) const { - if (arc.id >= _arcLimit) { - arc.id = -1; - } else if (arc.id % _width < _width - 1) { - arc.id = _arcLimit + arc.id % _width + - (arc.id / _width) * (_width - 1); + Arc left(Node n) const { + if (n._id % _width > 0) { + return Arc((_edge_limit + n._id % _width + + (n._id / _width) * (_width - 1) - 1) << 1); } else { - arc.id = -1; + return INVALID; } } - void firstIn(Arc& arc, const Node& node) const { - if (node.id >= _width) { - arc.id = node.id - _width; - } else if (node.id % _width > 0) { - arc.id = _arcLimit + node.id % _width + - (node.id / _width) * (_width - 1) - 1; + Arc up(Node n) const { + if (n._id < _edge_limit) { + return Arc((n._id << 1) | 1); } else { - arc.id = -1; + return INVALID; } } - void nextIn(Arc& arc) const { - if (arc.id >= _arcLimit) { - arc.id = -1; - } else if (arc.id % _width > 0) { - arc.id = _arcLimit + arc.id % _width + - (arc.id / _width + 1) * (_width - 1) - 1; + Arc down(Node n) const { + if (n._id >= _width) { + return Arc((n._id - _width) << 1); } else { - arc.id = -1; + return INVALID; } } private: int _width, _height; - int _nodeNum, _arcNum; - int _arcLimit; + int _node_num, _edge_num; + int _edge_limit; }; - typedef GraphExtender > - ExtendedGridGraphBase; + + typedef GraphExtender ExtendedGridGraphBase; /// \ingroup graphs /// /// \brief Grid graph class /// /// This class implements a special graph type. The nodes of the - /// graph can be indiced by two integer \c (i,j) value where \c i - /// is in the \c [0,width) range and j is in the [0, height) range. - /// Two nodes are connected in the graph if the indices differ only - /// on one position and only one is the difference. + /// graph can be indexed by two integer \c (i,j) value where \c i is + /// in the \c [0..width()-1] range and j is in the \c + /// [0..height()-1] range. Two nodes are connected in the graph if + /// the indexes differ exactly on one position and exactly one is + /// the difference. The nodes of the graph be indexed by position + /// with \c operator()() function. The positions of the nodes can be + /// get with \c pos(), \c col() and \c row() members. The outgoing + /// arcs can be retrieved with the \c right(), \c up(), \c left() + /// and \c down() functions, where the bottom-left corner is the + /// origin. /// /// \image html grid_graph.png - /// \image latex grid_graph.eps "Grid graph" width=\textwidth + /// \image latex grid_graph.eps "Grid digraph" row_num=\textrow_num /// - /// The graph can be indiced in the following way: + /// A short example about the basic usage: ///\code - /// GridGraph gr(w, h); - /// GridGraph::NodeMap val(gr); - /// for (int i = 0; i < gr.width(); ++i) { - /// for (int j = 0; j < gr.height(); ++j) { - /// val[gr(i, j)] = i + j; + /// GridGraph graph(rows, cols); + /// GridGraph::NodeMap val(graph); + /// for (int i = 0; i < graph.width(); ++i) { + /// for (int j = 0; j < graph.height(); ++j) { + /// val[graph(i, j)] = i + j; /// } /// } ///\endcode /// - /// This graph type is fully conform to the \ref concepts::Graph - /// "Undirected Graph" concept, and it also has an important extra - /// feature that its maps are real \ref concepts::ReferenceMap - /// "reference map"s. + /// The graph type is fully conform to the \ref concepts::Graph + /// "Graph" concept, and it also has an important extra feature + /// that its maps are real \ref concepts::ReferenceMap "reference + /// map"s. class GridGraph : public ExtendedGridGraphBase { public: @@ -292,17 +507,47 @@ /// Map to get the indices of the nodes as dim2::Point. class IndexMap { public: - /// The key type of the map + /// \brief The key type of the map typedef GridGraph::Node Key; - /// The value type of the map + /// \brief The value type of the map typedef dim2::Point Value; + /// \brief Constructor + /// /// Constructor IndexMap(const GridGraph& graph) : _graph(graph) {} - /// The subscript operator - Value operator[](const Key& key) const { - return dim2::Point(_graph.row(key), _graph.col(key)); + /// \brief The subscript operator + /// + /// The subscript operator. + Value operator[](Key key) const { + return _graph.pos(key); + } + + private: + const GridGraph& _graph; + }; + + /// \brief Map to get the column of the nodes. + /// + /// Map to get the column of the nodes. + class ColMap { + public: + /// \brief The key type of the map + typedef GridGraph::Node Key; + /// \brief The value type of the map + typedef int Value; + + /// \brief Constructor + /// + /// Constructor + ColMap(const GridGraph& graph) : _graph(graph) {} + + /// \brief The subscript operator + /// + /// The subscript operator. + Value operator[](Key key) const { + return _graph.col(key); } private: @@ -314,16 +559,20 @@ /// Map to get the row of the nodes. class RowMap { public: - /// The key type of the map + /// \brief The key type of the map typedef GridGraph::Node Key; - /// The value type of the map + /// \brief The value type of the map typedef int Value; + /// \brief Constructor + /// /// Constructor RowMap(const GridGraph& graph) : _graph(graph) {} - /// The subscript operator - Value operator[](const Key& key) const { + /// \brief The subscript operator + /// + /// The subscript operator. + Value operator[](Key key) const { return _graph.row(key); } @@ -331,38 +580,17 @@ const GridGraph& _graph; }; - /// \brief Map to get the column of the nodes. - /// - /// Map to get the column of the nodes. - class ColMap { - public: - /// The key type of the map - typedef GridGraph::Node Key; - /// The value type of the map - typedef int Value; - - /// Constructor - ColMap(const GridGraph& graph) : _graph(graph) {} - - /// The subscript operator - Value operator[](const Key& key) const { - return _graph.col(key); - } - - private: - const GridGraph& _graph; - }; - /// \brief Constructor /// - /// Constructor. - /// \param width The width of the grid. - /// \param height The height of the grid. + /// Construct a grid graph with given size. GridGraph(int width, int height) { construct(width, height); } /// \brief Resize the graph /// - /// Resize the grid. + /// Resize the graph. The function will fully destroy and rebuild + /// the graph. This cause that the maps of the graph will + /// reallocated automatically and the previous values will be + /// lost. void resize(int width, int height) { Parent::notifier(Arc()).clear(); Parent::notifier(Edge()).clear(); @@ -380,6 +608,13 @@ return Parent::operator()(i, j); } + /// \brief Gives back the column index of the node. + /// + /// Gives back the column index of the node. + int col(Node n) const { + return Parent::col(n); + } + /// \brief Gives back the row index of the node. /// /// Gives back the row index of the node. @@ -387,85 +622,81 @@ return Parent::row(n); } - /// \brief Gives back the column index of the node. + /// \brief Gives back the position of the node. /// - /// Gives back the column index of the node. - int col(Node n) const { - return Parent::col(n); + /// Gives back the position of the node, ie. the (col,row) pair. + dim2::Point pos(Node n) const { + return Parent::pos(n); } - /// \brief Gives back the width of the grid. + /// \brief Gives back the number of the columns. /// - /// Gives back the width of the grid. + /// Gives back the number of the columns. int width() const { return Parent::width(); } - /// \brief Gives back the height of the grid. + /// \brief Gives back the number of the rows. /// - /// Gives back the height of the grid. + /// Gives back the number of the rows. int height() const { return Parent::height(); } + /// \brief Gives back the arc goes right from the node. + /// + /// Gives back the arc goes right from the node. If there is not + /// outgoing arc then it gives back INVALID. + Arc right(Node n) const { + return Parent::right(n); + } + + /// \brief Gives back the arc goes left from the node. + /// + /// Gives back the arc goes left from the node. If there is not + /// outgoing arc then it gives back INVALID. + Arc left(Node n) const { + return Parent::left(n); + } + + /// \brief Gives back the arc goes up from the node. + /// + /// Gives back the arc goes up from the node. If there is not + /// outgoing arc then it gives back INVALID. + Arc up(Node n) const { + return Parent::up(n); + } + /// \brief Gives back the arc goes down from the node. /// /// Gives back the arc goes down from the node. If there is not - /// outgoing arc then it gives back \c INVALID. + /// outgoing arc then it gives back INVALID. Arc down(Node n) const { - Edge e = _down(n); - return e != INVALID ? direct(e, true) : INVALID; + return Parent::down(n); } - /// \brief Gives back the arc goes up from the node. + /// \brief Index map of the grid graph /// - /// Gives back the arc goes up from the node. If there is not - /// outgoing arc then it gives back \c INVALID. - Arc up(Node n) const { - Edge e = _up(n); - return e != INVALID ? direct(e, false) : INVALID; + /// Just returns an IndexMap for the grid graph. + IndexMap indexMap() const { + return IndexMap(*this); } - /// \brief Gives back the arc goes right from the node. + /// \brief Row map of the grid graph /// - /// Gives back the arc goes right from the node. If there is not - /// outgoing arc then it gives back \c INVALID. - Arc right(Node n) const { - Edge e = _right(n); - return e != INVALID ? direct(e, true) : INVALID; + /// Just returns a RowMap for the grid graph. + RowMap rowMap() const { + return RowMap(*this); } - /// \brief Gives back the arc goes left from the node. + /// \brief Column map of the grid graph /// - /// Gives back the arc goes left from the node. If there is not - /// outgoing arc then it gives back \c INVALID. - Arc left(Node n) const { - Edge e = _left(n); - return e != INVALID ? direct(e, false) : INVALID; + /// Just returns a ColMap for the grid graph. + ColMap colMap() const { + return ColMap(*this); } - }; // class GridGraph + }; - /// \brief Index map of the grid graph - /// - /// Just returns an IndexMap for the grid graph. - inline GridGraph::IndexMap indexMap(const GridGraph& graph) { - return GridGraph::IndexMap(graph); - } - - /// \brief Row map of the grid graph - /// - /// Just returns a RowMap for the grid graph. - inline GridGraph::RowMap rowMap(const GridGraph& graph) { - return GridGraph::RowMap(graph); - } - - /// \brief Column map of the grid graph - /// - /// Just returns a ColMap for the grid graph. - inline GridGraph::ColMap colMap(const GridGraph& graph) { - return GridGraph::ColMap(graph); - } } - -#endif // GRID_GRAPH_H +#endif diff --git a/test/graph_test.cc b/test/graph_test.cc --- a/test/graph_test.cc +++ b/test/graph_test.cc @@ -126,6 +126,7 @@ } // { // Checking FullGraph // checkConcept(); +// checkGraphIterators(); // } { // Checking GridGraph checkConcept(); @@ -186,76 +187,83 @@ check(!g.valid(g.arcFromId(-1)), "Wrong validity check"); } -void checkGridGraph(const GridGraph& g, int w, int h) { - check(g.width() == w, "Wrong width"); - check(g.height() == h, "Wrong height"); +void checkGridGraph(int width, int height) { + typedef GridGraph Graph; + GRAPH_TYPEDEFS(Graph); + Graph G(width, height); - for (int i = 0; i < w; ++i) { - for (int j = 0; j < h; ++j) { - check(g.col(g(i, j)) == i, "Wrong col"); - check(g.row(g(i, j)) == j, "Wrong row"); + check(G.width() == width, "Wrong row number"); + check(G.height() == height, "Wrong column number"); + + for (int i = 0; i < width; ++i) { + for (int j = 0; j < height; ++j) { + check(G.col(G(i, j)) == i, "Wrong column"); + check(G.row(G(i, j)) == j, "Wrong row"); + check(G.pos(G(i, j)).x == i, "Wrong column"); + check(G.pos(G(i, j)).y == j, "Wrong row"); } } - for (int i = 0; i < w; ++i) { - for (int j = 0; j < h - 1; ++j) { - check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down"); - check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down"); + for (int j = 0; j < height; ++j) { + for (int i = 0; i < width - 1; ++i) { + check(G.source(G.right(G(i, j))) == G(i, j), "Wrong right"); + check(G.target(G.right(G(i, j))) == G(i + 1, j), "Wrong right"); } - check(g.down(g(i, h - 1)) == INVALID, "Wrong down"); + check(G.right(G(width - 1, j)) == INVALID, "Wrong right"); } - for (int i = 0; i < w; ++i) { - for (int j = 1; j < h; ++j) { - check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up"); - check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up"); + for (int j = 0; j < height; ++j) { + for (int i = 1; i < width; ++i) { + check(G.source(G.left(G(i, j))) == G(i, j), "Wrong left"); + check(G.target(G.left(G(i, j))) == G(i - 1, j), "Wrong left"); } - check(g.up(g(i, 0)) == INVALID, "Wrong up"); + check(G.left(G(0, j)) == INVALID, "Wrong left"); } - for (int j = 0; j < h; ++j) { - for (int i = 0; i < w - 1; ++i) { - check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right"); - check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right"); + for (int i = 0; i < width; ++i) { + for (int j = 0; j < height - 1; ++j) { + check(G.source(G.up(G(i, j))) == G(i, j), "Wrong up"); + check(G.target(G.up(G(i, j))) == G(i, j + 1), "Wrong up"); } - check(g.right(g(w - 1, j)) == INVALID, "Wrong right"); + check(G.up(G(i, height - 1)) == INVALID, "Wrong up"); } - for (int j = 0; j < h; ++j) { - for (int i = 1; i < w; ++i) { - check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left"); - check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left"); + for (int i = 0; i < width; ++i) { + for (int j = 1; j < height; ++j) { + check(G.source(G.down(G(i, j))) == G(i, j), "Wrong down"); + check(G.target(G.down(G(i, j))) == G(i, j - 1), "Wrong down"); } - check(g.left(g(0, j)) == INVALID, "Wrong left"); + check(G.down(G(i, 0)) == INVALID, "Wrong down"); } - checkGraphNodeList(g, w*h); - checkGraphArcList(g, 2*(2*w*h-w-h)); - checkGraphEdgeList(g, 2*w*h-w-h); + checkGraphNodeList(G, width * height); + checkGraphEdgeList(G, width * (height - 1) + (width - 1) * height); + checkGraphArcList(G, 2 * (width * (height - 1) + (width - 1) * height)); - checkGraphOutArcList(g, g(0,0), 2); - checkGraphOutArcList(g, g(0,1), 3); - checkGraphOutArcList(g, g(w-2,h-2), 4); + for (NodeIt n(G); n != INVALID; ++n) { + int nb = 4; + if (G.col(n) == 0) --nb; + if (G.col(n) == width - 1) --nb; + if (G.row(n) == 0) --nb; + if (G.row(n) == height - 1) --nb; - checkGraphInArcList(g, g(0,0), 2); - checkGraphInArcList(g, g(0,1), 3); - checkGraphInArcList(g, g(w-2,h-2), 4); + checkGraphOutArcList(G, n, nb); + checkGraphInArcList(G, n, nb); + checkGraphIncEdgeList(G, n, nb); + } - checkGraphIncEdgeList(g, g(0,0), 2); - checkGraphIncEdgeList(g, g(0,1), 3); - checkGraphIncEdgeList(g, g(w-2,h-2), 4); + checkArcDirections(G); - checkGraphConArcList(g, 2*(2*w*h-w-h)); - checkGraphConEdgeList(g, 2*w*h-w-h); + checkGraphConArcList(G, 2 * (width * (height - 1) + (width - 1) * height)); + checkGraphConEdgeList(G, width * (height - 1) + (width - 1) * height); - checkArcDirections(g); + checkNodeIds(G); + checkArcIds(G); + checkEdgeIds(G); + checkGraphNodeMap(G); + checkGraphArcMap(G); + checkGraphEdgeMap(G); - checkNodeIds(g); - checkArcIds(g); - checkEdgeIds(g); - checkGraphNodeMap(g); - checkGraphArcMap(g); - checkGraphEdgeMap(g); } void checkGraphs() { @@ -273,8 +281,11 @@ // checkGraphEdgeList(g, 10); // } { // Checking GridGraph - GridGraph g(5, 6); - checkGridGraph(g, 5, 6); + checkGridGraph(5, 8); + checkGridGraph(8, 5); + checkGridGraph(5, 5); + checkGridGraph(0, 0); + checkGridGraph(1, 1); } }