add Seminar11

5 files changed, 293 insertions, 0 deletions

diff --git a/Seminar11/Graph-Impl/AdjacencyListGraph/AdjListGraph.cpp b/Seminar11/Graph-Impl/AdjacencyListGraph/AdjListGraph.cpp
new file mode 100644
index 0000000..3cbbdd0
--- /dev/null
+++ b/Seminar11/Graph-Impl/AdjacencyListGraph/AdjListGraph.cpp
@@ -0,0 +1,82 @@
+#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
new file mode 100644
index 0000000..40446fd
--- /dev/null
+++ b/Seminar11/Graph-Impl/AdjacencyListGraph/AdjListGraph.h
@@ -0,0 +1,50 @@
+/*
+Тегловен неориентиран граф представен чрез списъци на съседство.
+
+Предимства:
+* Паметта която използваме е вече 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
new file mode 100644
index 0000000..b0484e0
--- /dev/null
+++ b/Seminar11/Graph-Impl/AdjacencyListGraph/src.cpp
@@ -0,0 +1,19 @@
+#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
diff --git a/Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.cpp b/Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.cpp
new file mode 100644
index 0000000..bf155a1
--- /dev/null
+++ b/Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.cpp
@@ -0,0 +1,92 @@
+#include"MatrixGraph.h"
+
+using vertex_t = MatrixGraph::vertex_t;
+using weight_t = MatrixGraph::weight_t;
+
+MatrixGraph::MatrixGraph(size_t v) {
+    data = std::vector<std::vector<weight_t>>(v, std::vector<weight_t>(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<weight_t>());
+}
+
+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<vertex_t> MatrixGraph::getSuccessors(vertex_t from) const {
+    if(!validVertex(from))
+        throw "Invalid vertex";
+
+    std::vector<vertex_t> result;
+
+    for (size_t i = 0; i < data.size(); i++)
+        if(data[from][i] > 0) 
+            result.push_back(i);
+
+    return result;
+}
+
+std::vector<vertex_t> MatrixGraph::getPredecessors(vertex_t from) const {
+    if(!validVertex(from))
+        throw "Invalid vertex";
+
+    std::vector<vertex_t> result;
+
+    for (size_t i = 0; i < data.size(); i++)
+        if(data[i][from] > 0) 
+            result.push_back(i);
+
+    return result;
+}
+
+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
new file mode 100644
index 0000000..1e4ec71
--- /dev/null
+++ b/Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.h
@@ -0,0 +1,50 @@
+/*
+Ориентиран тегловен граф представен чрез матрица на съседство.
+
+Плюсове:
+* Лесна имплементация
+* Проверка за ребро, премахване на ребро, добавяне на ребро са O(1)
+
+Минуси:
+* Паметта винаги е O(|V|^2)
+* Намирането на предшественици (наследници) или в неориентирания случай на съседи отнема O(|V|) време.
+
+weight_t => тип, чрез който представяме тежест
+vertex_t => тип, чрез който представяме връх
+*/
+
+#ifndef GRAPH_IMPL_H
+#define GRAPH_IMPL_H
+
+#include<vector>
+#include<cstddef>
+
+class MatrixGraph {
+    public:
+    using vertex_t = unsigned int;
+    using weight_t = unsigned int;
+
+    private:
+    std::vector<std::vector<weight_t>> 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<vertex_t> getSuccessors(vertex_t) const;
+    std::vector<vertex_t> getPredecessors(vertex_t) const;
+};
+
+#endif
\ No newline at end of file