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 <iostream>
alpar@100: #include <fstream>
alpar@100: #include <string>
alpar@100: #include <vector>
alpar@100: 
alpar@100: #include <lemon/concept_check.h>
alpar@100: #include <lemon/concepts/heap.h>
alpar@100: 
alpar@100: #include <lemon/list_graph.h>
alpar@100: 
alpar@100: #include <lemon/digraph_reader.h>
alpar@100: 
alpar@100: #include <lemon/bin_heap.h>
alpar@100: #include <lemon/fib_heap.h>
alpar@100: #include <lemon/radix_heap.h>
alpar@100: #include <lemon/bucket_heap.h>
alpar@100: 
alpar@100: #include "test_tools.h"
alpar@100: 
alpar@100: #include "heap_test.h"
alpar@100: 
alpar@100: #include <lemon/time_measure.h>
alpar@100: 
alpar@100: using namespace lemon;
alpar@100: using namespace lemon::concepts;
alpar@100: 
alpar@100: int main() {
alpar@100: 
alpar@100:   typedef int Item;
alpar@100:   typedef int Prio;
alpar@100:   typedef IntIntMap ItemIntMap;
alpar@100: 
alpar@100:   typedef ListDigraph Digraph;
alpar@100: 
alpar@100:   typedef Digraph::Arc Arc;
alpar@100:   typedef Digraph::Node Node;
alpar@100:   typedef Digraph::ArcIt ArcIt;
alpar@100:   typedef Digraph::NodeIt NodeIt;
alpar@100:   typedef Digraph::ArcMap<int> LengthMap;
alpar@100: 
alpar@100:   Digraph digraph;
alpar@100:   LengthMap length(digraph);
alpar@100:   Node start;
alpar@100: 
alpar@100:   /// \todo create own test digraph
alpar@100: 
alpar@100:   std::string f_name;
alpar@100:   if( getenv("srcdir") )
alpar@100:     f_name = std::string(getenv("srcdir"));
alpar@100:   else f_name = ".";
alpar@100:   f_name += "/test/dijkstra_test.lgf";
alpar@100:   
alpar@100:   std::ifstream input(f_name.c_str());
alpar@100:   check(input, "Input file '" << f_name << "' not found.");
alpar@100:   DigraphReader<Digraph>(input, digraph).
alpar@100:     readArcMap("capacity", length).
alpar@100:     readNode("source", start).
alpar@100:     run();  
alpar@100:  
alpar@100:   {
kpeter@171:     std::cout << "Checking Bin Heap" << std::endl;
alpar@100: 
alpar@100:     typedef BinHeap<Prio, ItemIntMap> IntHeap;
alpar@100:     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
alpar@100:     heapSortTest<IntHeap>(100);
alpar@100:     heapIncreaseTest<IntHeap>(100);
alpar@100:     
alpar@100:     typedef FibHeap<Prio, Digraph::NodeMap<int> > NodeHeap;
alpar@100:     checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
alpar@100:     Timer timer;
alpar@100:     dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
alpar@100:     std::cout << timer << std::endl;
alpar@100:   }
alpar@100:   {
kpeter@171:     std::cout << "Checking Fib Heap" << std::endl;
alpar@100: 
alpar@100:     typedef FibHeap<Prio, ItemIntMap> IntHeap;
alpar@100:     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
alpar@100:     heapSortTest<IntHeap>(100);
alpar@100:     heapIncreaseTest<IntHeap>(100);
alpar@100: 
alpar@100:     typedef FibHeap<Prio, Digraph::NodeMap<int> > NodeHeap;
alpar@100:     checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
alpar@100:     Timer timer;
alpar@100:     dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
alpar@100:     std::cout << timer << std::endl;
alpar@100:   }
alpar@100:   {
kpeter@171:     std::cout << "Checking Radix Heap" << std::endl;
alpar@100: 
alpar@100:     typedef RadixHeap<ItemIntMap> IntHeap;
alpar@100:     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
alpar@100:     heapSortTest<IntHeap>(100);
alpar@100:     heapIncreaseTest<IntHeap>(100);
alpar@100: 
alpar@100:     typedef RadixHeap<Digraph::NodeMap<int> > NodeHeap;
alpar@100:     checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
alpar@100:     Timer timer;
alpar@100:     dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
alpar@100:     std::cout << timer << std::endl;
alpar@100:   }
alpar@100: 
alpar@100:   {
kpeter@171:     std::cout << "Checking Bucket Heap" << std::endl;
alpar@100: 
alpar@100:     typedef BucketHeap<ItemIntMap> IntHeap;
alpar@100:     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
alpar@100:     heapSortTest<IntHeap>(100);
alpar@100:     heapIncreaseTest<IntHeap>(100);
alpar@100: 
alpar@100:     typedef BucketHeap<Digraph::NodeMap<int> > NodeHeap;
alpar@100:     checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
alpar@100:     Timer timer;
alpar@100:     dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
alpar@100:     std::cout << timer << std::endl;
alpar@100:   }
alpar@100: 
alpar@100:   return 0;
alpar@100: }