alpar@209: /* -*- mode: C++; indent-tabs-mode: nil; -*- alpar@96: * alpar@209: * This file is a part of LEMON, a generic C++ optimization library. alpar@96: * alpar@1270: * Copyright (C) 2003-2013 alpar@96: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@96: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@96: * alpar@96: * Permission to use, modify and distribute this software is granted alpar@96: * provided that this copyright notice appears in all copies. For alpar@96: * precise terms see the accompanying LICENSE file. alpar@96: * alpar@96: * This software is provided "AS IS" with no warranty of any kind, alpar@96: * express or implied, and with no claim as to its suitability for any alpar@96: * purpose. alpar@96: * alpar@96: */ alpar@96: alpar@96: #include alpar@96: #include alpar@96: alpar@96: #include alpar@96: #include kpeter@1212: #include alpar@96: alpar@96: #include alpar@96: #include alpar@96: alpar@96: #include "test_tools.h" alpar@96: alpar@96: using namespace std; alpar@96: using namespace lemon; alpar@96: kpeter@1212: template kpeter@1212: void checkConcepts() { kpeter@1212: checkConcept, concepts::Path >(); kpeter@1212: checkConcept, Path >(); kpeter@1212: checkConcept, SimplePath >(); kpeter@1212: checkConcept, StaticPath >(); kpeter@1212: checkConcept, ListPath >(); kpeter@1212: } kpeter@1212: kpeter@1212: // Conecpt checking for path structures kpeter@1212: void checkPathConcepts() { kpeter@1212: checkConcepts(); kpeter@1212: checkConcepts(); alpar@96: } alpar@96: alpar@1144: // Check if proper copy consructor is called (use valgrind for testing) kpeter@1212: template kpeter@1212: void checkCopy(typename GR::Arc a) { kpeter@1212: P1 p; kpeter@1212: p.addBack(a); kpeter@1212: P1 q; kpeter@1212: q = p; kpeter@1212: P1 r(p); kpeter@1212: P2 q2; kpeter@1212: q2 = p; kpeter@1212: P2 r2(p); kpeter@1212: } kpeter@1212: kpeter@1212: // Tests for copy constructors and assignment operators of paths kpeter@1212: void checkPathCopy() { alpar@1144: ListDigraph g; kpeter@1212: ListDigraph::Arc a = g.addArc(g.addNode(), g.addNode()); kpeter@1212: kpeter@1212: typedef Path Path1; kpeter@1212: typedef SimplePath Path2; kpeter@1212: typedef ListPath Path3; kpeter@1212: typedef StaticPath Path4; kpeter@1212: checkCopy(a); kpeter@1212: checkCopy(a); kpeter@1212: checkCopy(a); kpeter@1212: checkCopy(a); kpeter@1212: checkCopy(a); kpeter@1212: checkCopy(a); kpeter@1212: checkCopy(a); kpeter@1212: checkCopy(a); kpeter@1212: checkCopy(a); alpar@1144: } kpeter@1212: kpeter@1212: // Class for testing path functions kpeter@1212: class CheckPathFunctions { kpeter@1212: typedef ListDigraph GR; kpeter@1212: DIGRAPH_TYPEDEFS(GR); kpeter@1212: GR gr; kpeter@1212: const GR& cgr; kpeter@1212: Node n1, n2, n3, n4; kpeter@1212: Node tmp_n; kpeter@1212: Arc a1, a2, a3, a4; kpeter@1212: Arc tmp_a; kpeter@1212: kpeter@1212: public: kpeter@1212: kpeter@1212: CheckPathFunctions() : cgr(gr) { kpeter@1212: n1 = gr.addNode(); kpeter@1212: n2 = gr.addNode(); kpeter@1212: n3 = gr.addNode(); kpeter@1212: n4 = gr.addNode(); kpeter@1212: a1 = gr.addArc(n1, n2); kpeter@1212: a2 = gr.addArc(n2, n3); kpeter@1212: a3 = gr.addArc(n3, n4); kpeter@1212: a4 = gr.addArc(n4, n1); kpeter@1212: } kpeter@1212: kpeter@1212: void run() { kpeter@1212: checkBackAndFrontInsertablePath >(); kpeter@1212: checkBackAndFrontInsertablePath >(); kpeter@1212: checkBackInsertablePath >(); kpeter@1212: kpeter@1212: checkListPathSplitAndSplice(); kpeter@1212: } kpeter@1212: kpeter@1212: private: kpeter@1212: kpeter@1212: template kpeter@1212: void checkBackInsertablePath() { kpeter@1212: kpeter@1212: // Create and check empty path kpeter@1212: P p; kpeter@1212: const P& cp = p; kpeter@1212: check(cp.empty(), "The path is not empty"); kpeter@1212: check(cp.length() == 0, "The path is not empty"); kpeter@1212: // check(cp.front() == INVALID, "Wrong front()"); kpeter@1212: // check(cp.back() == INVALID, "Wrong back()"); kpeter@1212: typename P::ArcIt ai(cp); kpeter@1212: check(ai == INVALID, "Wrong ArcIt"); kpeter@1212: check(pathSource(cgr, cp) == INVALID, "Wrong pathSource()"); kpeter@1212: check(pathTarget(cgr, cp) == INVALID, "Wrong pathTarget()"); kpeter@1212: check(checkPath(cgr, cp), "Wrong checkPath()"); kpeter@1212: PathNodeIt

