From 61d9117e1f9b771bd91ddd89acbcd21c35977d8e Mon Sep 17 00:00:00 2001
From: Tomas Mlcoch <xtojaj@gmail.com>
Date: Tue, 11 Feb 2014 22:45:40 +0100
Subject: [PATCH] deltarepo: Implemented Dijkstra's algorithm.

---
 deltarepo/deltarepo/updater_common.py  | 62 ++++++++++++++++++++++++++++++++--
 deltarepo/tests/test_updater_common.py |  2 +-
 2 files changed, 60 insertions(+), 4 deletions(-)

diff --git a/deltarepo/deltarepo/updater_common.py b/deltarepo/deltarepo/updater_common.py
index d119699..24add58 100644
--- a/deltarepo/deltarepo/updater_common.py
+++ b/deltarepo/deltarepo/updater_common.py
@@ -285,9 +285,65 @@ class Solver(LoggingInterface):
         if not target_node:
             raise DeltaRepoError("Target repo ({0}) not available".format(self.target_ch))
 
-        # TODO: Implement Dijkstra's algorithm here
-
-        pass
+        # Dijkstra's algorithm
+        # http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
+        dist = {}       # Distance
+        previous = {}   # Predecessor
+        Q = []
+
+        for _, node in graph.nodes.items():
+            dist[node] = -1 # -1 Stands for infinity here
+            previous[node] = None
+            Q.append(node)
+
+        dist[source_node] = 0
+
+        while Q:
+            u = None
+            val = -1
+            # Select node from Q with the smallest distance in dist
+            for node in Q:
+                if dist[node] == -1:
+                    continue
+                if val == -1 or dist[node] < val:
+                    val = dist[node]
+                    u = node
+
+            if u:
+                # Remove the u from the queue
+                Q.remove(u)
+            else:
+                # All remaining nodes are inaccessible from source
+                break
+
+            if u == target_node:
+                # Cool!
+                break
+
+            # Iterate over the u neighbors
+            for v, link in u.targets.items():
+                alt = dist[u] + link.cost()
+                if alt < dist[v] or dist[v] == -1:
+                    dist[v] = alt
+                    previous[v] = u
+
+        # At this point we have previous and dist filled
+        import pprint
+        print
+        pprint.pprint(previous)
+        print
+        pprint.pprint(dist)
+
+        resolved_path = []
+        u = target_node
+        while previous[u] is not None:
+            resolved_path.append(previous[u])
+            u = previous[u]
+
+        resolved_path.reverse()
+
+        print "xxxx"
+        pprint.pprint(resolved_path)
 
 class DRUpdater(object):
 
diff --git a/deltarepo/tests/test_updater_common.py b/deltarepo/tests/test_updater_common.py
index 1342ca0..c3f9a64 100644
--- a/deltarepo/tests/test_updater_common.py
+++ b/deltarepo/tests/test_updater_common.py
@@ -96,5 +96,5 @@ class TestCaseSolver(unittest.TestCase):
         links.append(TestCaseSolver.LinkMock("bbb", "ccc"))
 
         logger = logging.getLogger("testloger")
-        solver = Solver(links, "aaa", "bbb", logger=logger)
+        solver = Solver(links, "aaa", "ccc", logger=logger)
         solver.solve()
\ No newline at end of file
-- 
2.7.4