AlgoPlus v0.1.0
Loading...
Searching...
No Matches
graph.h
1#ifndef GRAPH_H
2#define GRAPH_H
3
4#include <cfloat>
5#ifdef ENABLE_GRAPH_VISUALIZATION
6#include "../../visualization/graph_visual/graph_visualization.h"
7#endif
8
9#ifdef __cplusplus
10#include <algorithm>
11#include <cassert>
12#include <climits>
13#include <iostream>
14#include <limits>
15#include <map>
16#include <queue>
17#include <set>
18#include <stack>
19#include <string>
20#include <type_traits>
21#include <unordered_map>
22#include <unordered_set>
23#include <utility>
24#endif
25
31template <typename T> class graph {
32 public:
39 graph(std::string _type, std::vector<std::pair<T, std::vector<T>>> _adj = {}) {
40 try {
41 if (_type == "directed" || _type == "undirected") {
42 this->_type = _type;
43 } else {
44 throw std::invalid_argument("Can't recognize the type of graph");
45 }
46 if (!_adj.empty()) {
47 for (size_t i = 0; i < _adj.size(); i++) {
48 for (T& neigh : _adj[i].second) {
49 this->add_edge(_adj[i].first, neigh);
50 }
51 }
52 }
53 } catch (std::invalid_argument& e) {
54 std::cerr << e.what() << '\n';
55 return;
56 }
57 }
58
64 graph(const graph& g) : adj(g.adj), _elements(g._elements), _type(g._type) {}
65
72 graph& operator=(const graph& g) {
73 adj = g.adj;
74 _elements = g._elements;
75 _type = g._type;
76 return *this;
77 }
78
82 ~graph() { adj.clear(); }
83
89 void add_edge(T u, T v) {
90 if (_type == "undirected") {
91 adj[u].push_back(v);
92 adj[v].push_back(u);
93 } else {
94 adj[u].push_back(v);
95 }
96 _elements.insert(u);
97 _elements.insert(v);
98 }
99
107 bool has_edge(T start, T end) {
108 if (_elements.find(start) == _elements.end()) {
109 return false;
110 }
111 for (T& x : adj[start]) {
112 if (x == end) {
113 return true;
114 }
115 }
116 return false;
117 }
118
123 void clear() {
124 _elements.clear();
125 adj.clear();
126 }
127
132 bool empty() { return _elements.empty(); }
133
138 size_t size();
139
145 std::vector<T> dfs(T start);
146
152 std::vector<T> bfs(T start);
153
158 int64_t connected_components();
159
164 bool cycle();
165
170 std::vector<T> topological_sort();
171
176 bool bipartite();
177
183
184 std::vector<std::vector<T>> bridge(T start);
185
191 int64_t scc();
192
197 bool connected();
198
205 int eulerian();
206
211 void visualize();
212
217 friend std::ostream& operator<<(std::ostream& out, graph<T>& g) {
218 out << '{';
219
220 std::vector<T> elements = g.topological_sort();
221 for (T& x : elements) {
222 out << x << ' ';
223 }
224 out << '}' << '\n';
225 return out;
226 }
227
228 private:
234 std::unordered_map<T, std::vector<T>> adj;
235 std::unordered_set<T> _elements;
236 std::string _type;
237
241 void dfs_bridge(T start, T parent, int64_t& time, std::unordered_map<T, bool>& visited,
242 std::unordered_map<T, int64_t>& in, std::unordered_map<T, int64_t>& out,
243 std::vector<std::vector<T>>& bridges) {
244 visited[start] = true;
245 in[start] = out[start] = time++;
246 for (T& x : adj[start]) {
247 if (x != parent) {
248 if (visited.find(x) == visited.end()) {
249 dfs_bridge(x, start, time, visited, in, out, bridges);
250 if (out[x] > in[start]) {
251 bridges.push_back({x, start});
252 }
253 }
254 out[start] = std::min(out[start], out[x]);
255 }
256 }
257 }
258
262 void dfs_scc(T start, std::unordered_map<T, bool>& visited, std::stack<T>& s) {
263 visited[start] = true;
264 for (auto& x : adj[start]) {
265 if (visited.find(x) == visited.end()) {
266 dfs_scc(x, visited, s);
267 }
268 }
269
270 s.push(start);
271 }
272};
273
274template <typename T> size_t graph<T>::size() {
275 return _elements.size();
276}
277
278template <typename T> std::vector<T> graph<T>::dfs(T start) {
279 std::vector<T> path;
280 if (this->empty() || _elements.find(start) == _elements.end()) {
281 return path;
282 }
283 std::stack<T> s;
284 std::unordered_map<T, bool> visited;
285 s.push(start);
286 visited[start] = true;
287 while (!s.empty()) {
288 T current = s.top();
289 path.push_back(current);
290 s.pop();
291 for (T& x : adj[current]) {
292 if (visited.find(x) == visited.end()) {
293 s.push(x);
294 visited[x] = true;
295 }
296 }
297 }
298 return path;
299}
300
301template <typename T> std::vector<T> graph<T>::bfs(T start) {
302 std::vector<T> path;
303 if (this->empty() || _elements.find(start) == _elements.end()) {
304 return path;
305 }
306 std::queue<T> q;
307 std::unordered_map<T, bool> visited;
308 q.push(start);
309 visited[start] = true;
310 while (!q.empty()) {
311 int64_t size = q.size();
312 for (int64_t i = 0; i < size; i++) {
313 T current = q.front();
314 path.push_back(current);
315 q.pop();
316 for (T& x : adj[current]) {
317 if (visited.find(x) == visited.end()) {
318 q.push(x);
319 visited[x] = true;
320 }
321 }
322 }
323 }
324 return path;
325}
326
327template <typename T> int64_t graph<T>::connected_components() {
328 auto explore = [&](std::unordered_map<T, bool>& visited, T element) -> void {
329 std::queue<T> q;
330 q.push(element);
331 visited[element] = true;
332 while (!q.empty()) {
333 T current = q.front();
334 q.pop();
335 for (T& x : adj[current]) {
336 if (visited.find(x) == visited.end()) {
337 q.push(x);
338 visited[x] = true;
339 }
340 }
341 }
342 };
343 size_t n = _elements.size();
344 int64_t cc = 0;
345 std::unordered_map<T, bool> visited;
346 for (T x : _elements) {
347 if (visited.find(x) == visited.end()) {
348 explore(visited, x);
349 cc++;
350 }
351 }
352 return cc;
353}
354
355template <typename T> bool graph<T>::cycle() {
356 std::unordered_map<T, int> indeg;
357 std::queue<T> q;
358 size_t visited = 0;
359
360 for (T x : _elements) {
361 for (T& y : adj[x]) {
362 indeg[y]++;
363 }
364 }
365
366 for (T x : _elements) {
367 if (indeg[x] == 0) {
368 q.push(x);
369 }
370 }
371
372 while (!q.empty()) {
373 T current = q.front();
374 q.pop();
375 visited++;
376 for (T& x : adj[current]) {
377 if (--indeg[x] == 0) {
378 q.push(x);
379 }
380 }
381 }
382 return visited == 0;
383}
384
385template <typename T> std::vector<T> graph<T>::topological_sort() {
386 std::vector<T> top_sort;
387 std::unordered_map<T, bool> visited;
388 std::unordered_map<T, int64_t> indeg;
389 for (T x : _elements) {
390 for (T& y : adj[x]) {
391 indeg[y]++;
392 }
393 }
394
395 std::queue<T> q;
396 for (T x : _elements) {
397 if (indeg[x] == 0) {
398 q.push(x);
399 visited[x] = true;
400 }
401 }
402
403 while (!q.empty()) {
404 T current = q.front();
405 q.pop();
406 top_sort.push_back(current);
407 for (T& x : adj[current]) {
408 if (visited.find(x) == visited.end()) {
409 if (--indeg[x] == 0) {
410 q.push(x);
411 visited[x] = true;
412 }
413 }
414 }
415 }
416
417 return top_sort;
418}
419
420template <typename T> bool graph<T>::bipartite() {
421 std::unordered_map<T, int> color;
422 std::queue<std::pair<T, int>> q;
423
424 for (T x : _elements) {
425 if (color.find(x) == color.end()) {
426 q.push({x, 0});
427 color[x] = 0;
428 while (!q.empty()) {
429 std::pair<T, int> current = q.front();
430 q.pop();
431 T v = current.first;
432 int col = current.second;
433 for (T& x : adj[v]) {
434 if (color.find(x) != color.end() && color[x] == col) {
435 return false;
436 }
437 if (color.find(x) == color.end()) {
438 color[x] = (col) ? 0 : 1;
439 q.push({x, color[x]});
440 }
441 }
442 }
443 }
444 }
445 return true;
446}
447
448template <typename T> std::vector<std::vector<T>> graph<T>::bridge(T start) {
449 int64_t timer = 0;
450 std::vector<std::vector<T>> bridges;
451 std::unordered_map<T, bool> visited;
452 std::unordered_map<T, int64_t> in, out;
453 for (T x : _elements) {
454 in[x] = 0;
455 out[x] = 0;
456 }
457 dfs_bridge(start, -1, timer, visited, in, out, bridges);
458 return bridges;
459}
460
461template <typename T> bool graph<T>::connected() {
462 std::unordered_map<T, bool> visited;
463 bool check = 0;
464 T start;
465 for (auto& ele : adj) {
466 if (adj[ele.first].size() != 0) {
467 start = ele.first;
468 check = 1;
469 break;
470 }
471 }
472 if (!check) {
473 return false;
474 }
475 std::stack<T> s;
476 s.push(start);
477 visited[start] = true;
478 while (!s.empty()) {
479 T current = s.top();
480 s.pop();
481 for (T& x : adj[current]) {
482 if (visited.find(x) == visited.end()) {
483 visited[x] = true;
484 s.push(x);
485 }
486 }
487 }
488
489 for (T x : _elements) {
490 if (visited.find(x) == visited.end() && adj[x].size() > 0) {
491 return false;
492 }
493 }
494 return true;
495}
496
497template <typename T> int64_t graph<T>::scc() {
498 if (this->size() == 0) {
499 return 0;
500 }
501
502 std::unordered_map<T, bool> visited;
503 std::stack<T> s;
504
505 for (const T& x : _elements) {
506 if (visited.find(x) == visited.end()) {
507 dfs_scc(x, visited, s);
508 }
509 }
510
511 std::unordered_map<T, std::vector<T>> new_adj;
512 for (const T& x : _elements) {
513 for (const auto& neigh : adj[x]) {
514 new_adj[neigh].push_back(x);
515 }
516 }
517
518 int64_t scc = 0;
519 visited.clear();
520
521 auto dfs_new = [&](T start) -> void {
522 std::stack<T> _s;
523 _s.push(start);
524 visited[start] = true;
525 while (!_s.empty()) {
526 T current = _s.top();
527 _s.pop();
528 for (auto& x : new_adj[current]) {
529 if (visited.find(x) == visited.end()) {
530 _s.push(x);
531 visited[x] = true;
532 }
533 }
534 }
535 };
536
537 while (!s.empty()) {
538 T current = s.top();
539 s.pop();
540 if (visited.find(current) == visited.end()) {
541 dfs_new(current);
542 scc++;
543 }
544 }
545
546 return scc;
547}
548
549template <typename T> int graph<T>::eulerian() {
550 if (this->connected() == false) {
551 return false;
552 }
553
554 int64_t odd = 0;
555 for (auto& el : adj) {
556 if (adj[el.first].size() & 1) {
557 odd++;
558 }
559 }
560
561 if (odd > 2) {
562 return false;
563 }
564 return (odd) ? 1 : 2;
565}
566
567#ifdef ENABLE_GRAPH_VISUALIZATION
568template <typename T> void graph<T>::visualize() {
569 std::string s;
570 if (_type == "directed") {
571 if (std::is_same_v<T, char> || std::is_same_v<T, std::string>) {
572 for (auto& [element, neighbors] : adj) {
573 for (T& x : neighbors) {
574 s += element;
575 s += "->";
576 s += x;
577 s += '\n';
578 }
579 }
580 } else {
581 for (auto& [element, neighbors] : adj) {
582 for (T& x : neighbors) {
583 s += std::to_string(element);
584 s += "->";
585 s += std::to_string(x);
586 s += '\n';
587 }
588 }
589 }
590 } else {
591 if (std::is_same_v<T, char> || std::is_same_v<T, std::string>) {
592 for (auto& [element, neighbors] : adj) {
593 for (T& x : neighbors) {
594 s += element;
595 s += "--";
596 s += x;
597 s += '\n';
598 }
599 }
600 } else {
601 for (auto& [element, neighbors] : adj) {
602 for (T& x : neighbors) {
603 s += std::to_string(element);
604 s += "--";
605 s += std::to_string(x);
606 s += '\n';
607 }
608 }
609 }
610 }
611 s += '\n';
612 if (_type == "directed") {
613 digraph_visualization::visualize(s);
614 } else {
615 graph_visualization::visualize(s);
616 }
617}
618#endif
619
623template <typename T> class weighted_graph {
624 public:
631 weighted_graph(std::string _type, std::vector<std::pair<std::pair<T, T>, int64_t>> _adj = {}) {
632 try {
633 if (_type == "directed" || _type == "undirected") {
634 this->_type = _type;
635 } else {
636 throw std::invalid_argument("Can't recognize the type of graph");
637 }
638 if (!_adj.empty()) {
639 for (size_t i = 0; i < _adj.size(); i++) {
640 this->add_edge(_adj[i].first.first, _adj[i].first.second, _adj[i].second);
641 }
642 }
643 } catch (std::invalid_argument& e) {
644 std::cerr << e.what() << '\n';
645 return;
646 }
647 }
648
653 explicit weighted_graph(const weighted_graph& g)
654 : adj(g.adj), _elements(g._elements), _type(g._type) {}
655
661 weighted_graph& operator=(const weighted_graph& g) {
662 adj = g.adj;
663 _elements = g._elements;
664 _type = g._type;
665 return *this;
666 }
667
672 ~weighted_graph() { adj.clear(); }
673
680 void add_edge(T u, T v, int64_t w) {
681 if (_type == "undirected") {
682 adj[u].push_back(std::make_pair(v, w));
683 adj[v].push_back(std::make_pair(u, w));
684 } else if (_type == "directed") {
685 adj[u].push_back(std::make_pair(v, w));
686 }
687 _elements.insert(u);
688 _elements.insert(v);
689 }
690
697 bool has_edge(T start, T end) {
698 if (_elements.find(start) == _elements.end()) {
699 return false;
700 }
701 for (std::pair<T, double>& x : adj[start]) {
702 if (x.first == end) {
703 return true;
704 }
705 }
706 return false;
707 }
708
713 void clear() {
714 _elements.clear();
715 adj.clear();
716 }
717
721 bool empty() { return _elements.empty(); }
722
727 size_t size();
728
734 std::vector<T> dfs(T start);
735
741 std::vector<T> bfs(T start);
742
749 double shortest_path(T start, T end);
750
755 int64_t connected_components();
756
761 bool cycle();
762
767 std::vector<T> topological_sort();
768
774 int64_t prim(T start);
775
780 bool bipartite();
781
787 std::vector<std::vector<T>> bridge(T start);
788
793 int64_t scc();
794
799 bool connected();
800
807 int eulerian();
808
813 std::unordered_map<T, double> bellman_ford(T start);
814
821 int max_flow(T start, T end);
822
827 void visualize();
828
833 friend std::ostream& operator<<(std::ostream& out, weighted_graph<T>& g) {
834 out << '{';
835 std::vector<T> elements = g.topological_sort();
836 for (T& x : elements) {
837 out << x << ' ';
838 }
839 out << '}' << '\n';
840 return out;
841 }
842
843 private:
849 std::unordered_map<T, std::vector<std::pair<T, double>>> adj;
850 std::string _type;
851 std::unordered_set<T> _elements;
852
856 void dfs_bridge(T start, T parent, int64_t& time, std::unordered_map<T, bool>& visited,
857 std::unordered_map<T, int64_t>& in, std::unordered_map<T, int64_t>& out,
858 std::vector<std::vector<T>>& bridges) {
859 visited[start] = true;
860 in[start] = out[start] = time++;
861 for (std::pair<T, double>& x : adj[start]) {
862 if (x.first != parent) {
863 if (visited.find(x.first) == visited.end()) {
864 dfs_bridge(x.first, start, time, visited, in, out, bridges);
865 if (out[x.first] > in[start]) {
866 bridges.push_back({x.first, start});
867 }
868 }
869 out[start] = std::min(out[start], out[x.first]);
870 }
871 }
872 }
873
877 void dfs_scc(T start, std::unordered_map<T, bool>& visited, std::stack<T>& s) {
878 visited[start] = true;
879 for (auto& x : adj[start]) {
880 if (visited.find(x.first) == visited.end()) {
881 dfs_scc(x.first, visited, s);
882 }
883 }
884
885 s.push(start);
886 }
887};
888
889template <typename T> size_t weighted_graph<T>::size() {
890 return _elements.size();
891}
892
893template <typename T> double weighted_graph<T>::shortest_path(T start, T end) {
894 if (_elements.find(start) == _elements.end()) {
895 std::cout << "Element: " << start << " is not found in the Graph" << '\n';
896 return -1;
897 }
898 if (_elements.find(end) == _elements.end()) {
899 std::cout << "Element: " << end << " is not found in the Graph" << '\n';
900 return -1;
901 }
902
903 if (!cycle() && _type == "directed") {
904 std::vector<T> top_sort = topological_sort();
905 std::reverse(top_sort.begin(), top_sort.end());
906 std::stack<T> s;
907 std::unordered_map<T, double> dist;
908 for (auto& x : _elements) {
909 dist[x] = std::numeric_limits<int64_t>::max();
910 }
911 dist[start] = 0;
912 while (!top_sort.empty()) {
913 auto current = top_sort.back();
914 top_sort.pop_back();
915 if (dist[current] != std::numeric_limits<int64_t>::max()) {
916 for (std::pair<T, double>& x : adj[current]) {
917 if (dist[x.first] > dist[current] + x.second) {
918 dist[x.first] = dist[current] + x.second;
919 top_sort.push_back(x.first);
920 }
921 }
922 }
923 }
924 return (dist[end] != std::numeric_limits<int64_t>::max()) ? dist[end] : -1;
925 } else {
926 std::unordered_map<T, double> dist;
927 for (auto& x : _elements) {
928 dist[x] = std::numeric_limits<int64_t>::max();
929 }
930 std::priority_queue<std::pair<double, T>, std::vector<std::pair<double, T>>,
931 std::greater<std::pair<double, T>>>
932 pq;
933 pq.push(std::make_pair(0, start));
934 dist[start] = 0;
935 while (!pq.empty()) {
936 T currentNode = pq.top().second;
937 double currentDist = pq.top().first;
938 pq.pop();
939 for (std::pair<T, double>& edge : adj[currentNode]) {
940 if (currentDist + edge.second < dist[edge.first]) {
941 dist[edge.first] = currentDist + edge.second;
942 pq.push(std::make_pair(dist[edge.first], edge.first));
943 }
944 }
945 }
946 return (dist[end] != std::numeric_limits<int64_t>::max()) ? dist[end] : -1;
947 }
948 return -1;
949}
950
951template <typename T> std::vector<T> weighted_graph<T>::dfs(T start) {
952
953 std::vector<T> path;
954 if (this->empty() || _elements.find(start) == _elements.end()) {
955 return path;
956 }
957 std::stack<T> s;
958 std::unordered_map<T, bool> visited;
959 s.push(start);
960 visited[start] = true;
961 while (!s.empty()) {
962 int64_t size = s.size();
963 for (int64_t i = 0; i < size; i++) {
964 T current = s.top();
965 path.push_back(current);
966 s.pop();
967 for (std::pair<T, double>& x : adj[current]) {
968 if (visited.find(x.first) == visited.end()) {
969 s.push(x.first);
970 visited[x.first] = true;
971 }
972 }
973 }
974 }
975 return path;
976}
977
978template <typename T> std::vector<T> weighted_graph<T>::bfs(T start) {
979 std::vector<T> path;
980 if (this->empty() || _elements.find(start) == _elements.end()) {
981 return path;
982 }
983 std::queue<T> q;
984 std::unordered_map<T, bool> visited;
985 q.push(start);
986 visited[start] = true;
987 while (!q.empty()) {
988 int64_t size = q.size();
989 for (int64_t i = 0; i < size; i++) {
990 T current = q.front();
991 path.push_back(current);
992 q.pop();
993 for (std::pair<T, double>& x : adj[current]) {
994 if (visited.find(x.first) == visited.end()) {
995 q.push(x.first);
996 visited[x.first] = true;
997 }
998 }
999 }
1000 }
1001 return path;
1002}
1003
1004template <typename T> int64_t weighted_graph<T>::connected_components() {
1005 auto explore = [&](std::unordered_map<T, bool>& visited, T element) -> void {
1006 std::stack<T> s;
1007 s.push(element);
1008 visited[element] = true;
1009 while (!s.empty()) {
1010 T current = s.top();
1011 s.pop();
1012 for (std::pair<T, double>& x : adj[current]) {
1013 if (visited.find(x.first) == visited.end()) {
1014 s.push(x.first);
1015 visited[x.first] = true;
1016 }
1017 }
1018 }
1019 };
1020 size_t n = _elements.size();
1021 int64_t cc = 0;
1022 std::unordered_map<T, bool> visited;
1023 for (T x : _elements) {
1024 if (visited.find(x) == visited.end()) {
1025 explore(visited, x);
1026 cc++;
1027 }
1028 }
1029 return cc;
1030}
1031
1032template <typename T> bool weighted_graph<T>::cycle() {
1033 std::unordered_map<T, int> indeg;
1034 std::queue<T> q;
1035 size_t visited = 0;
1036
1037 for (T x : _elements) {
1038 for (std::pair<T, double>& y : adj[x]) {
1039 indeg[y.first]++;
1040 }
1041 }
1042
1043 for (T x : _elements) {
1044 if (indeg[x] == 0) {
1045 q.push(x);
1046 }
1047 }
1048
1049 while (!q.empty()) {
1050 T current = q.front();
1051 q.pop();
1052 visited++;
1053 for (std::pair<T, double>& x : adj[current]) {
1054 if (--indeg[x.first] == 0) {
1055 q.push(x.first);
1056 }
1057 }
1058 }
1059 return visited == 0;
1060}
1061
1062template <typename T> std::vector<T> weighted_graph<T>::topological_sort() {
1063 std::vector<T> top_sort;
1064 std::unordered_map<T, bool> visited;
1065 std::unordered_map<T, int64_t> indeg;
1066 for (T x : _elements) {
1067 for (std::pair<T, double>& y : adj[x]) {
1068 indeg[y.first]++;
1069 }
1070 }
1071
1072 std::queue<T> q;
1073 for (T x : _elements) {
1074 if (indeg[x] == 0) {
1075 q.push(x);
1076 visited[x] = true;
1077 }
1078 }
1079
1080 while (!q.empty()) {
1081 T current = q.front();
1082 q.pop();
1083 top_sort.push_back(current);
1084 for (std::pair<T, double>& x : adj[current]) {
1085 if (visited.find(x.first) == visited.end()) {
1086 if (--indeg[x.first] == 0) {
1087 q.push(x.first);
1088 visited[x.first] = true;
1089 }
1090 }
1091 }
1092 }
1093
1094 return top_sort;
1095}
1096
1097template <typename T> int64_t weighted_graph<T>::prim(T _temp) {
1098 std::priority_queue<std::pair<T, int64_t>, std::vector<std::pair<T, int64_t>>,
1099 std::greater<std::pair<T, int64_t>>>
1100 q;
1101 std::unordered_map<T, bool> visited;
1102 int64_t cost = 0;
1103 q.push(std::make_pair(0, _temp));
1104 while (!q.empty()) {
1105 std::pair<T, int64_t> current = q.top();
1106 q.pop();
1107 _temp = current.first;
1108 if (visited.find(_temp) != visited.end()) {
1109 continue;
1110 }
1111 cost += current.second;
1112 visited[_temp] = true;
1113 for (std::pair<T, double>& x : adj[current.first]) {
1114 if (visited.find(x.first) == visited.end()) {
1115 q.push(x);
1116 }
1117 }
1118 }
1119 return cost;
1120}
1121
1122template <typename T> bool weighted_graph<T>::bipartite() {
1123 std::unordered_map<T, int> color;
1124 std::queue<std::pair<T, int>> q;
1125
1126 for (T x : _elements) {
1127 if (color.find(x) == color.end()) {
1128 q.push({x, 0});
1129 color[x] = 0;
1130 while (!q.empty()) {
1131 std::pair<T, int> current = q.front();
1132 q.pop();
1133 T v = current.first;
1134 int col = current.second;
1135 for (std::pair<T, double>& x : adj[v]) {
1136 if (color.find(x.first) != color.end() && color[x.first] == col) {
1137 return false;
1138 }
1139 if (color.find(x.first) == color.end()) {
1140 color[x.first] = (col) ? 0 : 1;
1141 q.push({x.first, color[x.first]});
1142 }
1143 }
1144 }
1145 }
1146 }
1147 return true;
1148}
1149
1150template <typename T> std::vector<std::vector<T>> weighted_graph<T>::bridge(T start) {
1151 int64_t timer = 0;
1152 std::vector<std::vector<T>> bridges;
1153 std::unordered_map<T, bool> visited;
1154 std::unordered_map<T, int64_t> in, out;
1155 for (T x : _elements) {
1156 in[x] = 0;
1157 out[x] = 0;
1158 }
1159 dfs_bridge(start, -1, timer, visited, in, out, bridges);
1160 return bridges;
1161}
1162
1163template <typename T> int64_t weighted_graph<T>::scc() {
1164 if (this->size() == 0) {
1165 return 0;
1166 }
1167
1168 std::unordered_map<T, bool> visited;
1169 std::stack<T> s;
1170
1171 for (const T& x : _elements) {
1172 if (visited.find(x) == visited.end()) {
1173 dfs_scc(x, visited, s);
1174 }
1175 }
1176
1177 std::unordered_map<T, std::vector<T>> new_adj;
1178 for (const T& x : _elements) {
1179 for (const auto& neigh : adj[x]) {
1180 new_adj[neigh.first].push_back(x);
1181 }
1182 }
1183
1184 int64_t scc = 0;
1185 visited.clear();
1186
1187 auto dfs_new = [&](T start) -> void {
1188 std::stack<T> _s;
1189 _s.push(start);
1190 visited[start] = true;
1191 while (!_s.empty()) {
1192 T current = _s.top();
1193 _s.pop();
1194 for (auto& x : new_adj[current]) {
1195 if (visited.find(x) == visited.end()) {
1196 _s.push(x);
1197 visited[x] = true;
1198 }
1199 }
1200 }
1201 };
1202
1203 while (!s.empty()) {
1204 T current = s.top();
1205 s.pop();
1206 if (visited.find(current) == visited.end()) {
1207 dfs_new(current);
1208 scc++;
1209 }
1210 }
1211
1212 return scc;
1213}
1214
1215template <typename T> bool weighted_graph<T>::connected() {
1216 std::unordered_map<T, bool> visited;
1217 bool check = 0;
1218 T start;
1219 for (auto& ele : adj) {
1220 if (adj[ele.first].size() != 0) {
1221 start = ele.first;
1222 check = 1;
1223 break;
1224 }
1225 }
1226 if (!check) {
1227 return false;
1228 }
1229 std::stack<T> s;
1230 s.push(start);
1231 visited[start] = true;
1232 while (!s.empty()) {
1233 T current = s.top();
1234 s.pop();
1235 for (std::pair<T, double>& x : adj[current]) {
1236 if (visited.find(x.first) == visited.end()) {
1237 visited[x.first] = true;
1238 s.push(x.first);
1239 }
1240 }
1241 }
1242
1243 for (T x : _elements) {
1244 if (visited.find(x) == visited.end() && adj[x].size() > 0) {
1245 return false;
1246 }
1247 }
1248 return true;
1249}
1250
1251template <typename T> int weighted_graph<T>::eulerian() {
1252 if (this->connected() == false) {
1253 return false;
1254 }
1255
1256 int odd = 0;
1257 for (auto& el : adj) {
1258 if (adj[el.first].size() & 1) {
1259 odd++;
1260 }
1261 }
1262
1263 if (odd > 2) {
1264 return 0;
1265 }
1266
1267 return (odd) ? 1 : 2;
1268}
1269
1270template <typename T> std::unordered_map<T, double> weighted_graph<T>::bellman_ford(T start) {
1271 std::unordered_map<T, double> dist;
1272 // Initialize the distance to all nodes to be infinity
1273 // except for the starting node which is zero.
1274 for (auto it : adj) {
1275 dist[it.first] = std::numeric_limits<double>::infinity();
1276 }
1277 dist[start] = 0;
1278
1279 // Get number of vertices present in the graph
1280 int v = adj.size();
1281
1282 // For each vertex, apply relaxation for all the edges
1283 for (int i = 0; i < v - 1; i++) {
1284 for (const auto j : adj) {
1285 for (const auto edge : adj[j.first]) {
1286 if (dist[j.first] + edge.second < dist[edge.first]) {
1287 dist[edge.first] = dist[j.first] + edge.second;
1288 }
1289 }
1290 }
1291 }
1292
1293 // Run algorithm a second time to detect which nodes are part
1294 // of a negative cycle. A negative cycle has occurred if we
1295 // can find a better path beyond the optimal solution.
1296 for (int i = 0; i < v - 1; i++) {
1297 for (const auto j : adj) {
1298 for (const auto edge : adj[j.first]) {
1299 if (dist[j.first] + edge.second < dist[edge.first]) {
1300 dist[edge.first] = -std::numeric_limits<double>::infinity();
1301 }
1302 }
1303 }
1304 }
1305
1306 // Return the array containing the shortest distance to every node
1307 return dist;
1308}
1309
1310#ifdef ENABLE_GRAPH_VISUALIZATION
1311template <typename T> void weighted_graph<T>::visualize() {
1312 std::string s;
1313 if (_type == "directed") {
1314 if (std::is_same_v<T, char> || std::is_same_v<T, std::string>) {
1315 for (auto& [element, neighbors] : adj) {
1316 for (std::pair<T, double>& x : neighbors) {
1317 if (x.first == element) {
1318 continue;
1319 }
1320 s += element;
1321 s += "->";
1322 s += x.first;
1323 s += "[label=";
1324 s += std::to_string(x.second);
1325 s += "]";
1326 s += '\n';
1327 }
1328 }
1329 } else {
1330 for (auto& [element, neighbors] : adj) {
1331 for (std::pair<T, double>& x : neighbors) {
1332 if (x.first == element) {
1333 continue;
1334 }
1335 s += std::to_string(element);
1336 s += "->";
1337 s += std::to_string(x.first);
1338 s += "[label=";
1339 s += std::to_string(x.second);
1340 s += "]";
1341 s += '\n';
1342 }
1343 }
1344 }
1345 } else {
1346 if (std::is_same_v<T, char> || std::is_same_v<T, std::string>) {
1347 for (auto& [element, neighbors] : adj) {
1348 for (std::pair<T, double>& x : neighbors) {
1349 if (x.first == element) {
1350 continue;
1351 }
1352 s += element;
1353 s += "--";
1354 s += x.first;
1355 s += "[label=";
1356 s += std::to_string(x.second);
1357 s += "]";
1358 s += '\n';
1359 }
1360 }
1361 } else {
1362 for (auto& [element, neighbors] : adj) {
1363 for (std::pair<T, double>& x : neighbors) {
1364 if (x.first == element) {
1365 continue;
1366 }
1367 s += std::to_string(element);
1368 s += "--";
1369 s += std::to_string(x.first);
1370 s += "[label=";
1371 s += std::to_string(x.second);
1372 s += "]";
1373 s += '\n';
1374 }
1375 }
1376 }
1377 }
1378 if (_type == "directed") {
1379 digraph_visualization::visualize(s);
1380 } else {
1381 graph_visualization::visualize(s);
1382 }
1383}
1384#endif
1385
1386#endif
graph::scc
int64_t scc()
scc(strongly connected components) function.
Definition graph.h:497
graph::operator<<
friend std::ostream & operator<<(std::ostream &out, graph< T > &g)
operator << for the graph class.
Definition graph.h:217
graph::bipartite
bool bipartite()
bipartite function.
Definition graph.h:420
graph::add_edge
void add_edge(T u, T v)
add_edge function
Definition graph.h:89
graph::bfs
std::vector< T > bfs(T start)
bfs function
Definition graph.h:301
graph::bridge
std::vector< std::vector< T > > bridge(T start)
bridge function.
Definition graph.h:448
graph::has_edge
bool has_edge(T start, T end)
has_edge function.
Definition graph.h:107
graph::dfs
std::vector< T > dfs(T start)
dfs function
Definition graph.h:278
graph::topological_sort
std::vector< T > topological_sort()
topological_sort function.
Definition graph.h:385
graph::cycle
bool cycle()
cycle function.
Definition graph.h:355
graph::visualize
void visualize()
visualize function.
graph::clear
void clear()
clear function Clearing the entire graph.
Definition graph.h:123
graph::~graph
~graph()
Destroy the graph object.
Definition graph.h:82
graph::connected
bool connected()
connected function.
Definition graph.h:461
graph::graph
graph(std::string _type, std::vector< std::pair< T, std::vector< T > > > _adj={})
Constructor for the unweighted graph.
Definition graph.h:39
graph::size
size_t size()
size function
Definition graph.h:274
graph::connected_components
int64_t connected_components()
connected_components function.
Definition graph.h:327
graph::graph
graph(const graph &g)
Construct a new graph object.
Definition graph.h:64
graph::eulerian
int eulerian()
eulerian function.
Definition graph.h:549
graph::operator=
graph & operator=(const graph &g)
operator = for the graph class
Definition graph.h:72
graph::empty
bool empty()
empty function Checks if a graph is empty.
Definition graph.h:132
weighted_graph::eulerian
int eulerian()
eulerian function.
Definition graph.h:1251
weighted_graph::scc
int64_t scc()
scc(strongly connected components) function.
Definition graph.h:1163
weighted_graph::shortest_path
double shortest_path(T start, T end)
shortest_path function.
Definition graph.h:893
weighted_graph::connected_components
int64_t connected_components()
connected_components function.
Definition graph.h:1004
weighted_graph::~weighted_graph
~weighted_graph()
Destroy the weighted graph object.
Definition graph.h:672
weighted_graph::bipartite
bool bipartite()
bipartite function.
Definition graph.h:1122
weighted_graph::bridge
std::vector< std::vector< T > > bridge(T start)
bridge function.
Definition graph.h:1150
weighted_graph::has_edge
bool has_edge(T start, T end)
has_edge function.
Definition graph.h:697
weighted_graph::weighted_graph
weighted_graph(const weighted_graph &g)
Copy constructor for weighted graph class.
Definition graph.h:653
weighted_graph::cycle
bool cycle()
cycle function.
Definition graph.h:1032
weighted_graph::topological_sort
std::vector< T > topological_sort()
topological sort function.
Definition graph.h:1062
weighted_graph::bfs
std::vector< T > bfs(T start)
bfs function.
Definition graph.h:978
weighted_graph::empty
bool empty()
empty function.
Definition graph.h:721
weighted_graph::connected
bool connected()
connected function.
Definition graph.h:1215
weighted_graph::visualize
void visualize()
visualize function.
weighted_graph::bellman_ford
std::unordered_map< T, double > bellman_ford(T start)
find SSSP and identify negative cycles.
Definition graph.h:1270
weighted_graph::dfs
std::vector< T > dfs(T start)
dfs function.
Definition graph.h:951
weighted_graph::add_edge
void add_edge(T u, T v, int64_t w)
add_edge function.
Definition graph.h:680
weighted_graph::size
size_t size()
size function.
Definition graph.h:889
weighted_graph::max_flow
int max_flow(T start, T end)
maximum flow function
weighted_graph::weighted_graph
weighted_graph(std::string _type, std::vector< std::pair< std::pair< T, T >, int64_t > > _adj={})
Constructor for weighted graph.
Definition graph.h:631
weighted_graph::clear
void clear()
clear function. Clearing the entire graph.
Definition graph.h:713
weighted_graph::operator=
weighted_graph & operator=(const weighted_graph &g)
operator = for weighted graph class
Definition graph.h:661
weighted_graph::prim
int64_t prim(T start)
prim function.
Definition graph.h:1097
weighted_graph::operator<<
friend std::ostream & operator<<(std::ostream &out, weighted_graph< T > &g)
<< operator for the weighted graph class.
Definition graph.h:833
Generated by doxygen 1.13.2