ni(cgr, cp); kpeter@1212: check(ni == INVALID, "Wrong PathNodeIt"); kpeter@1212: kpeter@1212: // Check single-arc path kpeter@1212: p.addBack(a1); kpeter@1212: check(!cp.empty(), "Wrong empty()"); kpeter@1212: check(cp.length() == 1, "Wrong length"); kpeter@1212: check(cp.front() == a1, "Wrong front()"); kpeter@1212: check(cp.back() == a1, "Wrong back()"); kpeter@1212: check(cp.nth(0) == a1, "Wrong nth()"); kpeter@1212: ai = cp.nthIt(0); kpeter@1212: check((tmp_a = ai) == a1, "Wrong nthIt()"); kpeter@1212: check(++ai == INVALID, "Wrong nthIt()"); kpeter@1212: typename P::ArcIt ai2(cp); kpeter@1212: check((tmp_a = ai2) == a1, "Wrong ArcIt"); kpeter@1212: check(++ai2 == INVALID, "Wrong ArcIt"); kpeter@1212: check(pathSource(cgr, cp) == n1, "Wrong pathSource()"); kpeter@1212: check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()"); kpeter@1212: check(checkPath(cgr, cp), "Wrong checkPath()"); kpeter@1212: PathNodeIt

ni2(cgr, cp); kpeter@1212: check((tmp_n = ni2) == n1, "Wrong PathNodeIt"); kpeter@1212: check((tmp_n = ++ni2) == n2, "Wrong PathNodeIt"); kpeter@1212: check(++ni2 == INVALID, "Wrong PathNodeIt"); kpeter@1212: kpeter@1212: // Check adding more arcs kpeter@1212: p.addBack(a2); kpeter@1212: p.addBack(a3); kpeter@1212: check(!cp.empty(), "Wrong empty()"); kpeter@1212: check(cp.length() == 3, "Wrong length"); kpeter@1212: check(cp.front() == a1, "Wrong front()"); kpeter@1212: check(cp.back() == a3, "Wrong back()"); kpeter@1212: check(cp.nth(0) == a1, "Wrong nth()"); kpeter@1212: check(cp.nth(1) == a2, "Wrong nth()"); kpeter@1212: check(cp.nth(2) == a3, "Wrong nth()"); kpeter@1212: typename P::ArcIt ai3(cp); kpeter@1212: check((tmp_a = ai3) == a1, "Wrong ArcIt"); kpeter@1212: check((tmp_a = ++ai3) == a2, "Wrong nthIt()"); kpeter@1212: check((tmp_a = ++ai3) == a3, "Wrong nthIt()"); kpeter@1212: check(++ai3 == INVALID, "Wrong nthIt()"); kpeter@1212: ai = cp.nthIt(0); kpeter@1212: check((tmp_a = ai) == a1, "Wrong nthIt()"); kpeter@1212: check((tmp_a = ++ai) == a2, "Wrong nthIt()"); kpeter@1212: ai = cp.nthIt(2); kpeter@1212: check((tmp_a = ai) == a3, "Wrong nthIt()"); kpeter@1212: check(++ai == INVALID, "Wrong nthIt()"); kpeter@1212: check(pathSource(cgr, cp) == n1, "Wrong pathSource()"); kpeter@1212: check(pathTarget(cgr, cp) == n4, "Wrong pathTarget()"); kpeter@1212: check(checkPath(cgr, cp), "Wrong checkPath()"); kpeter@1212: PathNodeIt

