deba@57: /* -*- C++ -*- deba@57: * deba@57: * This file is a part of LEMON, a generic C++ optimization library deba@57: * alpar@107: * Copyright (C) 2003-2008 deba@57: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@57: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@57: * deba@57: * Permission to use, modify and distribute this software is granted deba@57: * provided that this copyright notice appears in all copies. For deba@57: * precise terms see the accompanying LICENSE file. deba@57: * deba@57: * This software is provided "AS IS" with no warranty of any kind, deba@57: * express or implied, and with no claim as to its suitability for any deba@57: * purpose. deba@57: * deba@57: */ deba@57: deba@57: #include deba@57: #include deba@109: #include deba@57: // #include deba@57: // #include deba@57: deba@149: #include deba@57: deba@57: #include "test_tools.h" deba@57: deba@57: deba@57: using namespace lemon; deba@57: using namespace lemon::concepts; deba@57: deba@57: void check_concepts() { deba@57: deba@57: { // checking digraph components deba@57: checkConcept(); deba@57: deba@57: checkConcept, deba@57: IDableGraphComponent<> >(); deba@57: deba@57: checkConcept, deba@57: IterableGraphComponent<> >(); deba@57: deba@57: checkConcept, deba@57: MappableGraphComponent<> >(); deba@57: deba@57: } deba@57: { deba@57: checkConcept(); deba@109: checkConcept(); deba@57: // checkConcept(); deba@57: // checkConcept(); deba@57: // checkConcept(); deba@57: } deba@57: } deba@57: deba@57: template deba@57: void check_item_counts(Graph &g, int n, int e) { deba@57: int nn = 0; deba@57: for (typename Graph::NodeIt it(g); it != INVALID; ++it) { deba@57: ++nn; deba@57: } deba@57: deba@57: check(nn == n, "Wrong node number."); deba@57: // check(countNodes(g) == n, "Wrong node number."); deba@57: deba@57: int ee = 0; deba@57: for (typename Graph::ArcIt it(g); it != INVALID; ++it) { deba@57: ++ee; deba@57: } deba@57: deba@57: check(ee == 2*e, "Wrong arc number."); deba@57: // check(countArcs(g) == 2*e, "Wrong arc number."); deba@57: deba@57: int uee = 0; deba@57: for (typename Graph::EdgeIt it(g); it != INVALID; ++it) { deba@57: ++uee; deba@57: } deba@57: deba@57: check(uee == e, "Wrong edge number."); deba@57: // check(countEdges(g) == e, "Wrong edge number."); deba@57: } deba@57: deba@57: template deba@149: void check_graph_counts() { deba@57: deba@149: TEMPLATE_GRAPH_TYPEDEFS(Graph); deba@57: Graph g; deba@57: deba@57: check_item_counts(g,0,0); deba@57: deba@57: Node deba@57: n1 = g.addNode(), deba@57: n2 = g.addNode(), deba@57: n3 = g.addNode(); deba@57: deba@57: Edge deba@57: e1 = g.addEdge(n1, n2), deba@57: e2 = g.addEdge(n2, n3); deba@57: deba@57: check_item_counts(g,3,2); deba@57: } deba@57: deba@149: template deba@149: void check_graph_validity() { deba@149: deba@149: TEMPLATE_GRAPH_TYPEDEFS(Graph); deba@149: Graph g; deba@149: deba@149: check_item_counts(g,0,0); deba@149: deba@149: Node deba@149: n1 = g.addNode(), deba@149: n2 = g.addNode(), deba@149: n3 = g.addNode(); deba@149: deba@149: Edge deba@149: e1 = g.addEdge(n1, n2), deba@149: e2 = g.addEdge(n2, n3); deba@149: deba@149: check(g.valid(n1), "Validity check"); deba@149: check(g.valid(e1), "Validity check"); deba@149: check(g.valid(g.direct(e1, true)), "Validity check"); deba@149: deba@149: check(!g.valid(g.nodeFromId(-1)), "Validity check"); deba@149: check(!g.valid(g.edgeFromId(-1)), "Validity check"); deba@149: check(!g.valid(g.arcFromId(-1)), "Validity check"); deba@149: deba@149: } deba@149: deba@149: template deba@149: void check_graph_validity_erase() { deba@149: deba@149: TEMPLATE_GRAPH_TYPEDEFS(Graph); deba@149: Graph g; deba@149: deba@149: check_item_counts(g,0,0); deba@149: deba@149: Node deba@149: n1 = g.addNode(), deba@149: n2 = g.addNode(), deba@149: n3 = g.addNode(); deba@149: deba@149: Edge deba@149: e1 = g.addEdge(n1, n2), deba@149: e2 = g.addEdge(n2, n3); deba@149: deba@149: check(g.valid(n1), "Validity check"); deba@149: check(g.valid(e1), "Validity check"); deba@149: check(g.valid(g.direct(e1, true)), "Validity check"); deba@149: deba@149: g.erase(n1); deba@149: deba@149: check(!g.valid(n1), "Validity check"); deba@149: check(g.valid(n2), "Validity check"); deba@149: check(g.valid(n3), "Validity check"); deba@149: check(!g.valid(e1), "Validity check"); deba@149: check(g.valid(e2), "Validity check"); deba@149: deba@149: check(!g.valid(g.nodeFromId(-1)), "Validity check"); deba@149: check(!g.valid(g.edgeFromId(-1)), "Validity check"); deba@149: check(!g.valid(g.arcFromId(-1)), "Validity check"); deba@149: deba@149: } deba@149: deba@149: deba@149: deba@57: // void checkGridGraph(const GridGraph& g, int w, int h) { deba@57: // check(g.width() == w, "Wrong width"); deba@57: // check(g.height() == h, "Wrong height"); deba@57: deba@57: // for (int i = 0; i < w; ++i) { deba@57: // for (int j = 0; j < h; ++j) { deba@57: // check(g.col(g(i, j)) == i, "Wrong col"); deba@57: // check(g.row(g(i, j)) == j, "Wrong row"); deba@57: // } deba@57: // } deba@57: deba@57: // for (int i = 0; i < w; ++i) { deba@57: // for (int j = 0; j < h - 1; ++j) { deba@57: // check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down"); deba@57: // check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down"); deba@57: // } deba@57: // check(g.down(g(i, h - 1)) == INVALID, "Wrong down"); deba@57: // } deba@57: deba@57: // for (int i = 0; i < w; ++i) { deba@57: // for (int j = 1; j < h; ++j) { deba@57: // check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up"); deba@57: // check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up"); deba@57: // } deba@57: // check(g.up(g(i, 0)) == INVALID, "Wrong up"); deba@57: // } deba@57: deba@57: // for (int j = 0; j < h; ++j) { deba@57: // for (int i = 0; i < w - 1; ++i) { deba@57: // check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right"); deba@57: // check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right"); deba@57: // } deba@57: // check(g.right(g(w - 1, j)) == INVALID, "Wrong right"); deba@57: // } deba@57: deba@57: // for (int j = 0; j < h; ++j) { deba@57: // for (int i = 1; i < w; ++i) { deba@57: // check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left"); deba@57: // check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left"); deba@57: // } deba@57: // check(g.left(g(0, j)) == INVALID, "Wrong left"); deba@57: // } deba@57: // } deba@57: deba@57: int main() { deba@57: check_concepts(); deba@57: deba@149: check_graph_counts(); deba@149: check_graph_counts(); deba@149: deba@149: check_graph_validity_erase(); deba@149: check_graph_validity(); deba@57: deba@57: // { deba@57: // FullGraph g(5); deba@57: // check_item_counts(g, 5, 10); deba@57: // } deba@57: deba@57: // { deba@57: // GridGraph g(5, 6); deba@57: // check_item_counts(g, 30, 49); deba@57: // checkGridGraph(g, 5, 6); deba@57: // } deba@57: deba@57: std::cout << __FILE__ ": All tests passed.\n"; deba@57: deba@57: return 0; deba@57: }