1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/doc/images/grid_ugraph.eps Fri Sep 29 11:25:27 2006 +0000
1.3 @@ -0,0 +1,303 @@
1.4 +%!PS-Adobe-2.0 EPSF-2.0
1.5 +%%Title: Grid undirected graph
1.6 +%%Copyright: (C) 2006 LEMON Project
1.7 +%%Creator: LEMON, graphToEps()
1.8 +%%CreationDate: Fri Sep 29 11:55:56 2006
1.9 +%%BoundingBox: 0 0 596 842
1.10 +%%DocumentPaperSizes: a4
1.11 +%%EndComments
1.12 +/lb { setlinewidth setrgbcolor newpath moveto
1.13 + 4 2 roll 1 index 1 index curveto stroke } bind def
1.14 +/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def
1.15 +/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def
1.16 +/sq { newpath 2 index 1 index add 2 index 2 index add moveto
1.17 + 2 index 1 index sub 2 index 2 index add lineto
1.18 + 2 index 1 index sub 2 index 2 index sub lineto
1.19 + 2 index 1 index add 2 index 2 index sub lineto
1.20 + closepath pop pop pop} bind def
1.21 +/di { newpath 2 index 1 index add 2 index moveto
1.22 + 2 index 2 index 2 index add lineto
1.23 + 2 index 1 index sub 2 index lineto
1.24 + 2 index 2 index 2 index sub lineto
1.25 + closepath pop pop pop} bind def
1.26 +/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill
1.27 + setrgbcolor 1.1 div c fill
1.28 + } bind def
1.29 +/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill
1.30 + setrgbcolor 1.1 div sq fill
1.31 + } bind def
1.32 +/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill
1.33 + setrgbcolor 1.1 div di fill
1.34 + } bind def
1.35 +/nfemale { 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
1.36 + newpath 5 index 5 index moveto 5 index 5 index 5 index 3.01 mul sub
1.37 + lineto 5 index 4 index .7 mul sub 5 index 5 index 2.2 mul sub moveto
1.38 + 5 index 4 index .7 mul add 5 index 5 index 2.2 mul sub lineto stroke
1.39 + 5 index 5 index 5 index c fill
1.40 + setrgbcolor 1.1 div c fill
1.41 + } bind def
1.42 +/nmale {
1.43 + 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
1.44 + newpath 5 index 5 index moveto
1.45 + 5 index 4 index 1 mul 1.5 mul add
1.46 + 5 index 5 index 3 sqrt 1.5 mul mul add
1.47 + 1 index 1 index lineto
1.48 + 1 index 1 index 7 index sub moveto
1.49 + 1 index 1 index lineto
1.50 + exch 5 index 3 sqrt .5 mul mul sub exch 5 index .5 mul sub lineto
1.51 + stroke
1.52 + 5 index 5 index 5 index c fill
1.53 + setrgbcolor 1.1 div c fill
1.54 + } bind def
1.55 +/arrl 1 def
1.56 +/arrw 0.3 def
1.57 +/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
1.58 +/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
1.59 + /w exch def /len exch def
1.60 + newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto
1.61 + len w sub arrl sub dx dy lrl
1.62 + arrw dy dx neg lrl
1.63 + dx arrl w add mul dy w 2 div arrw add mul sub
1.64 + dy arrl w add mul dx w 2 div arrw add mul add rlineto
1.65 + dx arrl w add mul neg dy w 2 div arrw add mul sub
1.66 + dy arrl w add mul neg dx w 2 div arrw add mul add rlineto
1.67 + arrw dy dx neg lrl
1.68 + len w sub arrl sub neg dx dy lrl
1.69 + closepath fill } bind def
1.70 +/cshow { 2 index 2 index moveto dup stringwidth pop
1.71 + neg 2 div fosi .35 mul neg rmoveto show pop pop} def
1.72 +
1.73 +gsave
1.74 +15 60.1011 translate
1.75 +7.8206 dup scale
1.76 +1.14018 1.14018 translate
1.77 +%Edges:
1.78 +gsave
1.79 +70 80 70 90 0 0 0 0.342053 l
1.80 +70 70 70 80 0 0 0 0.342053 l
1.81 +70 60 70 70 0 0 0 0.342053 l
1.82 +70 50 70 60 0 0 0 0.342053 l
1.83 +70 40 70 50 0 0 0 0.342053 l
1.84 +70 30 70 40 0 0 0 0.342053 l
1.85 +70 20 70 30 0 0 0 0.342053 l
1.86 +70 10 70 20 0 0 0 0.342053 l
1.87 +70 0 70 10 0 0 0 0.342053 l
1.88 +60 80 60 90 0 0 0 0.342053 l
1.89 +60 70 60 80 0 0 0 0.342053 l
1.90 +60 60 60 70 0 0 0 0.342053 l
1.91 +60 50 60 60 0 0 0 0.342053 l
1.92 +60 40 60 50 0 0 0 0.342053 l
1.93 +60 30 60 40 0 0 0 0.342053 l
1.94 +60 20 60 30 0 0 0 0.342053 l
1.95 +60 10 60 20 0 0 0 0.342053 l
1.96 +60 0 60 10 0 0 0 0.342053 l
1.97 +50 80 50 90 0 0 0 0.342053 l
1.98 +50 70 50 80 0 0 0 0.342053 l
1.99 +50 60 50 70 0 0 0 0.342053 l
1.100 +50 50 50 60 0 0 0 0.342053 l
1.101 +50 40 50 50 0 0 0 0.342053 l
1.102 +50 30 50 40 0 0 0 0.342053 l
1.103 +50 20 50 30 0 0 0 0.342053 l
1.104 +50 10 50 20 0 0 0 0.342053 l
1.105 +50 0 50 10 0 0 0 0.342053 l
1.106 +40 80 40 90 0 0 0 0.342053 l
1.107 +40 70 40 80 0 0 0 0.342053 l
1.108 +40 60 40 70 0 0 0 0.342053 l
1.109 +40 50 40 60 0 0 0 0.342053 l
1.110 +40 40 40 50 0 0 0 0.342053 l
1.111 +40 30 40 40 0 0 0 0.342053 l
1.112 +40 20 40 30 0 0 0 0.342053 l
1.113 +40 10 40 20 0 0 0 0.342053 l
1.114 +40 0 40 10 0 0 0 0.342053 l
1.115 +30 80 30 90 0 0 0 0.342053 l
1.116 +30 70 30 80 0 0 0 0.342053 l
1.117 +30 60 30 70 0 0 0 0.342053 l
1.118 +30 50 30 60 0 0 0 0.342053 l
1.119 +30 40 30 50 0 0 0 0.342053 l
1.120 +30 30 30 40 0 0 0 0.342053 l
1.121 +30 20 30 30 0 0 0 0.342053 l
1.122 +30 10 30 20 0 0 0 0.342053 l
1.123 +30 0 30 10 0 0 0 0.342053 l
1.124 +20 80 20 90 0 0 0 0.342053 l
1.125 +20 70 20 80 0 0 0 0.342053 l
1.126 +20 60 20 70 0 0 0 0.342053 l
1.127 +20 50 20 60 0 0 0 0.342053 l
1.128 +20 40 20 50 0 0 0 0.342053 l
1.129 +20 30 20 40 0 0 0 0.342053 l
1.130 +20 20 20 30 0 0 0 0.342053 l
1.131 +20 10 20 20 0 0 0 0.342053 l
1.132 +20 0 20 10 0 0 0 0.342053 l
1.133 +10 80 10 90 0 0 0 0.342053 l
1.134 +10 70 10 80 0 0 0 0.342053 l
1.135 +10 60 10 70 0 0 0 0.342053 l
1.136 +10 50 10 60 0 0 0 0.342053 l
1.137 +10 40 10 50 0 0 0 0.342053 l
1.138 +10 30 10 40 0 0 0 0.342053 l
1.139 +10 20 10 30 0 0 0 0.342053 l
1.140 +10 10 10 20 0 0 0 0.342053 l
1.141 +10 0 10 10 0 0 0 0.342053 l
1.142 +0 80 0 90 0 0 0 0.342053 l
1.143 +0 70 0 80 0 0 0 0.342053 l
1.144 +0 60 0 70 0 0 0 0.342053 l
1.145 +0 50 0 60 0 0 0 0.342053 l
1.146 +0 40 0 50 0 0 0 0.342053 l
1.147 +0 30 0 40 0 0 0 0.342053 l
1.148 +0 20 0 30 0 0 0 0.342053 l
1.149 +0 10 0 20 0 0 0 0.342053 l
1.150 +0 0 0 10 0 0 0 0.342053 l
1.151 +60 90 70 90 0 0 0 0.342053 l
1.152 +60 80 70 80 0 0 0 0.342053 l
1.153 +60 70 70 70 0 0 0 0.342053 l
1.154 +60 60 70 60 0 0 0 0.342053 l
1.155 +60 50 70 50 0 0 0 0.342053 l
1.156 +60 40 70 40 0 0 0 0.342053 l
1.157 +60 30 70 30 0 0 0 0.342053 l
1.158 +60 20 70 20 0 0 0 0.342053 l
1.159 +60 10 70 10 0 0 0 0.342053 l
1.160 +60 0 70 0 0 0 0 0.342053 l
1.161 +50 90 60 90 0 0 0 0.342053 l
1.162 +50 80 60 80 0 0 0 0.342053 l
1.163 +50 70 60 70 0 0 0 0.342053 l
1.164 +50 60 60 60 0 0 0 0.342053 l
1.165 +50 50 60 50 0 0 0 0.342053 l
1.166 +50 40 60 40 0 0 0 0.342053 l
1.167 +50 30 60 30 0 0 0 0.342053 l
1.168 +50 20 60 20 0 0 0 0.342053 l
1.169 +50 10 60 10 0 0 0 0.342053 l
1.170 +50 0 60 0 0 0 0 0.342053 l
1.171 +40 90 50 90 0 0 0 0.342053 l
1.172 +40 80 50 80 0 0 0 0.342053 l
1.173 +40 70 50 70 0 0 0 0.342053 l
1.174 +40 60 50 60 0 0 0 0.342053 l
1.175 +40 50 50 50 0 0 0 0.342053 l
1.176 +40 40 50 40 0 0 0 0.342053 l
1.177 +40 30 50 30 0 0 0 0.342053 l
1.178 +40 20 50 20 0 0 0 0.342053 l
1.179 +40 10 50 10 0 0 0 0.342053 l
1.180 +40 0 50 0 0 0 0 0.342053 l
1.181 +30 90 40 90 0 0 0 0.342053 l
1.182 +30 80 40 80 0 0 0 0.342053 l
1.183 +30 70 40 70 0 0 0 0.342053 l
1.184 +30 60 40 60 0 0 0 0.342053 l
1.185 +30 50 40 50 0 0 0 0.342053 l
1.186 +30 40 40 40 0 0 0 0.342053 l
1.187 +30 30 40 30 0 0 0 0.342053 l
1.188 +30 20 40 20 0 0 0 0.342053 l
1.189 +30 10 40 10 0 0 0 0.342053 l
1.190 +30 0 40 0 0 0 0 0.342053 l
1.191 +20 90 30 90 0 0 0 0.342053 l
1.192 +20 80 30 80 0 0 0 0.342053 l
1.193 +20 70 30 70 0 0 0 0.342053 l
1.194 +20 60 30 60 0 0 0 0.342053 l
1.195 +20 50 30 50 0 0 0 0.342053 l
1.196 +20 40 30 40 0 0 0 0.342053 l
1.197 +20 30 30 30 0 0 0 0.342053 l
1.198 +20 20 30 20 0 0 0 0.342053 l
1.199 +20 10 30 10 0 0 0 0.342053 l
1.200 +20 0 30 0 0 0 0 0.342053 l
1.201 +10 90 20 90 0 0 0 0.342053 l
1.202 +10 80 20 80 0 0 0 0.342053 l
1.203 +10 70 20 70 0 0 0 0.342053 l
1.204 +10 60 20 60 0 0 0 0.342053 l
1.205 +10 50 20 50 0 0 0 0.342053 l
1.206 +10 40 20 40 0 0 0 0.342053 l
1.207 +10 30 20 30 0 0 0 0.342053 l
1.208 +10 20 20 20 0 0 0 0.342053 l
1.209 +10 10 20 10 0 0 0 0.342053 l
1.210 +10 0 20 0 0 0 0 0.342053 l
1.211 +0 90 10 90 0 0 0 0.342053 l
1.212 +0 80 10 80 0 0 0 0.342053 l
1.213 +0 70 10 70 0 0 0 0.342053 l
1.214 +0 60 10 60 0 0 0 0.342053 l
1.215 +0 50 10 50 0 0 0 0.342053 l
1.216 +0 40 10 40 0 0 0 0.342053 l
1.217 +0 30 10 30 0 0 0 0.342053 l
1.218 +0 20 10 20 0 0 0 0.342053 l
1.219 +0 10 10 10 0 0 0 0.342053 l
1.220 +0 0 10 0 0 0 0 0.342053 l
1.221 +grestore
1.222 +%Nodes:
1.223 +gsave
1.224 +70 90 1.14018 1 1 1 nc
1.225 +70 80 1.14018 1 1 1 nc
1.226 +70 70 1.14018 1 1 1 nc
1.227 +70 60 1.14018 1 1 1 nc
1.228 +70 50 1.14018 1 1 1 nc
1.229 +70 40 1.14018 1 1 1 nc
1.230 +70 30 1.14018 1 1 1 nc
1.231 +70 20 1.14018 1 1 1 nc
1.232 +70 10 1.14018 1 1 1 nc
1.233 +70 0 1.14018 1 1 1 nc
1.234 +60 90 1.14018 1 1 1 nc
1.235 +60 80 1.14018 1 1 1 nc
1.236 +60 70 1.14018 1 1 1 nc
1.237 +60 60 1.14018 1 1 1 nc
1.238 +60 50 1.14018 1 1 1 nc
1.239 +60 40 1.14018 1 1 1 nc
1.240 +60 30 1.14018 1 1 1 nc
1.241 +60 20 1.14018 1 1 1 nc
1.242 +60 10 1.14018 1 1 1 nc
1.243 +60 0 1.14018 1 1 1 nc
1.244 +50 90 1.14018 1 1 1 nc
1.245 +50 80 1.14018 1 1 1 nc
1.246 +50 70 1.14018 1 1 1 nc
1.247 +50 60 1.14018 1 1 1 nc
1.248 +50 50 1.14018 1 1 1 nc
1.249 +50 40 1.14018 1 1 1 nc
1.250 +50 30 1.14018 1 1 1 nc
1.251 +50 20 1.14018 1 1 1 nc
1.252 +50 10 1.14018 1 1 1 nc
1.253 +50 0 1.14018 1 1 1 nc
1.254 +40 90 1.14018 1 1 1 nc
1.255 +40 80 1.14018 1 1 1 nc
1.256 +40 70 1.14018 1 1 1 nc
1.257 +40 60 1.14018 1 1 1 nc
1.258 +40 50 1.14018 1 1 1 nc
1.259 +40 40 1.14018 1 1 1 nc
1.260 +40 30 1.14018 1 1 1 nc
1.261 +40 20 1.14018 1 1 1 nc
1.262 +40 10 1.14018 1 1 1 nc
1.263 +40 0 1.14018 1 1 1 nc
1.264 +30 90 1.14018 1 1 1 nc
1.265 +30 80 1.14018 1 1 1 nc
1.266 +30 70 1.14018 1 1 1 nc
1.267 +30 60 1.14018 1 1 1 nc
1.268 +30 50 1.14018 1 1 1 nc
1.269 +30 40 1.14018 1 1 1 nc
1.270 +30 30 1.14018 1 1 1 nc
1.271 +30 20 1.14018 1 1 1 nc
1.272 +30 10 1.14018 1 1 1 nc
1.273 +30 0 1.14018 1 1 1 nc
1.274 +20 90 1.14018 1 1 1 nc
1.275 +20 80 1.14018 1 1 1 nc
1.276 +20 70 1.14018 1 1 1 nc
1.277 +20 60 1.14018 1 1 1 nc
1.278 +20 50 1.14018 1 1 1 nc
1.279 +20 40 1.14018 1 1 1 nc
1.280 +20 30 1.14018 1 1 1 nc
1.281 +20 20 1.14018 1 1 1 nc
1.282 +20 10 1.14018 1 1 1 nc
1.283 +20 0 1.14018 1 1 1 nc
1.284 +10 90 1.14018 1 1 1 nc
1.285 +10 80 1.14018 1 1 1 nc
1.286 +10 70 1.14018 1 1 1 nc
1.287 +10 60 1.14018 1 1 1 nc
1.288 +10 50 1.14018 1 1 1 nc
1.289 +10 40 1.14018 1 1 1 nc
1.290 +10 30 1.14018 1 1 1 nc
1.291 +10 20 1.14018 1 1 1 nc
1.292 +10 10 1.14018 1 1 1 nc
1.293 +10 0 1.14018 1 1 1 nc
1.294 +0 90 1.14018 1 1 1 nc
1.295 +0 80 1.14018 1 1 1 nc
1.296 +0 70 1.14018 1 1 1 nc
1.297 +0 60 1.14018 1 1 1 nc
1.298 +0 50 1.14018 1 1 1 nc
1.299 +0 40 1.14018 1 1 1 nc
1.300 +0 30 1.14018 1 1 1 nc
1.301 +0 20 1.14018 1 1 1 nc
1.302 +0 10 1.14018 1 1 1 nc
1.303 +0 0 1.14018 1 1 1 nc
1.304 +grestore
1.305 +grestore
1.306 +showpage
2.1 Binary file doc/images/grid_ugraph.png has changed
3.1 --- a/lemon/full_graph.h Fri Sep 29 11:23:54 2006 +0000
3.2 +++ b/lemon/full_graph.h Fri Sep 29 11:25:27 2006 +0000
3.3 @@ -35,9 +35,6 @@
3.4
3.5 namespace lemon {
3.6
3.7 - /// \brief Base of the FullGrpah.
3.8 - ///
3.9 - /// Base of the FullGrpah.
3.10 class FullGraphBase {
3.11 int _nodeNum;
3.12 int _edgeNum;
3.13 @@ -48,71 +45,35 @@
3.14 class Node;
3.15 class Edge;
3.16
3.17 - public:
3.18 + protected:
3.19
3.20 FullGraphBase() {}
3.21
3.22 + void construct(int n) { _nodeNum = n; _edgeNum = n * n; }
3.23
3.24 - ///Creates a full graph with \c n nodes.
3.25 - void construct(int n) { _nodeNum = n; _edgeNum = n * n; }
3.26 + public:
3.27
3.28 typedef True NodeNumTag;
3.29 typedef True EdgeNumTag;
3.30
3.31 - /// \brief Returns the node with the given index.
3.32 - ///
3.33 - /// Returns the node with the given index. Because it is a
3.34 - /// static size graph the node's of the graph can be indiced
3.35 - /// by the range from 0 to \e nodeNum()-1 and the index of
3.36 - /// the node can accessed by the \e index() member.
3.37 Node operator()(int index) const { return Node(index); }
3.38 -
3.39 - /// \brief Returns the index of the node.
3.40 - ///
3.41 - /// Returns the index of the node. Because it is a
3.42 - /// static size graph the node's of the graph can be indiced
3.43 - /// by the range from 0 to \e nodeNum()-1 and the index of
3.44 - /// the node can accessed by the \e index() member.
3.45 int index(const Node& node) const { return node.id; }
3.46
3.47 - ///Number of nodes.
3.48 + Edge edge(const Node& u, const Node& v) const {
3.49 + return Edge(*this, u.id, v.id);
3.50 + }
3.51 +
3.52 int nodeNum() const { return _nodeNum; }
3.53 - ///Number of edges.
3.54 int edgeNum() const { return _edgeNum; }
3.55
3.56 - /// Maximum node ID.
3.57 -
3.58 - /// Maximum node ID.
3.59 - ///\sa id(Node)
3.60 int maxNodeId() const { return _nodeNum-1; }
3.61 - /// Maximum edge ID.
3.62 -
3.63 - /// Maximum edge ID.
3.64 - ///\sa id(Edge)
3.65 int maxEdgeId() const { return _edgeNum-1; }
3.66
3.67 Node source(Edge e) const { return e.id % _nodeNum; }
3.68 Node target(Edge e) const { return e.id / _nodeNum; }
3.69
3.70
3.71 - /// Node ID.
3.72 -
3.73 - /// The ID of a valid Node is a nonnegative integer not greater than
3.74 - /// \ref maxNodeId(). The range of the ID's is not surely continuous
3.75 - /// and the greatest node ID can be actually less then \ref maxNodeId().
3.76 - ///
3.77 - /// The ID of the \ref INVALID node is -1.
3.78 - ///\return The ID of the node \c v.
3.79 -
3.80 static int id(Node v) { return v.id; }
3.81 - /// Edge ID.
3.82 -
3.83 - /// The ID of a valid Edge is a nonnegative integer not greater than
3.84 - /// \ref maxEdgeId(). The range of the ID's is not surely continuous
3.85 - /// and the greatest edge ID can be actually less then \ref maxEdgeId().
3.86 - ///
3.87 - /// The ID of the \ref INVALID edge is -1.
3.88 - ///\return The ID of the edge \c e.
3.89 static int id(Edge e) { return e.id; }
3.90
3.91 static Node nodeFromId(int id) { return Node(id);}
3.92 @@ -121,14 +82,6 @@
3.93
3.94 typedef True FindEdgeTag;
3.95
3.96 - /// Finds an edge between two nodes.
3.97 -
3.98 - /// Finds an edge from node \c u to node \c v.
3.99 - ///
3.100 - /// If \c prev is \ref INVALID (this is the default value), then
3.101 - /// It finds the first edge from \c u to \c v. Otherwise it looks for
3.102 - /// the next edge from \c u to \c v after \c prev.
3.103 - /// \return The found edge or INVALID if there is no such an edge.
3.104 Edge findEdge(Node u,Node v, Edge prev = INVALID) const {
3.105 return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID;
3.106 }
3.107 @@ -217,7 +170,6 @@
3.108 /// the \ref concept::Graph "Graph" concept
3.109 /// \sa concept::Graph.
3.110 ///
3.111 - /// \sa FullGraphBase
3.112 /// \sa FullUGraph
3.113 ///
3.114 /// \author Alpar Juttner
3.115 @@ -245,12 +197,37 @@
3.116 Parent::getNotifier(Node()).build();
3.117 Parent::getNotifier(Edge()).build();
3.118 }
3.119 +
3.120 + /// \brief Returns the node with the given index.
3.121 + ///
3.122 + /// Returns the node with the given index. Because it is a
3.123 + /// static size graph the node's of the graph can be indiced
3.124 + /// by the range from 0 to \e nodeNum()-1 and the index of
3.125 + /// the node can accessed by the \e index() member.
3.126 + Node operator()(int index) const { return Parent::operator()(index); }
3.127 +
3.128 + /// \brief Returns the index of the node.
3.129 + ///
3.130 + /// Returns the index of the node. Because it is a
3.131 + /// static size graph the node's of the graph can be indiced
3.132 + /// by the range from 0 to \e nodeNum()-1 and the index of
3.133 + /// the node can accessed by the \e index() member.
3.134 + int index(const Node& node) const { return Parent::index(node); }
3.135 +
3.136 + /// \brief Returns the edge connects the given nodes.
3.137 + ///
3.138 + /// Returns the edge connects the given nodes.
3.139 + Edge edge(const Node& u, const Node& v) const {
3.140 + return Parent::edge(u, v);
3.141 + }
3.142 +
3.143 + /// \brief Number of nodes.
3.144 + int nodeNum() const { return Parent::nodeNum(); }
3.145 + /// \brief Number of edges.
3.146 + int edgeNum() const { return Parent::edgeNum(); }
3.147 };
3.148
3.149
3.150 - /// \brief Base of the FullUGrpah.
3.151 - ///
3.152 - /// Base of the FullUGrpah.
3.153 class FullUGraphBase {
3.154 int _nodeNum;
3.155 int _edgeNum;
3.156 @@ -261,59 +238,32 @@
3.157 class Node;
3.158 class Edge;
3.159
3.160 - public:
3.161 + protected:
3.162
3.163 FullUGraphBase() {}
3.164
3.165 -
3.166 - ///Creates a full graph with \c n nodes.
3.167 void construct(int n) { _nodeNum = n; _edgeNum = n * (n - 1) / 2; }
3.168
3.169 - /// \brief Returns the node with the given index.
3.170 - ///
3.171 - /// Returns the node with the given index. Because it is a
3.172 - /// static size graph the node's of the graph can be indiced
3.173 - /// by the range from 0 to \e nodeNum()-1 and the index of
3.174 - /// the node can accessed by the \e index() member.
3.175 + public:
3.176 +
3.177 +
3.178 Node operator()(int index) const { return Node(index); }
3.179 + int index(const Node& node) const { return node.id; }
3.180
3.181 - /// \brief Returns the index of the node.
3.182 - ///
3.183 - /// Returns the index of the node. Because it is a
3.184 - /// static size graph the node's of the graph can be indiced
3.185 - /// by the range from 0 to \e nodeNum()-1 and the index of
3.186 - /// the node can accessed by the \e index() member.
3.187 - int index(const Node& node) const { return node.id; }
3.188 + Edge edge(const Node& u, const Node& v) const {
3.189 + return Edge(u.id * (u.id - 1) / 2 + v.id);
3.190 + }
3.191
3.192 typedef True NodeNumTag;
3.193 typedef True EdgeNumTag;
3.194
3.195 - ///Number of nodes.
3.196 int nodeNum() const { return _nodeNum; }
3.197 - ///Number of edges.
3.198 int edgeNum() const { return _edgeNum; }
3.199
3.200 - /// Maximum node ID.
3.201 -
3.202 - /// Maximum node ID.
3.203 - ///\sa id(Node)
3.204 int maxNodeId() const { return _nodeNum-1; }
3.205 - /// Maximum edge ID.
3.206 -
3.207 - /// Maximum edge ID.
3.208 - ///\sa id(Edge)
3.209 int maxEdgeId() const { return _edgeNum-1; }
3.210
3.211 - /// \brief Returns the node from its \c id.
3.212 - ///
3.213 - /// Returns the node from its \c id. If there is not node
3.214 - /// with the given id the effect of the function is undefinied.
3.215 static Node nodeFromId(int id) { return Node(id);}
3.216 -
3.217 - /// \brief Returns the edge from its \c id.
3.218 - ///
3.219 - /// Returns the edge from its \c id. If there is not edge
3.220 - /// with the given id the effect of the function is undefinied.
3.221 static Edge edgeFromId(int id) { return Edge(id);}
3.222
3.223 Node source(Edge e) const {
3.224 @@ -326,36 +276,9 @@
3.225 return Node(e.id - (source) * (source - 1) / 2);
3.226 }
3.227
3.228 -
3.229 - /// \brief Node ID.
3.230 - ///
3.231 - /// The ID of a valid Node is a nonnegative integer not greater than
3.232 - /// \ref maxNodeId(). The range of the ID's is not surely continuous
3.233 - /// and the greatest node ID can be actually less then \ref maxNodeId().
3.234 - ///
3.235 - /// The ID of the \ref INVALID node is -1.
3.236 - /// \return The ID of the node \c v.
3.237 -
3.238 static int id(Node v) { return v.id; }
3.239 -
3.240 - /// \brief Edge ID.
3.241 - ///
3.242 - /// The ID of a valid Edge is a nonnegative integer not greater than
3.243 - /// \ref maxEdgeId(). The range of the ID's is not surely continuous
3.244 - /// and the greatest edge ID can be actually less then \ref maxEdgeId().
3.245 - ///
3.246 - /// The ID of the \ref INVALID edge is -1.
3.247 - ///\return The ID of the edge \c e.
3.248 static int id(Edge e) { return e.id; }
3.249
3.250 - /// \brief Finds an edge between two nodes.
3.251 - ///
3.252 - /// Finds an edge from node \c u to node \c v.
3.253 - ///
3.254 - /// If \c prev is \ref INVALID (this is the default value), then
3.255 - /// It finds the first edge from \c u to \c v. Otherwise it looks for
3.256 - /// the next edge from \c u to \c v after \c prev.
3.257 - /// \return The found edge or INVALID if there is no such an edge.
3.258 Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
3.259 if (prev.id != -1 || u.id <= v.id) return Edge(-1);
3.260 return Edge(u.id * (u.id - 1) / 2 + v.id);
3.261 @@ -456,7 +379,6 @@
3.262 /// is that this class conforms to the undirected graph concept and
3.263 /// it does not contain the loop edges.
3.264 ///
3.265 - /// \sa FullUGraphBase
3.266 /// \sa FullGraph
3.267 ///
3.268 /// \author Balazs Dezso
3.269 @@ -485,6 +407,55 @@
3.270 Parent::getNotifier(UEdge()).build();
3.271 Parent::getNotifier(Edge()).build();
3.272 }
3.273 +
3.274 + /// \brief Returns the node with the given index.
3.275 + ///
3.276 + /// Returns the node with the given index. Because it is a
3.277 + /// static size graph the node's of the graph can be indiced
3.278 + /// by the range from 0 to \e nodeNum()-1 and the index of
3.279 + /// the node can accessed by the \e index() member.
3.280 + Node operator()(int index) const { return Parent::operator()(index); }
3.281 +
3.282 + /// \brief Returns the index of the node.
3.283 + ///
3.284 + /// Returns the index of the node. Because it is a
3.285 + /// static size graph the node's of the graph can be indiced
3.286 + /// by the range from 0 to \e nodeNum()-1 and the index of
3.287 + /// the node can accessed by the \e index() member.
3.288 + int index(const Node& node) const { return Parent::index(node); }
3.289 +
3.290 + /// \brief Number of nodes.
3.291 + int nodeNum() const { return Parent::nodeNum(); }
3.292 + /// \brief Number of edges.
3.293 + int edgeNum() const { return Parent::edgeNum(); }
3.294 + /// \brief Number of undirected edges.
3.295 + int uEdgeNum() const { return Parent::uEdgeNum(); }
3.296 +
3.297 + /// \brief Returns the edge connects the given nodes.
3.298 + ///
3.299 + /// Returns the edge connects the given nodes.
3.300 + Edge edge(const Node& u, const Node& v) const {
3.301 + if (Parent::index(u) > Parent::index(v)) {
3.302 + return Parent::direct(Parent::edge(u, v), true);
3.303 + } else if (Parent::index(u) == Parent::index(v)) {
3.304 + return INVALID;
3.305 + } else {
3.306 + return Parent::direct(Parent::edge(v, u), false);
3.307 + }
3.308 + }
3.309 +
3.310 + /// \brief Returns the undirected edge connects the given nodes.
3.311 + ///
3.312 + /// Returns the undirected edge connects the given nodes.
3.313 + UEdge uEdge(const Node& u, const Node& v) const {
3.314 + if (Parent::index(u) > Parent::index(v)) {
3.315 + return Parent::edge(u, v);
3.316 + } else if (Parent::index(u) == Parent::index(v)) {
3.317 + return INVALID;
3.318 + } else {
3.319 + return Parent::edge(v, u);
3.320 + }
3.321 + }
3.322 };
3.323
3.324
3.325 @@ -496,6 +467,16 @@
3.326
3.327 int _edgeNum;
3.328
3.329 + protected:
3.330 +
3.331 + FullBpUGraphBase() {}
3.332 +
3.333 + void construct(int aNodeNum, int bNodeNum) {
3.334 + _aNodeNum = aNodeNum;
3.335 + _bNodeNum = bNodeNum;
3.336 + _edgeNum = aNodeNum * bNodeNum;
3.337 + }
3.338 +
3.339 public:
3.340
3.341 class NodeSetError : public LogicError {
3.342 @@ -533,10 +514,20 @@
3.343 bool operator<(const UEdge i) const {return id<i.id;}
3.344 };
3.345
3.346 - void construct(int aNodeNum, int bNodeNum) {
3.347 - _aNodeNum = aNodeNum;
3.348 - _bNodeNum = bNodeNum;
3.349 - _edgeNum = aNodeNum * bNodeNum;
3.350 + Node aNode(int index) const { return Node(index << 1); }
3.351 + Node bNode(int index) const { return Node((index << 1) + 1); }
3.352 +
3.353 + int aNodeIndex(const Node& node) const { return node.id >> 1; }
3.354 + int bNodeIndex(const Node& node) const { return node.id >> 1; }
3.355 +
3.356 + UEdge uEdge(const Node& u, const Node& v) const {
3.357 + if (((u.id ^ v.id) & 1) != 1) {
3.358 + return UEdge(-1);
3.359 + } else if ((u.id & 1) == 0) {
3.360 + return UEdge((u.id >> 1) * _bNodeNum + (v.id >> 1));
3.361 + } else {
3.362 + return UEdge((v.id >> 1) * _bNodeNum + (u.id >> 1));
3.363 + }
3.364 }
3.365
3.366 void firstANode(Node& node) const {
3.367 @@ -650,13 +641,6 @@
3.368 return (node.id & 1) == 1;
3.369 }
3.370
3.371 - static Node aNode(int index) {
3.372 - return Node(index << 1);
3.373 - }
3.374 -
3.375 - static Node bNode(int index) {
3.376 - return Node((index << 1) + 1);
3.377 - }
3.378
3.379 typedef True NodeNumTag;
3.380 int nodeNum() const { return _aNodeNum + _bNodeNum; }
3.381 @@ -666,6 +650,18 @@
3.382 typedef True EdgeNumTag;
3.383 int uEdgeNum() const { return _edgeNum; }
3.384
3.385 +
3.386 + typedef True FindEdgeTag;
3.387 + UEdge findUEdge(Node u, Node v, UEdge prev = INVALID) const {
3.388 + if (prev.id != -1 || ((u.id ^ v.id) & 1) != 1) {
3.389 + return UEdge(-1);
3.390 + } else if ((u.id & 1) == 0) {
3.391 + return UEdge((u.id >> 1) * _bNodeNum + (v.id >> 1));
3.392 + } else {
3.393 + return UEdge((v.id >> 1) * _bNodeNum + (u.id >> 1));
3.394 + }
3.395 + }
3.396 +
3.397 };
3.398
3.399
3.400 @@ -680,9 +676,6 @@
3.401 /// It is completely static, so you can neither add nor delete either
3.402 /// edges or nodes.
3.403 ///
3.404 - /// \sa FullUGraphBase
3.405 - /// \sa FullGraph
3.406 - ///
3.407 /// \author Balazs Dezso
3.408 class FullBpUGraph :
3.409 public ExtendedFullBpUGraphBase {
3.410 @@ -700,6 +693,7 @@
3.411
3.412 /// \brief Resize the graph
3.413 ///
3.414 + /// Resize the graph
3.415 void resize(int n, int m) {
3.416 Parent::getNotifier(Edge()).clear();
3.417 Parent::getNotifier(UEdge()).clear();
3.418 @@ -713,6 +707,72 @@
3.419 Parent::getNotifier(UEdge()).build();
3.420 Parent::getNotifier(Edge()).build();
3.421 }
3.422 +
3.423 + /// \brief Number of nodes.
3.424 + int nodeNum() const { return Parent::nodeNum(); }
3.425 + /// \brief Number of A-nodes.
3.426 + int aNodeNum() const { return Parent::aNodeNum(); }
3.427 + /// \brief Number of B-nodes.
3.428 + int bNodeNum() const { return Parent::bNodeNum(); }
3.429 + /// \brief Number of edges.
3.430 + int edgeNum() const { return Parent::edgeNum(); }
3.431 + /// \brief Number of undirected edges.
3.432 + int uEdgeNum() const { return Parent::uEdgeNum(); }
3.433 +
3.434 +
3.435 + using Parent::aNode;
3.436 + using Parent::bNode;
3.437 +
3.438 + /// \brief Returns the A-node with the given index.
3.439 + ///
3.440 + /// Returns the A-node with the given index. Because it is a
3.441 + /// static size graph the node's of the graph can be indiced
3.442 + /// by the range from 0 to \e aNodeNum()-1 and the index of
3.443 + /// the node can accessed by the \e aNodeIndex() member.
3.444 + Node aNode(int index) const { return Parent::aNode(index); }
3.445 +
3.446 + /// \brief Returns the B-node with the given index.
3.447 + ///
3.448 + /// Returns the B-node with the given index. Because it is a
3.449 + /// static size graph the node's of the graph can be indiced
3.450 + /// by the range from 0 to \e bNodeNum()-1 and the index of
3.451 + /// the node can accessed by the \e bNodeIndex() member.
3.452 + Node bNode(int index) const { return Parent::bNode(index); }
3.453 +
3.454 + /// \brief Returns the index of the A-node.
3.455 + ///
3.456 + /// Returns the index of the A-node. Because it is a
3.457 + /// static size graph the node's of the graph can be indiced
3.458 + /// by the range from 0 to \e aNodeNum()-1 and the index of
3.459 + /// the node can accessed by the \e aNodeIndex() member.
3.460 + int aNodeIndex(const Node& node) const { return Parent::aNodeIndex(node); }
3.461 +
3.462 + /// \brief Returns the index of the B-node.
3.463 + ///
3.464 + /// Returns the index of the B-node. Because it is a
3.465 + /// static size graph the node's of the graph can be indiced
3.466 + /// by the range from 0 to \e bNodeNum()-1 and the index of
3.467 + /// the node can accessed by the \e bNodeIndex() member.
3.468 + int bNodeIndex(const Node& node) const { return Parent::bNodeIndex(node); }
3.469 +
3.470 + /// \brief Returns the edge connects the given nodes.
3.471 + ///
3.472 + /// Returns the edge connects the given nodes.
3.473 + Edge edge(const Node& u, const Node& v) const {
3.474 + UEdge uedge = Parent::uEdge(u, v);
3.475 + if (uedge != INVALID) {
3.476 + return Parent::direct(uedge, Parent::aNode(u));
3.477 + } else {
3.478 + return INVALID;
3.479 + }
3.480 + }
3.481 +
3.482 + /// \brief Returns the undirected edge connects the given nodes.
3.483 + ///
3.484 + /// Returns the undirected edge connects the given nodes.
3.485 + UEdge uEdge(const Node& u, const Node& v) const {
3.486 + return Parent::uEdge(u, v);
3.487 + }
3.488 };
3.489
3.490 } //namespace lemon
4.1 --- a/lemon/grid_ugraph.h Fri Sep 29 11:23:54 2006 +0000
4.2 +++ b/lemon/grid_ugraph.h Fri Sep 29 11:25:27 2006 +0000
4.3 @@ -34,13 +34,6 @@
4.4
4.5 namespace lemon {
4.6
4.7 - /// \brief Base graph for GridUGraph.
4.8 - ///
4.9 - /// Base graph for grid graph. It describes some member functions
4.10 - /// which can be used in the GridUGraph.
4.11 - ///
4.12 - /// \warning Always use the GridUGraph instead of this.
4.13 - /// \see GridUGraph
4.14 class GridUGraphBase {
4.15
4.16 public:
4.17 @@ -56,19 +49,12 @@
4.18
4.19 protected:
4.20
4.21 - /// \brief Creates a grid graph with the given size.
4.22 - ///
4.23 - /// Creates a grid graph with the given size.
4.24 void construct(int width, int height) {
4.25 _height = height; _width = width;
4.26 _nodeNum = height * width; _edgeNum = 2 * _nodeNum - width - height;
4.27 _edgeLimit = _nodeNum - width;
4.28 }
4.29
4.30 - /// \brief Gives back the edge goes down from the node.
4.31 - ///
4.32 - /// Gives back the edge goes down from the node. If there is not
4.33 - /// outgoing edge then it gives back INVALID.
4.34 Edge _down(Node n) const {
4.35 if (n.id < _nodeNum - _width) {
4.36 return Edge(n.id);
4.37 @@ -77,10 +63,6 @@
4.38 }
4.39 }
4.40
4.41 - /// \brief Gives back the edge comes from up into the node.
4.42 - ///
4.43 - /// Gives back the edge comes from up into the node. If there is not
4.44 - /// incoming edge then it gives back INVALID.
4.45 Edge _up(Node n) const {
4.46 if (n.id >= _width) {
4.47 return Edge(n.id - _width);
4.48 @@ -89,10 +71,6 @@
4.49 }
4.50 }
4.51
4.52 - /// \brief Gives back the edge goes right from the node.
4.53 - ///
4.54 - /// Gives back the edge goes right from the node. If there is not
4.55 - /// outgoing edge then it gives back INVALID.
4.56 Edge _right(Node n) const {
4.57 if (n.id % _width < _width - 1) {
4.58 return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1);
4.59 @@ -101,10 +79,6 @@
4.60 }
4.61 }
4.62
4.63 - /// \brief Gives back the edge comes from left into the node.
4.64 - ///
4.65 - /// Gives back the edge comes left up into the node. If there is not
4.66 - /// incoming edge then it gives back INVALID.
4.67 Edge _left(Node n) const {
4.68 if (n.id % _width > 0) {
4.69 return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1) - 1;
4.70 @@ -123,39 +97,24 @@
4.71 };
4.72
4.73
4.74 - /// \brief The node on the given position.
4.75 - ///
4.76 - /// Gives back the node on the given position.
4.77 Node operator()(int i, int j) const {
4.78 LEMON_ASSERT(0 <= i && i < width() && 0 <= j &&
4.79 j < height(), IndexError());
4.80 return Node(i + j * _width);
4.81 }
4.82
4.83 - /// \brief Gives back the row index of the node.
4.84 - ///
4.85 - /// Gives back the row index of the node.
4.86 int row(Node n) const {
4.87 return n.id / _width;
4.88 }
4.89
4.90 - /// \brief Gives back the coloumn index of the node.
4.91 - ///
4.92 - /// Gives back the coloumn index of the node.
4.93 int col(Node n) const {
4.94 return n.id % _width;
4.95 }
4.96
4.97 - /// \brief Gives back the width of the graph.
4.98 - ///
4.99 - /// Gives back the width of the graph.
4.100 int width() const {
4.101 return _width;
4.102 }
4.103
4.104 - /// \brief Gives back the height of the graph.
4.105 - ///
4.106 - /// Gives back the height of the graph.
4.107 int height() const {
4.108 return _height;
4.109 }
4.110 @@ -163,25 +122,12 @@
4.111 typedef True NodeNumTag;
4.112 typedef True EdgeNumTag;
4.113
4.114 - ///Number of nodes.
4.115 int nodeNum() const { return _nodeNum; }
4.116 - ///Number of edges.
4.117 int edgeNum() const { return _edgeNum; }
4.118
4.119 - /// Maximum node ID.
4.120 -
4.121 - /// Maximum node ID.
4.122 - ///\sa id(Node)
4.123 int maxNodeId() const { return nodeNum() - 1; }
4.124 - /// Maximum edge ID.
4.125 -
4.126 - /// Maximum edge ID.
4.127 - ///\sa id(Edge)
4.128 int maxEdgeId() const { return edgeNum() - 1; }
4.129
4.130 - /// \brief Gives back the source node of an edge.
4.131 - ///
4.132 - /// Gives back the source node of an edge.
4.133 Node source(Edge e) const {
4.134 if (e.id < _edgeLimit) {
4.135 return e.id;
4.136 @@ -191,9 +137,6 @@
4.137 }
4.138 }
4.139
4.140 - /// \brief Gives back the target node of an edge.
4.141 - ///
4.142 - /// Gives back the target node of an edge.
4.143 Node target(Edge e) const {
4.144 if (e.id < _edgeLimit) {
4.145 return e.id + _width;
4.146 @@ -203,24 +146,7 @@
4.147 }
4.148 }
4.149
4.150 - /// Node ID.
4.151 -
4.152 - /// The ID of a valid Node is a nonnegative integer not greater than
4.153 - /// \ref maxNodeId(). The range of the ID's is not surely continuous
4.154 - /// and the greatest node ID can be actually less then \ref maxNodeId().
4.155 - ///
4.156 - /// The ID of the \ref INVALID node is -1.
4.157 - ///\return The ID of the node \c v.
4.158 -
4.159 static int id(Node v) { return v.id; }
4.160 - /// Edge ID.
4.161 -
4.162 - /// The ID of a valid Edge is a nonnegative integer not greater than
4.163 - /// \ref maxEdgeId(). The range of the ID's is not surely continuous
4.164 - /// and the greatest edge ID can be actually less then \ref maxEdgeId().
4.165 - ///
4.166 - /// The ID of the \ref INVALID edge is -1.
4.167 - ///\return The ID of the edge \c e.
4.168 static int id(Edge e) { return e.id; }
4.169
4.170 static Node nodeFromId(int id) { return Node(id);}
4.171 @@ -229,14 +155,6 @@
4.172
4.173 typedef True FindEdgeTag;
4.174
4.175 - /// Finds an edge between two nodes.
4.176 -
4.177 - /// Finds an edge from node \c u to node \c v.
4.178 - ///
4.179 - /// If \c prev is \ref INVALID (this is the default value), then
4.180 - /// It finds the first edge from \c u to \c v. Otherwise it looks for
4.181 - /// the next edge from \c u to \c v after \c prev.
4.182 - /// \return The found edge or INVALID if there is no such an edge.
4.183 Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
4.184 if (prev != INVALID) return INVALID;
4.185 if (v.id - u.id == _width) return Edge(u.id);
4.186 @@ -360,6 +278,9 @@
4.187 /// Two nodes are connected in the graph if the indices differ only
4.188 /// on one position and only one is the difference.
4.189 ///
4.190 + /// \image html grid_ugraph.png
4.191 + /// \image latex grid_ugraph.eps "Grid graph" width=\textwidth
4.192 + ///
4.193 /// The graph can be indiced in the following way:
4.194 ///\code
4.195 /// GridUGraph graph(w, h);
4.196 @@ -375,7 +296,6 @@
4.197 /// "Undirected Graph" concept.
4.198 ///
4.199 /// \author Balazs Dezso
4.200 - /// \see GridUGraphBase
4.201 class GridUGraph : public ExtendedGridUGraphBase {
4.202 public:
4.203
4.204 @@ -476,6 +396,41 @@
4.205 Parent::getNotifier(Edge()).build();
4.206 }
4.207
4.208 + /// \brief The node on the given position.
4.209 + ///
4.210 + /// Gives back the node on the given position.
4.211 + Node operator()(int i, int j) const {
4.212 + return Parent::operator()(i, j);
4.213 + }
4.214 +
4.215 + /// \brief Gives back the row index of the node.
4.216 + ///
4.217 + /// Gives back the row index of the node.
4.218 + int row(Node n) const {
4.219 + return Parent::row(n);
4.220 + }
4.221 +
4.222 + /// \brief Gives back the coloumn index of the node.
4.223 + ///
4.224 + /// Gives back the coloumn index of the node.
4.225 + int col(Node n) const {
4.226 + return Parent::col(n);
4.227 + }
4.228 +
4.229 + /// \brief Gives back the width of the graph.
4.230 + ///
4.231 + /// Gives back the width of the graph.
4.232 + int width() const {
4.233 + return Parent::width();
4.234 + }
4.235 +
4.236 + /// \brief Gives back the height of the graph.
4.237 + ///
4.238 + /// Gives back the height of the graph.
4.239 + int height() const {
4.240 + return Parent::height();
4.241 + }
4.242 +
4.243 /// \brief Gives back the edge goes down from the node.
4.244 ///
4.245 /// Gives back the edge goes down from the node. If there is not
5.1 --- a/lemon/hypercube_graph.h Fri Sep 29 11:23:54 2006 +0000
5.2 +++ b/lemon/hypercube_graph.h Fri Sep 29 11:25:27 2006 +0000
5.3 @@ -34,13 +34,6 @@
5.4
5.5 namespace lemon {
5.6
5.7 - /// \brief Base graph for HyperCubeGraph.
5.8 - ///
5.9 - /// Base graph for hyper-cube graph. It describes some member functions
5.10 - /// which can be used in the HyperCubeGraph.
5.11 - ///
5.12 - /// \warning Always use the HyperCubeGraph instead of this.
5.13 - /// \see HyperCubeGraph
5.14 class HyperCubeGraphBase {
5.15
5.16 public:
5.17 @@ -56,9 +49,6 @@
5.18
5.19 protected:
5.20
5.21 - /// \brief Creates a hypercube graph with the given size.
5.22 - ///
5.23 - /// Creates a hypercube graph with the given size.
5.24 void construct(int dim) {
5.25 _dim = dim;
5.26 _nodeNum = 1 << dim;
5.27 @@ -70,54 +60,21 @@
5.28 typedef True NodeNumTag;
5.29 typedef True EdgeNumTag;
5.30
5.31 - ///Number of nodes.
5.32 int nodeNum() const { return _nodeNum; }
5.33 - ///Number of edges.
5.34 int edgeNum() const { return _nodeNum * _dim; }
5.35
5.36 - /// Maximum node ID.
5.37 -
5.38 - /// Maximum node ID.
5.39 - ///\sa id(Node)
5.40 int maxNodeId() const { return nodeNum() - 1; }
5.41 - /// Maximum edge ID.
5.42 -
5.43 - /// Maximum edge ID.
5.44 - ///\sa id(Edge)
5.45 int maxEdgeId() const { return edgeNum() - 1; }
5.46
5.47 - /// \brief Gives back the source node of an edge.
5.48 - ///
5.49 - /// Gives back the source node of an edge.
5.50 Node source(Edge e) const {
5.51 return e.id / _dim;
5.52 }
5.53
5.54 - /// \brief Gives back the target node of an edge.
5.55 - ///
5.56 - /// Gives back the target node of an edge.
5.57 Node target(Edge e) const {
5.58 return (e.id / _dim) ^ ( 1 << (e.id % _dim));
5.59 }
5.60
5.61 - /// Node ID.
5.62 -
5.63 - /// The ID of a valid Node is a nonnegative integer not greater than
5.64 - /// \ref maxNodeId(). The range of the ID's is not surely continuous
5.65 - /// and the greatest node ID can be actually less then \ref maxNodeId().
5.66 - ///
5.67 - /// The ID of the \ref INVALID node is -1.
5.68 - ///\return The ID of the node \c v.
5.69 -
5.70 static int id(Node v) { return v.id; }
5.71 - /// Edge ID.
5.72 -
5.73 - /// The ID of a valid Edge is a nonnegative integer not greater than
5.74 - /// \ref maxEdgeId(). The range of the ID's is not surely continuous
5.75 - /// and the greatest edge ID can be actually less then \ref maxEdgeId().
5.76 - ///
5.77 - /// The ID of the \ref INVALID edge is -1.
5.78 - ///\return The ID of the edge \c e.
5.79 static int id(Edge e) { return e.id; }
5.80
5.81 static Node nodeFromId(int id) { return Node(id);}
5.82 @@ -192,39 +149,22 @@
5.83 }
5.84 }
5.85
5.86 - /// \brief Gives back the number of the dimensions.
5.87 - ///
5.88 - /// Gives back the number of the dimensions.
5.89 int dimension() const {
5.90 return _dim;
5.91 }
5.92
5.93 - /// \brief Returns true if the n'th bit of the node is one.
5.94 - ///
5.95 - /// Returns true if the n'th bit of the node is one.
5.96 bool projection(Node node, int n) const {
5.97 return (bool)(node.id & (1 << n));
5.98 }
5.99
5.100 - /// \brief The dimension id of the edge.
5.101 - ///
5.102 - /// It returns the dimension id of the edge. It can
5.103 - /// be in the ${0, 1, dim-1}$ intervall.
5.104 int dimension(Edge edge) const {
5.105 return edge.id % _dim;
5.106 }
5.107
5.108 - /// \brief Gives back the index of the node.
5.109 - ///
5.110 - /// Gives back the index of the node. The lower bits of the
5.111 - /// integer describe the node.
5.112 int index(Node node) const {
5.113 return node.id;
5.114 }
5.115
5.116 - /// \brief Gives back the node by its index.
5.117 - ///
5.118 - /// Gives back the node by its index.
5.119 Node operator()(int index) const {
5.120 return Node(index);
5.121 }
5.122 @@ -252,16 +192,59 @@
5.123 /// The graph type is fully conform to the \ref concept::Graph
5.124 /// concept but it does not conform to the \ref concept::UGraph.
5.125 ///
5.126 - /// \see HyperCubeGraphBase
5.127 /// \author Balazs Dezso
5.128 class HyperCubeGraph : public ExtendedHyperCubeGraphBase {
5.129 public:
5.130
5.131 + typedef ExtendedHyperCubeGraphBase Parent;
5.132 +
5.133 /// \brief Construct a graph with \c dim dimension.
5.134 ///
5.135 /// Construct a graph with \c dim dimension.
5.136 HyperCubeGraph(int dim) { construct(dim); }
5.137
5.138 + /// \brief Gives back the number of the dimensions.
5.139 + ///
5.140 + /// Gives back the number of the dimensions.
5.141 + int dimension() const {
5.142 + return Parent::dimension();
5.143 + }
5.144 +
5.145 + /// \brief Returns true if the n'th bit of the node is one.
5.146 + ///
5.147 + /// Returns true if the n'th bit of the node is one.
5.148 + bool projection(Node node, int n) const {
5.149 + return Parent::projection(node, n);
5.150 + }
5.151 +
5.152 + /// \brief The dimension id of the edge.
5.153 + ///
5.154 + /// It returns the dimension id of the edge. It can
5.155 + /// be in the \f$ \{0, 1, \dots, dim-1\} \f$ intervall.
5.156 + int dimension(Edge edge) const {
5.157 + return Parent::dimension(edge);
5.158 + }
5.159 +
5.160 + /// \brief Gives back the index of the node.
5.161 + ///
5.162 + /// Gives back the index of the node. The lower bits of the
5.163 + /// integer describes the node.
5.164 + int index(Node node) const {
5.165 + return Parent::index(node);
5.166 + }
5.167 +
5.168 + /// \brief Gives back the node by its index.
5.169 + ///
5.170 + /// Gives back the node by its index.
5.171 + Node operator()(int index) const {
5.172 + return Parent::operator()(index);
5.173 + }
5.174 +
5.175 + /// \brief Number of nodes.
5.176 + int nodeNum() const { return Parent::nodeNum(); }
5.177 + /// \brief Number of edges.
5.178 + int edgeNum() const { return Parent::edgeNum(); }
5.179 +
5.180 /// \brief Linear combination map.
5.181 ///
5.182 /// It makes possible to give back a linear combination
