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
19 #include <lemon/time_measure.h>
20 #include <lemon/smart_graph.h>
21 #include <lemon/graph_utils.h>
22 #include <lemon/maps.h>
23 #include <lemon/radix_sort.h>
25 #include "test_tools.h"
33 using namespace lemon;
35 void checkRadixSort() {
38 vector<int> data1(n), data2(n);
39 for (int i = 0; i < n; ++i) {
40 data1[i] = data2[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500;
42 radixSort(data1.begin(), data1.end());
43 sort(data2.begin(), data2.end());
44 for (int i = 0; i < n; ++i) {
45 check(data1[i] == data2[i], "Test failed");
49 vector<unsigned char> data1(n), data2(n);
50 for (int i = 0; i < n; ++i) {
51 data1[i] = data2[i] = (int)(200 * (rand() / (RAND_MAX + 1.0)));
53 radixSort(data1.begin(), data1.end());
54 sort(data2.begin(), data2.end());
55 for (int i = 0; i < n; ++i) {
56 check(data1[i] == data2[i], "Test failed");
62 void checkCounterSort() {
65 vector<int> data1(n), data2(n);
66 for (int i = 0; i < n; ++i) {
67 data1[i] = data2[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500;
69 counterSort(data1.begin(), data1.end());
70 sort(data2.begin(), data2.end());
71 for (int i = 0; i < n; ++i) {
72 check(data1[i] == data2[i], "Test failed");
76 vector<unsigned char> data1(n), data2(n);
77 for (int i = 0; i < n; ++i) {
78 data1[i] = data2[i] = (int)(200 * (rand() / (RAND_MAX + 1.0)));
80 counterSort(data1.begin(), data1.end());
81 sort(data2.begin(), data2.end());
82 for (int i = 0; i < n; ++i) {
83 check(data1[i] == data2[i], "Test failed");
93 void checkGraphRadixSort() {
94 typedef SmartGraph Graph;
95 typedef Graph::Node Node;
96 typedef Graph::Edge Edge;
99 const int e = (int)(n * log((double)n));
104 for (int i = 0; i < n; ++i) {
105 nodes.push_back(graph.addNode());
108 for (int i = 0; i < e; ++i) {
109 int s = (int)(n * (double)rand() / (RAND_MAX + 1.0));
110 int t = (int)(n * (double)rand() / (RAND_MAX + 1.0));
111 edges.push_back(graph.addEdge(nodes[s], nodes[t]));
114 radixSort(edges.begin(), edges.end(),
115 mapFunctor(composeMap(IdMap<Graph, Node>(graph),
118 Graph::EdgeMap<bool> was(graph, false);
120 for (int i = 0; i < (int)edges.size(); ++i) {
121 check(!was[edges[i]], "Test failed");
122 was[edges[i]] = true;
125 for (int i = 1; i < (int)edges.size(); ++i) {
126 check(graph.id(graph.source(edges[i - 1])) <=
127 graph.id(graph.source(edges[i])), "Test failed");
132 void checkGraphCounterSort() {
133 typedef SmartGraph Graph;
134 typedef Graph::Node Node;
135 typedef Graph::Edge Edge;
138 const int e = (int)(n * log((double)n));
143 for (int i = 0; i < n; ++i) {
144 nodes.push_back(graph.addNode());
147 for (int i = 0; i < e; ++i) {
148 int s = (int)(n * (double)rand() / (RAND_MAX + 1.0));
149 int t = (int)(n * (double)rand() / (RAND_MAX + 1.0));
150 edges.push_back(graph.addEdge(nodes[s], nodes[t]));
153 counterSort(edges.begin(), edges.end(),
154 mapFunctor(composeMap(IdMap<Graph, Node>(graph),
157 counterSort(edges.begin(), edges.end(),
158 mapFunctor(composeMap(IdMap<Graph, Node>(graph),
161 Graph::EdgeMap<bool> was(graph, false);
163 for (int i = 0; i < (int)edges.size(); ++i) {
164 check(!was[edges[i]], "Test failed");
165 was[edges[i]] = true;
168 for (int i = 1; i < (int)edges.size(); ++i) {
169 check(graph.id(graph.target(edges[i - 1])) <
170 graph.id(graph.target(edges[i])) ||
171 (graph.id(graph.target(edges[i - 1])) ==
172 graph.id(graph.target(edges[i])) &&
173 graph.id(graph.source(edges[i - 1])) <=
174 graph.id(graph.source(edges[i]))), "Test failed");
179 void checkGraphSorts() {
180 checkGraphRadixSort();
181 checkGraphCounterSort();