1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/test/graph_test.cc Sun Jan 20 20:43:48 2008 +0100
1.3 @@ -0,0 +1,207 @@
1.4 +/* -*- C++ -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library
1.7 + *
1.8 + * Copyright (C) 2003-2007
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#include <lemon/concepts/graph.h>
1.23 +#include <lemon/list_graph.h>
1.24 +// #include <lemon/smart_graph.h>
1.25 +// #include <lemon/full_graph.h>
1.26 +// #include <lemon/grid_graph.h>
1.27 +
1.28 +//#include <lemon/graph_utils.h>
1.29 +
1.30 +#include "test_tools.h"
1.31 +
1.32 +
1.33 +using namespace lemon;
1.34 +using namespace lemon::concepts;
1.35 +
1.36 +void check_concepts() {
1.37 +
1.38 + { // checking digraph components
1.39 + checkConcept<BaseGraphComponent, BaseGraphComponent >();
1.40 +
1.41 + checkConcept<IDableGraphComponent<>,
1.42 + IDableGraphComponent<> >();
1.43 +
1.44 + checkConcept<IterableGraphComponent<>,
1.45 + IterableGraphComponent<> >();
1.46 +
1.47 + checkConcept<MappableGraphComponent<>,
1.48 + MappableGraphComponent<> >();
1.49 +
1.50 + }
1.51 + {
1.52 + checkConcept<Graph, ListGraph>();
1.53 +// checkConcept<Graph, SmartGraph>();
1.54 +// checkConcept<Graph, FullGraph>();
1.55 +// checkConcept<Graph, Graph>();
1.56 +// checkConcept<Graph, GridGraph>();
1.57 + }
1.58 +}
1.59 +
1.60 +template <typename Graph>
1.61 +void check_item_counts(Graph &g, int n, int e) {
1.62 + int nn = 0;
1.63 + for (typename Graph::NodeIt it(g); it != INVALID; ++it) {
1.64 + ++nn;
1.65 + }
1.66 +
1.67 + check(nn == n, "Wrong node number.");
1.68 + // check(countNodes(g) == n, "Wrong node number.");
1.69 +
1.70 + int ee = 0;
1.71 + for (typename Graph::ArcIt it(g); it != INVALID; ++it) {
1.72 + ++ee;
1.73 + }
1.74 +
1.75 + check(ee == 2*e, "Wrong arc number.");
1.76 + // check(countArcs(g) == 2*e, "Wrong arc number.");
1.77 +
1.78 + int uee = 0;
1.79 + for (typename Graph::EdgeIt it(g); it != INVALID; ++it) {
1.80 + ++uee;
1.81 + }
1.82 +
1.83 + check(uee == e, "Wrong edge number.");
1.84 + // check(countEdges(g) == e, "Wrong edge number.");
1.85 +}
1.86 +
1.87 +template <typename Graph>
1.88 +void print_items(Graph &g) {
1.89 +
1.90 + typedef typename Graph::NodeIt NodeIt;
1.91 + typedef typename Graph::EdgeIt EdgeIt;
1.92 + typedef typename Graph::ArcIt ArcIt;
1.93 +
1.94 + std::cout << "Nodes" << std::endl;
1.95 + int i=0;
1.96 + for(NodeIt it(g); it!=INVALID; ++it, ++i) {
1.97 + std::cout << " " << i << ": " << g.id(it) << std::endl;
1.98 + }
1.99 +
1.100 + std::cout << "Edge" << std::endl;
1.101 + i=0;
1.102 + for(EdgeIt it(g); it!=INVALID; ++it, ++i) {
1.103 + std::cout << " " << i << ": " << g.id(it)
1.104 + << " (" << g.id(g.source(it)) << ", " << g.id(g.target(it))
1.105 + << ")" << std::endl;
1.106 + }
1.107 +
1.108 + std::cout << "Arc" << std::endl;
1.109 + i=0;
1.110 + for(ArcIt it(g); it!=INVALID; ++it, ++i) {
1.111 + std::cout << " " << i << ": " << g.id(it)
1.112 + << " (" << g.id(g.source(it)) << ", " << g.id(g.target(it))
1.113 + << ")" << std::endl;
1.114 + }
1.115 +
1.116 +}
1.117 +
1.118 +template <typename Graph>
1.119 +void check_graph() {
1.120 +
1.121 + typedef typename Graph::Node Node;
1.122 + typedef typename Graph::Edge Edge;
1.123 + typedef typename Graph::Arc Arc;
1.124 + typedef typename Graph::NodeIt NodeIt;
1.125 + typedef typename Graph::EdgeIt EdgeIt;
1.126 + typedef typename Graph::ArcIt ArcIt;
1.127 +
1.128 + Graph g;
1.129 +
1.130 + check_item_counts(g,0,0);
1.131 +
1.132 + Node
1.133 + n1 = g.addNode(),
1.134 + n2 = g.addNode(),
1.135 + n3 = g.addNode();
1.136 +
1.137 + Edge
1.138 + e1 = g.addEdge(n1, n2),
1.139 + e2 = g.addEdge(n2, n3);
1.140 +
1.141 + // print_items(g);
1.142 +
1.143 + check_item_counts(g,3,2);
1.144 +}
1.145 +
1.146 +// void checkGridGraph(const GridGraph& g, int w, int h) {
1.147 +// check(g.width() == w, "Wrong width");
1.148 +// check(g.height() == h, "Wrong height");
1.149 +
1.150 +// for (int i = 0; i < w; ++i) {
1.151 +// for (int j = 0; j < h; ++j) {
1.152 +// check(g.col(g(i, j)) == i, "Wrong col");
1.153 +// check(g.row(g(i, j)) == j, "Wrong row");
1.154 +// }
1.155 +// }
1.156 +
1.157 +// for (int i = 0; i < w; ++i) {
1.158 +// for (int j = 0; j < h - 1; ++j) {
1.159 +// check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down");
1.160 +// check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down");
1.161 +// }
1.162 +// check(g.down(g(i, h - 1)) == INVALID, "Wrong down");
1.163 +// }
1.164 +
1.165 +// for (int i = 0; i < w; ++i) {
1.166 +// for (int j = 1; j < h; ++j) {
1.167 +// check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up");
1.168 +// check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up");
1.169 +// }
1.170 +// check(g.up(g(i, 0)) == INVALID, "Wrong up");
1.171 +// }
1.172 +
1.173 +// for (int j = 0; j < h; ++j) {
1.174 +// for (int i = 0; i < w - 1; ++i) {
1.175 +// check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right");
1.176 +// check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right");
1.177 +// }
1.178 +// check(g.right(g(w - 1, j)) == INVALID, "Wrong right");
1.179 +// }
1.180 +
1.181 +// for (int j = 0; j < h; ++j) {
1.182 +// for (int i = 1; i < w; ++i) {
1.183 +// check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left");
1.184 +// check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left");
1.185 +// }
1.186 +// check(g.left(g(0, j)) == INVALID, "Wrong left");
1.187 +// }
1.188 +// }
1.189 +
1.190 +int main() {
1.191 + check_concepts();
1.192 +
1.193 + check_graph<ListGraph>();
1.194 +// check_graph<SmartGraph>();
1.195 +
1.196 +// {
1.197 +// FullGraph g(5);
1.198 +// check_item_counts(g, 5, 10);
1.199 +// }
1.200 +
1.201 +// {
1.202 +// GridGraph g(5, 6);
1.203 +// check_item_counts(g, 30, 49);
1.204 +// checkGridGraph(g, 5, 6);
1.205 +// }
1.206 +
1.207 + std::cout << __FILE__ ": All tests passed.\n";
1.208 +
1.209 + return 0;
1.210 +}