The graph adadptors can be alteration observed.
In most cases it uses the adapted graph alteration notifiers.
Only special case is now the UndirGraphAdaptor, where
we have to proxy the signals from the graph.
The SubBidirGraphAdaptor is removed, because it doest not
gives more feature than the EdgeSubGraphAdaptor<UndirGraphAdaptor<Graph>>.
The ResGraphAdaptor is based on this composition.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
24 #include <lemon/concept_check.h>
25 #include <lemon/concept/heap.h>
27 #include <lemon/smart_graph.h>
29 #include <lemon/graph_reader.h>
31 #include <lemon/bin_heap.h>
32 #include <lemon/fib_heap.h>
33 #include <lemon/radix_heap.h>
34 #include <lemon/linear_heap.h>
36 #include "test_tools.h"
38 #include "heap_test.h"
40 #include <lemon/time_measure.h>
42 using namespace lemon;
43 using namespace lemon::concept;
50 typedef IntIntMap ItemIntMap;
52 typedef ListGraph Graph;
54 typedef Graph::Edge Edge;
55 typedef Graph::Node Node;
56 typedef Graph::EdgeIt EdgeIt;
57 typedef Graph::NodeIt NodeIt;
58 typedef Graph::EdgeMap<int> LengthMap;
61 LengthMap length(graph);
64 /// \todo create own test graph
67 if( getenv("srcdir") )
68 f_name = std::string(getenv("srcdir"));
70 f_name += "/dijkstra_test.lgf";
72 std::ifstream input(f_name.c_str());
73 check(input, "Input file '" << f_name << "' not found.");
74 GraphReader<Graph>(input, graph).
75 readEdgeMap("capacity", length).
76 readNode("source", start).
80 std::cerr << "Checking Bin Heap" << std::endl;
82 typedef BinHeap<Item, Prio, ItemIntMap> IntHeap;
83 checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>();
84 heapSortTest<IntHeap>(100);
85 heapIncreaseTest<IntHeap>(100);
87 typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
88 checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
90 dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
91 std::cout << timer << std::endl;
94 std::cerr << "Checking Fib Heap" << std::endl;
96 typedef FibHeap<Item, Prio, ItemIntMap> IntHeap;
97 checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>();
98 heapSortTest<IntHeap>(100);
99 heapIncreaseTest<IntHeap>(100);
101 typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
102 checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
104 dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
105 std::cout << timer << std::endl;
108 std::cerr << "Checking Radix Heap" << std::endl;
110 typedef RadixHeap<Item, ItemIntMap> IntHeap;
111 checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>();
112 heapSortTest<IntHeap>(100);
113 heapIncreaseTest<IntHeap>(100);
115 typedef RadixHeap<Node, Graph::NodeMap<int> > NodeHeap;
116 checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
118 dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
119 std::cout << timer << std::endl;
123 std::cerr << "Checking Linear Heap" << std::endl;
125 typedef LinearHeap<Item, ItemIntMap> IntHeap;
126 checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>();
127 heapSortTest<IntHeap>(100);
128 heapIncreaseTest<IntHeap>(100);
130 typedef LinearHeap<Node, Graph::NodeMap<int> > NodeHeap;
131 checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
133 dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
134 std::cout << timer << std::endl;
137 std::cout << __FILE__ ": All tests passed.\n";