1.1 --- a/test/graph_test.h Fri Jul 18 17:26:12 2008 +0100
1.2 +++ b/test/graph_test.h Mon Jul 21 16:30:28 2008 +0200
1.3 @@ -19,7 +19,11 @@
1.4 #ifndef LEMON_TEST_GRAPH_TEST_H
1.5 #define LEMON_TEST_GRAPH_TEST_H
1.6
1.7 +#include <set>
1.8 +
1.9 #include <lemon/core.h>
1.10 +#include <lemon/maps.h>
1.11 +
1.12 #include "test_tools.h"
1.13
1.14 namespace lemon {
1.15 @@ -42,6 +46,10 @@
1.16 typename Graph::ArcIt e(G);
1.17 for(int i=0;i<cnt;i++) {
1.18 check(e!=INVALID,"Wrong Arc list linking.");
1.19 + check(G.oppositeNode(G.source(e), e) == G.target(e),
1.20 + "Wrong opposite node");
1.21 + check(G.oppositeNode(G.target(e), e) == G.source(e),
1.22 + "Wrong opposite node");
1.23 ++e;
1.24 }
1.25 check(e==INVALID,"Wrong Arc list linking.");
1.26 @@ -55,6 +63,8 @@
1.27 for(int i=0;i<cnt;i++) {
1.28 check(e!=INVALID,"Wrong OutArc list linking.");
1.29 check(n==G.source(e),"Wrong OutArc list linking.");
1.30 + check(n==G.baseNode(e),"Wrong OutArc list linking.");
1.31 + check(G.target(e)==G.runningNode(e),"Wrong OutArc list linking.");
1.32 ++e;
1.33 }
1.34 check(e==INVALID,"Wrong OutArc list linking.");
1.35 @@ -68,6 +78,8 @@
1.36 for(int i=0;i<cnt;i++) {
1.37 check(e!=INVALID,"Wrong InArc list linking.");
1.38 check(n==G.target(e),"Wrong InArc list linking.");
1.39 + check(n==G.baseNode(e),"Wrong OutArc list linking.");
1.40 + check(G.source(e)==G.runningNode(e),"Wrong OutArc list linking.");
1.41 ++e;
1.42 }
1.43 check(e==INVALID,"Wrong InArc list linking.");
1.44 @@ -80,6 +92,8 @@
1.45 typename Graph::EdgeIt e(G);
1.46 for(int i=0;i<cnt;i++) {
1.47 check(e!=INVALID,"Wrong Edge list linking.");
1.48 + check(G.oppositeNode(G.u(e), e) == G.v(e), "Wrong opposite node");
1.49 + check(G.oppositeNode(G.v(e), e) == G.u(e), "Wrong opposite node");
1.50 ++e;
1.51 }
1.52 check(e==INVALID,"Wrong Edge list linking.");
1.53 @@ -93,170 +107,178 @@
1.54 for(int i=0;i<cnt;i++) {
1.55 check(e!=INVALID,"Wrong IncEdge list linking.");
1.56 check(n==G.u(e) || n==G.v(e),"Wrong IncEdge list linking.");
1.57 + check(n==G.baseNode(e),"Wrong OutArc list linking.");
1.58 + check(G.u(e)==G.runningNode(e) || G.v(e)==G.runningNode(e),
1.59 + "Wrong OutArc list linking.");
1.60 ++e;
1.61 }
1.62 check(e==INVALID,"Wrong IncEdge list linking.");
1.63 check(countIncEdges(G,n)==cnt,"Wrong IncEdge number.");
1.64 }
1.65
1.66 - template <class Digraph>
1.67 - void checkDigraphIterators() {
1.68 - typedef typename Digraph::Node Node;
1.69 - typedef typename Digraph::NodeIt NodeIt;
1.70 - typedef typename Digraph::Arc Arc;
1.71 - typedef typename Digraph::ArcIt ArcIt;
1.72 - typedef typename Digraph::InArcIt InArcIt;
1.73 - typedef typename Digraph::OutArcIt OutArcIt;
1.74 + template <class Graph>
1.75 + void checkGraphConArcList(const Graph &G, int cnt) {
1.76 + int i = 0;
1.77 + for (typename Graph::NodeIt u(G); u != INVALID; ++u) {
1.78 + for (typename Graph::NodeIt v(G); v != INVALID; ++v) {
1.79 + for (ConArcIt<Graph> a(G, u, v); a != INVALID; ++a) {
1.80 + check(G.source(a) == u, "Wrong iterator.");
1.81 + check(G.target(a) == v, "Wrong iterator.");
1.82 + ++i;
1.83 + }
1.84 + }
1.85 + }
1.86 + check(cnt == i, "Wrong iterator.");
1.87 }
1.88
1.89 template <class Graph>
1.90 - void checkGraphIterators() {
1.91 - checkDigraphIterators<Graph>();
1.92 - typedef typename Graph::Edge Edge;
1.93 - typedef typename Graph::EdgeIt EdgeIt;
1.94 - typedef typename Graph::IncEdgeIt IncEdgeIt;
1.95 + void checkGraphConEdgeList(const Graph &G, int cnt) {
1.96 + int i = 0;
1.97 + for (typename Graph::NodeIt u(G); u != INVALID; ++u) {
1.98 + for (typename Graph::NodeIt v(G); v != INVALID; ++v) {
1.99 + for (ConEdgeIt<Graph> e(G, u, v); e != INVALID; ++e) {
1.100 + check((G.u(e) == u && G.v(e) == v) ||
1.101 + (G.u(e) == v && G.v(e) == u), "Wrong iterator.");
1.102 + i += u == v ? 2 : 1;
1.103 + }
1.104 + }
1.105 + }
1.106 + check(2 * cnt == i, "Wrong iterator.");
1.107 }
1.108
1.109 - // Structure returned by addPetersen()
1.110 - template<class Digraph>
1.111 - struct PetStruct
1.112 - {
1.113 - // Vector containing the outer nodes
1.114 - std::vector<typename Digraph::Node> outer;
1.115 - // Vector containing the inner nodes
1.116 - std::vector<typename Digraph::Node> inner;
1.117 - // Vector containing the arcs of the inner circle
1.118 - std::vector<typename Digraph::Arc> incir;
1.119 - // Vector containing the arcs of the outer circle
1.120 - std::vector<typename Digraph::Arc> outcir;
1.121 - // Vector containing the chord arcs
1.122 - std::vector<typename Digraph::Arc> chords;
1.123 - };
1.124 -
1.125 - // Adds the reverse pair of all arcs to a digraph
1.126 - template<class Digraph>
1.127 - void bidirDigraph(Digraph &G)
1.128 - {
1.129 - typedef typename Digraph::Arc Arc;
1.130 - typedef typename Digraph::ArcIt ArcIt;
1.131 -
1.132 - std::vector<Arc> ee;
1.133 -
1.134 - for(ArcIt e(G);e!=INVALID;++e) ee.push_back(e);
1.135 -
1.136 - for(int i=0;i<int(ee.size());++i)
1.137 - G.addArc(G.target(ee[i]),G.source(ee[i]));
1.138 - }
1.139 -
1.140 - // Adds a Petersen digraph to G.
1.141 - // Returns the nodes and arcs of the generated digraph.
1.142 - template<typename Digraph>
1.143 - PetStruct<Digraph> addPetersen(Digraph &G,int num = 5)
1.144 - {
1.145 - PetStruct<Digraph> n;
1.146 -
1.147 - for(int i=0;i<num;i++) {
1.148 - n.outer.push_back(G.addNode());
1.149 - n.inner.push_back(G.addNode());
1.150 - }
1.151 -
1.152 - for(int i=0;i<num;i++) {
1.153 - n.chords.push_back(G.addArc(n.outer[i],n.inner[i]));
1.154 - n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1) % num]));
1.155 - n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2) % num]));
1.156 - }
1.157 -
1.158 - return n;
1.159 - }
1.160 -
1.161 - // Checks the bidirectioned Petersen digraph
1.162 - template<class Digraph>
1.163 - void checkBidirPetersen(const Digraph &G, int num = 5)
1.164 - {
1.165 - typedef typename Digraph::NodeIt NodeIt;
1.166 -
1.167 - checkGraphNodeList(G, 2 * num);
1.168 - checkGraphArcList(G, 6 * num);
1.169 -
1.170 - for(NodeIt n(G);n!=INVALID;++n) {
1.171 - checkGraphInArcList(G, n, 3);
1.172 - checkGraphOutArcList(G, n, 3);
1.173 + template <typename Graph>
1.174 + void checkArcDirections(const Graph& G) {
1.175 + for (typename Graph::ArcIt a(G); a != INVALID; ++a) {
1.176 + check(G.source(a) == G.target(G.oppositeArc(a)), "Wrong direction");
1.177 + check(G.target(a) == G.source(G.oppositeArc(a)), "Wrong direction");
1.178 + check(G.direct(a, G.direction(a)) == a, "Wrong direction");
1.179 }
1.180 }
1.181
1.182 - // Structure returned by addUPetersen()
1.183 - template<class Graph>
1.184 - struct UPetStruct
1.185 - {
1.186 - // Vector containing the outer nodes
1.187 - std::vector<typename Graph::Node> outer;
1.188 - // Vector containing the inner nodes
1.189 - std::vector<typename Graph::Node> inner;
1.190 - // Vector containing the edges of the inner circle
1.191 - std::vector<typename Graph::Edge> incir;
1.192 - // Vector containing the edges of the outer circle
1.193 - std::vector<typename Graph::Edge> outcir;
1.194 - // Vector containing the chord edges
1.195 - std::vector<typename Graph::Edge> chords;
1.196 - };
1.197 -
1.198 - // Adds a Petersen graph to \c G.
1.199 - // Returns the nodes and edges of the generated graph.
1.200 - template<typename Graph>
1.201 - UPetStruct<Graph> addUPetersen(Graph &G,int num=5)
1.202 - {
1.203 - UPetStruct<Graph> n;
1.204 -
1.205 - for(int i=0;i<num;i++) {
1.206 - n.outer.push_back(G.addNode());
1.207 - n.inner.push_back(G.addNode());
1.208 - }
1.209 -
1.210 - for(int i=0;i<num;i++) {
1.211 - n.chords.push_back(G.addEdge(n.outer[i],n.inner[i]));
1.212 - n.outcir.push_back(G.addEdge(n.outer[i],n.outer[(i+1)%num]));
1.213 - n.incir.push_back(G.addEdge(n.inner[i],n.inner[(i+2)%num]));
1.214 - }
1.215 -
1.216 - return n;
1.217 - }
1.218 -
1.219 - // Checks the undirected Petersen graph
1.220 - template<class Graph>
1.221 - void checkUndirPetersen(const Graph &G, int num = 5)
1.222 - {
1.223 - typedef typename Graph::NodeIt NodeIt;
1.224 -
1.225 - checkGraphNodeList(G, 2 * num);
1.226 - checkGraphEdgeList(G, 3 * num);
1.227 - checkGraphArcList(G, 6 * num);
1.228 -
1.229 - for(NodeIt n(G);n!=INVALID;++n) {
1.230 - checkGraphIncEdgeList(G, n, 3);
1.231 + template <typename Graph>
1.232 + void checkNodeIds(const Graph& G) {
1.233 + std::set<int> values;
1.234 + for (typename Graph::NodeIt n(G); n != INVALID; ++n) {
1.235 + check(G.nodeFromId(G.id(n)) == n, "Wrong id");
1.236 + check(values.find(G.id(n)) == values.end(), "Wrong id");
1.237 + check(G.id(n) <= G.maxNodeId(), "Wrong maximum id");
1.238 + values.insert(G.id(n));
1.239 }
1.240 }
1.241
1.242 - template <class Digraph>
1.243 - void checkDigraph() {
1.244 - const int num = 5;
1.245 - Digraph G;
1.246 - checkGraphNodeList(G, 0);
1.247 - checkGraphArcList(G, 0);
1.248 - addPetersen(G, num);
1.249 - bidirDigraph(G);
1.250 - checkBidirPetersen(G, num);
1.251 + template <typename Graph>
1.252 + void checkArcIds(const Graph& G) {
1.253 + std::set<int> values;
1.254 + for (typename Graph::ArcIt a(G); a != INVALID; ++a) {
1.255 + check(G.arcFromId(G.id(a)) == a, "Wrong id");
1.256 + check(values.find(G.id(a)) == values.end(), "Wrong id");
1.257 + check(G.id(a) <= G.maxArcId(), "Wrong maximum id");
1.258 + values.insert(G.id(a));
1.259 + }
1.260 }
1.261
1.262 - template <class Graph>
1.263 - void checkGraph() {
1.264 - const int num = 5;
1.265 - Graph G;
1.266 - checkGraphNodeList(G, 0);
1.267 - checkGraphEdgeList(G, 0);
1.268 - addUPetersen(G, num);
1.269 - checkUndirPetersen(G, num);
1.270 + template <typename Graph>
1.271 + void checkEdgeIds(const Graph& G) {
1.272 + std::set<int> values;
1.273 + for (typename Graph::EdgeIt e(G); e != INVALID; ++e) {
1.274 + check(G.edgeFromId(G.id(e)) == e, "Wrong id");
1.275 + check(values.find(G.id(e)) == values.end(), "Wrong id");
1.276 + check(G.id(e) <= G.maxEdgeId(), "Wrong maximum id");
1.277 + values.insert(G.id(e));
1.278 + }
1.279 }
1.280
1.281 + template <typename Graph>
1.282 + void checkGraphNodeMap(const Graph& G) {
1.283 + typedef typename Graph::Node Node;
1.284 + typedef typename Graph::NodeIt NodeIt;
1.285 +
1.286 + typedef typename Graph::template NodeMap<int> IntNodeMap;
1.287 + IntNodeMap map(G, 42);
1.288 + for (NodeIt it(G); it != INVALID; ++it) {
1.289 + check(map[it] == 42, "Wrong map constructor.");
1.290 + }
1.291 + int s = 0;
1.292 + for (NodeIt it(G); it != INVALID; ++it) {
1.293 + map[it] = 0;
1.294 + check(map[it] == 0, "Wrong operator[].");
1.295 + map.set(it, s);
1.296 + check(map[it] == s, "Wrong set.");
1.297 + ++s;
1.298 + }
1.299 + s = s * (s - 1) / 2;
1.300 + for (NodeIt it(G); it != INVALID; ++it) {
1.301 + s -= map[it];
1.302 + }
1.303 + check(s == 0, "Wrong sum.");
1.304 +
1.305 + map = constMap<Node>(12);
1.306 + for (NodeIt it(G); it != INVALID; ++it) {
1.307 + check(map[it] == 12, "Wrong operator[].");
1.308 + }
1.309 + }
1.310 +
1.311 + template <typename Graph>
1.312 + void checkGraphArcMap(const Graph& G) {
1.313 + typedef typename Graph::Arc Arc;
1.314 + typedef typename Graph::ArcIt ArcIt;
1.315 +
1.316 + typedef typename Graph::template ArcMap<int> IntArcMap;
1.317 + IntArcMap map(G, 42);
1.318 + for (ArcIt it(G); it != INVALID; ++it) {
1.319 + check(map[it] == 42, "Wrong map constructor.");
1.320 + }
1.321 + int s = 0;
1.322 + for (ArcIt it(G); it != INVALID; ++it) {
1.323 + map[it] = 0;
1.324 + check(map[it] == 0, "Wrong operator[].");
1.325 + map.set(it, s);
1.326 + check(map[it] == s, "Wrong set.");
1.327 + ++s;
1.328 + }
1.329 + s = s * (s - 1) / 2;
1.330 + for (ArcIt it(G); it != INVALID; ++it) {
1.331 + s -= map[it];
1.332 + }
1.333 + check(s == 0, "Wrong sum.");
1.334 +
1.335 + map = constMap<Arc>(12);
1.336 + for (ArcIt it(G); it != INVALID; ++it) {
1.337 + check(map[it] == 12, "Wrong operator[].");
1.338 + }
1.339 + }
1.340 +
1.341 + template <typename Graph>
1.342 + void checkGraphEdgeMap(const Graph& G) {
1.343 + typedef typename Graph::Edge Edge;
1.344 + typedef typename Graph::EdgeIt EdgeIt;
1.345 +
1.346 + typedef typename Graph::template EdgeMap<int> IntEdgeMap;
1.347 + IntEdgeMap map(G, 42);
1.348 + for (EdgeIt it(G); it != INVALID; ++it) {
1.349 + check(map[it] == 42, "Wrong map constructor.");
1.350 + }
1.351 + int s = 0;
1.352 + for (EdgeIt it(G); it != INVALID; ++it) {
1.353 + map[it] = 0;
1.354 + check(map[it] == 0, "Wrong operator[].");
1.355 + map.set(it, s);
1.356 + check(map[it] == s, "Wrong set.");
1.357 + ++s;
1.358 + }
1.359 + s = s * (s - 1) / 2;
1.360 + for (EdgeIt it(G); it != INVALID; ++it) {
1.361 + s -= map[it];
1.362 + }
1.363 + check(s == 0, "Wrong sum.");
1.364 +
1.365 + map = constMap<Edge>(12);
1.366 + for (EdgeIt it(G); it != INVALID; ++it) {
1.367 + check(map[it] == 12, "Wrong operator[].");
1.368 + }
1.369 + }
1.370 +
1.371 +
1.372 } //namespace lemon
1.373
1.374 #endif