diff options
Add code for sem12
8 files changed, 538 insertions, 0 deletions
| -rw-r--r-- | Seminar12/src/connected-components/count-cc.cpp | 51 | ||||
| -rw-r--r-- | Seminar12/src/graph_impl/graph/graph.cpp | 53 | ||||
| -rw-r--r-- | Seminar12/src/graph_impl/graph/graph.h | 23 | ||||
| -rw-r--r-- | Seminar12/src/graph_impl/weighted_graph/weighted_graph.cpp | 71 | ||||
| -rw-r--r-- | Seminar12/src/graph_impl/weighted_graph/weighted_graph.h | 32 | ||||
| -rw-r--r-- | Seminar12/src/shortest_paths/shp_no_wight.cpp | 82 | ||||
| -rw-r--r-- | Seminar12/src/shortest_paths/shp_weighted.cpp | 128 | ||||
| -rw-r--r-- | Seminar12/src/topological_sort/toposort.cpp | 98 |
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 |
