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