Repository: UTSAVS26/PySnippets

Issue:
[Feature Request]: Add searching, greedy and dynamic programming algorithms.
### Is there an existing issue for this?

- [X] I have searched the existing issues

### Feature Description

I would like to request the addition of two searching algorithms: Depth First Search (DFS) & Breadth First Search (BFS), two greedy algorithms: Dijkstra's and Prim's Algorithm and one dynamic programming algorithm: Fibonacci Sequence. 

Please assign this issue to me.

### Record

- [X] I agree to follow this project's Code of Conduct
- [X] I want to work on this issue
- [X] I'm willing to provide further clarification or assistance if needed.

### Full Name

Rishika Hazarika

### Participant Role

Contributor @ GSSoC'24 Extd.

Discussion:

Patch:
diff --git a/pysnippets/algorithms/breadth_first_search.py b/pysnippets/algorithms/breadth_first_search.py
new file mode 100644
index 0000000..ed4fa67
--- /dev/null
+++ b/pysnippets/algorithms/breadth_first_search.py
@@ -0,0 +1,50 @@
+from collections import deque
+
+def bfs(graph, start):
+  """
+  Performs Breadth First Search (BFS) traversal on a graph.
+
+  Args:
+      graph (dict): The adjaceny list representing the graph.
+      start (str): The starting node for BFS traversal.
+
+  Returns:
+      None: Prints nodes in BFS order during traversal.
+
+  Example:
+      >>> graph = {
+      ... 'A': ['B', 'C'],
+      ... 'B': ['D', 'E'],
+      ... 'C': ['F'],
+      ... 'D': [],
+      ... 'E': ['F'],
+      ... 'F': []
+      ... }
+      >>> bfs(graph, 'A')
+      A B C D E F
+  """
+  visited = set()
+  queue = deque([start])
+
+  visited.add(start)
+
+  while queue:
+    vertex = queue.popleft()
+    print(vertex, end=' ')
+
+    for neighbor in graph[vertex]:
+      if neighbor not in visited:
+        visited.add(neighbor)
+        queue.append(neighbor)
+
+# Example usage
+if __name__ == "__main__":
+    graph = {
+        'A': ['B', 'C'],
+        'B': ['D', 'E'],
+        'C': ['F'],
+        'D': [],
+        'E': ['F'],
+        'F': []
+    }
+    bfs(graph, 'A') # Output: A B C D E F
diff --git a/pysnippets/algorithms/depth_first_search.py b/pysnippets/algorithms/depth_first_search.py
new file mode 100644
index 0000000..74de497
--- /dev/null
+++ b/pysnippets/algorithms/depth_first_search.py
@@ -0,0 +1,45 @@
+def dfs(graph, start, visited=None):
+  """
+  Performs Depth First Search (DFS) traversal on a graph.
+
+  Args:
+     graph (dict): The adjacency list representing the graph.
+     start (str): The starting node for DFS traversal.
+     visited (set): Keeps track of visited nodes to avoid cycles (default is None).
+
+  Returns:
+     None: Prints nodes in DFS order during traversal.
+
+  Example:
+     >>> graph = {
+     ... 'A': ['B', 'C'],
+     ... 'B': ['D', 'E'],
+     ... 'C': ['F'],
+     ... 'D': [],
+     ... 'E': ['F'],
+     ... 'F': [],
+     ... }
+     >>> dfs(graph, 'A')
+     A B D E F C
+  """
+  if visited is None:
+    visited = set()
+
+  visited.add(start)
+  print(start, end=' ')
+
+  for neighbor in graph[start]:
+    if neighbor not in visited:
+      dfs(graph, neighbor, visited)
+
+# Example usage
+if __name__ == "__main__":
+  graph = {
+    'A': ['B', 'C'],
+    'B': ['D', 'E'],
+    'C': ['F'],
+    'D': [],
+    'E': ['F'],
+    'F': []
+  }
+  dfs(graph, 'A') # Output: A B D E F C
diff --git a/pysnippets/algorithms/dijkstra.py b/pysnippets/algorithms/dijkstra.py
new file mode 100644
index 0000000..a5d29ab
--- /dev/null
+++ b/pysnippets/algorithms/dijkstra.py
@@ -0,0 +1,47 @@
+import heapq
+
+def dijkstra(graph, start):
+    """
+    Performs Dijkstra's algorithm to find the shortest path from the start node to all other nodes.
+
+    Args:
+        graph (dict): The graph represented as an adjacency list where keys are nodes, and values are lists of tuples (neighbor, weight).
+        start (str): The starting node for the algorithm.
+
+    Returns:
+        dict: A dictionary where keys are nodes and values are the shortest distances from the start node.
+
+    Example:
+        >>> graph = {
+        ... 'A': [('B', 1), ('C', 4)],
+        ... 'B': [('C', 2), ('D', 5)],
+        ... 'C': [('D', 1)],
+        ... 'D': []
+        ... }
+        >>> dijkstra(graph, 'A')
+        {'A': 0, 'B': 1, 'C': 3, 'D': 4}
+    """
+    priority_queue = [(0, start)]
+    distances = {start: 0}
+
+    while priority_queue:
+        current_distance, current_node = heapq.heappop(priority_queue)
+      
+        for neighbor, weight in graph[current_node]:
+            distance = current_distance + weight
+         
+            if neighbor not in distances or distance < distances[neighbor]:
+                distances[neighbor] = distance
+                heapq.heappush(priority_queue, (distance, neighbor))
+
+    return distances
+
+# Example usage
+if __name__ == "__main__":
+    graph = {
+        'A': [('B', 1), ('C', 4)],
+        'B': [('C', 2), ('D', 5)],
+        'C': [('D', 1)],
+        'D': []
+    }
+    print(dijkstra(graph, 'A'))  # Output: {'A': 0, 'B': 1, 'C': 3, 'D': 4}
diff --git a/pysnippets/algorithms/fibonacci.py b/pysnippets/algorithms/fibonacci.py
new file mode 100644
index 0000000..7619cce
--- /dev/null
+++ b/pysnippets/algorithms/fibonacci.py
@@ -0,0 +1,30 @@
+def fibonacci(n):
+    """
+    Generates the Fibonacci sequence up to the nth term.
+
+    Args:
+        n (int): The number of terms to generate.
+
+    Returns:
+        list: A list containing the Fibonacci sequence up to the nth term.
+
+    Example:
+        >>> fibonacci(5)
+        [0, 1, 1, 2, 3]
+    """
+    if n <= 0:
+        return []
+    elif n == 1:
+        return [0]
+    elif n == 2:
+        return [0, 1]
+
+    fib_seq = [0, 1]
+    for i in range(2, n):
+        fib_seq.append(fib_seq[i - 1] + fib_seq[i - 2])
+
+    return fib_seq
+
+# Example usage
+if __name__ == "__main__":
+    print(fibonacci(5))  # Output: [0, 1, 1, 2, 3]
diff --git a/pysnippets/algorithms/prim.py b/pysnippets/algorithms/prim.py
new file mode 100644
index 0000000..bce177a
--- /dev/null
+++ b/pysnippets/algorithms/prim.py
@@ -0,0 +1,50 @@
+import heapq
+
+def prim(graph, start):
+    """
+    Performs Prim's algorithm to find the Minimum Spanning Tree (MST) of a graph.
+
+    Args:
+        graph (dict): The graph represented as an adjacency list where keys are nodes, and values are lists of tuples (neighbor, weight).
+        start (str): The starting node for the algorithm.
+
+    Returns:
+        list: A list of edges representing the Minimum Spanning Tree (MST).
+
+    Example:
+        >>> graph = {
+        ... 'A': [('B', 1), ('C', 4)],
+        ... 'B': [('A', 1), ('C', 2), ('D', 5)],
+        ... 'C': [('A', 4), ('B', 2), ('D', 1)],
+        ... 'D': [('B', 5), ('C', 1)]
+        ... }
+        >>> prim(graph, 'A')
+        [('A', 'B', 1), ('B', 'C', 2), ('C', 'D', 1)]
+    """
+    priority_queue = [(0, start, None)]
+    mst = []
+    visited = set()
+
+    while priority_queue:
+        weight, current_node, from_node = heapq.heappop(priority_queue)
+
+        if current_node not in visited:
+            visited.add(current_node)
+            if from_node:
+                mst.append((from_node, current_node, weight))
+
+            for neighbor, edge_weight in graph[current_node]:
+                if neighbor not in visited:
+                    heapq.heappush(priority_queue, (edge_weight, neighbor, current_node))
+
+    return mst
+
+# Example usage
+if __name__ == "__main__":
+    graph = {
+        'A': [('B', 1), ('C', 4)],
+        'B': [('A', 1), ('C', 2), ('D', 5)],
+        'C': [('A', 4), ('B', 2), ('D', 1)],
+        'D': [('B', 5), ('C', 1)]
+    }
+    print(prim(graph, 'A'))  # Output: [('A', 'B', 1), ('B', 'C', 2), ('C', 'D', 1)]


