Started on Dijkstra

okkevaneck · Nov 20, 2022 · bda9648 · bda9648
1 parent c360c34
commit bda9648
Show file tree

Hide file tree

Showing 6 changed files with 57 additions and 18 deletions.
diff --git a/archives/prospr_core.tar.gz b/archives/prospr_core.tar.gz
diff --git a/archives/prospr_core.zip b/archives/prospr_core.zip
diff --git a/prospr/core/src/dijkstra.cpp b/prospr/core/src/dijkstra.cpp
@@ -5,7 +5,7 @@
  *                  specifics.
  */
 
-#include "breadth_first.hpp"
+#include "dijkstra.hpp"
 #include <queue>
 #include <iostream>
 
@@ -22,6 +22,27 @@ struct Conformation {
         this->length = length;
         this->hash = hash;
     }
+
+    /* Create and return vector of children Conformations. */
+    std::vector<Conformation> create_children(Protein* protein) {
+        std::vector<Conformation> children;
+        std::vector<int> moves = {-2, -1, 1, 2};
+        protein->set_hash(this->hash);
+
+        for (int m : moves) {
+            /* Only add valid conformations to list of children. */
+            if (protein->is_valid(m)) {
+                protein->place_amino(m);
+
+                Conformation conf = Conformation(protein->get_score(), protein->get_cur_len(), protein->hash_fold());
+                children.push_back(conf);
+
+                protein->remove_amino();
+            }
+        }
+
+        return children;
+    }
 };
 
 
@@ -37,8 +58,9 @@ bool operator>(const struct Conformation& conf1, const struct Conformation& conf
 std::ostream &operator<<(std::ostream &os, const Conformation& conf) {
     std::cout << "<" << conf.score << ", " << conf.length << ", [";
 
-    for (int i: conf.hash)
+    for (int i: conf.hash) {
         std::cout << i << ", ";
+    }
 
     std::cout << "]>";
     return os;
@@ -47,18 +69,35 @@ std::ostream &operator<<(std::ostream &os, const Conformation& conf) {
 
 /* A breadth-first search function for finding a minimum energy conformation. */
 Protein* dijkstra(Protein* protein) {
+    /* Make priority queue and set initial conformation as only node. */
     std::priority_queue<Conformation, std::vector<Conformation>, std::greater<Conformation>> prioq;
+    Conformation conf = Conformation(0, 1, std::vector<int>{});
+    prioq.push(conf);
 
-    prioq.push(Conformation(-1, 2, std::vector<int>{1,1,2,2,2}));
-    prioq.push(Conformation(-1, 3, std::vector<int>{1,1,-1,2,2}));
-    prioq.push(Conformation(-1, 1, std::vector<int>{1,2,2,2,2}));
-    prioq.push(Conformation(-2, 2, std::vector<int>{1,-1,2,2,2}));
-    prioq.push(Conformation(-1, 3, std::vector<int>{1,1,-1,2,2}));
-
-    while (! prioq.empty() ) {
-        std::cout << prioq.top() << "\n";
+    /* Fetch shortest path while the queue is not empty. */
+    while (!prioq.empty()) {
+        conf = prioq.top();
         prioq.pop();
+
+        /* Create children of current conformation and add to queue. */
+        std::vector<Conformation> children = conf.create_children(protein);
+        for (Conformation c : children) {
+            std::cout << c << "\n";
+        }
     }
 
+
+
+//    prioq.push(Conformation(-1, 2, std::vector<int>{1,1,2,2,2}));
+//    prioq.push(Conformation(-1, 3, std::vector<int>{1,1,-1,2,2}));
+//    prioq.push(Conformation(-1, 1, std::vector<int>{1,2,2,2,2}));
+//    prioq.push(Conformation(-2, 2, std::vector<int>{1,-1,2,2,2}));
+//    prioq.push(Conformation(-1, 3, std::vector<int>{1,1,-1,2,2}));
+
+//    while (! prioq.empty() ) {
+//        std::cout << prioq.top() << "\n";
+//        prioq.pop();
+//    }
+
     return protein;
 }
diff --git a/prospr/core/src/protein.cpp b/prospr/core/src/protein.cpp
@@ -183,7 +183,7 @@ void Protein::reset() {
     last_move = 0;
     score = 0;
     solutions_checked = 0;
-    aminos_placed = 0;
+    aminos_placed = 1;
 
     space[last_pos] = amino_acids[0];
 }

diff --git a/prospr/core/tests/test_algorithms b/prospr/core/tests/test_algorithms
diff --git a/prospr/core/tests/test_algorithms.cpp b/prospr/core/tests/test_algorithms.cpp
@@ -13,7 +13,7 @@
 #include "../src/protein.hpp"
 #include "../src/depth_first.hpp"
 #include "../src/depth_first_bnb.hpp"
-#include "../src/breadth_first.hpp"
+#include "../src/dijkstra.hpp"
 
 
 /* Test functionality of depth_first. */
@@ -47,16 +47,16 @@ void test_depth_first_bnb() {
 }
 
 /* Test functionality of depth_first_bnb. */
-void test_breadth_first() {
+void test_dijkstra() {
     /* Check if 2D solutions are found correctly. */
     Protein* protein = new Protein("PHPHPHPPH", 2, "HP");
-    protein = breadth_first(protein);
+    protein = dijkstra(protein);
     assert (protein->get_score() == -3);
     std::cout << "\t2D Protein solution scores matches.\n";
 
     /* Check if 3D solutions are found correctly. */
     protein = new Protein("HPPHPHPHPH", 3, "HP");
-    protein = breadth_first(protein);
+    protein = dijkstra(protein);
     assert (protein->get_score() == -4);
     std::cout << "\t3D Protein solution scores matches.\n";
 }
@@ -65,7 +65,7 @@ void test_breadth_first() {
 void run_all() {
     test_depth_first();
     test_depth_first_bnb();
-    test_breadth_first();
+    test_dijkstra();
 }
 
 int main(int argc, char* argv[]) {
@@ -78,8 +78,8 @@ int main(int argc, char* argv[]) {
         test_depth_first();
     } else if (strcmp(argv[1], "depth_first_bnb") == 0) {
         test_depth_first_bnb();
-    } else if (strcmp(argv[1], "breadth_first") == 0) {
-        test_breadth_first();
+    } else if (strcmp(argv[1], "dijkstra") == 0) {
+        test_dijkstra();
     } else {
         std::cout << "\tSpecific algorithm not detected..\n";
     }