diff options
Cleanup
3 files changed, 0 insertions, 151 deletions
| -rw-r--r-- | Seminar11/Graph-Impl/AdjacencyListGraph/AdjListGraph.cpp | 82 | ||||
| -rw-r--r-- | Seminar11/Graph-Impl/AdjacencyListGraph/AdjListGraph.h | 50 | ||||
| -rw-r--r-- | Seminar11/Graph-Impl/AdjacencyListGraph/src.cpp | 19 |
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<std::list<Edge>>(vertexCount, std::list<Edge>()); -} - -void AdjListGraph::addVertex() { - data.push_back(std::list<Edge>()); -} - -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::Edge> AdjListGraph::adjacent(vertex_t v) const { - return std::vector<Edge>(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<vector> -#include<list> -#include<algorithm> - -class AdjListGraph { - public: - using vertex_t = unsigned int; - using weight_t = unsigned int; - - private: - struct Edge { - vertex_t to; - weight_t weight; - }; - - std::vector<std::list<Edge>> 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<Edge> 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<iostream> -#include<list> -#include<algorithm> -#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 |
