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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167

#include <routingkit/graph_util.h>
#include <routingkit/constants.h>
#include <routingkit/sort.h>
#include <routingkit/permutation.h>

#include <assert.h>
#include <algorithm>

namespace RoutingKit{

unsigned find_arc(const std::vector<unsigned>&first_out, const std::vector<unsigned>&head, unsigned x, unsigned y){
	unsigned ret = find_arc_or_return_invalid(first_out, head, x, y);
	assert(ret != invalid_id && "arc does not exist");
	return ret;
}

unsigned find_arc_or_return_invalid(const std::vector<unsigned>&first_out, const std::vector<unsigned>&head, unsigned x, unsigned y){
	assert(x < first_out.size()-1 && "node id out of bounds");
	assert(y < first_out.size()-1 && "node id out of bounds");

	for(unsigned xy = first_out[x]; xy < first_out[x+1]; ++xy)
		if(head[xy] == y)
			return xy;
	return invalid_id;
}

unsigned find_arc_given_sorted_head(const std::vector<unsigned>&first_out, const std::vector<unsigned>&head, unsigned x, unsigned y){
	unsigned ret = find_arc_or_return_invalid_given_sorted_head(first_out, head, x, y);
	assert(ret != invalid_id && "arc does not exist");
	return ret;
}

unsigned find_arc_or_return_invalid_given_sorted_head(const std::vector<unsigned>&first_out, const std::vector<unsigned>&head, unsigned x, unsigned y){
	assert(x < first_out.size()-1 && "node id out of bounds");
	assert(y < first_out.size()-1 && "node id out of bounds");

	auto
		begin = head.begin() + first_out[x],
		end = head.begin() + first_out[x+1];

	assert(std::is_sorted(begin, end) && "heads are not sorted");
	auto
		pos = std::lower_bound(begin, end, y);
	if(pos == end)
		return invalid_id;
	if(*pos != y)
		return invalid_id;
	return pos - head.begin();
}


std::vector<unsigned>convert_node_path_to_arc_path(const std::vector<unsigned>&first_out, const std::vector<unsigned>&head, std::vector<unsigned>path){
	if(!path.empty()){
		for(unsigned i=0; i<path.size()-1; ++i) {
			for(unsigned xy=first_out[path[i]]; ; ++xy) {
				assert(xy<first_out[path[i]+1]);
				if(head[xy] == path[i+1]) {
					path[i] = xy;
					break;
				}
			}
		}
		path.pop_back();
	}
	return path;
}


std::vector<unsigned>convert_arc_path_to_node_path(unsigned source, const std::vector<unsigned>&head, std::vector<unsigned>path){
	if(!path.empty()){
		path.resize(path.size()+1);
		for(unsigned i=path.size()-1; i>1; --i)
			path[i] = head[path[i-1]];
		path[0] = source;
	}
	return path;
}




std::vector<unsigned>compute_inverse_sort_permutation_first_by_left_then_by_right(
	unsigned a_count,
	const std::vector<unsigned>&a,
	unsigned b_count,
	const std::vector<unsigned>&b
){
	auto p = compute_inverse_stable_sort_permutation_using_key(b, b_count, [](unsigned x){return x;});
	auto q = compute_inverse_stable_sort_permutation_using_key(apply_inverse_permutation(p, std::move(a)), a_count, [](unsigned x){return x;});
	assert(is_sorted_using_less(a));
	return chain_permutation_first_left_then_right(q, p);
}

std::vector<unsigned>compute_sort_permutation_first_by_left_then_by_right(
	unsigned a_count,
	const std::vector<unsigned>&a,
	unsigned b_count,
	const std::vector<unsigned>&b
){
	auto p = compute_stable_sort_permutation_using_key(b, b_count, [](unsigned x){return x;});
	auto q = compute_stable_sort_permutation_using_key(apply_permutation(p, std::move(a)), a_count, [](unsigned x){return x;});
	assert(is_sorted_using_less(a));
	return chain_permutation_first_left_then_right(p, q);
}

std::vector<unsigned>compute_sort_permutation_first_by_left_then_by_right_and_apply_sort_to_left(
	unsigned a_count,
	std::vector<unsigned>&a,
	unsigned b_count,
	const std::vector<unsigned>&b
){
	auto p = compute_stable_sort_permutation_using_key(b, b_count, [](unsigned x){return x;});
	a = apply_permutation(p, std::move(a));
	auto q = compute_stable_sort_permutation_using_key(a, a_count, [](unsigned x){return x;});
	a = apply_permutation(q, std::move(a));
	assert(is_sorted_using_less(a));
	return chain_permutation_first_left_then_right(p, q);
}

std::vector<unsigned>compute_inverse_sort_permutation_first_by_left_then_by_right_and_apply_sort_to_left(
	unsigned a_count,
	std::vector<unsigned>&a,
	unsigned b_count,
	const std::vector<unsigned>&b
){
	auto p = compute_inverse_stable_sort_permutation_using_key(b, b_count, [](unsigned x){return x;});
	a = apply_inverse_permutation(p, std::move(a));
	auto q = compute_inverse_stable_sort_permutation_using_key(a, a_count, [](unsigned x){return x;});
	a = apply_inverse_permutation(q, std::move(a));
	assert(is_sorted_using_less(a));
	return chain_permutation_first_left_then_right(q, p);
}

std::vector<unsigned>compute_inverse_sort_permutation_first_by_tail_then_by_head_and_apply_sort_to_tail(
	unsigned node_count,
	std::vector<unsigned>&tail,
	const std::vector<unsigned>&head
){
	return compute_inverse_sort_permutation_first_by_left_then_by_right_and_apply_sort_to_left(node_count, tail, node_count, head);
}

std::vector<unsigned>compute_sort_permutation_first_by_tail_then_by_head_and_apply_sort_to_tail(
	unsigned node_count,
	std::vector<unsigned>&tail,
	const std::vector<unsigned>&head
){
	return compute_sort_permutation_first_by_left_then_by_right_and_apply_sort_to_left(node_count, tail, node_count, head);
}

std::vector<unsigned>compute_inverse_sort_permutation_first_by_tail_then_by_head(
	unsigned node_count,
	const std::vector<unsigned>&tail,
	const std::vector<unsigned>&head
){
	return compute_inverse_sort_permutation_first_by_left_then_by_right(node_count, tail, node_count, head);
}

std::vector<unsigned>compute_sort_permutation_first_by_tail_then_by_head(
	unsigned node_count,
	const std::vector<unsigned>&tail,
	const std::vector<unsigned>&head
){
	return compute_sort_permutation_first_by_left_then_by_right(node_count, tail, node_count, head);
}

} // RoutingKit