Add code for sem12

4 files changed, 179 insertions, 0 deletions

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