Repository: keon/algorithms (python)

Issue:
Add Dijkastra's Algorithm
Dijkastra's algorithm python implementation is missing

Pull request:
Added dijkstra test and missing link from documentation
(Put an `X` inside the `[ ]` to denote check mark `[X]`.)


- [ ] **If creating a new file :**
  - [ ] added links to it in the README files ?
  - [ ] included tests with it ?
  - [ ] added description (overview of algorithm, time and space complexity, and possible edge case) in docstrings ?

- [X] **if done some changes :**
  - [X] wrote short description in the PR explaining what the changes do ?
  - [X] Fixes #559

- [ ] **other**


Patch:
diff --git a/README.md b/README.md
index 4b67fe5..1e00297 100644
--- a/README.md
+++ b/README.md
@@ -116,6 +116,7 @@ If you want to uninstall algorithms, it is as simple as:
 - [compression](algorithms/compression)
     - [huffman_coding](algorithms/compression/huffman_coding.py)
     - [rle_compression](algorithms/compression/rle_compression.py)
+    - [elias](algorithms/compression/elias.py)
 - [dfs](algorithms/dfs)
     - [all_factors](algorithms/dfs/all_factors.py)
     - [count_islands](algorithms/dfs/count_islands.py)
@@ -150,6 +151,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [find_all_cliques](algorithms/graph/find_all_cliques.py)
     - [find_path](algorithms/graph/find_path.py)
     - [graph](algorithms/graph/graph.py)
+    - [dijkstra](algorithms/graph/dijkstra.py)
     - [markov_chain](algorithms/graph/markov_chain.py)
     - [minimum_spanning_tree](algorithms/graph/minimum_spanning_tree.py)
     - [satisfiability](algorithms/graph/satisfiability.py)
diff --git a/algorithms/compression/elias.py b/algorithms/compression/elias.py
new file mode 100644
index 0000000..bdeb7fd
--- /dev/null
+++ b/algorithms/compression/elias.py
@@ -0,0 +1,49 @@
+"""
+Elias γ code or Elias gamma code is a universal code encoding positive integers.
+It is used most commonly when coding integers whose upper-bound cannot be determined beforehand.
+Elias δ code or Elias delta code is a universal code encoding the positive integers,
+that includes Elias γ code when calculating.
+Both were developed by Peter Elias.
+
+"""
+from math import log,ceil
+
+log2 = lambda x: log(x,2)
+
+# Calculates the binary number
+def binary(x,l=1):
+	fmt = '{0:0%db}' % l
+	return fmt.format(x)
+
+# Calculates the unary number
+def unary(x):
+	return (x-1)*'1'+'0'
+
+def elias_generic(lencoding, x):
+	"""
+	The compressed data is calculated in two parts. 
+	The first part is the unary number of 1 + ⌊log2(x)⌋. 
+	The second part is the binary number of x - 2^(⌊log2(x)⌋).
+	For the final result we add these two parts.
+	"""
+	if x == 0: return '0'
+	
+	first_part = 1 + int(log2(x))
+	
+	a = x - 2**(int(log2(x)))
+	
+	k = int(log2(x))
+
+	return lencoding(first_part) + binary(a,k)
+
+def elias_gamma(x):
+	"""
+	For the first part we put the unary number of x.
+	"""
+	return elias_generic(unary, x)
+
+def elias_delta(x):
+	"""
+	For the first part we put the elias_g of the number.
+	"""
+	return elias_generic(elias_gamma,x)
diff --git a/algorithms/graph/dijkstra.py b/algorithms/graph/dijkstra.py
index fe5772e..2cf0430 100644
--- a/algorithms/graph/dijkstra.py
+++ b/algorithms/graph/dijkstra.py
@@ -1,6 +1,6 @@
 #Dijkstra's single source shortest path algorithm
 
-class Graph():
+class Dijkstra():
 
     def __init__(self, vertices):
         self.vertices = vertices


Test patch:
diff --git a/tests/test_compression.py b/tests/test_compression.py
index 144d944..cd41283 100644
--- a/tests/test_compression.py
+++ b/tests/test_compression.py
@@ -1,5 +1,6 @@
 from algorithms.compression.huffman_coding import HuffmanCoding
 from algorithms.compression.rle_compression import (decode_rle, encode_rle)
+from algorithms.compression.elias import (elias_gamma, elias_delta)
 
 import unittest
 
@@ -44,6 +45,25 @@ class TestRLECompression(unittest.TestCase):
         self.assertEqual('WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW', 
             decode_rle('12W1B12W3B24W1B14W'))
 
+class TestEliasCoding(unittest.TestCase):
+
+    def test_elias_gamma(self):
+        correct_result = ['0', '00', '100', '101', '11000', '11001', '11010', '11011', '1110000', '1110001', '1110010']
+        
+        result = []
+        for i in range(11):	
+            result.append(elias_gamma(i))
+
+        self.assertEqual(correct_result, result)
+
+    def test_elias_delta(self):
+        correct_result = ['0', '000', '1000', '1001', '10100', '10101', '10110', '10111', '11000000', '11000001', '11000010']
+
+        result = []
+        for i in range(11):	
+            result.append(elias_delta(i))
+
+        self.assertEqual(correct_result, result)        
 
 if __name__ == "__main__":
     unittest.main()
diff --git a/tests/test_graph.py b/tests/test_graph.py
index d402b86..893ea77 100644
--- a/tests/test_graph.py
+++ b/tests/test_graph.py
@@ -1,5 +1,6 @@
 from algorithms.graph import Tarjan
 from algorithms.graph import check_bipartite
+from algorithms.graph.dijkstra import Dijkstra
 
 import unittest
 
@@ -57,3 +58,20 @@ class TestCheckBipartite(unittest.TestCase):
         
         adj_list_3 = [[0, 1, 0, 0], [1, 0, 1, 1], [0, 1, 0, 1], [0, 1, 1, 0]]
         self.assertEqual(False, check_bipartite(adj_list_3))
+
+class TestDijkstra(unittest.TestCase):
+    
+    def test_dijkstra(self):
+        g = Dijkstra(9) 
+        g.graph = [[0, 4, 0, 0, 0, 0, 0, 8, 0], 
+           [4, 0, 8, 0, 0, 0, 0, 11, 0], 
+           [0, 8, 0, 7, 0, 4, 0, 0, 2], 
+           [0, 0, 7, 0, 9, 14, 0, 0, 0], 
+           [0, 0, 0, 9, 0, 10, 0, 0, 0], 
+           [0, 0, 4, 14, 10, 0, 2, 0, 0], 
+           [0, 0, 0, 0, 0, 2, 0, 1, 6], 
+           [8, 11, 0, 0, 0, 0, 1, 0, 7], 
+           [0, 0, 2, 0, 0, 0, 6, 7, 0] 
+          ]; 
+
+        self.assertEqual(g.dijkstra(0), [0, 4, 12, 19, 21, 11, 9, 8, 14]);
\ No newline at end of file