omega

1 files changed, 37 insertions, 9 deletions

diff --git a/test_dijkstra.py b/test_dijkstra.py
index a0f315c..f906b59 100644
--- a/test_dijkstra.py
+++ b/test_dijkstra.py
@@ -1,21 +1,49 @@
-import notebooks.Graph as Graph 
 from collections import defaultdict
 from heapq import heappush, heappop
 import math
 
 def dijkstra(adjacency_list, source_id, target_id):
-    """ To be implemented by students. `adjacency_list` is a dictionary with structure: 
+    """ To be implemented by students (optional exercise). `adjacency_list` is a dictionary with structure: 
     {node_id: [...(neighbor_id, weight)]}.
     Function should return (distance, path). Path should be a list of the nodes in the shortest path
-    **including** the source_id and target_id. If no shortest path is found, it should return (infinity, []) """
-    
-    return math.inf, [source_id]
+    **including** the source_id and target_id. If no shortest path is found, it should return (float('inf'), []) """
+    return float('inf'), []
 
 
 if __name__ == '__main__':
+    file = open('data/dijkstra.test') # Feel free to add your own test cases to the file!
+    testcase = 0
     try:
-        Graph.test_dijkstra(dijkstra)
-        print('Passed ALL tests!')
+        while True:
+            num_nodes = file.readline()
+            if num_nodes[0] == '#':
+                continue 
+            testcase += 1
+            num_nodes = int(num_nodes)
+            source, target = map(int, file.readline().split())
+            nodes = []
+            for n in range(num_nodes):
+                x, y = map(float, file.readline().split())
+                nodes.append((x, y))
+            adjacency_list = defaultdict(list)
+            num_edges = int(file.readline())
+            for m in range(num_edges):
+                v1, v2 = map(int, file.readline().split())
+                x1, y1 = nodes[v1]
+                x2, y2 = nodes[v2]
+                weight = math.hypot(x2-x1, y2-y1) # Get distance between the nodes
+                adjacency_list[v1].append((v2, weight))
+                adjacency_list[v2].append((v1, weight))
+            correct_dist = float(file.readline())
+            correct_path = [int(v) for v in file.readline().split()]
+            dist, path = dijkstra(adjacency_list, source, target)
+            assert abs(correct_dist-dist) < 1e-3
+            assert correct_path == path
+            print("Passed test case {}".format(testcase))
     except AssertionError:
-        print('Failed one or more tests')
-
+        print("Failed test case {}".format(testcase))
+    except IndexError:
+        print('Passed all test cases')
+    except EOFError:
+        print('Passed all test cases')
+