summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorSanto Cariotti <dcariotti24@gmail.com>2020-07-17 17:18:40 +0200
committerSanto Cariotti <dcariotti24@gmail.com>2020-07-17 17:18:40 +0200
commit0c6faed1acb130ae5bbc572dc7194a263f1cca6c (patch)
treefd22d57fddd0eb4d73b9e90703125e1fbb4d6801
parentdc54a3392cd038e35dc9c24bdaa1644055b6813e (diff)
feat: add graph in c++ with list and all algorithms
BFS, DFS, topological sort, SSC
-rw-r--r--I_anno/Programmazione_2/data_structures/graph_stl.cc221
1 files changed, 221 insertions, 0 deletions
diff --git a/I_anno/Programmazione_2/data_structures/graph_stl.cc b/I_anno/Programmazione_2/data_structures/graph_stl.cc
new file mode 100644
index 0000000..5381747
--- /dev/null
+++ b/I_anno/Programmazione_2/data_structures/graph_stl.cc
@@ -0,0 +1,221 @@
+#include<iostream>
+#include<vector>
+#include<algorithm>
+#include<queue>
+#include<stack>
+#define INF 99999999
+#define W -1
+#define G 0
+#define B 1
+
+using namespace std;
+
+template<class H>
+class graph {
+public:
+ graph(int len) : _len{len}, _nodes{0}, _edges{0} {
+ _k = new H*[len];
+ _adj = new vector<int>[len];
+ _colors = new int[len];
+ _d = new int[len];
+ _f = new int[len];
+ _p = new int[len];
+
+ for(int i = 0; i < len; ++i) {
+ _k[i] = nullptr;
+ }
+ }
+ ~graph() {
+ delete[] _k;
+ delete[] _adj;
+ }
+
+ graph<H>* add_node(H x) {
+ if(_index(x) > -1) return this;
+ if(_nodes == _len) return this;
+ _k[_nodes++] = new H(x);
+
+ return this;
+ }
+ graph<H>* add_edge(H u, H v) {
+ int i = _index(u);
+ int j = _index(v);
+ if(i < 0 || j < 0) return this;
+
+ if(find(_adj[i].begin(), _adj[i].end(), j) == _adj[i].end()) {
+ _adj[i].push_back(j);
+ }
+ return this;
+ }
+ void print() {
+ for(int i = 0; i < _nodes; ++i) {
+ cout << "(" << *_k[i] << ", " << i << "): ";
+ for(auto const& j : _adj[i]) {
+ cout << "(" << *_k[j] << ", " << j << ") ";
+ }
+ cout << endl;
+ }
+ }
+ void dfsvisit(int u, bool visited[]) {
+ visited[u] = true;
+ cout << "(" << *_k[u] << ", " << u << ") ";
+ for(auto const& i : _adj[u]) {
+ if(!visited[i])
+ dfsvisit(i, visited);
+ }
+ }
+ int dfsvisit(int u) {
+ int cycle = 0;
+ _colors[u] = G;
+ _d[u] = _time++;
+
+ for(auto const& j : _adj[u]) {
+ if(_colors[j] == W)
+ cycle |= dfsvisit(j);
+ }
+
+ _colors[u] = B;
+ _stack.push(u);
+ _f[u] = _time++;
+ return cycle;
+ }
+ int dfs() {
+ int cycle = 0;
+ for(int i = 0; i < _nodes; ++i) {
+ _colors[i] = W;
+ }
+ _time = 0;
+ for(int i = 0; i < _nodes; ++i) {
+ if(_colors[i] == W)
+ cycle |= dfsvisit(i);
+ else if(_colors[i] == G)
+ cycle = 1;
+ }
+ for(int i = 0; i < _nodes; ++i) {
+ cout << "(" << *_k[i] << ", " << i << "): [" << _d[i] << "," << _f[i] << "]" << endl;
+ }
+ return cycle;
+ }
+
+ void top_sort() {
+ int cycle = dfs();
+ if(cycle) {
+ cout << "cyclic graph!" << endl;
+ return;
+ }
+ int* s = new int[_nodes];
+ for(int i = 0; i < _nodes; ++i) s[i] = i;
+ _sort(s, _nodes, _f);
+ for(int i = 0; i < _nodes; ++i) {
+ cout << "(" << s[i] << ", " << _f[s[i]] << ") ";
+ }
+
+ }
+
+ void bfs(H v) {
+ int s = _index(v);
+ if(s < 0) return;
+
+ for(int i = 0; i < _nodes; ++i) {
+ _colors[i] = W;
+ _d[i] = INF;
+ _p[i] = -1;
+ }
+ _colors[s] = G;
+ _d[s] = 0;
+ queue<int> q;
+ q.push(s);
+ while(!q.empty()) {
+ int u = q.front();
+ q.pop();
+ for(auto const& j : _adj[u]) {
+ if(_colors[j] == W) {
+ _colors[j] = G;
+ _d[j] = _d[u]+1;
+ _p[j] = u;
+ q.push(j);
+ }
+ }
+ _colors[u] = B;
+ }
+ for(int i = 0; i < _nodes; ++i) {
+ cout << "(" << *_k[i] << ", " << i << "): [" << _d[i] << "]" << endl;
+ }
+ }
+ void ssc() {
+ dfs();
+ cout << endl << endl;
+ auto gr = _transpose();
+ bool* visited = new bool[_nodes];
+ for(int i = 0; i < _nodes; ++i)
+ visited[i] = false;
+
+ while(!_stack.empty()) {
+ int v = _stack.top();
+ _stack.pop();
+ if(!visited[v]) {
+ gr->dfsvisit(v, visited);
+ cout << endl;
+ }
+ }
+ delete[] visited;
+ }
+private:
+ graph<H>* _transpose() {
+ graph<H>* g = new graph<H>{_len};
+ for(int i = 0; i < _nodes; ++i) {
+ g->add_node(*_k[i]);
+ }
+
+ for(int i = 0; i < _nodes; ++i) {
+ for(auto const& j : _adj[i]) {
+ g->add_edge(j, i);
+ }
+ }
+
+ return g;
+ }
+ void _sort(int* d, int n, int* s) {
+ for(int i = -1; i < n; ++i) {
+ int j = i-1;
+ while(j > -1 && s[d[j+1]]>s[d[j]]) {
+ swap(d[s[j+1]], d[s[j]]);
+ --j;
+ }
+ }
+ }
+ int _index(H x) {
+ for(int i = 0; i < _nodes; ++i)
+ if(*_k[i] == x) return i;
+
+ return -1;
+ }
+ stack<int> _stack;
+ H** _k;
+ vector<int>* _adj;
+ int _len, _nodes, _edges;
+ int* _colors;
+ int _time;
+ int* _d;
+ int* _f;
+ int* _p;
+};
+
+int main() {
+ graph<int>* g = new graph<int>{5};
+ for(auto const& i : {0, 1, 2, 3, 4})
+ g->add_node(i);
+ g->add_edge(1, 0);
+ g->add_edge(2, 1);
+ g->add_edge(0, 2);
+ g->add_edge(0, 3);
+ g->add_edge(3, 4);
+ //g->print();
+ cout << endl;
+ //g->top_sort();
+ g->ssc();
+ cout << endl;
+ //g->bfs(0);
+ delete g;
+ return 0;
+}