// -*- c++ -*- #include #include #include #include #include #include #include #include #include "test_tools.h" #include "heap_test.h" #include "map_test.h" using namespace lemon; template class HeapConcept { public: template struct Constraints { public: void constraints() { Item item; Prio prio; typedef typename _Heap::state_enum state_enum; state_enum state; _Heap heap1 = _Heap(map); heap.push(item, prio); prio = heap.prio(); item = heap.top(); heap.pop(); heap.set(item, prio); heap.decrease(item, prio); heap.increase(item, prio); prio = heap[item]; heap.erase(item); state = heap.state(item); state = _Heap::PRE_HEAP; state = _Heap::IN_HEAP; state = _Heap::POST_HEAP; } _Heap& heap; ItemIntMap& map; }; }; int main() { typedef int Item; typedef int Prio; typedef IntIntMap ItemIntMap; typedef ListGraph Graph; typedef Graph::Edge Edge; typedef Graph::Node Node; typedef Graph::EdgeIt EdgeIt; typedef Graph::NodeIt NodeIt; typedef Graph::EdgeMap LengthMap; Graph graph; LengthMap length(graph); Node start; std::ifstream input("preflow_graph.dim"); readDimacs(input, graph, length, start); { std::cerr << "Checking Bin Heap" << std::endl; typedef BinHeap IntHeap; checkConcept, IntHeap>(); heapSortTest(20); typedef FibHeap > NodeHeap; checkConcept >, NodeHeap>(); dijkstraHeapTest(graph, length, start); } { std::cerr << "Checking Fib Heap" << std::endl; typedef FibHeap IntHeap; checkConcept, IntHeap>(); heapSortTest(20); typedef FibHeap > NodeHeap; checkConcept >, NodeHeap>(); dijkstraHeapTest(graph, length, start); } { std::cerr << "Checking Radix Heap" << std::endl; typedef RadixHeap IntHeap; checkConcept, IntHeap>(); heapSortTest(20); typedef RadixHeap > NodeHeap; checkConcept >, NodeHeap>(); dijkstraHeapTest(graph, length, start); } std::cout << __FILE__ ": All tests passed.\n"; return 0; }