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 <vector>
deba@1187: #include <algorithm>
deba@1187: 
deba@1187: #include <lemon/dijkstra.h>
deba@1187: 
deba@1187: class IntIntMap : public std::vector<int> {
deba@1187: public:
deba@1187:   typedef std::vector<int> Parent;
deba@1187: 
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 <typename _Heap>
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<int> v(n);
deba@1187: 
deba@1187:   for (int i = 0; i < n; ++i) {
deba@1187:     v[i] = rand() % 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 <typename _Heap>
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<int> v(n);
deba@1206: 
deba@1206:   for (int i = 0; i < n; ++i) {
deba@1206:     v[i] = rand() % 1000;
deba@1206:     heap.push(i, v[i]);
deba@1206:   }
deba@1206:   for (int i = 0; i < n; ++i) {
deba@1206:     v[i] += rand() % 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 <typename _Graph, typename _LengthMap, typename _Heap>
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<Graph, LengthMap>::template DefStandardHeap<Heap>::
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: }