alpar@1956: /* -*- C++ -*-
alpar@1956:  *
alpar@1956:  * This file is a part of LEMON, a generic C++ optimization library
alpar@1956:  *
alpar@2553:  * Copyright (C) 2003-2008
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@1187: 
deba@1187: #include <iostream>
deba@1187: #include <fstream>
alpar@1215: #include <string>
deba@1187: #include <vector>
deba@1187: 
deba@1187: #include <lemon/concept_check.h>
alpar@2260: #include <lemon/concepts/heap.h>
deba@1187: 
deba@1206: #include <lemon/smart_graph.h>
deba@1206: 
deba@1206: #include <lemon/graph_reader.h>
deba@1206: 
deba@1187: #include <lemon/bin_heap.h>
deba@1187: #include <lemon/fib_heap.h>
deba@1187: #include <lemon/radix_heap.h>
deba@2038: #include <lemon/bucket_heap.h>
deba@1187: 
deba@1206: #include "test_tools.h"
deba@1187: 
deba@1187: #include "heap_test.h"
deba@1187: 
deba@1728: #include <lemon/time_measure.h>
deba@1187: 
deba@1187: using namespace lemon;
alpar@2260: using namespace lemon::concepts;
deba@1187: 
deba@1187: 
deba@1187: int main() {
deba@1187: 
deba@1187:   typedef int Item;
deba@1187:   typedef int Prio;
deba@1187:   typedef IntIntMap ItemIntMap;
deba@1187: 
deba@1187:   typedef ListGraph Graph;
deba@1187: 
deba@1187:   typedef Graph::Edge Edge;
deba@1187:   typedef Graph::Node Node;
deba@1187:   typedef Graph::EdgeIt EdgeIt;
deba@1187:   typedef Graph::NodeIt NodeIt;
deba@1187:   typedef Graph::EdgeMap<int> LengthMap;
deba@1187: 
deba@1187:   Graph graph;
deba@1187:   LengthMap length(graph);
deba@1187:   Node start;
deba@1187: 
deba@1206:   /// \todo create own test graph
alpar@1215: 
alpar@1215:   std::string f_name;
alpar@1215:   if( getenv("srcdir") )
alpar@1215:     f_name = std::string(getenv("srcdir"));
alpar@1215:   else f_name = ".";
ladanyi@2108:   f_name += "/test/dijkstra_test.lgf";
alpar@1215:   
alpar@1215:   std::ifstream input(f_name.c_str());
alpar@1215:   check(input, "Input file '" << f_name << "' not found.");
deba@1744:   GraphReader<Graph>(input, graph).
deba@1845:     readEdgeMap("capacity", length).
deba@1744:     readNode("source", start).
deba@1744:     run();  
deba@1187:  
deba@1187:   {
kpeter@2565:     std::cout << "Checking Bin Heap" << std::endl;
deba@1187: 
deba@2269:     typedef BinHeap<Prio, ItemIntMap> IntHeap;
deba@2269:     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
deba@1206:     heapSortTest<IntHeap>(100);
deba@1206:     heapIncreaseTest<IntHeap>(100);
deba@1187:     
kpeter@2565:     typedef BinHeap<Prio, Graph::NodeMap<int> > NodeHeap;
deba@2269:     checkConcept<Heap<Prio, Graph::NodeMap<int> >, NodeHeap>();
deba@1728:     Timer timer;
deba@1187:     dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
deba@1728:     std::cout << timer << std::endl;
deba@1187:   }
deba@1187:   {
kpeter@2565:     std::cout << "Checking Fib Heap" << std::endl;
deba@1187: 
deba@2269:     typedef FibHeap<Prio, ItemIntMap> IntHeap;
deba@2269:     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
deba@1206:     heapSortTest<IntHeap>(100);
deba@1206:     heapIncreaseTest<IntHeap>(100);
deba@1187: 
deba@2269:     typedef FibHeap<Prio, Graph::NodeMap<int> > NodeHeap;
deba@2269:     checkConcept<Heap<Prio, Graph::NodeMap<int> >, NodeHeap>();
deba@1728:     Timer timer;
deba@1187:     dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
deba@1728:     std::cout << timer << std::endl;
deba@1187:   }
deba@1187:   {
kpeter@2565:     std::cout << "Checking Radix Heap" << std::endl;
deba@1187: 
deba@2269:     typedef RadixHeap<ItemIntMap> IntHeap;
deba@2269:     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
deba@1206:     heapSortTest<IntHeap>(100);
deba@1206:     heapIncreaseTest<IntHeap>(100);
deba@1187: 
deba@2269:     typedef RadixHeap<Graph::NodeMap<int> > NodeHeap;
deba@2269:     checkConcept<Heap<Prio, Graph::NodeMap<int> >, NodeHeap>();
deba@1728:     Timer timer;
deba@1187:     dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
deba@1728:     std::cout << timer << std::endl;
deba@1728:   }
deba@1728: 
deba@1728:   {
kpeter@2565:     std::cout << "Checking Bucket Heap" << std::endl;
deba@1728: 
deba@2269:     typedef BucketHeap<ItemIntMap> IntHeap;
deba@2269:     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
deba@1728:     heapSortTest<IntHeap>(100);
deba@1728:     heapIncreaseTest<IntHeap>(100);
deba@1728: 
deba@2269:     typedef BucketHeap<Graph::NodeMap<int> > NodeHeap;
deba@2269:     checkConcept<Heap<Prio, Graph::NodeMap<int> >, NodeHeap>();
deba@1728:     Timer timer;
deba@1728:     dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
deba@1728:     std::cout << timer << std::endl;
deba@1187:   }
deba@1187: 
deba@1187:   std::cout << __FILE__ ": All tests passed.\n";
deba@1187: 
deba@1187:   return 0;
deba@1187: }