1.1 --- a/test/graph_utils_test.cc Sun Jun 15 22:03:33 2008 +0200
1.2 +++ b/test/graph_utils_test.cc Sun Jun 15 22:05:23 2008 +0200
1.3 @@ -16,41 +16,177 @@
1.4 *
1.5 */
1.6
1.7 -#include <iostream>
1.8 -#include <vector>
1.9 +#include <cstdlib>
1.10 +#include <ctime>
1.11
1.12 +#include <lemon/random.h>
1.13 #include <lemon/graph_utils.h>
1.14 -
1.15 #include <lemon/list_graph.h>
1.16 #include <lemon/smart_graph.h>
1.17
1.18 +#include "graph_test.h"
1.19 #include "test_tools.h"
1.20 -#include "graph_utils_test.h"
1.21 -
1.22
1.23 using namespace lemon;
1.24
1.25 -template <class Graph>
1.26 -void checkSnapDeg()
1.27 +template <typename Digraph>
1.28 +void checkFindArcs() {
1.29 + TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
1.30 +
1.31 + {
1.32 + Digraph digraph;
1.33 + for (int i = 0; i < 10; ++i) {
1.34 + digraph.addNode();
1.35 + }
1.36 + DescriptorMap<Digraph, Node> nodes(digraph);
1.37 + typename DescriptorMap<Digraph, Node>::InverseMap invNodes(nodes);
1.38 + for (int i = 0; i < 100; ++i) {
1.39 + int src = rnd[invNodes.size()];
1.40 + int trg = rnd[invNodes.size()];
1.41 + digraph.addArc(invNodes[src], invNodes[trg]);
1.42 + }
1.43 + typename Digraph::template ArcMap<bool> found(digraph, false);
1.44 + DescriptorMap<Digraph, Arc> arcs(digraph);
1.45 + for (NodeIt src(digraph); src != INVALID; ++src) {
1.46 + for (NodeIt trg(digraph); trg != INVALID; ++trg) {
1.47 + for (ConArcIt<Digraph> con(digraph, src, trg); con != INVALID; ++con) {
1.48 + check(digraph.source(con) == src, "Wrong source.");
1.49 + check(digraph.target(con) == trg, "Wrong target.");
1.50 + check(found[con] == false, "The arc found already.");
1.51 + found[con] = true;
1.52 + }
1.53 + }
1.54 + }
1.55 + for (ArcIt it(digraph); it != INVALID; ++it) {
1.56 + check(found[it] == true, "The arc is not found.");
1.57 + }
1.58 + }
1.59 +
1.60 + {
1.61 + int num = 5;
1.62 + Digraph fg;
1.63 + std::vector<Node> nodes;
1.64 + for (int i = 0; i < num; ++i) {
1.65 + nodes.push_back(fg.addNode());
1.66 + }
1.67 + for (int i = 0; i < num * num; ++i) {
1.68 + fg.addArc(nodes[i / num], nodes[i % num]);
1.69 + }
1.70 + check(countNodes(fg) == num, "Wrong node number.");
1.71 + check(countArcs(fg) == num*num, "Wrong arc number.");
1.72 + for (NodeIt src(fg); src != INVALID; ++src) {
1.73 + for (NodeIt trg(fg); trg != INVALID; ++trg) {
1.74 + ConArcIt<Digraph> con(fg, src, trg);
1.75 + check(con != INVALID, "There is no connecting arc.");
1.76 + check(fg.source(con) == src, "Wrong source.");
1.77 + check(fg.target(con) == trg, "Wrong target.");
1.78 + check(++con == INVALID, "There is more connecting arc.");
1.79 + }
1.80 + }
1.81 + ArcLookUp<Digraph> al1(fg);
1.82 + DynArcLookUp<Digraph> al2(fg);
1.83 + AllArcLookUp<Digraph> al3(fg);
1.84 + for (NodeIt src(fg); src != INVALID; ++src) {
1.85 + for (NodeIt trg(fg); trg != INVALID; ++trg) {
1.86 + Arc con1 = al1(src, trg);
1.87 + Arc con2 = al2(src, trg);
1.88 + Arc con3 = al3(src, trg);
1.89 + Arc con4 = findArc(fg, src, trg);
1.90 + check(con1 == con2 && con2 == con3 && con3 == con4, "Different results.")
1.91 + check(con1 != INVALID, "There is no connecting arc.");
1.92 + check(fg.source(con1) == src, "Wrong source.");
1.93 + check(fg.target(con1) == trg, "Wrong target.");
1.94 + check(al3(src, trg, con3) == INVALID, "There is more connecting arc.");
1.95 + check(findArc(fg, src, trg, con4) == INVALID, "There is more connecting arc.");
1.96 + }
1.97 + }
1.98 + }
1.99 +}
1.100 +
1.101 +template <typename Graph>
1.102 +void checkFindEdges() {
1.103 + TEMPLATE_GRAPH_TYPEDEFS(Graph);
1.104 + Graph graph;
1.105 + for (int i = 0; i < 10; ++i) {
1.106 + graph.addNode();
1.107 + }
1.108 + DescriptorMap<Graph, Node> nodes(graph);
1.109 + typename DescriptorMap<Graph, Node>::InverseMap invNodes(nodes);
1.110 + for (int i = 0; i < 100; ++i) {
1.111 + int src = rnd[invNodes.size()];
1.112 + int trg = rnd[invNodes.size()];
1.113 + graph.addEdge(invNodes[src], invNodes[trg]);
1.114 + }
1.115 + typename Graph::template EdgeMap<int> found(graph, 0);
1.116 + DescriptorMap<Graph, Edge> edges(graph);
1.117 + for (NodeIt src(graph); src != INVALID; ++src) {
1.118 + for (NodeIt trg(graph); trg != INVALID; ++trg) {
1.119 + for (ConEdgeIt<Graph> con(graph, src, trg); con != INVALID; ++con) {
1.120 + check( (graph.u(con) == src && graph.v(con) == trg) ||
1.121 + (graph.v(con) == src && graph.u(con) == trg), "Wrong end nodes.");
1.122 + ++found[con];
1.123 + check(found[con] <= 2, "The edge found more than twice.");
1.124 + }
1.125 + }
1.126 + }
1.127 + for (EdgeIt it(graph); it != INVALID; ++it) {
1.128 + check( (graph.u(it) != graph.v(it) && found[it] == 2) ||
1.129 + (graph.u(it) == graph.v(it) && found[it] == 1),
1.130 + "The edge is not found correctly.");
1.131 + }
1.132 +}
1.133 +
1.134 +template <class Digraph>
1.135 +void checkDeg()
1.136 {
1.137 - Graph g;
1.138 - typename Graph::Node n1=g.addNode();
1.139 - typename Graph::Node n2=g.addNode();
1.140 -
1.141 - InDegMap<Graph> ind(g);
1.142 -
1.143 + TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
1.144 +
1.145 + const int nodeNum = 10;
1.146 + const int arcNum = 100;
1.147 + Digraph digraph;
1.148 + InDegMap<Digraph> inDeg(digraph);
1.149 + OutDegMap<Digraph> outDeg(digraph);
1.150 + std::vector<Node> nodes(nodeNum);
1.151 + for (int i = 0; i < nodeNum; ++i) {
1.152 + nodes[i] = digraph.addNode();
1.153 + }
1.154 + std::vector<Arc> arcs(arcNum);
1.155 + for (int i = 0; i < arcNum; ++i) {
1.156 + arcs[i] = digraph.addArc(nodes[rnd[nodeNum]], nodes[rnd[nodeNum]]);
1.157 + }
1.158 + for (int i = 0; i < nodeNum; ++i) {
1.159 + check(inDeg[nodes[i]] == countInArcs(digraph, nodes[i]),
1.160 + "Wrong in degree map");
1.161 + }
1.162 + for (int i = 0; i < nodeNum; ++i) {
1.163 + check(outDeg[nodes[i]] == countOutArcs(digraph, nodes[i]),
1.164 + "Wrong out degree map");
1.165 + }
1.166 +}
1.167 +
1.168 +template <class Digraph>
1.169 +void checkSnapDeg()
1.170 +{
1.171 + TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
1.172 +
1.173 + Digraph g;
1.174 + Node n1=g.addNode();
1.175 + Node n2=g.addNode();
1.176 +
1.177 + InDegMap<Digraph> ind(g);
1.178 +
1.179 g.addArc(n1,n2);
1.180
1.181 - typename Graph::Snapshot snap(g);
1.182 + typename Digraph::Snapshot snap(g);
1.183
1.184 - OutDegMap<Graph> outd(g);
1.185 + OutDegMap<Digraph> outd(g);
1.186
1.187 check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
1.188 check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
1.189
1.190 g.addArc(n1,n2);
1.191 g.addArc(n2,n1);
1.192 -
1.193 +
1.194 check(ind[n1]==1 && ind[n2]==2, "Wrong InDegMap value.");
1.195 check(outd[n1]==2 && outd[n2]==1, "Wrong OutDegMap value.");
1.196
1.197 @@ -58,84 +194,20 @@
1.198
1.199 check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
1.200 check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
1.201 -
1.202 }
1.203
1.204 int main() {
1.205 - ///\file
1.206 - { // checking list graph
1.207 - checkDigraphCounters<ListDigraph>();
1.208 - checkFindArc<ListDigraph>();
1.209 - }
1.210 - { // checking smart graph
1.211 - checkDigraphCounters<SmartDigraph>();
1.212 - checkFindArc<SmartDigraph>();
1.213 - }
1.214 - {
1.215 - int num = 5;
1.216 - SmartDigraph fg;
1.217 - std::vector<SmartDigraph::Node> nodes;
1.218 - for (int i = 0; i < num; ++i) {
1.219 - nodes.push_back(fg.addNode());
1.220 - }
1.221 - for (int i = 0; i < num * num; ++i) {
1.222 - fg.addArc(nodes[i / num], nodes[i % num]);
1.223 - }
1.224 - check(countNodes(fg) == num, "FullGraph: wrong node number.");
1.225 - check(countArcs(fg) == num*num, "FullGraph: wrong arc number.");
1.226 - for (SmartDigraph::NodeIt src(fg); src != INVALID; ++src) {
1.227 - for (SmartDigraph::NodeIt trg(fg); trg != INVALID; ++trg) {
1.228 - ConArcIt<SmartDigraph> con(fg, src, trg);
1.229 - check(con != INVALID, "There is no connecting arc.");
1.230 - check(fg.source(con) == src, "Wrong source.");
1.231 - check(fg.target(con) == trg, "Wrong target.");
1.232 - check(++con == INVALID, "There is more connecting arc.");
1.233 - }
1.234 - }
1.235 - AllArcLookUp<SmartDigraph> el(fg);
1.236 - for (SmartDigraph::NodeIt src(fg); src != INVALID; ++src) {
1.237 - for (SmartDigraph::NodeIt trg(fg); trg != INVALID; ++trg) {
1.238 - SmartDigraph::Arc con = el(src, trg);
1.239 - check(con != INVALID, "There is no connecting arc.");
1.240 - check(fg.source(con) == src, "Wrong source.");
1.241 - check(fg.target(con) == trg, "Wrong target.");
1.242 - check(el(src,trg,con) == INVALID, "There is more connecting arc.");
1.243 - }
1.244 - }
1.245 - }
1.246 + // Checking ConArcIt, ConEdgeIt, ArcLookUp, AllArcLookUp, and DynArcLookUp
1.247 + checkFindArcs<ListDigraph>();
1.248 + checkFindArcs<SmartDigraph>();
1.249 + checkFindEdges<ListGraph>();
1.250 + checkFindEdges<SmartGraph>();
1.251
1.252 - //check In/OutDegMap (and Snapshot feature)
1.253 -
1.254 + // Checking In/OutDegMap (and Snapshot feature)
1.255 + checkDeg<ListDigraph>();
1.256 + checkDeg<SmartDigraph>();
1.257 checkSnapDeg<ListDigraph>();
1.258 checkSnapDeg<SmartDigraph>();
1.259 -
1.260 - {
1.261 - const int nodeNum = 10;
1.262 - const int arcNum = 100;
1.263 - ListDigraph digraph;
1.264 - InDegMap<ListDigraph> inDeg(digraph);
1.265 - OutDegMap<ListDigraph> outDeg(digraph);
1.266 - std::vector<ListDigraph::Node> nodes(nodeNum);
1.267 - for (int i = 0; i < nodeNum; ++i) {
1.268 - nodes[i] = digraph.addNode();
1.269 - }
1.270 - std::vector<ListDigraph::Arc> arcs(arcNum);
1.271 - for (int i = 0; i < arcNum; ++i) {
1.272 - arcs[i] =
1.273 - digraph.addArc(nodes[rnd[nodeNum]], nodes[rnd[nodeNum]]);
1.274 - }
1.275 - for (int i = 0; i < nodeNum; ++i) {
1.276 - check(inDeg[nodes[i]] == countInArcs(digraph, nodes[i]),
1.277 - "Wrong in degree map");
1.278 - }
1.279 - for (int i = 0; i < nodeNum; ++i) {
1.280 - check(outDeg[nodes[i]] == countOutArcs(digraph, nodes[i]),
1.281 - "Wrong in degree map");
1.282 - }
1.283 - }
1.284 -
1.285 - ///Everything is OK
1.286 - std::cout << __FILE__ ": All tests passed.\n";
1.287
1.288 return 0;
1.289 }