alpar@100: /* -*- C++ -*- alpar@100: * alpar@100: * This file is a part of LEMON, a generic C++ optimization library alpar@100: * alpar@100: * Copyright (C) 2003-2008 alpar@100: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@100: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@100: * alpar@100: * Permission to use, modify and distribute this software is granted alpar@100: * provided that this copyright notice appears in all copies. For alpar@100: * precise terms see the accompanying LICENSE file. alpar@100: * alpar@100: * This software is provided "AS IS" with no warranty of any kind, alpar@100: * express or implied, and with no claim as to its suitability for any alpar@100: * purpose. alpar@100: * alpar@100: */ alpar@100: alpar@100: #include alpar@100: #include alpar@100: alpar@100: #include alpar@100: alpar@100: class IntIntMap : public std::vector { alpar@100: public: alpar@100: typedef std::vector Parent; alpar@100: alpar@100: typedef int Key; alpar@100: typedef int Value; alpar@100: alpar@100: IntIntMap() : Parent() {} alpar@100: IntIntMap(int n) : Parent(n) {} alpar@100: IntIntMap(int n, int v) : Parent(n, v) {} alpar@100: alpar@100: void set(int key, int value) { alpar@100: Parent::operator[](key) = value; alpar@100: } alpar@100: }; alpar@100: alpar@100: alpar@100: template alpar@100: void heapSortTest(int n) { alpar@100: typedef _Heap Heap; alpar@100: IntIntMap map(n, -1); alpar@100: alpar@100: Heap heap(map); alpar@100: alpar@100: std::vector v(n); alpar@100: alpar@100: for (int i = 0; i < n; ++i) { alpar@100: v[i] = rnd[1000]; alpar@100: heap.push(i, v[i]); alpar@100: } alpar@100: std::sort(v.begin(), v.end()); alpar@100: for (int i = 0; i < n; ++i) { alpar@100: check(v[i] == heap.prio() ,"Wrong order in heap sort."); alpar@100: heap.pop(); alpar@100: } alpar@100: } alpar@100: alpar@100: template alpar@100: void heapIncreaseTest(int n) { alpar@100: typedef _Heap Heap; alpar@100: IntIntMap map(n, -1); alpar@100: alpar@100: Heap heap(map); alpar@100: alpar@100: std::vector v(n); alpar@100: alpar@100: for (int i = 0; i < n; ++i) { alpar@100: v[i] = rnd[1000]; alpar@100: heap.push(i, v[i]); alpar@100: } alpar@100: for (int i = 0; i < n; ++i) { alpar@100: v[i] += rnd[1000]; alpar@100: heap.increase(i, v[i]); alpar@100: } alpar@100: std::sort(v.begin(), v.end()); alpar@100: for (int i = 0; i < n; ++i) { alpar@100: check(v[i] == heap.prio() ,"Wrong order in heap increase test."); alpar@100: heap.pop(); alpar@100: } alpar@100: } alpar@100: alpar@100: alpar@100: alpar@100: template alpar@100: void dijkstraHeapTest(_Digraph& digraph, _LengthMap& length, alpar@100: typename _Digraph::Node& start) { alpar@100: alpar@100: typedef _Heap Heap; alpar@100: typedef _Digraph Digraph; alpar@100: typedef _LengthMap LengthMap; alpar@100: alpar@100: typedef typename Digraph::Node Node; alpar@100: typedef typename Digraph::Arc Arc; alpar@100: typedef typename Digraph::NodeIt NodeIt; alpar@100: typedef typename Digraph::ArcIt ArcIt; alpar@100: alpar@100: typename Dijkstra::template DefStandardHeap:: alpar@100: Create dijkstra(digraph, length); alpar@100: alpar@100: dijkstra.run(start); alpar@100: alpar@100: for(ArcIt e(digraph); e!=INVALID; ++e) { alpar@100: Node u=digraph.source(e); alpar@100: Node v=digraph.target(e); alpar@100: if (dijkstra.reached(u)) { alpar@100: check( dijkstra.dist(v) - dijkstra.dist(u) <= length[e], alpar@100: "Error in a shortest path tree arc!"); alpar@100: } alpar@100: } alpar@100: alpar@100: for(NodeIt v(digraph); v!=INVALID; ++v) { alpar@100: if ( dijkstra.reached(v) && dijkstra.predArc(v) != INVALID ) { alpar@100: Arc e=dijkstra.predArc(v); alpar@100: Node u=digraph.source(e); alpar@100: check( dijkstra.dist(v) - dijkstra .dist(u) == length[e], alpar@100: "Error in a shortest path tree arc!"); alpar@100: } alpar@100: } alpar@100: alpar@100: }