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