From f9db5ea3d85862050fa3cb921baacab4cf1529dd Mon Sep 17 00:00:00 2001 From: Santo Cariotti Date: Wed, 24 Jun 2020 17:08:36 +0200 Subject: feat: add graph with matrix instead of list --- .../data_structures/matrix-graph.cc | 81 ++++++++++++++++++++++ 1 file changed, 81 insertions(+) create mode 100644 I_anno/Programmazione_2/data_structures/matrix-graph.cc (limited to 'I_anno') diff --git a/I_anno/Programmazione_2/data_structures/matrix-graph.cc b/I_anno/Programmazione_2/data_structures/matrix-graph.cc new file mode 100644 index 0000000..a644ec1 --- /dev/null +++ b/I_anno/Programmazione_2/data_structures/matrix-graph.cc @@ -0,0 +1,81 @@ +#include +#include + +using namespace std; + +template +class matrix_graph { +public: + ~matrix_graph() { + delete[] _m; + delete[] _k; + } + matrix_graph(int len) : _len{len}, _nodes{0}, _edges{0} { + _m = new int*[len]; + _k = new H*[len]; + for(int i = 0; i < len; ++i) { + _m[i] = new int[len]; + _k[i] = nullptr; + for(int j = 0; j < len; ++j) + _m[i][j] = 0; + } + } + + matrix_graph* add_node(H k) { + if(_len == _nodes) return this; // no more space for new nodes + if(_index(k) > -1) return this; // nodes already exists + + _k[_nodes++] = new H(k); + + return this; + } + + matrix_graph* add_edge(H x, H y) { + int i = _index(x); + int j = _index(y); + if(i < 0 || j < 0) return this; + if(!_m[i][j]) { + _m[i][j] = 1; + _edges++; + } + return this; + } + void print() { + for(int i = 0; i < _len; ++i) { + cout << i << ' ' << *_k[i] << ": "; + for(int j = 0; j < _len; ++j) { + if(_m[i][j]) + cout << *_k[j] << ' '; + } + cout << '\n'; + } + cout << endl; + for(int i = 0; i < _len; ++i) { + for(int j = 0; j < _len; ++j) { + cout << _m[i][j] << ' '; + } + cout << '\n'; + } + } +private: + int _len, _nodes, _edges; + int** _m; + H** _k; + int _index(H x) { + for(int i = 0; i < _nodes; ++i) + if(*_k[i] == x) return i; + return -1; + } +}; + +int main() { + matrix_graph* g = new matrix_graph(5); + g->add_node("hello")->add_node("greg")->add_node("yes"); + g->add_node("nop")->add_node("ok"); + g->add_edge("hello", "ok"); + g->add_edge("ok", "yes")->add_edge("yes", "ok")->add_edge("yes", "yes"); + g->add_edge("yes", "nop"); + g->print(); + delete g; + return 0; +} -- cgit v1.2.3-18-g5258