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 <string>
alpar@96: #include <iostream>
alpar@96: 
alpar@96: #include <lemon/concepts/path.h>
alpar@96: #include <lemon/concepts/digraph.h>
kpeter@1212: #include <lemon/concept_check.h>
alpar@96: 
alpar@96: #include <lemon/path.h>
alpar@96: #include <lemon/list_graph.h>
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 <typename GR>
kpeter@1212: void checkConcepts() {
kpeter@1212:   checkConcept<concepts::Path<GR>, concepts::Path<GR> >();
kpeter@1212:   checkConcept<concepts::Path<GR>, Path<GR> >();
kpeter@1212:   checkConcept<concepts::Path<GR>, SimplePath<GR> >();
kpeter@1212:   checkConcept<concepts::Path<GR>, StaticPath<GR> >();
kpeter@1212:   checkConcept<concepts::Path<GR>, ListPath<GR> >();
kpeter@1212: }
kpeter@1212: 
kpeter@1212: // Conecpt checking for path structures
kpeter@1212: void checkPathConcepts() {
kpeter@1212:   checkConcepts<concepts::Digraph>();
kpeter@1212:   checkConcepts<ListDigraph>();
alpar@96: }
alpar@96: 
alpar@1144: // Check if proper copy consructor is called (use valgrind for testing)
kpeter@1212: template <typename GR, typename P1, typename P2>
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<ListDigraph> Path1;
kpeter@1212:   typedef SimplePath<ListDigraph> Path2;
kpeter@1212:   typedef ListPath<ListDigraph> Path3;
kpeter@1212:   typedef StaticPath<ListDigraph> Path4;
kpeter@1212:   checkCopy<ListDigraph, Path1, Path2>(a);
kpeter@1212:   checkCopy<ListDigraph, Path1, Path3>(a);
kpeter@1212:   checkCopy<ListDigraph, Path1, Path4>(a);
kpeter@1212:   checkCopy<ListDigraph, Path2, Path1>(a);
kpeter@1212:   checkCopy<ListDigraph, Path2, Path3>(a);
kpeter@1212:   checkCopy<ListDigraph, Path2, Path4>(a);
kpeter@1212:   checkCopy<ListDigraph, Path3, Path1>(a);
kpeter@1212:   checkCopy<ListDigraph, Path3, Path2>(a);
kpeter@1212:   checkCopy<ListDigraph, Path3, Path4>(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<Path<GR> >();
kpeter@1212:     checkBackAndFrontInsertablePath<ListPath<GR> >();
kpeter@1212:     checkBackInsertablePath<SimplePath<GR> >();
kpeter@1212: 
kpeter@1421:     checkSubscriptOperator<Path<GR> >();
kpeter@1421:     checkSubscriptOperator<SimplePath<GR> >();
kpeter@1421:     checkSubscriptOperator<StaticPath<GR> >();
kpeter@1421:     checkSubscriptOperator<ListPath<GR> >();
kpeter@1421: 
kpeter@1212:     checkListPathSplitAndSplice();
kpeter@1212:   }
kpeter@1212: 
kpeter@1212: private:
kpeter@1212: 
kpeter@1212:   template <typename P>
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<P> 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<P> 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<P> 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 <typename P>
kpeter@1212:   void checkBackAndFrontInsertablePath() {
kpeter@1212: 
kpeter@1212:     // Include back insertable test cases
kpeter@1212:     checkBackInsertablePath<P>();
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@1421:   template <typename P>
kpeter@1421:   void checkSubscriptOperator() {
kpeter@1421:     SimplePath<GR> p0;
kpeter@1421:     p0.addBack(a1);
kpeter@1421:     p0.addBack(a3);
kpeter@1421:     p0.addBack(a2);
kpeter@1421:     P p = p0;
kpeter@1421:     check(!p.empty(), "Wrong empty()");
kpeter@1421:     check(p.length() == 3, "Wrong length");
kpeter@1421:     check(p.front() == a1, "Wrong front()");
kpeter@1421:     check(p.back() == a2, "Wrong back()");
kpeter@1421:     check(p.nth(0) == a1, "Wrong nth()");
kpeter@1421:     check(p.nth(1) == a3, "Wrong nth()");
kpeter@1421:     check(p.nth(2) == a2, "Wrong nth()");
kpeter@1421:     check(p[0] == a1, "Wrong operator[]");
kpeter@1421:     check(p[1] == a3, "Wrong operator[]");
kpeter@1421:     check(p[2] == a2, "Wrong operator[]");
kpeter@1421:   }
kpeter@1421: 
kpeter@1212:   void checkListPathSplitAndSplice() {
kpeter@1212: 
kpeter@1212:     // Build a path with spliceFront() and spliceBack()
kpeter@1212:     ListPath<GR> 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<GR>::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: }