Line data Source code
1 : /*************************************************************************
2 : *
3 : * Project
4 : * _____ _____ __ __ _____
5 : * / ____| __ \| \/ | __ \
6 : * ___ _ __ ___ _ __ | | __| |__) | \ / | |__) |
7 : * / _ \| '_ \ / _ \ '_ \| | |_ | ___/| |\/| | ___/
8 : *| (_) | |_) | __/ | | | |__| | | | | | | |
9 : * \___/| .__/ \___|_| |_|\_____|_| |_| |_|_|
10 : * | |
11 : * |_|
12 : *
13 : * Copyright (C) Akiel Aries, <akiel@akiel.org>, et al.
14 : *
15 : * This software is licensed as described in the file LICENSE, which
16 : * you should have received as part of this distribution. The terms
17 : * among other details are referenced in the official documentation
18 : * seen here : https://akielaries.github.io/openGPMP/ along with
19 : * important files seen in this project.
20 : *
21 : * You may opt to use, copy, modify, merge, publish, distribute
22 : * and/or sell copies of the Software, and permit persons to whom
23 : * the Software is furnished to do so, under the terms of the
24 : * LICENSE file.
25 : *
26 : *
27 : *
28 : * This software is distributed on an AS IS basis, WITHOUT
29 : * WARRANTY OF ANY KIND, either express or implied.
30 : *
31 : ************************************************************************/
32 : #include <algorithm>
33 : #include <bitset>
34 : #include <cmath>
35 : #include <cstdint>
36 : #include <iostream>
37 : #include <limits>
38 : #include <openGPMP/disct/graphs.hpp>
39 : #include <queue>
40 : #include <set>
41 : #include <stack>
42 : #include <vector>
43 :
44 3 : void gpmp::Graph::add_edge(int v, int w, int weight) {
45 3 : adj_list[v].emplace_back(w, weight);
46 3 : adj_list[w].emplace_back(v, weight); // uncomment for undirected graph
47 3 : }
48 :
49 0 : void gpmp::Graph::dfs(int start) {
50 0 : std::vector<bool> visited(vertices, false);
51 0 : dfs_rec(start, visited);
52 0 : }
53 :
54 0 : void gpmp::Graph::dfs_rec(int v, std::vector<bool> &visited) {
55 0 : visited[v] = true;
56 0 : std::cout << v << " ";
57 :
58 0 : for (const auto &neighbor : adj_list[v]) {
59 0 : if (!visited[neighbor.first]) {
60 0 : dfs_rec(neighbor.first, visited);
61 : }
62 : }
63 0 : }
64 :
65 0 : void gpmp::Graph::bfs(int start) {
66 0 : std::vector<bool> visited(vertices, false);
67 0 : std::queue<int> bfs_queue;
68 :
69 0 : visited[start] = true;
70 0 : bfs_queue.push(start);
71 :
72 0 : while (!bfs_queue.empty()) {
73 0 : int v = bfs_queue.front();
74 0 : bfs_queue.pop();
75 0 : std::cout << v << " ";
76 :
77 0 : for (const auto &neighbor : adj_list[v]) {
78 0 : if (!visited[neighbor.first]) {
79 0 : visited[neighbor.first] = true;
80 0 : bfs_queue.push(neighbor.first);
81 : }
82 : }
83 : }
84 0 : }
85 :
86 0 : void gpmp::Graph::dijkstra(int start) {
87 : std::priority_queue<std::pair<int, int>,
88 : std::vector<std::pair<int, int>>,
89 : std::greater<std::pair<int, int>>>
90 0 : pq;
91 0 : std::vector<int> dist(vertices, std::numeric_limits<int>::max());
92 :
93 0 : dist[start] = 0;
94 0 : pq.push({0, start});
95 :
96 0 : while (!pq.empty()) {
97 0 : int u = pq.top().second;
98 0 : pq.pop();
99 :
100 0 : for (const auto &neighbor : adj_list[u]) {
101 0 : int v = neighbor.first;
102 0 : int weight = neighbor.second;
103 :
104 0 : if (dist[u] + weight < dist[v]) {
105 0 : dist[v] = dist[u] + weight;
106 0 : pq.push({dist[v], v});
107 : }
108 : }
109 : }
110 :
111 0 : std::cout << "Dijkstra's Shortest Paths from vertex " << start << ":\n";
112 0 : for (int i = 0; i < vertices; ++i)
113 0 : std::cout << "Vertex " << i << ": " << dist[i] << "\n";
114 0 : }
115 :
116 0 : void gpmp::Graph::bellman_ford(int start) {
117 0 : std::vector<int> dist(vertices, std::numeric_limits<int>::max());
118 0 : dist[start] = 0;
119 :
120 0 : for (int i = 0; i < vertices - 1; ++i) {
121 0 : for (int u = 0; u < vertices; ++u) {
122 0 : for (const auto &neighbor : adj_list[u]) {
123 0 : int v = neighbor.first;
124 0 : int weight = neighbor.second;
125 :
126 0 : if (dist[u] != std::numeric_limits<int>::max() &&
127 0 : dist[u] + weight < dist[v]) {
128 0 : dist[v] = dist[u] + weight;
129 : }
130 : }
131 : }
132 : }
133 :
134 0 : std::cout << "Bellman-Ford Shortest Paths from vertex " << start << ":\n";
135 0 : for (int i = 0; i < vertices; ++i)
136 0 : std::cout << "Vertex " << i << ": " << dist[i] << "\n";
137 0 : }
138 :
139 0 : std::vector<std::pair<int, std::pair<int, int>>> gpmp::Graph::kruskal() {
140 0 : std::vector<std::pair<int, std::pair<int, int>>> edges;
141 0 : for (int u = 0; u < vertices; ++u) {
142 0 : for (const auto &neighbor : adj_list[u]) {
143 0 : int v = neighbor.first;
144 0 : int weight = neighbor.second;
145 0 : edges.emplace_back(weight, std::make_pair(u, v));
146 : }
147 : }
148 :
149 0 : std::sort(edges.begin(), edges.end());
150 :
151 0 : std::vector<std::pair<int, std::pair<int, int>>> min_span_tree;
152 0 : std::vector<int> parent(vertices, -1);
153 :
154 0 : for (const auto &edge : edges) {
155 0 : int u = edge.second.first;
156 0 : int v = edge.second.second;
157 :
158 0 : int setU = find(parent, u);
159 0 : int setV = find(parent, v);
160 :
161 0 : if (setU != setV) {
162 0 : min_span_tree.push_back(edge);
163 0 : union_sets(parent, setU, setV);
164 : }
165 : }
166 :
167 0 : return min_span_tree;
168 0 : }
169 :
170 0 : void gpmp::Graph::floyd_warshall() {
171 : std::vector<std::vector<int>> dist(
172 0 : vertices,
173 0 : std::vector<int>(vertices, std::numeric_limits<int>::max()));
174 :
175 0 : for (int i = 0; i < vertices; ++i) {
176 0 : dist[i][i] = 0;
177 0 : for (const auto &neighbor : adj_list[i]) {
178 0 : int v = neighbor.first;
179 0 : int weight = neighbor.second;
180 0 : dist[i][v] = weight;
181 : }
182 : }
183 :
184 0 : for (int k = 0; k < vertices; ++k) {
185 0 : for (int i = 0; i < vertices; ++i) {
186 0 : for (int j = 0; j < vertices; ++j) {
187 0 : if (dist[i][k] != std::numeric_limits<int>::max() &&
188 0 : dist[k][j] != std::numeric_limits<int>::max() &&
189 0 : dist[i][k] + dist[k][j] < dist[i][j]) {
190 0 : dist[i][j] = dist[i][k] + dist[k][j];
191 : }
192 : }
193 : }
194 : }
195 :
196 0 : std::cout << "Floyd-Warshall Shortest Paths:\n";
197 0 : for (int i = 0; i < vertices; ++i) {
198 0 : for (int j = 0; j < vertices; ++j) {
199 0 : std::cout << "From " << i << " to " << j << ": ";
200 0 : if (dist[i][j] == std::numeric_limits<int>::max())
201 0 : std::cout << "INF";
202 : else
203 0 : std::cout << dist[i][j];
204 0 : std::cout << "\n";
205 : }
206 : }
207 0 : }
208 :
209 0 : void gpmp::Graph::topo_sort() {
210 0 : std::stack<int> topo_stack;
211 0 : std::vector<bool> visited(vertices, false);
212 :
213 0 : for (int i = 0; i < vertices; ++i) {
214 0 : if (!visited[i]) {
215 0 : topo_sort_util(i, visited, topo_stack);
216 : }
217 : }
218 :
219 0 : std::cout << "Topological Sorting: ";
220 0 : while (!topo_stack.empty()) {
221 0 : std::cout << topo_stack.top() << " ";
222 0 : topo_stack.pop();
223 : }
224 0 : std::cout << std::endl;
225 0 : }
226 :
227 0 : void gpmp::Graph::topo_sort_util(int v,
228 : std::vector<bool> &visited,
229 : std::stack<int> &topo_stack) {
230 0 : visited[v] = true;
231 :
232 0 : for (const auto &neighbor : adj_list[v]) {
233 0 : int u = neighbor.first;
234 0 : if (!visited[u]) {
235 0 : topo_sort_util(u, visited, topo_stack);
236 : }
237 : }
238 :
239 0 : topo_stack.push(v);
240 0 : }
241 :
242 0 : int gpmp::Graph::find(std::vector<int> &parent, int i) {
243 0 : if (parent[i] == -1)
244 0 : return i;
245 0 : return find(parent, parent[i]);
246 : }
247 :
248 0 : void gpmp::Graph::union_sets(std::vector<int> &parent, int x, int y) {
249 0 : int setX = find(parent, x);
250 0 : int setY = find(parent, y);
251 0 : parent[setX] = setY;
252 0 : }
253 :
254 0 : std::vector<std::vector<int>> gpmp::Graph::connected_components() {
255 0 : std::vector<std::vector<int>> components;
256 0 : std::vector<bool> visited(vertices, false);
257 :
258 0 : for (int v = 0; v < vertices; ++v) {
259 0 : if (!visited[v]) {
260 0 : std::vector<int> component;
261 0 : dfs_connected_components(v, visited, component);
262 0 : components.push_back(component);
263 0 : }
264 : }
265 :
266 0 : return components;
267 0 : }
268 :
269 0 : bool gpmp::Graph::is_bipartite() {
270 0 : std::vector<int> color(vertices, -1);
271 0 : std::queue<int> bfs_queue;
272 :
273 0 : for (int start = 0; start < vertices; ++start) {
274 0 : if (color[start] == -1) {
275 0 : color[start] = 0;
276 0 : bfs_queue.push(start);
277 :
278 0 : while (!bfs_queue.empty()) {
279 0 : int v = bfs_queue.front();
280 0 : bfs_queue.pop();
281 :
282 0 : for (const auto &neighbor : adj_list[v]) {
283 0 : int u = neighbor.first;
284 0 : if (color[u] == -1) {
285 0 : color[u] = 1 - color[v];
286 0 : bfs_queue.push(u);
287 0 : } else if (color[u] == color[v]) {
288 0 : return false; // Not bipartite
289 : }
290 : }
291 : }
292 : }
293 : }
294 :
295 0 : return true; // Bipartite
296 0 : }
297 :
298 0 : std::vector<double> gpmp::Graph::betweenness_centrality() {
299 0 : std::vector<double> centrality(vertices, 0.0);
300 :
301 0 : for (int s = 0; s < vertices; ++s) {
302 0 : std::vector<int> predecessors(vertices, -1);
303 0 : std::vector<int> distance(vertices, -1);
304 0 : std::vector<int> num_shortest_paths(vertices, 0);
305 0 : std::stack<int> stack;
306 0 : std::queue<int> bfs_queue;
307 :
308 0 : distance[s] = 0;
309 0 : num_shortest_paths[s] = 1;
310 0 : bfs_queue.push(s);
311 :
312 0 : while (!bfs_queue.empty()) {
313 0 : int v = bfs_queue.front();
314 0 : bfs_queue.pop();
315 0 : stack.push(v);
316 :
317 0 : for (const auto &neighbor : adj_list[v]) {
318 0 : int w = neighbor.first;
319 0 : if (distance[w] == -1) {
320 0 : distance[w] = distance[v] + 1;
321 0 : bfs_queue.push(w);
322 : }
323 :
324 0 : if (distance[w] == distance[v] + 1) {
325 0 : num_shortest_paths[w] += num_shortest_paths[v];
326 0 : predecessors[w] = v;
327 : }
328 : }
329 : }
330 :
331 0 : std::vector<double> dependency(vertices, 0.0);
332 :
333 0 : while (!stack.empty()) {
334 0 : int w = stack.top();
335 0 : stack.pop();
336 :
337 0 : for (const auto &predecessor : adj_list[w]) {
338 0 : int v = predecessor.first;
339 0 : dependency[v] += (static_cast<double>(num_shortest_paths[v]) /
340 0 : num_shortest_paths[w]) *
341 0 : (1 + dependency[w]);
342 : }
343 :
344 0 : if (w != s) {
345 0 : centrality[w] += dependency[w];
346 : }
347 : }
348 0 : }
349 :
350 0 : return centrality;
351 0 : }
352 :
353 0 : void gpmp::Graph::dfs_connected_components(int v,
354 : std::vector<bool> &visited,
355 : std::vector<int> &component) {
356 0 : visited[v] = true;
357 0 : component.push_back(v);
358 :
359 0 : for (const auto &neighbor : adj_list[v]) {
360 0 : int u = neighbor.first;
361 0 : if (!visited[u]) {
362 0 : dfs_connected_components(u, visited, component);
363 : }
364 : }
365 0 : }
366 :
367 0 : bool gpmp::Graph::has_hamiltonian_circuit() {
368 0 : std::vector<int> path;
369 0 : std::vector<bool> visited(vertices, false);
370 :
371 0 : for (int v = 0; v < vertices; ++v) {
372 0 : path.clear();
373 0 : if (hamiltonian_circuit_util(v, visited, path, 1)) {
374 0 : return true;
375 : }
376 : }
377 :
378 0 : return false;
379 0 : }
380 :
381 0 : bool gpmp::Graph::has_eulerian_path() {
382 : // A connected graph has an Eulerian path if and only if it has exactly 0 or
383 : // 2 vertices with an odd degree.
384 0 : int odd_degrees = 0;
385 :
386 0 : for (int v = 0; v < vertices; ++v) {
387 0 : if (adj_list[v].size() % 2 != 0) {
388 0 : ++odd_degrees;
389 : }
390 : }
391 :
392 0 : return odd_degrees == 0 || odd_degrees == 2;
393 : }
394 :
395 0 : bool gpmp::Graph::hamiltonian_circuit_util(int v,
396 : std::vector<bool> &visited,
397 : std::vector<int> &path,
398 : int count) {
399 0 : visited[v] = true;
400 0 : path.push_back(v);
401 :
402 0 : if (count == vertices) {
403 : // all vertices are visited; check if there is an edge from the last
404 : // added vertex to the starting vertex
405 0 : for (const auto &neighbor : adj_list[v]) {
406 0 : if (neighbor.first == path[0]) {
407 0 : return true; // Hamiltonian circuit found
408 : }
409 : }
410 : } else {
411 : // recursive step to try all vertices as the next one in the Hamiltonian
412 : // circuit
413 0 : for (const auto &neighbor : adj_list[v]) {
414 0 : if (!visited[neighbor.first]) {
415 0 : if (hamiltonian_circuit_util(neighbor.first,
416 : visited,
417 : path,
418 : count + 1)) {
419 0 : return true;
420 : }
421 : }
422 : }
423 : }
424 :
425 : // backtrack
426 0 : visited[v] = false;
427 0 : path.pop_back();
428 0 : return false;
429 : }
430 :
431 0 : int gpmp::Graph::eccentricity(int vertex) {
432 0 : std::vector<int> distance(vertices, std::numeric_limits<int>::max());
433 0 : distance[vertex] = 0;
434 :
435 0 : std::queue<int> bfs_queue;
436 0 : bfs_queue.push(vertex);
437 :
438 0 : while (!bfs_queue.empty()) {
439 0 : int v = bfs_queue.front();
440 0 : bfs_queue.pop();
441 :
442 0 : for (const auto &neighbor : adj_list[v]) {
443 0 : int u = neighbor.first;
444 0 : if (distance[u] == std::numeric_limits<int>::max()) {
445 0 : distance[u] = distance[v] + 1;
446 0 : bfs_queue.push(u);
447 : }
448 : }
449 : }
450 :
451 : // the eccentricity is the maximum distance from the given vertex
452 0 : return *std::max_element(distance.begin(), distance.end());
453 0 : }
454 :
455 : // method to calculate the radius of the graph
456 0 : int gpmp::Graph::radius() {
457 0 : int min_ecntrc = std::numeric_limits<int>::max();
458 :
459 0 : for (int v = 0; v < vertices; ++v) {
460 0 : int vEccentricity = eccentricity(v);
461 0 : min_ecntrc = std::min(min_ecntrc, vEccentricity);
462 : }
463 :
464 0 : return min_ecntrc;
465 : }
466 :
467 0 : int gpmp::Graph::chromatic_number() {
468 0 : std::vector<int> result(vertices, -1);
469 :
470 : // assign the first color to the first vertex
471 0 : result[0] = 0;
472 :
473 : // initialize available colors. For each vertex, remove colors used by its
474 : // neighbors.
475 0 : std::vector<bool> available(vertices, false);
476 0 : for (const auto &neighbor : adj_list[0]) {
477 0 : int v = neighbor.first;
478 0 : if (result[v] != -1) {
479 0 : available[result[v]] = true;
480 : }
481 : }
482 :
483 : // assign colors to the remaining vertices
484 0 : for (int v = 1; v < vertices; ++v) {
485 0 : for (int c = 0; c < vertices; ++c) {
486 0 : if (!available[c]) {
487 0 : result[v] = c;
488 0 : break;
489 : }
490 : }
491 :
492 : // reset available colors for the next vertex
493 0 : std::fill(available.begin(), available.end(), false);
494 :
495 : // update available colors for neighbors
496 0 : for (const auto &neighbor : adj_list[v]) {
497 0 : int u = neighbor.first;
498 0 : if (result[u] != -1) {
499 0 : available[result[u]] = true;
500 : }
501 : }
502 : }
503 :
504 : // find the maximum color assigned, which represents the chromatic number
505 0 : int chrom_num = *std::max_element(result.begin(), result.end()) + 1;
506 :
507 0 : return chrom_num;
508 0 : }
509 :
510 : // method to perform graph coloring using the greedy algorithm
511 0 : std::vector<int> gpmp::Graph::greedy_coloring() {
512 0 : std::vector<int> result(vertices, -1);
513 :
514 : // assign colors to vertices
515 0 : for (int v = 0; v < vertices; ++v) {
516 0 : std::vector<bool> available(vertices, false);
517 0 : for (const auto &neighbor : adj_list[v]) {
518 0 : int u = neighbor.first;
519 0 : if (result[u] != -1) {
520 0 : available[result[u]] = true;
521 : }
522 : }
523 :
524 0 : for (int c = 0; c < vertices; ++c) {
525 0 : if (!available[c]) {
526 0 : result[v] = c;
527 0 : break;
528 : }
529 : }
530 0 : }
531 :
532 0 : return result;
533 0 : }
534 :
535 0 : std::vector<std::pair<int, int>> gpmp::Graph::match_cardinality() {
536 0 : std::vector<std::pair<int, int>> matching;
537 :
538 : // iterate through each vertex and find unmatched neighbors
539 0 : for (int v = 0; v < vertices; ++v) {
540 0 : if (!is_matched[v]) {
541 0 : for (const auto &neighbor : adj_list[v]) {
542 0 : int u = neighbor.first;
543 0 : if (!is_matched[u]) {
544 0 : matching.push_back({v, u});
545 0 : is_matched[v] = true;
546 0 : is_matched[u] = true;
547 0 : break;
548 : }
549 : }
550 : }
551 : }
552 :
553 0 : return matching;
554 0 : }
555 :
556 : // method to find a maximum weight matching in the graph using greedy algorithm
557 0 : std::vector<std::pair<int, int>> gpmp::Graph::match_wt() {
558 0 : std::vector<std::pair<int, int>> matching;
559 :
560 : // sort edges in descending order based on weights
561 0 : std::vector<std::pair<std::pair<int, int>, int>> wt_edges;
562 0 : for (int v = 0; v < vertices; ++v) {
563 0 : for (const auto &neighbor : adj_list[v]) {
564 0 : int u = neighbor.first;
565 0 : int weight = neighbor.second;
566 0 : wt_edges.push_back({{v, u}, weight});
567 : }
568 : }
569 :
570 0 : std::sort(wt_edges.rbegin(),
571 0 : wt_edges.rend(),
572 0 : [](const auto &a, const auto &b) { return a.second < b.second; });
573 :
574 : // iterate through sorted edges and add to matching if both vertices are
575 : // unmatched
576 0 : for (const auto &edge : wt_edges) {
577 0 : int v = edge.first.first;
578 0 : int u = edge.first.second;
579 0 : if (!is_matched[v] && !is_matched[u]) {
580 0 : matching.push_back({v, u});
581 0 : is_matched[v] = true;
582 0 : is_matched[u] = true;
583 : }
584 : }
585 :
586 0 : return matching;
587 0 : }
588 :
589 0 : bool gpmp::Graph::is_planar() {
590 : // planar graphs satisfy Kuratowski's theorem: they do not contain a
591 : // subgraph that is a subdivision of K5 or K3,3.
592 0 : return !has_k5() && !has_k33();
593 : }
594 :
595 : // method to generate a random planar graph using the random geometric graph
596 : // model
597 0 : void gpmp::Graph::planar_gen(int num_vertices, double radius) {
598 0 : vertices = num_vertices;
599 0 : adj_list.resize(vertices);
600 :
601 : // generate random points in a 2D plane
602 0 : std::vector<std::pair<double, double>> points;
603 0 : for (int v = 0; v < vertices; ++v) {
604 0 : double x = static_cast<double>(rand()) / RAND_MAX;
605 0 : double y = static_cast<double>(rand()) / RAND_MAX;
606 0 : points.push_back({x, y});
607 : }
608 :
609 : // connect vertices if their Euclidean distance is less than the specified
610 : // radius
611 0 : for (int v = 0; v < vertices; ++v) {
612 0 : for (int u = v + 1; u < vertices; ++u) {
613 0 : double distance = euclid_dist(points[v], points[u]);
614 0 : if (distance < radius) {
615 : // TODO the weight of the generated edges should probably be
616 : // determined algorithmically
617 0 : add_edge(v, u, 0);
618 : }
619 : }
620 : }
621 0 : }
622 :
623 : // method to check if the graph contains a subgraph that is a subdivision of K5
624 0 : bool gpmp::Graph::has_k5() {
625 0 : for (int v = 0; v < vertices; ++v) {
626 0 : if (adj_list[v].size() >= 5) {
627 0 : std::set<int> neighbors;
628 0 : for (const auto &neighbor : adj_list[v]) {
629 0 : neighbors.insert(neighbor.first);
630 : }
631 :
632 0 : for (const auto &u : neighbors) {
633 0 : std::set<int> common_neighbors;
634 0 : for (const auto &neighbor : adj_list[u]) {
635 0 : if (neighbors.find(neighbor.first) != neighbors.end()) {
636 0 : common_neighbors.insert(neighbor.first);
637 : }
638 : }
639 :
640 0 : for (const auto &w : common_neighbors) {
641 0 : if (neighbors.find(w) != neighbors.end()) {
642 0 : return true;
643 : }
644 : }
645 0 : }
646 0 : }
647 : }
648 :
649 0 : return false;
650 : }
651 :
652 : // method to check if the graph contains a subgraph that is a subdivision of
653 : // K3,3
654 0 : bool gpmp::Graph::has_k33() {
655 0 : for (int v = 0; v < vertices; ++v) {
656 0 : if (adj_list[v].size() >= 3) {
657 0 : std::set<int> neighbors;
658 0 : for (const auto &neighbor : adj_list[v]) {
659 0 : neighbors.insert(neighbor.first);
660 : }
661 :
662 0 : if (is_k33(neighbors)) {
663 0 : return true;
664 : }
665 0 : }
666 : }
667 :
668 0 : return false;
669 : }
670 :
671 : // helper method to check if a set of vertices forms a K3,3 subgraph
672 0 : bool gpmp::Graph::is_k33(const std::set<int> &k_vertices) {
673 0 : if (k_vertices.size() == 6) {
674 0 : int degree_sum = 0;
675 0 : for (int v : k_vertices) {
676 0 : degree_sum += adj_list[v].size();
677 : }
678 :
679 : // Cast vertices.size() to int to avoid the comparison warning
680 0 : return degree_sum == 2 * static_cast<int>(k_vertices.size());
681 : }
682 0 : return false;
683 : }
684 :
685 : // helper method to calculate the Euclidean distance between two points
686 0 : double gpmp::Graph::euclid_dist(const std::pair<double, double> &point1,
687 : const std::pair<double, double> &point2) {
688 0 : double dx = point1.first - point2.first;
689 0 : double dy = point1.second - point2.second;
690 0 : return std::sqrt(dx * dx + dy * dy);
691 : }
692 :
693 0 : std::vector<uint64_t> gpmp::Graph::compress() {
694 0 : std::vector<uint64_t> compressed;
695 0 : compressed.push_back(vertices);
696 :
697 0 : for (int v = 0; v < vertices; ++v) {
698 : // encode the number of neighbors using Elias Gamma encoding
699 0 : std::bitset<64> binary_representation(adj_list[v].size() + 1);
700 0 : int length = log2(adj_list[v].size() + 1) + 1;
701 :
702 : // store the length of the encoded number
703 0 : compressed.push_back(length);
704 :
705 : // store the encoded number
706 0 : compressed.push_back(
707 0 : std::stoull(binary_representation.to_string(), 0, 2));
708 :
709 : // store the neighbors
710 0 : for (const auto &neighbor : adj_list[v]) {
711 0 : compressed.push_back(neighbor.first);
712 : }
713 : }
714 :
715 0 : return compressed;
716 0 : }
717 :
718 : // method to decompress a compressed graph using the Elias Gamma encoding
719 0 : void gpmp::Graph::decompress(const std::vector<uint64_t> &compressed) {
720 0 : int index = 0;
721 0 : vertices = compressed[index++];
722 :
723 0 : adj_list.resize(vertices);
724 :
725 0 : for (int v = 0; v < vertices; ++v) {
726 0 : int length = compressed[index++];
727 0 : uint64_t encoded_neighbors = compressed[index++];
728 0 : std::bitset<64> binary_representation(encoded_neighbors);
729 :
730 : // decode the number of neighbors
731 : int num_neighbors =
732 0 : std::stoi(binary_representation.to_string().substr(64 - length),
733 : nullptr,
734 : 2) -
735 0 : 1;
736 :
737 : // decode and add neighbors
738 0 : for (int i = 0; i < num_neighbors; ++i) {
739 0 : adj_list[v].emplace_back(compressed[index++],
740 0 : 0); // TODO assuming unweighted graph
741 : }
742 : }
743 0 : }
|