ni3(cgr, cp); kpeter@1212: check((tmp_n = ni3) == n1, "Wrong PathNodeIt"); kpeter@1212: check((tmp_n = ++ni3) == n2, "Wrong PathNodeIt"); kpeter@1212: check((tmp_n = ++ni3) == n3, "Wrong PathNodeIt"); kpeter@1212: check((tmp_n = ++ni3) == n4, "Wrong PathNodeIt"); kpeter@1212: check(++ni3 == INVALID, "Wrong PathNodeIt"); kpeter@1212: kpeter@1212: // Check arc removal and addition kpeter@1212: p.eraseBack(); kpeter@1212: p.eraseBack(); kpeter@1212: p.addBack(a2); kpeter@1212: check(!cp.empty(), "Wrong empty()"); kpeter@1212: check(cp.length() == 2, "Wrong length"); kpeter@1212: check(cp.front() == a1, "Wrong front()"); kpeter@1212: check(cp.back() == a2, "Wrong back()"); kpeter@1212: check(pathSource(cgr, cp) == n1, "Wrong pathSource()"); kpeter@1212: check(pathTarget(cgr, cp) == n3, "Wrong pathTarget()"); kpeter@1212: check(checkPath(cgr, cp), "Wrong checkPath()"); kpeter@1212: kpeter@1212: // Check clear() kpeter@1212: p.clear(); kpeter@1212: check(cp.empty(), "The path is not empty"); kpeter@1212: check(cp.length() == 0, "The path is not empty"); kpeter@1212: kpeter@1212: // Check inconsistent path kpeter@1212: p.addBack(a4); kpeter@1212: p.addBack(a2); kpeter@1212: p.addBack(a1); kpeter@1212: check(!cp.empty(), "Wrong empty()"); kpeter@1212: check(cp.length() == 3, "Wrong length"); kpeter@1212: check(cp.front() == a4, "Wrong front()"); kpeter@1212: check(cp.back() == a1, "Wrong back()"); kpeter@1212: check(pathSource(cgr, cp) == n4, "Wrong pathSource()"); kpeter@1212: check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()"); kpeter@1212: check(!checkPath(cgr, cp), "Wrong checkPath()"); kpeter@1212: } kpeter@1212: kpeter@1212: template kpeter@1212: void checkBackAndFrontInsertablePath() { kpeter@1212: kpeter@1212: // Include back insertable test cases kpeter@1212: checkBackInsertablePath

