routingkit-cch 0.1.4

Rust bindings for RoutingKit's Customizable Contraction Hierarchies (CCH)
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148

#include <routingkit/vector_io.h>
#include <routingkit/permutation.h>
#include <routingkit/inverse_vector.h>
#include <routingkit/customizable_contraction_hierarchy.h>
#include <routingkit/graph_util.h>
#include <routingkit/min_max.h>
#include <routingkit/timer.h>

#include <iostream>
#include <stdexcept>
#include <vector>

using namespace RoutingKit;
using namespace std;

int main(int argc, char*argv[]){
	try{
		string first_out_file;
		string head_file;
		string weight_file;
		string cch_order_file;

		if(argc != 5){
			cerr << argv[0] << " first_out head weight_file cch_order" << endl;
			return 1;
		}else{
			first_out_file = argv[1];
			head_file = argv[2];
			weight_file = argv[3];
			cch_order_file = argv[4];
		}

		long long timer;

		cout << "Loading Graph ... " << flush;

		auto first_out = load_vector<unsigned>(first_out_file);
		auto tail = invert_inverse_vector(first_out);
		auto head = load_vector<unsigned>(head_file);
		auto weight = load_vector<unsigned>(weight_file);

		cout << "done" << endl;

		cout << "Loading order ... " << flush;

		auto cch_order = load_vector<unsigned>(cch_order_file);

		cout << "done" << endl;


		cout << "Building CCH ... " << flush;

		timer = -get_micro_time();
		CustomizableContractionHierarchy cch(cch_order, invert_inverse_vector(first_out), head);
		timer += get_micro_time();

		cout << "done [" << timer << "musec]" << endl;

		cout << "Regular CCH Customization ... " << flush;

		timer = -get_micro_time();
		CustomizableContractionHierarchyMetric reference_metric(cch, weight);
		reference_metric.customize();
		timer += get_micro_time();

		cout << "done [" << timer << "musec]" << endl;


		#ifdef _OPENMP
		cout << "Constructing Parallelization data structures ... " << flush;
		timer = -get_micro_time();
		CustomizableContractionHierarchyParallelization parallel_customization(cch);
		timer += get_micro_time();
		cout << "done [" << timer << "musec]" << endl;

		cout << "Parallel CCH Customization ... " << flush;
		timer = -get_micro_time();
		CustomizableContractionHierarchyMetric parallel_metric(cch, weight);
		parallel_customization.customize(parallel_metric);
		timer += get_micro_time();
		cout << "done [" << timer << "musec]" << endl;

		if(reference_metric.forward != parallel_metric.forward || reference_metric.backward != parallel_metric.backward){
			throw std::runtime_error("Parallel Customization is broken");
		}else{
			cout << "Parallel Customization is ok" << endl;
		}
		#endif

		CustomizableContractionHierarchyMetric partial_metric = reference_metric;
		CustomizableContractionHierarchyPartialCustomization partial_update(cch);

		cout << "Nop Partial Customization ... " << flush;
		timer = -get_micro_time();
		partial_update.customize(partial_metric);
		timer += get_micro_time();
		cout << "done [" << timer << "musec]" << endl;


		if(reference_metric.forward != partial_metric.forward || reference_metric.backward != partial_metric.backward){
			throw std::runtime_error("Nop Partial Customization is broken");
		}else{
			cout << "Nop Partial Customization is ok" << endl;
		}

		cout << "No-Change Partial Customization ... " << flush;
		timer = -get_micro_time();
		for(unsigned i=0; i<1000; ++i)
			partial_update.update_arc(rand()%head.size());
		partial_update.customize(partial_metric);
		timer += get_micro_time();
		cout << "done [" << timer << "musec]" << endl;

		if(reference_metric.forward != partial_metric.forward || reference_metric.backward != partial_metric.backward){
			throw std::runtime_error("No-Change Partial Customization is broken");
		}else{
			cout << "No-Change Partial Customization is ok" << endl;
		}

		cout << "Partial Customization ... " << flush;
		timer = -get_micro_time();
		for(unsigned i=0; i<1000; ++i){
			unsigned a = rand()%head.size();
			weight[a] = rand()%1000;
			partial_update.update_arc(a);
		}
		partial_update.customize(partial_metric);
		timer += get_micro_time();
		cout << "done [" << timer << "musec]" << endl;

		reference_metric.customize();

		for(unsigned a = 0; a < reference_metric.forward.size(); ++a){
			if(reference_metric.forward[a] != partial_metric.forward[a])
				throw std::runtime_error("Partial Customization is broken: forward weight of "+std::to_string(a)+" is "+std::to_string(partial_metric.forward[a]) + " but should be "+std::to_string(reference_metric.forward[a]));
			if(reference_metric.backward[a] != partial_metric.backward[a])
				throw std::runtime_error("Partial Customization is broken: backward weight of "+std::to_string(a)+" is "+std::to_string(partial_metric.forward[a]) + " but should be "+std::to_string(reference_metric.forward[a]));

		}
		cout << "Partial Customization is ok" << endl;

	}catch(exception&err){
		cerr << "Stopped on exception : " << err.what() << endl;
		return 1;
	}
	return 0;
}