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 ----- 3 files changed, 151 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 (limited to 'Seminar11/Graph-Impl/AdjacencyListGraph') 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 -- cgit v1.3.1-26-gb76a