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