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: 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: { alpar@100: std::cerr << "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: { alpar@100: std::cerr << "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: { alpar@100: std::cerr << "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: { alpar@100: std::cerr << "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: std::cout << __FILE__ ": All tests passed.\n"; alpar@100: alpar@100: return 0; alpar@100: }