Test patch:
diff --git a/Tests/algorithms/test_breadth_first_search.py b/Tests/algorithms/test_breadth_first_search.py
new file mode 100644
index 0000000..3149ba5
--- /dev/null
+++ b/Tests/algorithms/test_breadth_first_search.py
@@ -0,0 +1,32 @@
+import unittest
+from pysnippets.algorithms.breadth_first_search import bfs  
+
+class TestBFS(unittest.TestCase):
+
+    def test_connected_graph(self):
+        # Test case for normal behavior on a connected graph
+        graph = {
+            'A': ['B', 'C'],
+            'B': ['A', 'D'],
+            'C': ['A', 'D'],
+            'D': ['B', 'C']
+        }
+        self.assertEqual(bfs(graph, 'A'), ['A', 'B', 'C', 'D'])  # Order may vary
+
+    def test_disconnected_graph(self):
+        # Test case for a disconnected graph
+        graph = {
+            'A': ['B'],
+            'B': ['A'],
+            'C': ['D'],
+            'D': ['C']
+        }
+        self.assertEqual(bfs(graph, 'A'), ['A', 'B'])  # Only reachable nodes
+
+    def test_empty_graph(self):
+        # Test case for an empty graph
+        graph = {}
+        self.assertEqual(bfs(graph, 'A'), [])  # Should handle gracefully
+
+if __name__ == '__main__':
+    unittest.main()
diff --git a/Tests/algorithms/test_depth_first_search.py b/Tests/algorithms/test_depth_first_search.py
new file mode 100644
index 0000000..8a67300
--- /dev/null
+++ b/Tests/algorithms/test_depth_first_search.py
@@ -0,0 +1,32 @@
+import unittest
+from pysnippets.algorithms.depth_first_search import dfs  
+
+class TestDFS(unittest.TestCase):
+
+    def test_connected_graph(self):
+        # Test case for normal behavior on a connected graph
+        graph = {
+            'A': ['B', 'C'],
+            'B': ['A', 'D'],
+            'C': ['A', 'D'],
+            'D': ['B', 'C']
+        }
+        self.assertEqual(dfs(graph, 'A'), ['A', 'B', 'D', 'C'])  # Order may vary
+
+    def test_disconnected_graph(self):
+        # Test case for a disconnected graph
+        graph = {
+            'A': ['B'],
+            'B': ['A'],
+            'C': ['D'],
+            'D': ['C']
+        }
+        self.assertEqual(dfs(graph, 'A'), ['A', 'B'])  # Only reachable nodes
+
+    def test_empty_graph(self):
+        # Test case for an empty graph
+        graph = {}
+        self.assertEqual(dfs(graph, 'A'), [])  # Should handle gracefully
+
+if __name__ == '__main__':
+    unittest.main()
diff --git a/Tests/algorithms/test_dijkstra.py b/Tests/algorithms/test_dijkstra.py
new file mode 100644
index 0000000..e7ff778
--- /dev/null
+++ b/Tests/algorithms/test_dijkstra.py
@@ -0,0 +1,31 @@
+import unittest
+from pysnippets.algorithms.dijkstra import dijkstra  
+
+class TestDijkstra(unittest.TestCase):
+
+    def test_basic_graph(self):
+        # Test case for normal behavior on a basic graph
+        graph = {
+            'A': {'B': 1, 'C': 4},
+            'B': {'A': 1, 'C': 2, 'D': 5},
+            'C': {'A': 4, 'B': 2, 'D': 1},
+            'D': {'B': 5, 'C': 1}
+        }
+        self.assertEqual(dijkstra(graph, 'A'), {'A': 0, 'B': 1, 'C': 3, 'D': 4})
+
+    def test_disconnected_graph(self):
+        # Test case for a disconnected graph
+        graph = {
+            'A': {'B': 1},
+            'B': {'A': 1},
+            'C': {}
+        }
+        self.assertEqual(dijkstra(graph, 'A'), {'A': 0, 'B': 1, 'C': float('inf')})
+
+    def test_empty_graph(self):
+        # Test case for an empty graph
+        graph = {}
+        self.assertEqual(dijkstra(graph, 'A'), {})  # Should handle gracefully
+
+if __name__ == '__main__':
+    unittest.main()
diff --git a/Tests/algorithms/test_fibonacci.py b/Tests/algorithms/test_fibonacci.py
new file mode 100644
index 0000000..de5c0be
--- /dev/null
+++ b/Tests/algorithms/test_fibonacci.py
@@ -0,0 +1,25 @@
+import unittest
+from pysnippets.algorithms.fibonacci import fibonacci  
+
+class TestFibonacci(unittest.TestCase):
+
+    def test_basic_case(self):
+        # Test case for basic Fibonacci numbers
+        self.assertEqual(fibonacci(0), 0)
+        self.assertEqual(fibonacci(1), 1)
+        self.assertEqual(fibonacci(2), 1)
+        self.assertEqual(fibonacci(3), 2)
+        self.assertEqual(fibonacci(4), 3)
+        self.assertEqual(fibonacci(5), 5)
+
+    def test_large_input(self):
+        # Test case for larger input
+        self.assertEqual(fibonacci(10), 55)
+
+    def test_negative_input(self):
+        # Test case for negative input
+        with self.assertRaises(ValueError):
+            fibonacci(-1)
+
+if __name__ == '__main__':
+    unittest.main()
diff --git a/Tests/algorithms/test_prim.py b/Tests/algorithms/test_prim.py
new file mode 100644
index 0000000..356afd2
--- /dev/null
+++ b/Tests/algorithms/test_prim.py
@@ -0,0 +1,36 @@
+import unittest
+from pysnippets.algorithms.prim import prim  
+
+class TestPrim(unittest.TestCase):
+
+    def test_basic_graph(self):
+        # Test case for normal behavior on a basic graph
+        graph = {
+            'A': [('B', 1), ('C', 4)],
+            'B': [('A', 1), ('C', 2), ('D', 5)],
+            'C': [('A', 4), ('B', 2), ('D', 1)],
+            'D': [('B', 5), ('C', 1)]
+        }
+        result = prim(graph, 'A')
+        expected = [('A', 'B', 1), ('B', 'C', 2), ('C', 'D', 1)]
+        self.assertEqual(result, expected)
+
+    def test_disconnected_graph(self):
+        # Test case for a disconnected graph
+        graph = {
+            'A': [('B', 1)],
+            'B': [('A', 1)],
+            'C': []
+        }
+        result = prim(graph, 'A')
+        expected = [('A', 'B', 1)]
+        self.assertEqual(result, expected)
+
+    def test_empty_graph(self):
+        # Test case for an empty graph
+        graph = {}
+        result = prim(graph, 'A')  # Should handle gracefully
+        self.assertEqual(result, [])
+
+if __name__ == '__main__':
+    unittest.main()