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