add Seminar11

14 files changed, 491 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
diff --git a/Seminar11/README.md b/Seminar11/README.md
new file mode 100644
index 0000000..d572d6e
--- /dev/null
+++ b/Seminar11/README.md
@@ -0,0 +1,134 @@
+# Графи
+
+## Определение
+```
+Граф е наредена двойка G = (V, E), където V e непразно множество, чиито елементи се наричат върхове. Множеството E е крайно множество от ребра. Ребро наричаме двуелементно множество {v1, v2}, където v1 и v2 са елементи на V.
+```
+Графите, както подсказва името, могат да бъдат изобразени "графично". Важно е да не се бърка рисунката на граф със самия граф. Един граф може да има безброй много рисунки.
+
+Примерно, нека V = {v1, v2, v3}, E = {{v1, v2}, {v2, v3}, {v3, v1}}. Този граф може да се нарисува като:
+![](media/graph.png)
+
+## Видове графи
+
+### Ориентирани и неориентирани графи
+Графът, който видяхте на първия пример е неориентиран. Когато говорим за граф, и не поясним дали е ориентиран или не, става въпрос за неориентиран граф. Понякога е удобно да различаваме дали реброто e от v към u или от u към v. За ребрата на ориентирания граф вече може да си мислим не като за двуелементни множества от върхове а за **наредени двойки от върхове**. 
+
+```
+Припомняне:
+Когато имаме двуелементно множество {v1, v2} е вярно, че {v1, v2} = {v2, v1}. При наредените двойки това не е вярно. За v1 != v2 имаме (v1, v2) != (v2, v1).
+Наредената двойка (a, b) e множеството {{a}, {a, b}}. Да твърдим, че (a, b) = (b, a) e същото като да твърдим, че {{a}, {a, b}} = {{b}, {a, b}}. Това става единствено когато a = b.
+```
+
+Сега, разглеждаме ребрата на графа като наредени двойки. 
+Нека V = {v1, v2, v3} и E = {(v1, v2), (v2, v3), (v2, v1)}.
+Този граф би изглеждал така:
+
+![](media/dir-graph.png)
+
+### Тегловен граф
+Често е полезно да "закачим" някакви тегла на ребрата. Примерно, ако върходете на графа представляват някакви забележителности, а ребрата са пътища между тях, теглата могат да представляват времето в минути, което отнема да стигнем от v1 до v2. 
+
+Примерно, това е **рисунка** на тегловен граф:
+![](media/weighted-graph.png)
+
+Можем да имаме и тегловни ориентирани графи.
+![](media/weighted-dirscted-graph%20(1).png)
+
+### Мултиграфи
+Неформално, в мултиграфа позволяваме да има много ребра с краища едни и същи два върха. Отново може да имаме тегловни и нетегловни мултиграфи. Може да имаме ориентирани и неориентирани мулти графи, нищо не ни спира.
+
+## Дефиниции
+| Понятие                        | Дефиниция 
+| :---                           |    :----:   
+| Примка в граф                  | Ребро от типа {v, v}
+| Път в граф                     | Редица от върхове (v_1, v_2, ..., v_n) за които е в сила {v_i, v_{i+1}} е елемент на E.
+| Цикъл в граф                   | Път **p** за който v_1 = v_n се нарича цикъл. 
+| Прост път                      | Път **p** e прост ако всички елементи в редицата са уникални.
+| Дължина на път                 | Дължината на пътя е **броя на ребрата в него**.
+| Ацикличен граф                 | Граф, в който няма цикъл. Ако в графът има цикъл то той се нарича цикличен.
+| Свързан граф                   | Граф е свързан ако за всеки два върха u, v има път между u и v.
+| Силно свързани върхове         | В **ориентиран граф** казваме, че върхове u, v са силно свързани ако съществува път от u до v и от v до u
+| Силно свързан граф             | Силно свързан граф е **ориентиран** граф, за който всеки два върха са силно свързани.
+
+# Основни операции върху графи:
+Графите (като абстрактен тип данни) трябва да поддържат (част) от следните операции:  
+
+- **addVertex** - добавяне на нов връх
+- **removeVertex** - премахване на връх 
+- **addEdge** - добавяне на ново ребро 
+- **removeEdge** - премахване на ребро
+- **getSuccessors** - взимане на наследниците на връх (при ориентирани графи)
+- **getPredecessors** - взимане на предшествениците на връх (при ориентирани графи)
+- **adjacent** - взимане на съседните върхове на даден връх (при неориентирани графи)
+
+# Представяне на графи
+Графите намират огромно приложение в програмирането. Ако обаче започнем да представяме граф като множество от върхове и второ множество от двуелементни множества, това представяне би било бавно. 
+
+Ние искаме да решаваме задачи върху графи с компютър. Представете си, че върховете на графа са именувани с етикети от 0 до |V| - 1. 
+
+Наистина, няма значение как именуваме върховете, дали ще е {0, 1..., |V| - 1} дали ще е {v1, v2...} просто имаме нужда от начин, по който да се обръщаме към тях. 
+
+## Матрици на съседство
+Нека си представим булева матрица |V|x|V|. Разбрахме, се че имената на върховете са между 0 и |V| - 1. Ако има ребро между v и u то в нашата матрица това ще отбелязваме с true. Ако няма ребро го отбелязваме с false.
+
+Нека разгледаме матрицата:
+```
+{
+    {0, 1, 1},
+    {1, 0, 1},
+    {1, 1, 0}
+}
+```
+Това е точно матрицата, която представя графът от пример 1, ако си мислим за v1 = 0, v2 = 1, v3 = 2.
+
+Ако матрицата представя неориентиран граф, то тя е симетрична спрямо главния диагонал.
+
+Ако матрицата представя ориентиран граф и примерно имаме ребро от 5 към 7, но не и от 7 към 5, ще е вярно, че 
+
+```
+matrix[5][7] = true
+matrix[7][5] = false
+```
+
+Можем да представяме тегловни графи чрез матрица на съседство. Тази матрица вече няма да е булева понеже ще искаме да записваме някъде теглата на ребрата. 
+
+Може да направим матрица от тип int, в която ако matrix[i][j] = 0 нямаме ребро между i и j а в противен случай стойността на matrix[i][j] e теглото на реброто започващо от i и завършващо в j. 
+
+Но какво става ако искаме да имаме ребра с тежест 0? Тогава трябва да изберем друга стойност, която да ни представя липсата на ребро, примерно INT_MIN или INT_MAX.
+
+Предимствата на това представяне са, че можем да проверим, дали има ребро от който и да е връх до който и да е връх за константно време. Също така за линейно време за някой възел можем да вземем всички негови съседни ребра. 
+
+Проблемът е, че често това представяне заема твърде много памет (O(|V|^2)). Ако графът има твърде много върхове а твърде малко ребра, матрицата ще има много нули (така наречената разредена матрица). Така ще ни се наложи да представяме малко информация с много памет.
+
+|Операция|Сложност||
+|--|--|--|
+|addVertex|O(n)||
+|removeVertex|O(n)||
+|addEdge|O(1)|
+|removeEdge|O(1)|
+|getSuccessors|O(n)||
+|getPredecessors|O(n)||
+
+![](media/matrix.png)
+* Тук може да си мислите за A = 0, B = 1 и тн.
+
+## Списък от списъци
+Друг начин е да държим някакъв списък (или масив) от |V| списъка. Вярно е, че списъкът на позиция i съдържа всички наследници на връх i.
+
+Примерно, графът от пример 1 ще се представи по следния начин:
+
+```
+0: 1 -> 2
+1: 0 -> 2
+2: 1 -> 2
+```
+
+Сега, ако искам да видя дали има ребро между връх i и връх j това е еквивалентно на lists[i].contains(j);
+
+Тегловни графи можем да представим, като вече списъците не са от числа а от двойки (Връх, Тегло).
+
+![](media/weighted-list.png)
+* Отново, тук индексацията започва от 1. Без никакъв проблем можем да я направим да започва от 0.
+
+Предимството на тази реализация е, че бързо можем да добавяме върхове и ребра. Също така паметта ни вече не е O(|V|^2) а O(|V| + |E|).
\ No newline at end of file
diff --git a/Seminar11/bfs-dfs.cpp b/Seminar11/bfs-dfs.cpp
new file mode 100644
index 0000000..a19abcd
--- /dev/null
+++ b/Seminar11/bfs-dfs.cpp
@@ -0,0 +1,64 @@
+#include<iostream>
+#include"Graph-Impl/AdjacencyListGraph/AdjListGraph.h"
+#include"Graph-Impl/MatrixGraph/MatrixGraph.h"
+#include<queue>
+
+void BFS(const MatrixGraph& g, MatrixGraph::vertex_t start) {
+    std::vector<bool> visited(g.vertexCount(), false);
+
+    std::queue<MatrixGraph::vertex_t> q;
+
+    q.push(start);
+
+    while(!q.empty()) {
+        MatrixGraph::vertex_t current = q.front();
+        q.pop();
+
+        if(visited[current])
+            continue;
+        
+        visited[current] = true;
+
+        std::cout << current << " ";
+
+        auto successors = g.getSuccessors(current);
+
+        for(const auto& edge : successors) {
+            if(!visited[edge])
+                q.push(edge);
+        }
+    }
+}
+
+void DFSRec(std::vector<bool>& visited, const AdjListGraph& g, AdjListGraph::vertex_t start) {
+    visited[start] = true;
+
+    auto child = g.adjacent(start);
+
+    std::cout << "Visited " << start << std::endl;
+
+    for(const auto& currChild : child) {
+        if(!visited[currChild.to]) {
+            DFSRec(visited, g, currChild.to);
+        }
+    }
+}
+
+void DFS(const AdjListGraph& g, AdjListGraph::vertex_t start) {
+    std::vector<bool> visited(g.vertexCount(), false);
+    DFSRec(visited, g, start);
+}
+
+int main() {
+    MatrixGraph g(5);
+    // AdjListGraph g(5);
+    g.addEdge(0, 2, 1);
+    g.addEdge(0, 3, 1);
+    g.addEdge(0, 1, 1);
+    g.addEdge(2, 3, 1);
+    g.addEdge(1, 4, 1);
+    g.addEdge(3, 4, 1);
+    g.addEdge(1, 3, 1);
+
+    BFS(g, 0);
+}
\ No newline at end of file
diff --git a/Seminar11/media/dir-graph.png b/Seminar11/media/dir-graph.png
new file mode 100644
index 0000000..5aaefed
--- /dev/null
+++ b/Seminar11/media/dir-graph.png
diff --git a/Seminar11/media/graph.png b/Seminar11/media/graph.png
new file mode 100644
index 0000000..194cab6
--- /dev/null
+++ b/Seminar11/media/graph.png
diff --git a/Seminar11/media/matrix.png b/Seminar11/media/matrix.png
new file mode 100644
index 0000000..a2af53b
--- /dev/null
+++ b/Seminar11/media/matrix.png
diff --git a/Seminar11/media/weighted-dirscted-graph (1).png b/Seminar11/media/weighted-dirscted-graph (1).png
new file mode 100644
index 0000000..e251ebf
--- /dev/null
+++ b/Seminar11/media/weighted-dirscted-graph (1).png
diff --git a/Seminar11/media/weighted-graph.png b/Seminar11/media/weighted-graph.png
new file mode 100644
index 0000000..ed5d0b9
--- /dev/null
+++ b/Seminar11/media/weighted-graph.png
diff --git a/Seminar11/media/weighted-list.png b/Seminar11/media/weighted-list.png
new file mode 100644
index 0000000..9d795e9
--- /dev/null
+++ b/Seminar11/media/weighted-list.png
diff --git a/Seminar11/package.json b/Seminar11/package.json
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/Seminar11/package.json