From 5c89ba385cca47ffd34b402e102f279f73f82cb5 Mon Sep 17 00:00:00 2001 From: Santo Cariotti Date: Wed, 1 Jul 2020 21:46:11 +0200 Subject: feat: topological sort --- .../Programmazione_2/data_structures/top-sort.cc | 212 +++++++++++++++++++++ 1 file changed, 212 insertions(+) create mode 100644 I_anno/Programmazione_2/data_structures/top-sort.cc (limited to 'I_anno/Programmazione_2/data_structures') diff --git a/I_anno/Programmazione_2/data_structures/top-sort.cc b/I_anno/Programmazione_2/data_structures/top-sort.cc new file mode 100644 index 0000000..7441ee9 --- /dev/null +++ b/I_anno/Programmazione_2/data_structures/top-sort.cc @@ -0,0 +1,212 @@ + +#include +#include +#include +#define W -1 +#define G 0 +#define B 1 + +using namespace std; + +template +class node { +public: + explicit node(H key, node* next) : _key{key}, _next(next) {} + const H& key() const { return _key; } + H& key() { return _key; } + const node*& next() const { return _next; } + node*& next() { return _next; } +private: + H _key; + node* _next; +}; + +template +class list { +public: + list() : _head{nullptr} {} + ~list() { + while(_head) { + auto tmp = _head; + _head = _head->next(); + delete tmp; + } + } + list* push(H val) { + auto iter = _head; + while(iter && iter->next()) + iter = iter->next(); + + if(!iter) + _head = new node{val, nullptr}; + else + iter->next() = new node{val, nullptr}; + + return this; + } + void print() { + auto iter = _head; + while(iter) { + cout << iter->key() << ' '; + iter = iter->next(); + } + } + vector as_vector() { + vector v; + auto iter = _head; + while(iter) { + v.push_back(iter->key()); + iter = iter->next(); + } + return v; + } + node* search(H val) { + auto iter = _head; + while(iter && iter->key() != val) { + iter = iter->next(); + } + + return iter; + } +private: + node* _head; +}; + +template +class graph { +private: + int _len, _nodes, _edges; + int* _parents; + int* _radixes; + int* _distances; + int* _finishes; + int* _colors; + int _time; + int _current; + H** _k; // it works like a dictionary, it saves the keys + list** _adj; + int _index(H val) { + for(int i = 0; i < _nodes; ++i) + if(*_k[i] == val) return i; + + return -1; + } + bool _dfsvisit(int u) { + bool cycle = false; + _colors[u] = G; + _distances[u] = _time++; + _radixes[u] = _current; + for(auto const& v : _adj[u]->as_vector()) { + if(_colors[v] == W) { + _parents[v] = u; + _dfsvisit(v); + } else if(_colors[v] == G) { + cycle = true; + } + } + _colors[u] = B; + _finishes[u] = _time++; + return cycle; + } +public: + graph(int len) : _len{len}, _nodes{0}, _edges{0} { + _k = new H*[len]; + _adj = new list*[_len]; + _parents = new int[_len]; + _radixes = new int[_len]; + _distances = new int[_len]; + _finishes = new int[_len]; + _colors = new int[_len]; + for(int i = 0; i < _len; ++i) { + _k[i] = nullptr; + _adj[i] = new list{}; + } + } + + graph* add_node(H k) { + if(_nodes == _len) return this; + if(_index(k) >= 0) return this; // node is already there + + _k[_nodes++] = new H(k); + + return this; + } + + + bool dfs() { + bool cycle = 0; + _time = 0; + for(int i = 0; i < _nodes; ++i) { + _colors[i] = W; + _parents[i] = -1; + } + + for(int i = 0; i < _nodes; ++i) { + if(_colors[i] == W) { + _current = i; + cycle |= _dfsvisit(i); + } + } + for(int i = 0; i < _nodes; ++i) { + cout << *_k[i] << "(" << _distances[i]+1 << ',' << _finishes[i]+1 << ")" << endl; + } + return cycle; + } + + void top_sort() { + bool cycle = dfs(); + if(cycle) { + cerr << "Grafo ciclico\n"; + return; + } + vector s(_finishes, _finishes+_nodes); + sort(begin(s), end(s)); + for(auto const& i : s) { + cout << "(" << i << ", " << _finishes[i] << ") "; + } + } + + graph* add_edge(H x, H y) { + int i = _index(x); + int j = _index(y); + if(i < 0 || j < 0) return this; + + if(!_adj[i]->search(j)) { + _adj[i]->push(j); + _edges++; + } + + return this; + } + + void print() { + for(int i = 0; i < _nodes; ++i) { + cout << "(" << i << ", " << *_k[i] << "): "; + for(auto const& j : _adj[i]->as_vector()) + cout << "(" << j << ", " << *_k[j] << "), "; + cout << '\n'; + } + } +}; + + +int main() { + graph* g = new graph(6); + g->add_node('u')->add_node('v')->add_node('x')->add_node('y'); + g->add_node('w')->add_node('z'); + g->add_edge('u', 'v'); + g->add_edge('u', 'x'); + g->add_edge('x', 'v'); + g->add_edge('y', 'x'); + g->add_edge('v', 'y'); + g->add_edge('w', 'y'); + g->add_edge('w', 'z'); + g->add_edge('z', 'z'); + + g->print(); + g->dfs(); + g->top_sort(); + + delete g; + return 0; +} -- cgit v1.2.3-18-g5258