alpar@209: /* -*- mode: C++; indent-tabs-mode: nil; -*- deba@57: * alpar@209: * 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@57: #include "test_tools.h" kpeter@171: #include "graph_test.h" deba@57: deba@57: using namespace lemon; deba@57: using namespace lemon::concepts; deba@57: deba@228: template kpeter@338: void checkGraphBuild() { deba@228: TEMPLATE_GRAPH_TYPEDEFS(Graph); deba@228: deba@228: Graph G; deba@228: checkGraphNodeList(G, 0); deba@228: checkGraphEdgeList(G, 0); kpeter@338: checkGraphArcList(G, 0); deba@228: deba@228: Node deba@228: n1 = G.addNode(), deba@228: n2 = G.addNode(), deba@228: n3 = G.addNode(); deba@228: checkGraphNodeList(G, 3); deba@228: checkGraphEdgeList(G, 0); kpeter@338: checkGraphArcList(G, 0); deba@228: deba@228: Edge e1 = G.addEdge(n1, n2); deba@228: check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1), deba@228: "Wrong edge"); kpeter@338: deba@228: checkGraphNodeList(G, 3); kpeter@338: checkGraphEdgeList(G, 1); deba@228: checkGraphArcList(G, 2); deba@228: kpeter@338: checkGraphIncEdgeArcLists(G, n1, 1); kpeter@338: checkGraphIncEdgeArcLists(G, n2, 1); kpeter@338: checkGraphIncEdgeArcLists(G, n3, 0); deba@228: kpeter@338: checkGraphConEdgeList(G, 1); kpeter@338: checkGraphConArcList(G, 2); deba@228: kpeter@338: Edge e2 = G.addEdge(n2, n1), kpeter@338: e3 = G.addEdge(n2, n3); deba@228: kpeter@338: checkGraphNodeList(G, 3); kpeter@338: checkGraphEdgeList(G, 3); kpeter@338: checkGraphArcList(G, 6); deba@228: kpeter@338: checkGraphIncEdgeArcLists(G, n1, 2); kpeter@338: checkGraphIncEdgeArcLists(G, n2, 3); kpeter@338: checkGraphIncEdgeArcLists(G, n3, 1); deba@228: kpeter@338: checkGraphConEdgeList(G, 3); deba@228: checkGraphConArcList(G, 6); deba@228: deba@228: checkArcDirections(G); deba@228: deba@228: checkNodeIds(G); deba@228: checkArcIds(G); deba@228: checkEdgeIds(G); deba@228: checkGraphNodeMap(G); deba@228: checkGraphArcMap(G); deba@228: checkGraphEdgeMap(G); deba@228: } deba@228: kpeter@338: template kpeter@338: void checkGraphAlter() { kpeter@338: TEMPLATE_GRAPH_TYPEDEFS(Graph); kpeter@338: kpeter@338: Graph G; kpeter@338: Node n1 = G.addNode(), n2 = G.addNode(), kpeter@338: n3 = G.addNode(), n4 = G.addNode(); kpeter@338: Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1), kpeter@338: e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4), kpeter@338: e5 = G.addEdge(n4, n3); kpeter@338: kpeter@338: checkGraphNodeList(G, 4); kpeter@338: checkGraphEdgeList(G, 5); kpeter@338: checkGraphArcList(G, 10); kpeter@338: kpeter@338: // Check changeU() and changeV() kpeter@338: if (G.u(e2) == n2) { kpeter@338: G.changeU(e2, n3); kpeter@338: } else { kpeter@338: G.changeV(e2, n3); kpeter@338: } kpeter@338: kpeter@338: checkGraphNodeList(G, 4); kpeter@338: checkGraphEdgeList(G, 5); kpeter@338: checkGraphArcList(G, 10); kpeter@338: kpeter@338: checkGraphIncEdgeArcLists(G, n1, 3); kpeter@338: checkGraphIncEdgeArcLists(G, n2, 2); kpeter@338: checkGraphIncEdgeArcLists(G, n3, 3); kpeter@338: checkGraphIncEdgeArcLists(G, n4, 2); kpeter@338: kpeter@338: checkGraphConEdgeList(G, 5); kpeter@338: checkGraphConArcList(G, 10); kpeter@338: kpeter@338: if (G.u(e2) == n1) { kpeter@338: G.changeU(e2, n2); kpeter@338: } else { kpeter@338: G.changeV(e2, n2); kpeter@338: } kpeter@338: kpeter@338: checkGraphNodeList(G, 4); kpeter@338: checkGraphEdgeList(G, 5); kpeter@338: checkGraphArcList(G, 10); kpeter@338: kpeter@338: checkGraphIncEdgeArcLists(G, n1, 2); kpeter@338: checkGraphIncEdgeArcLists(G, n2, 3); kpeter@338: checkGraphIncEdgeArcLists(G, n3, 3); kpeter@338: checkGraphIncEdgeArcLists(G, n4, 2); kpeter@338: kpeter@338: checkGraphConEdgeList(G, 5); kpeter@338: checkGraphConArcList(G, 10); kpeter@338: kpeter@338: // Check contract() kpeter@338: G.contract(n1, n4, false); kpeter@338: kpeter@338: checkGraphNodeList(G, 3); kpeter@338: checkGraphEdgeList(G, 5); kpeter@338: checkGraphArcList(G, 10); kpeter@338: kpeter@338: checkGraphIncEdgeArcLists(G, n1, 4); kpeter@338: checkGraphIncEdgeArcLists(G, n2, 3); kpeter@338: checkGraphIncEdgeArcLists(G, n3, 3); kpeter@338: kpeter@338: checkGraphConEdgeList(G, 5); kpeter@338: checkGraphConArcList(G, 10); kpeter@338: kpeter@338: G.contract(n2, n3); kpeter@338: kpeter@338: checkGraphNodeList(G, 2); kpeter@338: checkGraphEdgeList(G, 3); kpeter@338: checkGraphArcList(G, 6); kpeter@338: kpeter@338: checkGraphIncEdgeArcLists(G, n1, 4); kpeter@338: checkGraphIncEdgeArcLists(G, n2, 2); kpeter@338: kpeter@338: checkGraphConEdgeList(G, 3); kpeter@338: checkGraphConArcList(G, 6); kpeter@338: } kpeter@338: kpeter@338: template kpeter@338: void checkGraphErase() { kpeter@338: TEMPLATE_GRAPH_TYPEDEFS(Graph); kpeter@338: kpeter@338: Graph G; kpeter@338: Node n1 = G.addNode(), n2 = G.addNode(), kpeter@338: n3 = G.addNode(), n4 = G.addNode(); kpeter@338: Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1), kpeter@338: e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4), kpeter@338: e5 = G.addEdge(n4, n3); kpeter@338: kpeter@338: // Check edge deletion kpeter@338: G.erase(e2); kpeter@338: kpeter@338: checkGraphNodeList(G, 4); kpeter@338: checkGraphEdgeList(G, 4); kpeter@338: checkGraphArcList(G, 8); kpeter@338: kpeter@338: checkGraphIncEdgeArcLists(G, n1, 2); kpeter@338: checkGraphIncEdgeArcLists(G, n2, 2); kpeter@338: checkGraphIncEdgeArcLists(G, n3, 2); kpeter@338: checkGraphIncEdgeArcLists(G, n4, 2); kpeter@338: kpeter@338: checkGraphConEdgeList(G, 4); kpeter@338: checkGraphConArcList(G, 8); kpeter@338: kpeter@338: // Check node deletion kpeter@338: G.erase(n3); kpeter@338: kpeter@338: checkGraphNodeList(G, 3); kpeter@338: checkGraphEdgeList(G, 2); kpeter@338: checkGraphArcList(G, 4); kpeter@338: kpeter@338: checkGraphIncEdgeArcLists(G, n1, 2); kpeter@338: checkGraphIncEdgeArcLists(G, n2, 1); kpeter@338: checkGraphIncEdgeArcLists(G, n4, 1); kpeter@338: kpeter@338: checkGraphConEdgeList(G, 2); kpeter@338: checkGraphConArcList(G, 4); kpeter@338: } kpeter@338: kpeter@338: kpeter@338: template kpeter@338: void checkGraphSnapshot() { kpeter@338: TEMPLATE_GRAPH_TYPEDEFS(Graph); kpeter@338: kpeter@338: Graph G; kpeter@338: Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode(); kpeter@338: Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1), kpeter@338: e3 = G.addEdge(n2, n3); kpeter@338: kpeter@338: checkGraphNodeList(G, 3); kpeter@338: checkGraphEdgeList(G, 3); kpeter@338: checkGraphArcList(G, 6); kpeter@338: kpeter@338: typename Graph::Snapshot snapshot(G); kpeter@338: kpeter@338: Node n = G.addNode(); kpeter@338: G.addEdge(n3, n); kpeter@338: G.addEdge(n, n3); kpeter@338: G.addEdge(n3, n2); kpeter@338: kpeter@338: checkGraphNodeList(G, 4); kpeter@338: checkGraphEdgeList(G, 6); kpeter@338: checkGraphArcList(G, 12); kpeter@338: kpeter@338: snapshot.restore(); kpeter@338: kpeter@338: checkGraphNodeList(G, 3); kpeter@338: checkGraphEdgeList(G, 3); kpeter@338: checkGraphArcList(G, 6); kpeter@338: kpeter@338: checkGraphIncEdgeArcLists(G, n1, 2); kpeter@338: checkGraphIncEdgeArcLists(G, n2, 3); kpeter@338: checkGraphIncEdgeArcLists(G, n3, 1); kpeter@338: kpeter@338: checkGraphConEdgeList(G, 3); kpeter@338: checkGraphConArcList(G, 6); kpeter@338: kpeter@338: checkNodeIds(G); kpeter@338: checkEdgeIds(G); kpeter@338: checkArcIds(G); kpeter@338: checkGraphNodeMap(G); kpeter@338: checkGraphEdgeMap(G); kpeter@338: checkGraphArcMap(G); kpeter@338: kpeter@338: G.addNode(); kpeter@338: snapshot.save(G); kpeter@338: kpeter@338: G.addEdge(G.addNode(), G.addNode()); kpeter@338: kpeter@338: snapshot.restore(); kpeter@338: kpeter@338: checkGraphNodeList(G, 4); kpeter@338: checkGraphEdgeList(G, 3); kpeter@338: checkGraphArcList(G, 6); kpeter@338: } kpeter@338: deba@228: void checkConcepts() { kpeter@171: { // Checking graph components deba@57: checkConcept(); deba@57: alpar@209: checkConcept, deba@57: IDableGraphComponent<> >(); deba@57: alpar@209: checkConcept, deba@57: IterableGraphComponent<> >(); deba@57: alpar@209: checkConcept, deba@57: MappableGraphComponent<> >(); deba@57: } kpeter@171: { // Checking skeleton graph kpeter@171: checkConcept(); deba@57: } kpeter@171: { // Checking ListGraph kpeter@171: checkConcept(); kpeter@171: checkConcept, ListGraph>(); kpeter@171: checkConcept, ListGraph>(); kpeter@171: checkConcept, ListGraph>(); kpeter@171: checkConcept, ListGraph>(); kpeter@171: } kpeter@171: { // Checking SmartGraph kpeter@171: checkConcept(); kpeter@171: checkConcept, SmartGraph>(); kpeter@171: checkConcept, SmartGraph>(); kpeter@171: checkConcept, SmartGraph>(); kpeter@171: } kpeter@171: // { // Checking FullGraph kpeter@171: // checkConcept(); kpeter@171: // checkGraphIterators(); kpeter@171: // } kpeter@171: // { // Checking GridGraph kpeter@171: // checkConcept(); kpeter@171: // checkGraphIterators(); kpeter@171: // } deba@57: } deba@57: deba@57: template deba@228: void checkGraphValidity() { deba@149: TEMPLATE_GRAPH_TYPEDEFS(Graph); deba@57: Graph g; 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: kpeter@171: check(g.valid(n1), "Wrong validity check"); kpeter@171: check(g.valid(e1), "Wrong validity check"); kpeter@171: check(g.valid(g.direct(e1, true)), "Wrong validity check"); kpeter@171: kpeter@171: check(!g.valid(g.nodeFromId(-1)), "Wrong validity check"); kpeter@171: check(!g.valid(g.edgeFromId(-1)), "Wrong validity check"); kpeter@171: check(!g.valid(g.arcFromId(-1)), "Wrong validity check"); deba@57: } deba@57: deba@149: template deba@228: void checkGraphValidityErase() { deba@149: TEMPLATE_GRAPH_TYPEDEFS(Graph); deba@149: Graph g; 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: kpeter@171: check(g.valid(n1), "Wrong validity check"); kpeter@171: check(g.valid(e1), "Wrong validity check"); kpeter@171: check(g.valid(g.direct(e1, true)), "Wrong validity check"); deba@149: deba@149: g.erase(n1); deba@149: kpeter@171: check(!g.valid(n1), "Wrong validity check"); kpeter@171: check(g.valid(n2), "Wrong validity check"); kpeter@171: check(g.valid(n3), "Wrong validity check"); kpeter@171: check(!g.valid(e1), "Wrong validity check"); kpeter@171: check(g.valid(e2), "Wrong validity check"); deba@149: kpeter@171: check(!g.valid(g.nodeFromId(-1)), "Wrong validity check"); kpeter@171: check(!g.valid(g.edgeFromId(-1)), "Wrong validity check"); kpeter@171: check(!g.valid(g.arcFromId(-1)), "Wrong validity check"); 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: // } alpar@209: 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"); alpar@209: // check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right"); deba@57: // } alpar@209: // 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"); alpar@209: // check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left"); deba@57: // } alpar@209: // check(g.left(g(0, j)) == INVALID, "Wrong left"); deba@57: // } deba@57: // } deba@57: deba@228: void checkGraphs() { kpeter@171: { // Checking ListGraph kpeter@338: checkGraphBuild(); kpeter@338: checkGraphAlter(); kpeter@338: checkGraphErase(); kpeter@338: checkGraphSnapshot(); deba@228: checkGraphValidityErase(); kpeter@171: } kpeter@171: { // Checking SmartGraph kpeter@338: checkGraphBuild(); kpeter@338: checkGraphSnapshot(); deba@228: checkGraphValidity(); kpeter@171: } kpeter@171: // { // Checking FullGraph kpeter@171: // FullGraph g(5); kpeter@171: // checkGraphNodeList(g, 5); kpeter@171: // checkGraphEdgeList(g, 10); kpeter@171: // } kpeter@171: // { // Checking GridGraph kpeter@171: // GridGraph g(5, 6); kpeter@171: // checkGraphNodeList(g, 30); kpeter@171: // checkGraphEdgeList(g, 49); kpeter@171: // checkGridGraph(g, 5, 6); kpeter@171: // } kpeter@171: } kpeter@171: deba@57: int main() { deba@228: checkConcepts(); deba@228: checkGraphs(); deba@57: return 0; deba@57: }