alpar@1956: /* -*- C++ -*- alpar@1956: * alpar@1956: * This file is a part of LEMON, a generic C++ optimization library alpar@1956: * alpar@1956: * Copyright (C) 2003-2006 alpar@1956: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@1956: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@1956: * alpar@1956: * Permission to use, modify and distribute this software is granted alpar@1956: * provided that this copyright notice appears in all copies. For alpar@1956: * precise terms see the accompanying LICENSE file. alpar@1956: * alpar@1956: * This software is provided "AS IS" with no warranty of any kind, alpar@1956: * express or implied, and with no claim as to its suitability for any alpar@1956: * purpose. alpar@1956: * alpar@1956: */ klao@962: klao@1795: #include klao@1909: #include klao@962: #include klao@962: #include klao@962: #include deba@1680: #include klao@962: klao@1053: #include klao@1053: klao@962: #include "test_tools.h" klao@962: klao@962: klao@962: using namespace lemon; klao@962: using namespace lemon::concept; klao@962: klao@1053: void check_concepts() { klao@1909: typedef UGraphExtender ListUGraphBase; klao@962: klao@1909: typedef IterableUGraphExtender< klao@1909: AlterableUGraphExtender > IterableListUGraph; klao@962: klao@1909: typedef MappableUGraphExtender klao@1909: MappableListUGraph; klao@1022: klao@1909: typedef ErasableUGraphExtender< klao@1909: ClearableUGraphExtender< klao@1909: ExtendableUGraphExtender > > Graph; klao@1022: klao@1909: checkConcept(); klao@1909: checkConcept(); klao@1909: checkConcept(); klao@1022: klao@1909: checkConcept(); klao@1909: checkConcept(); klao@962: klao@1909: checkConcept(); klao@1909: checkConcept(); klao@1034: klao@1909: checkConcept(); klao@1909: checkConcept(); klao@1034: klao@1909: checkConcept(); deba@1568: klao@1909: checkConcept(); deba@1680: klao@1909: checkConcept(); klao@1053: } klao@1053: klao@1054: template klao@1053: void check_item_counts(Graph &g, int n, int e) { deba@1680: int nn = 0; deba@1680: for (typename Graph::NodeIt it(g); it != INVALID; ++it) { deba@1680: ++nn; deba@1680: } deba@1680: deba@1680: check(nn == n, "Wrong node number."); deba@1680: check(countNodes(g) == n, "Wrong node number."); deba@1680: deba@1680: int ee = 0; deba@1680: for (typename Graph::EdgeIt it(g); it != INVALID; ++it) { deba@1680: ++ee; deba@1680: } deba@1680: deba@1680: check(ee == 2*e, "Wrong edge number."); deba@1680: check(countEdges(g) == 2*e, "Wrong edge number."); deba@1680: deba@1680: int uee = 0; klao@1909: for (typename Graph::UEdgeIt it(g); it != INVALID; ++it) { deba@1680: ++uee; deba@1680: } deba@1680: klao@1909: check(uee == e, "Wrong uedge number."); klao@1909: check(countUEdges(g) == e, "Wrong uedge number."); klao@1053: } klao@1053: klao@1054: template klao@1053: void print_items(Graph &g) { klao@1054: klao@1054: typedef typename Graph::NodeIt NodeIt; klao@1909: typedef typename Graph::UEdgeIt UEdgeIt; klao@1054: typedef typename Graph::EdgeIt EdgeIt; klao@1054: alpar@1367: std::cout << "Nodes" << std::endl; klao@1053: int i=0; klao@1053: for(NodeIt it(g); it!=INVALID; ++it, ++i) { alpar@1367: std::cout << " " << i << ": " << g.id(it) << std::endl; klao@1053: } klao@1053: klao@1909: std::cout << "UEdge" << std::endl; klao@1053: i=0; klao@1053: for(UEdgeIt it(g); it!=INVALID; ++it, ++i) { alpar@1367: std::cout << " " << i << ": " << g.id(it) klao@1053: << " (" << g.id(g.source(it)) << ", " << g.id(g.target(it)) alpar@1367: << ")" << std::endl; klao@1053: } klao@1053: alpar@1367: std::cout << "Edge" << std::endl; klao@1053: i=0; klao@1053: for(EdgeIt it(g); it!=INVALID; ++it, ++i) { alpar@1367: std::cout << " " << i << ": " << g.id(it) klao@1053: << " (" << g.id(g.source(it)) << ", " << g.id(g.target(it)) alpar@1367: << ")" << std::endl; klao@1053: } klao@1053: klao@1053: } klao@1053: klao@1054: template klao@1054: void check_graph() { klao@1053: klao@1054: typedef typename Graph::Node Node; klao@1909: typedef typename Graph::UEdge UEdge; klao@1054: typedef typename Graph::Edge Edge; klao@1054: typedef typename Graph::NodeIt NodeIt; klao@1909: typedef typename Graph::UEdgeIt UEdgeIt; klao@1054: typedef typename Graph::EdgeIt EdgeIt; klao@1053: klao@1053: Graph g; klao@1053: klao@1053: check_item_counts(g,0,0); klao@1053: klao@1053: Node klao@1053: n1 = g.addNode(), klao@1053: n2 = g.addNode(), klao@1053: n3 = g.addNode(); klao@1053: klao@1053: UEdge klao@1053: e1 = g.addEdge(n1, n2), klao@1053: e2 = g.addEdge(n2, n3); klao@1053: klao@1053: // print_items(g); klao@1053: klao@1053: check_item_counts(g,3,2); deba@1680: } klao@1030: deba@1680: void checkGridGraph(const GridGraph& g, int w, int h) { deba@1680: check(g.width() == w, "Wrong width"); deba@1680: check(g.height() == h, "Wrong height"); klao@1054: deba@1680: for (int i = 0; i < w; ++i) { deba@1680: for (int j = 0; j < h; ++j) { deba@1680: check(g.col(g(i, j)) == i, "Wrong col"); deba@1680: check(g.row(g(i, j)) == j, "Wrong row"); deba@1680: } deba@1680: } deba@1680: deba@1680: for (int i = 0; i < w; ++i) { deba@1680: for (int j = 0; j < h - 1; ++j) { deba@1680: check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down"); deba@1680: check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down"); deba@1680: } deba@1680: check(g.down(g(i, h - 1)) == INVALID, "Wrong down"); deba@1680: } deba@1680: deba@1680: for (int i = 0; i < w; ++i) { deba@1680: for (int j = 1; j < h; ++j) { deba@1680: check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up"); deba@1680: check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up"); deba@1680: } deba@1680: check(g.up(g(i, 0)) == INVALID, "Wrong up"); deba@1680: } deba@1680: deba@1680: for (int j = 0; j < h; ++j) { deba@1680: for (int i = 0; i < w - 1; ++i) { deba@1680: check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right"); deba@1680: check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right"); deba@1680: } deba@1680: check(g.right(g(w - 1, j)) == INVALID, "Wrong right"); deba@1680: } deba@1680: deba@1680: for (int j = 0; j < h; ++j) { deba@1680: for (int i = 1; i < w; ++i) { deba@1680: check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left"); deba@1680: check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left"); deba@1680: } deba@1680: check(g.left(g(0, j)) == INVALID, "Wrong left"); deba@1680: } klao@1054: } klao@1054: klao@1054: int main() { klao@1054: check_concepts(); klao@1054: klao@1909: check_graph(); klao@1909: check_graph(); klao@1054: deba@1568: { klao@1909: FullUGraph g(5); deba@1568: check_item_counts(g, 5, 10); deba@1568: } deba@1568: deba@1680: { deba@1680: GridGraph g(5, 6); deba@1680: check_item_counts(g, 30, 49); deba@1680: checkGridGraph(g, 5, 6); deba@1680: } deba@1680: deba@1680: std::cout << __FILE__ ": All tests passed.\n"; deba@1680: klao@962: return 0; klao@962: }