(); kpeter@1212: kpeter@1212: // Check front and back insertion kpeter@1212: P p; kpeter@1212: const P& cp = p; kpeter@1212: p.addFront(a4); kpeter@1212: p.addBack(a1); kpeter@1212: p.addFront(a3); kpeter@1212: check(!cp.empty(), "Wrong empty()"); kpeter@1212: check(cp.length() == 3, "Wrong length"); kpeter@1212: check(cp.front() == a3, "Wrong front()"); kpeter@1212: check(cp.back() == a1, "Wrong back()"); kpeter@1212: check(cp.nth(0) == a3, "Wrong nth()"); kpeter@1212: check(cp.nth(1) == a4, "Wrong nth()"); kpeter@1212: check(cp.nth(2) == a1, "Wrong nth()"); kpeter@1212: typename P::ArcIt ai(cp); kpeter@1212: check((tmp_a = ai) == a3, "Wrong ArcIt"); kpeter@1212: check((tmp_a = ++ai) == a4, "Wrong nthIt()"); kpeter@1212: check((tmp_a = ++ai) == a1, "Wrong nthIt()"); kpeter@1212: check(++ai == INVALID, "Wrong nthIt()"); kpeter@1212: ai = cp.nthIt(0); kpeter@1212: check((tmp_a = ai) == a3, "Wrong nthIt()"); kpeter@1212: check((tmp_a = ++ai) == a4, "Wrong nthIt()"); kpeter@1212: ai = cp.nthIt(2); kpeter@1212: check((tmp_a = ai) == a1, "Wrong nthIt()"); kpeter@1212: check(++ai == INVALID, "Wrong nthIt()"); kpeter@1212: check(pathSource(cgr, cp) == n3, "Wrong pathSource()"); kpeter@1212: check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()"); kpeter@1212: check(checkPath(cgr, cp), "Wrong checkPath()"); kpeter@1212: kpeter@1212: // Check eraseFront() kpeter@1212: p.eraseFront(); kpeter@1212: p.addBack(a2); kpeter@1212: check(!cp.empty(), "Wrong empty()"); kpeter@1212: check(cp.length() == 3, "Wrong length"); kpeter@1212: check(cp.front() == a4, "Wrong front()"); kpeter@1212: check(cp.back() == a2, "Wrong back()"); kpeter@1212: check(cp.nth(0) == a4, "Wrong nth()"); kpeter@1212: check(cp.nth(1) == a1, "Wrong nth()"); kpeter@1212: check(cp.nth(2) == a2, "Wrong nth()"); kpeter@1212: typename P::ArcIt ai2(cp); kpeter@1212: check((tmp_a = ai2) == a4, "Wrong ArcIt"); kpeter@1212: check((tmp_a = ++ai2) == a1, "Wrong nthIt()"); kpeter@1212: check((tmp_a = ++ai2) == a2, "Wrong nthIt()"); kpeter@1212: check(++ai2 == INVALID, "Wrong nthIt()"); kpeter@1212: ai = cp.nthIt(0); kpeter@1212: check((tmp_a = ai) == a4, "Wrong nthIt()"); kpeter@1212: check((tmp_a = ++ai) == a1, "Wrong nthIt()"); kpeter@1212: ai = cp.nthIt(2); kpeter@1212: check((tmp_a = ai) == a2, "Wrong nthIt()"); kpeter@1212: check(++ai == INVALID, "Wrong nthIt()"); kpeter@1212: check(pathSource(cgr, cp) == n4, "Wrong pathSource()"); kpeter@1212: check(pathTarget(cgr, cp) == n3, "Wrong pathTarget()"); kpeter@1212: check(checkPath(cgr, cp), "Wrong checkPath()"); kpeter@1212: } kpeter@1212: kpeter@1212: void checkListPathSplitAndSplice() { kpeter@1212: kpeter@1212: // Build a path with spliceFront() and spliceBack() kpeter@1212: ListPath p1, p2, p3, p4; kpeter@1212: p1.addBack(a3); kpeter@1212: p1.addFront(a2); kpeter@1212: p2.addBack(a1); kpeter@1212: p1.spliceFront(p2); kpeter@1212: p3.addFront(a4); kpeter@1212: p1.spliceBack(p3); kpeter@1212: check(p1.length() == 4, "Wrong length"); kpeter@1212: check(p1.front() == a1, "Wrong front()"); kpeter@1212: check(p1.back() == a4, "Wrong back()"); kpeter@1212: ListPath::ArcIt ai(p1); kpeter@1212: check((tmp_a = ai) == a1, "Wrong ArcIt"); kpeter@1212: check((tmp_a = ++ai) == a2, "Wrong nthIt()"); kpeter@1212: check((tmp_a = ++ai) == a3, "Wrong nthIt()"); kpeter@1212: check((tmp_a = ++ai) == a4, "Wrong nthIt()"); kpeter@1212: check(++ai == INVALID, "Wrong nthIt()"); kpeter@1212: check(checkPath(cgr, p1), "Wrong checkPath()"); kpeter@1212: kpeter@1212: // Check split() kpeter@1212: p1.split(p1.nthIt(2), p2); kpeter@1212: check(p1.length() == 2, "Wrong length"); kpeter@1212: ai = p1.nthIt(0); kpeter@1212: check((tmp_a = ai) == a1, "Wrong ArcIt"); kpeter@1212: check((tmp_a = ++ai) == a2, "Wrong nthIt()"); kpeter@1212: check(++ai == INVALID, "Wrong nthIt()"); kpeter@1212: check(checkPath(cgr, p1), "Wrong checkPath()"); kpeter@1212: check(p2.length() == 2, "Wrong length"); kpeter@1212: ai = p2.nthIt(0); kpeter@1212: check((tmp_a = ai) == a3, "Wrong ArcIt"); kpeter@1212: check((tmp_a = ++ai) == a4, "Wrong nthIt()"); kpeter@1212: check(++ai == INVALID, "Wrong nthIt()"); kpeter@1212: check(checkPath(cgr, p2), "Wrong checkPath()"); kpeter@1212: kpeter@1212: // Check split() and splice() kpeter@1212: p1.spliceFront(p2); kpeter@1212: p1.split(p1.nthIt(2), p2); kpeter@1212: p2.split(p2.nthIt(1), p3); kpeter@1212: p2.spliceBack(p1); kpeter@1212: p2.splice(p2.nthIt(1), p3); kpeter@1212: check(p2.length() == 4, "Wrong length"); kpeter@1212: check(p2.front() == a1, "Wrong front()"); kpeter@1212: check(p2.back() == a4, "Wrong back()"); kpeter@1212: ai = p2.nthIt(0); kpeter@1212: check((tmp_a = ai) == a1, "Wrong ArcIt"); kpeter@1212: check((tmp_a = ++ai) == a2, "Wrong nthIt()"); kpeter@1212: check((tmp_a = ++ai) == a3, "Wrong nthIt()"); kpeter@1212: check((tmp_a = ++ai) == a4, "Wrong nthIt()"); kpeter@1212: check(++ai == INVALID, "Wrong nthIt()"); kpeter@1212: check(checkPath(cgr, p2), "Wrong checkPath()"); kpeter@1212: } kpeter@1212: kpeter@1212: }; kpeter@1212: alpar@96: int main() { kpeter@1212: checkPathConcepts(); kpeter@1212: checkPathCopy(); kpeter@1212: CheckPathFunctions cpf; kpeter@1212: cpf.run(); alpar@1144: alpar@96: return 0; alpar@96: }