From 7eee5a78005a9a569186d2c8b4b645a818ab9bf1 Mon Sep 17 00:00:00 2001 From: Stoycho Kyosev Date: Sun, 6 Oct 2024 07:04:44 -0400 Subject: Cleanup --- .../Graph-Impl/AdjacencyListGraph/AdjListGraph.cpp | 82 ------------------ .../Graph-Impl/AdjacencyListGraph/AdjListGraph.h | 50 ----------- Seminar11/Graph-Impl/AdjacencyListGraph/src.cpp | 19 ----- Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.cpp | 97 ---------------------- Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.h | 52 ------------ 5 files changed, 300 deletions(-) delete mode 100644 Seminar11/Graph-Impl/AdjacencyListGraph/AdjListGraph.cpp delete mode 100644 Seminar11/Graph-Impl/AdjacencyListGraph/AdjListGraph.h delete mode 100644 Seminar11/Graph-Impl/AdjacencyListGraph/src.cpp delete mode 100644 Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.cpp delete mode 100644 Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.h (limited to 'Seminar11/Graph-Impl') diff --git a/Seminar11/Graph-Impl/AdjacencyListGraph/AdjListGraph.cpp b/Seminar11/Graph-Impl/AdjacencyListGraph/AdjListGraph.cpp deleted file mode 100644 index 3cbbdd0..0000000 --- a/Seminar11/Graph-Impl/AdjacencyListGraph/AdjListGraph.cpp +++ /dev/null @@ -1,82 +0,0 @@ -#include"AdjListGraph.h" - -using vertex_t = AdjListGraph::vertex_t; -using weight_t = AdjListGraph::weight_t; - -AdjListGraph::AdjListGraph(size_t vertexCount) { - data = std::vector>(vertexCount, std::list()); -} - -void AdjListGraph::addVertex() { - data.push_back(std::list()); -} - -void AdjListGraph::removeVertex(vertex_t v) { - if(!validVertex(v)) - throw "Invalid vertex"; - - // Премахва самия връх - data.erase(data.begin() + v); - - // За всеки от останалите върхове ако - // има елемент, който сочи към него трябва да се изтрие - // ако има елемент, който е по - голям от него трябва да се намали с 1 - - for(auto& vertexList : data) { - vertexList.remove_if([&](Edge e) -> bool { return e.to == v; }); - - for(Edge& e : vertexList) - if(e.to > v) - e.to--; - } -} - -bool AdjListGraph::validVertex(vertex_t v) const { - return v < data.size(); -} - -void AdjListGraph::addEdge(vertex_t from, vertex_t to, weight_t w) { - if(!validVertex(from) || !validVertex(to)) - throw "Invalid vertex"; - - data[from].push_back( {to, w} ); - data[to].push_back( {from, w} ); -} - -void AdjListGraph::removeEdge(vertex_t from, vertex_t to) { - if(!validVertex(from) || !validVertex(to)) - throw "Invalid vertex"; - - data[from].remove_if([&](Edge e) -> bool {return e.to == to; }); - data[to].remove_if([&](Edge e) -> bool {return e.to == from; }); -} - -bool AdjListGraph::hasEdge(vertex_t from, vertex_t to) const { - if(!validVertex(from) || !validVertex(to)) - throw "Invalid vertex"; - - for(const Edge& e : data[from]) - if(e.to == to) - return true; - - return false; -} - -weight_t AdjListGraph::getWeight(vertex_t from, vertex_t to) const { - if(!validVertex(from) || !validVertex(to)) - throw "Invalid vertex"; - - for(const Edge& e : data[from]) - if(e.to == to) - return e.weight; - - return 0; -} - -std::vector AdjListGraph::adjacent(vertex_t v) const { - return std::vector(data[v].begin(), data[v].end()); -} - -size_t AdjListGraph::vertexCount() const { - return data.size(); -} \ No newline at end of file diff --git a/Seminar11/Graph-Impl/AdjacencyListGraph/AdjListGraph.h b/Seminar11/Graph-Impl/AdjacencyListGraph/AdjListGraph.h deleted file mode 100644 index 40446fd..0000000 --- a/Seminar11/Graph-Impl/AdjacencyListGraph/AdjListGraph.h +++ /dev/null @@ -1,50 +0,0 @@ -/* -Тегловен неориентиран граф представен чрез списъци на съседство. - -Предимства: -* Паметта която използваме е вече O(|V| + |E|) -* Вземането на всички съседи е по - бързо - -Недостатъци: -* Да проверим дали има ребро между два върха вече не е O(1) - -*/ -#ifndef ADJ_LIST_GRAPH_IMPL -#define ADJ_LIST_GRAPH_IMPL - -#include -#include -#include - -class AdjListGraph { - public: - using vertex_t = unsigned int; - using weight_t = unsigned int; - - private: - struct Edge { - vertex_t to; - weight_t weight; - }; - - std::vector> data; - - public: - AdjListGraph(size_t n); - - void addVertex(); - void removeVertex(vertex_t); - bool validVertex(vertex_t) const; - - void addEdge(vertex_t, vertex_t, weight_t); - void removeEdge(vertex_t, vertex_t); - - weight_t getWeight(vertex_t, vertex_t) const; - bool hasEdge(vertex_t, vertex_t) const; - - size_t vertexCount() const; - - std::vector adjacent(vertex_t) const; -}; - -#endif \ No newline at end of file diff --git a/Seminar11/Graph-Impl/AdjacencyListGraph/src.cpp b/Seminar11/Graph-Impl/AdjacencyListGraph/src.cpp deleted file mode 100644 index b0484e0..0000000 --- a/Seminar11/Graph-Impl/AdjacencyListGraph/src.cpp +++ /dev/null @@ -1,19 +0,0 @@ -#include -#include -#include -#include"AdjListGraph.h" - -int main() { - AdjListGraph g(10); - - g.addEdge(0, 1, 1); - g.addEdge(0, 2, 1); - g.addEdge(0, 3, 1); - g.addEdge(0, 4, 1); - - auto res = g.adjacent(1); - - for(auto i : res) { - std::cout << i.to << " "; - } -} \ No newline at end of file diff --git a/Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.cpp b/Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.cpp deleted file mode 100644 index b5835f8..0000000 --- a/Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.cpp +++ /dev/null @@ -1,97 +0,0 @@ -#include"MatrixGraph.h" - -using vertex_t = MatrixGraph::vertex_t; -using weight_t = MatrixGraph::weight_t; - -MatrixGraph::MatrixGraph(size_t v) { - data = std::vector>(v, std::vector(v, 0)); -} - -bool MatrixGraph::validVertex(vertex_t v) const { - return v < data.size(); -} - -bool MatrixGraph::adjacent(vertex_t from, vertex_t to) const { - if(!validVertex(from) || !validVertex(to)) - throw "Invalid vertex"; - - return data[from][to] > 0; -} - -void MatrixGraph::addDirectedEdge(vertex_t from, vertex_t to, weight_t w) { - if(!validVertex(from) || !validVertex(to)) - throw "Invalid vertex"; - - data[from][to] = w; -} - -void MatrixGraph::addEdge(vertex_t from, vertex_t to, weight_t w) { - addDirectedEdge(from, to, w); - addDirectedEdge(to, from, w); -} - -void MatrixGraph::addVertex() { - for(auto& v : data) - v.push_back(0); - - data.push_back(std::vector()); -} - -void MatrixGraph::removeEdge(vertex_t from, vertex_t to) { - if(!validVertex(from) || !validVertex(to)) - throw "Invalid vertex"; - - data[from][to] = 0; -} - -void MatrixGraph::removeVertex(vertex_t v) { - if(!validVertex(v)) - throw "Invalid vertex"; - - data.erase(data.begin() + v); - - for(auto& vertex : data) - vertex.erase(vertex.begin() + v); -} - -weight_t MatrixGraph::getWeight(vertex_t from, vertex_t to) const { - if(!validVertex(from) || !validVertex(to)) - throw "Invalid vertex"; - - return data[from][to]; -} - -std::vector MatrixGraph::getSuccessors(vertex_t from) const { - if(!validVertex(from)) - throw "Invalid vertex"; - - std::vector result; - - for (size_t i = 0; i < data.size(); i++) - if(data[from][i] > 0) - result.push_back(i); - - return result; -} - -std::vector MatrixGraph::getPredecessors(vertex_t from) const { - if(!validVertex(from)) - throw "Invalid vertex"; - - std::vector result; - - for (size_t i = 0; i < data.size(); i++) - if(data[i][from] > 0) - result.push_back(i); - - return result; -} - -std::vector MatrixGraph::adjacent(vertex_t from) const { - return getSuccessors(from); -} - - -size_t MatrixGraph::vertexCount() const { - return data.size(); -} \ No newline at end of file diff --git a/Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.h b/Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.h deleted file mode 100644 index aade1a1..0000000 --- a/Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.h +++ /dev/null @@ -1,52 +0,0 @@ -/* -Ориентиран тегловен граф представен чрез матрица на съседство. - -Плюсове: -* Лесна имплементация -* Проверка за ребро, премахване на ребро, добавяне на ребро са O(1) - -Минуси: -* Паметта винаги е O(|V|^2) -* Намирането на предшественици (наследници) или в неориентирания случай на съседи отнема O(|V|) време. - -weight_t => тип, чрез който представяме тежест -vertex_t => тип, чрез който представяме връх -*/ - -#ifndef GRAPH_IMPL_H -#define GRAPH_IMPL_H - -#include -#include - -class MatrixGraph { - public: - using vertex_t = unsigned int; - using weight_t = unsigned int; - - private: - std::vector> data; - - public: - MatrixGraph(size_t); - - void addVertex(); - void removeVertex(vertex_t); - - void addDirectedEdge(vertex_t from, vertex_t to, weight_t w); - void addEdge(vertex_t from, vertex_t to, weight_t w); - void removeEdge(vertex_t from, vertex_t to); - - bool validVertex(vertex_t) const; - weight_t getWeight(vertex_t, vertex_t) const; - - size_t vertexCount() const; - bool adjacent(vertex_t from, vertex_t to) const; - - std::vector getSuccessors(vertex_t) const; - std::vector getPredecessors(vertex_t) const; - // Same as getSuccessors, here for interface purposes. - std::vector adjacent(vertex_t) const; -}; - -#endif \ No newline at end of file -- cgit v1.3.1-26-gb76a