1.1 --- a/test/undir_graph_test.cc Thu Jan 26 06:44:22 2006 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,201 +0,0 @@
1.4 -// -*- C++ -*-
1.5 -
1.6 -#include <lemon/bits/graph_extender.h>
1.7 -#include <lemon/concept/undir_graph.h>
1.8 -#include <lemon/list_graph.h>
1.9 -#include <lemon/smart_graph.h>
1.10 -#include <lemon/full_graph.h>
1.11 -#include <lemon/grid_graph.h>
1.12 -
1.13 -#include <lemon/graph_utils.h>
1.14 -
1.15 -#include "test_tools.h"
1.16 -
1.17 -
1.18 -using namespace lemon;
1.19 -using namespace lemon::concept;
1.20 -
1.21 -void check_concepts() {
1.22 - typedef UndirGraphExtender<ListGraphBase> UndirListGraphBase;
1.23 -
1.24 - typedef IterableUndirGraphExtender<
1.25 - AlterableUndirGraphExtender<UndirListGraphBase> > IterableUndirListGraph;
1.26 -
1.27 - typedef MappableUndirGraphExtender<IterableUndirListGraph>
1.28 - MappableUndirListGraph;
1.29 -
1.30 - typedef ErasableUndirGraphExtender<
1.31 - ClearableUndirGraphExtender<
1.32 - ExtendableUndirGraphExtender<MappableUndirListGraph> > > Graph;
1.33 -
1.34 - checkConcept<BaseIterableUndirGraphConcept, Graph>();
1.35 - checkConcept<IterableUndirGraphConcept, Graph>();
1.36 - checkConcept<MappableUndirGraphConcept, Graph>();
1.37 -
1.38 - checkConcept<UndirGraph, Graph>();
1.39 - checkConcept<ErasableUndirGraph, Graph>();
1.40 -
1.41 - checkConcept<UndirGraph, UndirListGraph>();
1.42 - checkConcept<ErasableUndirGraph, UndirListGraph>();
1.43 -
1.44 - checkConcept<UndirGraph, UndirSmartGraph>();
1.45 - checkConcept<ExtendableUndirGraph, UndirSmartGraph>();
1.46 -
1.47 - checkConcept<UndirGraph, UndirFullGraph>();
1.48 -
1.49 - checkConcept<UndirGraph, UndirGraph>();
1.50 -
1.51 - checkConcept<UndirGraph, GridGraph>();
1.52 -}
1.53 -
1.54 -template <typename Graph>
1.55 -void check_item_counts(Graph &g, int n, int e) {
1.56 - int nn = 0;
1.57 - for (typename Graph::NodeIt it(g); it != INVALID; ++it) {
1.58 - ++nn;
1.59 - }
1.60 -
1.61 - check(nn == n, "Wrong node number.");
1.62 - check(countNodes(g) == n, "Wrong node number.");
1.63 -
1.64 - int ee = 0;
1.65 - for (typename Graph::EdgeIt it(g); it != INVALID; ++it) {
1.66 - ++ee;
1.67 - }
1.68 -
1.69 - check(ee == 2*e, "Wrong edge number.");
1.70 - check(countEdges(g) == 2*e, "Wrong edge number.");
1.71 -
1.72 - int uee = 0;
1.73 - for (typename Graph::UndirEdgeIt it(g); it != INVALID; ++it) {
1.74 - ++uee;
1.75 - }
1.76 -
1.77 - check(uee == e, "Wrong undir edge number.");
1.78 - check(countUndirEdges(g) == e, "Wrong undir edge number.");
1.79 -}
1.80 -
1.81 -template <typename Graph>
1.82 -void print_items(Graph &g) {
1.83 -
1.84 - typedef typename Graph::NodeIt NodeIt;
1.85 - typedef typename Graph::UndirEdgeIt UEdgeIt;
1.86 - typedef typename Graph::EdgeIt EdgeIt;
1.87 -
1.88 - std::cout << "Nodes" << std::endl;
1.89 - int i=0;
1.90 - for(NodeIt it(g); it!=INVALID; ++it, ++i) {
1.91 - std::cout << " " << i << ": " << g.id(it) << std::endl;
1.92 - }
1.93 -
1.94 - std::cout << "UndirEdge" << std::endl;
1.95 - i=0;
1.96 - for(UEdgeIt it(g); it!=INVALID; ++it, ++i) {
1.97 - std::cout << " " << i << ": " << g.id(it)
1.98 - << " (" << g.id(g.source(it)) << ", " << g.id(g.target(it))
1.99 - << ")" << std::endl;
1.100 - }
1.101 -
1.102 - std::cout << "Edge" << std::endl;
1.103 - i=0;
1.104 - for(EdgeIt it(g); it!=INVALID; ++it, ++i) {
1.105 - std::cout << " " << i << ": " << g.id(it)
1.106 - << " (" << g.id(g.source(it)) << ", " << g.id(g.target(it))
1.107 - << ")" << std::endl;
1.108 - }
1.109 -
1.110 -}
1.111 -
1.112 -template <typename Graph>
1.113 -void check_graph() {
1.114 -
1.115 - typedef typename Graph::Node Node;
1.116 - typedef typename Graph::UndirEdge UEdge;
1.117 - typedef typename Graph::Edge Edge;
1.118 - typedef typename Graph::NodeIt NodeIt;
1.119 - typedef typename Graph::UndirEdgeIt UEdgeIt;
1.120 - typedef typename Graph::EdgeIt EdgeIt;
1.121 -
1.122 - Graph g;
1.123 -
1.124 - check_item_counts(g,0,0);
1.125 -
1.126 - Node
1.127 - n1 = g.addNode(),
1.128 - n2 = g.addNode(),
1.129 - n3 = g.addNode();
1.130 -
1.131 - UEdge
1.132 - e1 = g.addEdge(n1, n2),
1.133 - e2 = g.addEdge(n2, n3);
1.134 -
1.135 - // print_items(g);
1.136 -
1.137 - check_item_counts(g,3,2);
1.138 -}
1.139 -
1.140 -void checkGridGraph(const GridGraph& g, int w, int h) {
1.141 - check(g.width() == w, "Wrong width");
1.142 - check(g.height() == h, "Wrong height");
1.143 -
1.144 - for (int i = 0; i < w; ++i) {
1.145 - for (int j = 0; j < h; ++j) {
1.146 - check(g.col(g(i, j)) == i, "Wrong col");
1.147 - check(g.row(g(i, j)) == j, "Wrong row");
1.148 - }
1.149 - }
1.150 -
1.151 - for (int i = 0; i < w; ++i) {
1.152 - for (int j = 0; j < h - 1; ++j) {
1.153 - check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down");
1.154 - check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down");
1.155 - }
1.156 - check(g.down(g(i, h - 1)) == INVALID, "Wrong down");
1.157 - }
1.158 -
1.159 - for (int i = 0; i < w; ++i) {
1.160 - for (int j = 1; j < h; ++j) {
1.161 - check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up");
1.162 - check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up");
1.163 - }
1.164 - check(g.up(g(i, 0)) == INVALID, "Wrong up");
1.165 - }
1.166 -
1.167 - for (int j = 0; j < h; ++j) {
1.168 - for (int i = 0; i < w - 1; ++i) {
1.169 - check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right");
1.170 - check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right");
1.171 - }
1.172 - check(g.right(g(w - 1, j)) == INVALID, "Wrong right");
1.173 - }
1.174 -
1.175 - for (int j = 0; j < h; ++j) {
1.176 - for (int i = 1; i < w; ++i) {
1.177 - check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left");
1.178 - check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left");
1.179 - }
1.180 - check(g.left(g(0, j)) == INVALID, "Wrong left");
1.181 - }
1.182 -}
1.183 -
1.184 -int main() {
1.185 - check_concepts();
1.186 -
1.187 - check_graph<UndirListGraph>();
1.188 - check_graph<UndirSmartGraph>();
1.189 -
1.190 - {
1.191 - UndirFullGraph g(5);
1.192 - check_item_counts(g, 5, 10);
1.193 - }
1.194 -
1.195 - {
1.196 - GridGraph g(5, 6);
1.197 - check_item_counts(g, 30, 49);
1.198 - checkGridGraph(g, 5, 6);
1.199 - }
1.200 -
1.201 - std::cout << __FILE__ ": All tests passed.\n";
1.202 -
1.203 - return 0;
1.204 -}