Website Summary Files Commits Branches @commit @diff @stats
diff options
context:
space:
mode:
Commit00cd4d0b3541c1026a4c0f8d66d953690299178a (patch)
Author
 Stoycho Kyosev <skyosev@192.168.100.17>
2025-01-10 07:51:36 -0500
Committer
 Stoycho Kyosev <skyosev@192.168.100.17>
2025-01-10 07:51:36 -0500
Filesf5ff87b8fec65e5fe38bad2b2186d41c3a4cd0e8
Data-structures-and-algorithms-00cd4d0b3541c1026a4c0f8d66d953690299178a.tar
Data-structures-and-algorithms-00cd4d0b3541c1026a4c0f8d66d953690299178a.tar.gz
Data-structures-and-algorithms-00cd4d0b3541c1026a4c0f8d66d953690299178a.zip
Parent90b32d10c043f97b364537758e4edf610acd6bd1 (diff)
Add code for sem12
diff --git a/Seminar12/src/connected-components/count-cc.cpp b/Seminar12/src/connected-components/count-cc.cpp
new file mode 100644
index 0000000..4e2e84c
--- /dev/null
+++ b/Seminar12/src/connected-components/count-cc.cpp
@@ -0,0 +1,51 @@
+#include "../graph_impl/graph/graph.h"
+#include <iostream>
+
+void dfs_visit(const graph& g, graph::vertex_t from, std::vector<bool>& visited)
+{
+ visited[from] = true;
+
+ const auto& adjacent = g.adjacent(from);
+
+ for(const auto& vertex : adjacent)
+ {
+ if(!visited[vertex])
+ {
+ dfs_visit(g, vertex, visited);
+ }
+ }
+}
+
+size_t count_cc(const graph& g)
+{
+ std::vector<bool> visited(g.vertex_count(), false);
+ size_t cnt = 0;
+
+ for (int i = 0; i < g.vertex_count(); i++)
+ {
+ if(!visited[i])
+ {
+ ++cnt;
+ dfs_visit(g, i, visited);
+ }
+ }
+
+ return cnt;
+}
+
+int main()
+{
+ graph g(6, false);
+
+ g.add_edge(0, 1);
+ g.add_edge(0, 2);
+ g.add_edge(2, 3);
+ g.add_edge(1, 4);
+ g.add_edge(3, 5);
+ g.add_edge(4, 5);
+ g.add_edge(2, 5);
+
+ g.add_vertex();
+
+ std::cout << count_cc(g);
+} \ No newline at end of file
diff --git a/Seminar12/src/graph_impl/graph/graph.cpp b/Seminar12/src/graph_impl/graph/graph.cpp
new file mode 100644
index 0000000..b173b51
--- /dev/null
+++ b/Seminar12/src/graph_impl/graph/graph.cpp
@@ -0,0 +1,53 @@
+#include "graph.h"
+#include <stdexcept>
+
+graph::graph(size_t vertex_count, bool is_oriented) :
+ _adjacent(vertex_count),
+ _oriented(is_oriented) {}
+
+void graph::add_edge(vertex_t from, vertex_t to)
+{
+ if(from >= _adjacent.size() || to >= _adjacent.size())
+ throw std::runtime_error("Invalid vertex passed");
+
+ _adjacent[from].push_back(to);
+ if(!_oriented)
+ _adjacent[to].push_back(from);
+}
+
+void graph::add_vertex()
+{
+ _adjacent.emplace_back();
+}
+
+size_t graph::vertex_count() const
+{
+ return _adjacent.size();
+}
+
+bool graph::is_oriented() const
+{
+ return _oriented;
+}
+
+const std::vector<graph::vertex_t>& graph::adjacent(vertex_t vertex) const
+{
+ if(vertex >= _adjacent.size())
+ throw std::runtime_error("Invalid vertex passed");
+
+ return _adjacent[vertex];
+}
+
+bool graph::are_adjacent(vertex_t v1, vertex_t v2) const
+{
+ if(v1 >= _adjacent.size() || v2 >= _adjacent.size())
+ throw std::runtime_error("Invalid vertex passed");
+
+ for (const auto& v : _adjacent[v1])
+ {
+ if(v == v2)
+ return true;
+ }
+
+ return false;
+} \ No newline at end of file
diff --git a/Seminar12/src/graph_impl/graph/graph.h b/Seminar12/src/graph_impl/graph/graph.h
new file mode 100644
index 0000000..fc1eb31
--- /dev/null
+++ b/Seminar12/src/graph_impl/graph/graph.h
@@ -0,0 +1,23 @@
+#pragma once
+#include <vector>
+
+class graph
+{
+public:
+ using vertex_t = int;
+private:
+ std::vector<std::vector<vertex_t>> _adjacent;
+ bool _oriented;
+
+public:
+ graph(size_t vertex_count, bool is_oriented);
+
+ void add_edge(vertex_t from, vertex_t to);
+ void add_vertex();
+
+ size_t vertex_count() const;
+ bool is_oriented() const;
+
+ const std::vector<vertex_t>& adjacent(vertex_t vertex) const;
+ bool are_adjacent(vertex_t v1, vertex_t v2) const;
+}; \ No newline at end of file
diff --git a/Seminar12/src/graph_impl/weighted_graph/weighted_graph.cpp b/Seminar12/src/graph_impl/weighted_graph/weighted_graph.cpp
new file mode 100644
index 0000000..99edd6a
--- /dev/null
+++ b/Seminar12/src/graph_impl/weighted_graph/weighted_graph.cpp
@@ -0,0 +1,71 @@
+#include "weighted_graph.h"
+#include <stdexcept>
+
+weighted_graph::weighted_graph(size_t vertex_count, bool is_oriented) :
+ _adjacent(vertex_count),
+ _oriented(is_oriented) {}
+
+void weighted_graph::add_edge(vertex_index_t from, vertex_index_t to, weight_t weight)
+{
+ if(from >= _adjacent.size() || to >= _adjacent.size())
+ throw std::runtime_error("Invalid vertex passed");
+
+ _adjacent[from].push_back(std::make_pair(to, weight));
+ if(!_oriented)
+ _adjacent[to].push_back(std::make_pair(from, weight));
+}
+
+void weighted_graph::add_vertex()
+{
+ _adjacent.emplace_back();
+}
+
+size_t weighted_graph::vertex_count() const
+{
+ return _adjacent.size();
+}
+
+bool weighted_graph::is_oriented() const
+{
+ return _oriented;
+}
+
+const std::vector<weighted_graph::vertex_t>& weighted_graph::adjacent(vertex_index_t vertex) const
+{
+ if(vertex >= _adjacent.size())
+ throw std::runtime_error("Invalid vertex passed");
+
+ return _adjacent[vertex];
+}
+
+bool weighted_graph::are_adjacent(vertex_index_t v1, vertex_index_t v2) const
+{
+ if(v1 >= _adjacent.size() || v2 >= _adjacent.size())
+ throw std::runtime_error("Invalid vertex passed");
+
+ for (const auto& v : _adjacent[v1])
+ {
+ if(v.first == v2)
+ return true;
+ }
+
+ return false;
+}
+
+weighted_graph::weight_t weighted_graph::get_weight(vertex_index_t from, vertex_index_t to) const
+{
+ if(from >= _adjacent.size() || to >= _adjacent.size())
+ throw std::runtime_error("Invalid vertex passed");
+
+
+ for(const auto& vertex : _adjacent[from])
+ {
+ if(vertex.first == to)
+ {
+ return vertex.second;
+ }
+ }
+
+ // TODO: This is ugly, maybe use another invaid edge error handling machanism?
+ throw std::runtime_error("No such edge found!");
+}
diff --git a/Seminar12/src/graph_impl/weighted_graph/weighted_graph.h b/Seminar12/src/graph_impl/weighted_graph/weighted_graph.h
new file mode 100644
index 0000000..77cd6fe
--- /dev/null
+++ b/Seminar12/src/graph_impl/weighted_graph/weighted_graph.h
@@ -0,0 +1,32 @@
+/*
+ A simplistic representation of weighted graph represented by adjacency list.
+*/
+
+#pragma once
+#include <vector>
+
+class weighted_graph
+{
+public:
+ using weight_t = int; // Type used to represent weight.
+ using vertex_index_t = int; // Type used to represent how we index a vertex.
+ using vertex_t = std::pair<vertex_index_t, weight_t>; // Type used to represent a vertex.
+
+private:
+ std::vector<std::vector<vertex_t>> _adjacent;
+ bool _oriented;
+
+public:
+ weighted_graph(size_t vertex_count, bool is_oriented);
+
+ void add_edge(vertex_index_t from, vertex_index_t to, weight_t weight);
+ void add_vertex();
+
+ size_t vertex_count() const;
+ bool is_oriented() const;
+
+ const std::vector<vertex_t>& adjacent(vertex_index_t vertex) const;
+ bool are_adjacent(vertex_index_t v1, vertex_index_t v2) const;
+
+ weight_t get_weight(vertex_index_t from, vertex_index_t to) const;
+}; \ No newline at end of file
diff --git a/Seminar12/src/shortest_paths/shp_no_wight.cpp b/Seminar12/src/shortest_paths/shp_no_wight.cpp
new file mode 100644
index 0000000..a05e517
--- /dev/null
+++ b/Seminar12/src/shortest_paths/shp_no_wight.cpp
@@ -0,0 +1,82 @@
+#include "../graph_impl/graph/graph.h"
+#include <queue>
+#include <unordered_map>
+#include <iostream>
+#include <algorithm>
+
+using vertex_t = graph::vertex_t;
+
+std::vector<vertex_t> shortest_path(const graph& g, vertex_t from, vertex_t to)
+{
+ std::queue<vertex_t> q;
+ q.push(from);
+
+ std::unordered_map<vertex_t, vertex_t> parent;
+ bool found_path = false;
+
+ while(!q.empty() && !found_path)
+ {
+ vertex_t current = q.front();
+ q.pop();
+
+ if(current == to)
+ {
+ found_path = true;
+ continue;
+ }
+
+ const auto& adjacent = g.adjacent(current);
+
+ for(const auto& vertex : adjacent)
+ {
+ if(parent.find(vertex) == parent.end())
+ {
+ // This means the vertex is yet to be visited...
+ q.push(vertex);
+ parent[vertex] = current;
+ }
+ }
+ }
+
+ if(!found_path)
+ return {};
+
+ std::vector<vertex_t> path;
+ vertex_t it = to;
+
+ while (true)
+ {
+ auto child_it = parent.find(it);
+
+ if(child_it == parent.end())
+ break;
+
+ path.push_back(it);
+ it = child_it->second;
+ }
+
+ path.push_back(from);
+ std::reverse(path.begin(), path.end());
+
+ return path;
+}
+
+int main()
+{
+ graph g(6, false);
+
+ g.add_edge(0, 1);
+ g.add_edge(0, 2);
+ g.add_edge(1, 2);
+ g.add_edge(1, 3);
+ g.add_edge(2, 4);
+ g.add_edge(3, 4);
+ g.add_edge(4, 5);
+
+ auto path = shortest_path(g, 0, 5);
+
+ for(auto vertex : path)
+ {
+ std::cout << vertex << " ";
+ }
+} \ No newline at end of file
diff --git a/Seminar12/src/shortest_paths/shp_weighted.cpp b/Seminar12/src/shortest_paths/shp_weighted.cpp
new file mode 100644
index 0000000..66c06f6
--- /dev/null
+++ b/Seminar12/src/shortest_paths/shp_weighted.cpp
@@ -0,0 +1,128 @@
+#include "../graph_impl/weighted_graph/weighted_graph.h"
+#include <algorithm>
+#include <climits>
+#include <iostream>
+#include <queue>
+#include <unordered_map>
+
+using vertex_t = weighted_graph::vertex_t;
+using vertex_index_t = weighted_graph::vertex_index_t;
+using weight_t = weighted_graph::weight_t;
+
+// A structure representind information which we
+// obtained using dijkstra's algorithm
+struct shp_info
+{
+ std::vector<vertex_index_t> path;
+ size_t cost = 0;
+};
+
+bool relax(std::vector<int>& distance,
+ const weighted_graph& g,
+ vertex_index_t reached,
+ vertex_index_t current_vertex)
+{
+ if (distance[reached] > distance[current_vertex] + g.get_weight(current_vertex, reached))
+ {
+ distance[reached] = distance[current_vertex] + g.get_weight(current_vertex, reached);
+ return true;
+ }
+ return false;
+}
+
+shp_info dijkstra_shortest_path(const weighted_graph& g, vertex_index_t from, vertex_index_t to)
+{
+ std::vector<int> distances(g.vertex_count(), INT_MAX);
+ std::vector<vertex_index_t> parent(g.vertex_count(), -1);
+
+ struct vertex_comparator
+ {
+ bool operator()(const vertex_t& lhs, const vertex_t& rhs) const
+ {
+ return lhs.second > rhs.second;
+ }
+ };
+
+ std::priority_queue<vertex_t, std::vector<vertex_t>, vertex_comparator> q;
+
+ q.push({from, 0});
+ distances[from] = 0;
+ bool found_path = false;
+
+ while(!q.empty() && !found_path)
+ {
+ auto current_vertex = q.top();
+ q.pop();
+
+ if (current_vertex.first == to)
+ {
+ found_path = true;
+ continue;
+ }
+
+ const auto& adjacent = g.adjacent(current_vertex.first);
+
+ for(const auto& vertex : adjacent)
+ {
+ if(relax(distances, g, vertex.first, current_vertex.first))
+ {
+ q.push({vertex.first, distances[vertex.first]});
+ parent[vertex.first] = current_vertex.first;
+ }
+ }
+ }
+
+ shp_info result;
+
+ if(!found_path)
+ return result;
+
+ vertex_index_t it = to;
+ while (true)
+ {
+ vertex_index_t it_parent = parent[it];
+ result.path.push_back(it);
+ it = it_parent;
+
+ if(it_parent == -1)
+ {
+ break;
+ }
+ }
+
+ result.cost = distances[to];
+ std::reverse(result.path.begin(), result.path.end());
+
+ return result;
+}
+
+int main()
+{
+ weighted_graph g(6, false);
+ g.add_edge(0, 1, 2);
+ g.add_edge(0, 2, 1);
+ g.add_edge(2, 3, 6);
+ g.add_edge(1, 4, 3);
+ g.add_edge(3, 5, 1);
+ g.add_edge(4, 5, 2);
+ g.add_edge(2, 5, 4);
+
+ auto result = dijkstra_shortest_path(g, 0, 5);
+
+ if (result.path.empty())
+ {
+ std::cout << "No path found from 0 to 5.\n";
+ }
+ else
+ {
+ std::cout << "Shortest path cost: " << result.cost << "\n";
+ std::cout << "Path: ";
+ for (int vertex : result.path)
+ {
+ std::cout << vertex << " ";
+ }
+ std::cout << "\n";
+ }
+
+ return 0;
+} \ No newline at end of file
diff --git a/Seminar12/src/topological_sort/toposort.cpp b/Seminar12/src/topological_sort/toposort.cpp
new file mode 100644
index 0000000..c51ed93
--- /dev/null
+++ b/Seminar12/src/topological_sort/toposort.cpp
@@ -0,0 +1,98 @@
+#include "../graph_impl/graph/graph.h"
+#include <algorithm>
+
+using vertex_t = graph::vertex_t;
+
+void tsort_visit(const graph& g,
+ vertex_t vertex,
+ std::vector<bool>& visited,
+ std::vector<vertex_t>& result)
+{
+ visited[vertex] = true;
+
+ const auto& adjacent = g.adjacent(vertex);
+
+ for (const auto& v : adjacent)
+ {
+ if(!visited[v])
+ {
+ tsort_visit(g, v, visited, result);
+ }
+ }
+
+ result.push_back(vertex);
+}
+
+std::vector<vertex_t> topological_sort(const graph& g)
+{
+ std::vector<bool> visited(g.vertex_count(), false);
+ std::vector<vertex_t> result(g.vertex_count());
+
+ for (int i = 0; i < g.vertex_count(); i++)
+ {
+ if(!visited[i])
+ tsort_visit(g, i, visited, result);
+ }
+
+ std::reverse(result.begin(), result.end());
+
+ return result;
+}
+
+void tsort_visit_dummy(const graph& g,
+ vertex_t vertex,
+ std::vector<int>& finalized,
+ std::vector<bool>& visited,
+ int& time)
+{
+ visited[vertex] = true;
+
+ const auto& adjacent = g.adjacent(vertex);
+
+ for (const auto& v : adjacent)
+ {
+ if(!visited[v])
+ {
+ tsort_visit_dummy(g, v, finalized, visited, time);
+ }
+ }
+
+ finalized[vertex] = time++;
+}
+
+std::vector<vertex_t> topological_sort_dummy(const graph& g)
+{
+ std::vector<int> finalized(g.vertex_count(), -1);
+ std::vector<bool> visited(g.vertex_count(), false);
+ int time = 0;
+
+ // Подобно обхождане е лошо, но върши работа за примера.
+ // Трябва да се имплементира итератор
+ // за вектора в противен случай разчитаме върховете да са числа...
+ for (int i = 0; i < g.vertex_count(); i++)
+ {
+ if(!visited[i])
+ tsort_visit_dummy(g, i, finalized, visited, time);
+ }
+
+ std::vector<vertex_t> result(g.vertex_count());
+
+ for (size_t i = 0; i < g.vertex_count(); i++)
+ {
+ result[i] = i;
+ }
+
+ std::sort(result.begin(),
+ result.end(),
+ [&finalized](const vertex_t& lhs, const vertex_t& rhs)
+ {
+ return finalized[lhs] < finalized[rhs];
+ });
+
+ return result;
+}
+
+int main()
+{
+
+} \ No newline at end of file