We are currently solving the following issue within our repository. Here is the issue text:
--- BEGIN ISSUE ---
[mypy] Need help to fix all `mypy` errors in the codebase
# Just one left to fix...
https://github.com/TheAlgorithms/Python/blob/master/mypy.ini#L5
* [x] other/least_recently_used.py
* [x] other/lfu_cache.py #5755
* [x] other/lru_cache.py #5755

---

__UPDATE:__ Our GitHub Actions now run `mypy --ignore-missing-imports` excluding those directories that fail that test.
* https://github.com/TheAlgorithms/Python/blob/master/mypy.ini#L5

Currently, we are not running `mypy` in our regular CI tests as there are a lot of errors in the entire codebase, which needs to be fixed. This won't be a one-person job, so we are asking for help from you. I cannot paste the entire message in here as there are around 600 of them, so here's just a gist of it:

```console
$ mypy --ignore-missing-imports .
strings/word_occurrence.py:17: error: Need type annotation for 'occurrence'
strings/min_cost_string_conversion.py:36: error: No overload variant of "__setitem__" of "list" matches argument types "int", "str"
strings/min_cost_string_conversion.py:36: note: Possible overload variants:
strings/min_cost_string_conversion.py:36: note:     def __setitem__(self, int, int) -> None
strings/min_cost_string_conversion.py:36: note:     def __setitem__(self, slice, Iterable[int]) -> None
strings/min_cost_string_conversion.py:40: error: No overload variant of "__setitem__" of "list" matches argument types "int", "str"
strings/min_cost_string_conversion.py:40: note: Possible overload variants:
strings/min_cost_string_conversion.py:40: note:     def __setitem__(self, int, int) -> None
strings/min_cost_string_conversion.py:40: note:     def __setitem__(self, slice, Iterable[int]) -> None
...
backtracking/n_queens_math.py:109: error: List comprehension has incompatible type List[str]; expected List[int]
backtracking/n_queens_math.py:110: error: Argument 1 to "append" of "list" has incompatible type "List[int]"; expected "List[str]"
backtracking/n_queens_math.py:149: error: Need type annotation for 'boards' (hint: "boards: List[<type>] = ...")
backtracking/minimax.py:15: error: "list" is not subscriptable, use "typing.List" instead
backtracking/knight_tour.py:6: error: "tuple" is not subscriptable, use "typing.Tuple" instead
backtracking/knight_tour.py:6: error: "list" is not subscriptable, use "typing.List" instead
...
```

# Guidelines to follow:

- Please make sure you read the [Contributing Guidelines](https://github.com/TheAlgorithms/Python/blob/master/CONTRIBUTING.md) first.
- Please submit a fix for a maximum of 3 files at a time (1 file is also acceptable).
- As we are not running `mypy` in our CI tests, the user who is submitting a pull request should run it on their local machine and ensure there are no errors in their submission.
- Please ensure your pull request title contains the word `mypy` in it. If possible use this template for your pull request title:
```
[mypy] Fix type annotations for <filenames>
```

### Which errors to fix?

Please follow the below steps to produce all the errors in this library:
- Fork this repository if you haven't already.
- Clone the forked repository on your local machine using the command:

```
git clone --depth 1 https://github.com/TheAlgorithms/Python.git
```
Then you need to install all the necessary requirements:
```
cd python/
python -m pip install --upgrade pip
python -m pip install -r requirements.txt
python -m pip install mypy
```
Then run either of the two commands:
- `mypy --ignore-missing-imports .` -> To produce all the error messages for the entire codebase.
- `mypy --ignore-missing-imports <filepath1> <filepath2> ...` -> To produce error messages for the mentioned file.

### How to fix the errors?

- Make a separate branch for your fix with the command: 
```
git checkout -b mypy-fix
```
- Make changes to the selected files.
- Push it to your forked copy and open a pull request with the appropriate title as mentioned above.

### Focus on one directory at a time:

```
.
├── [x] arithmetic_analysis
├── [x] backtracking
├── [x] bit_manipulation
├── [x] blockchain
├── [x] boolean_algebra
├── [x] cellular_automata
├── [x] ciphers
├── [x] compression
├── [x] computer_vision
├── [x] conversions
├── [ ] data_structures
├── [x] digital_image_processing
├── [x] divide_and_conquer
├── [ ] dynamic_programming
├── [x] electronics
├── [x] file_transfer
├── [x] fractals
├── [x] fuzzy_logic
├── [x] genetic_algorithm
├── [x] geodesy
├── [x] graphics
├── [ ] graphs
├── [x] hashes
├── [x] knapsack
├── [x] linear_algebra
├── [x] machine_learning
├── [ ] maths
├── [ ] matrix
├── [x] networking_flow
├── [x] neural_network
├── [ ] other
├── [ ] project_euler
├── [x] quantum
├── [x] scheduling
├── [x] scripts
├── [ ] searches
├── [x] sorts
├── [ ] strings
└── [x] web_programming
```

### Pre-requisites:
- You should be familiar with `mypy`: https://mypy.readthedocs.io
- You should be familiar with Python type hints: https://docs.python.org/3/library/typing.html

--- END ISSUE ---

Below are some code segments, each from a relevant file. One or more of these files may contain bugs.
--- BEGIN FILES ---
Path: `graphs/boruvka.py`
Content:
```
1 """Borůvka's algorithm.
2 
3     Determines the minimum spanning tree (MST) of a graph using the Borůvka's algorithm.
4     Borůvka's algorithm is a greedy algorithm for finding a minimum spanning tree in a
5     connected graph, or a minimum spanning forest if a graph that is not connected.
6 
7     The time complexity of this algorithm is O(ELogV), where E represents the number
8     of edges, while V represents the number of nodes.
9     O(number_of_edges Log number_of_nodes)
10 
11     The space complexity of this algorithm is O(V + E), since we have to keep a couple
12     of lists whose sizes are equal to the number of nodes, as well as keep all the
13     edges of a graph inside of the data structure itself.
14 
15     Borůvka's algorithm gives us pretty much the same result as other MST Algorithms -
16     they all find the minimum spanning tree, and the time complexity is approximately
17     the same.
18 
19     One advantage that Borůvka's algorithm has compared to the alternatives is that it
20     doesn't need to presort the edges or maintain a priority queue in order to find the
21     minimum spanning tree.
22     Even though that doesn't help its complexity, since it still passes the edges logE
23     times, it is a bit simpler to code.
24 
25     Details: https://en.wikipedia.org/wiki/Bor%C5%AFvka%27s_algorithm
26 """
27 
28 
29 class Graph:
30     def __init__(self, num_of_nodes: int) -> None:
31         """
32         Arguments:
33             num_of_nodes - the number of nodes in the graph
34         Attributes:
35             m_num_of_nodes - the number of nodes in the graph.
36             m_edges - the list of edges.
37             m_component - the dictionary which stores the index of the component which
38             a node belongs to.
39         """
40 
41         self.m_num_of_nodes = num_of_nodes
42         self.m_edges = []
43         self.m_component = {}
44 
45     def add_edge(self, u_node: int, v_node: int, weight: int) -> None:
46         """Adds an edge in the format [first, second, edge weight] to graph."""
47 
48         self.m_edges.append([u_node, v_node, weight])
49 
50     def find_component(self, u_node: int) -> int:
51         """Propagates a new component throughout a given component."""
52 
53         if self.m_component[u_node] == u_node:
54             return u_node
55         return self.find_component(self.m_component[u_node])
56 
57     def set_component(self, u_node: int) -> None:
58         """Finds the component index of a given node"""
59 
60         if self.m_component[u_node] != u_node:
61             for k in self.m_component:
62                 self.m_component[k] = self.find_component(k)
63 
64     def union(self, component_size: list, u_node: int, v_node: int) -> None:
65         """Union finds the roots of components for two nodes, compares the components
66         in terms of size, and attaches the smaller one to the larger one to form
67         single component"""
68 
69         if component_size[u_node] <= component_size[v_node]:
70             self.m_component[u_node] = v_node
71             component_size[v_node] += component_size[u_node]
72             self.set_component(u_node)
73 
74         elif component_size[u_node] >= component_size[v_node]:
75             self.m_component[v_node] = self.find_component(u_node)
76             component_size[u_node] += component_size[v_node]
77             self.set_component(v_node)
78 
79     def boruvka(self) -> None:
80         """Performs Borůvka's algorithm to find MST."""
81 
82         # Initialize additional lists required to algorithm.
83         component_size = []
84         mst_weight = 0
85 
86         minimum_weight_edge = [-1] * self.m_num_of_nodes
87 
88         # A list of components (initialized to all of the nodes)
89         for node in range(self.m_num_of_nodes):
90             self.m_component.update({node: node})
91             component_size.append(1)
92 
93         num_of_components = self.m_num_of_nodes
94 
95         while num_of_components > 1:
96             for edge in self.m_edges:
97                 u, v, w = edge
98 
99                 u_component = self.m_component[u]
100                 v_component = self.m_component[v]
101 
102                 if u_component != v_component:
103                     """If the current minimum weight edge of component u doesn't
104                     exist (is -1), or if it's greater than the edge we're
105                     observing right now, we will assign the value of the edge
106                     we're observing to it.
107 
108                     If the current minimum weight edge of component v doesn't
109                     exist (is -1), or if it's greater than the edge we're
110                     observing right now, we will assign the value of the edge
111                     we're observing to it"""
112 
113                     for component in (u_component, v_component):
114                         if (
115                             minimum_weight_edge[component] == -1
116                             or minimum_weight_edge[component][2] > w
117                         ):
118                             minimum_weight_edge[component] = [u, v, w]
119 
120             for edge in minimum_weight_edge:
121                 if edge != -1:
122                     u, v, w = edge
123 
124                     u_component = self.m_component[u]
125                     v_component = self.m_component[v]
126 
127                     if u_component != v_component:
128                         mst_weight += w
129                         self.union(component_size, u_component, v_component)
130                         print(f"Added edge [{u} - {v}]\nAdded weight: {w}\n")
131                         num_of_components -= 1
132 
133             minimum_weight_edge = [-1] * self.m_num_of_nodes
134         print(f"The total weight of the minimal spanning tree is: {mst_weight}")
135 
136 
137 def test_vector() -> None:
138     """
139     >>> g = Graph(8)
140     >>> for u_v_w in ((0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4),
141     ...    (3, 4, 8), (4, 5, 10), (4, 6, 6), (4, 7, 5), (5, 7, 15), (6, 7, 4)):
142     ...        g.add_edge(*u_v_w)
143     >>> g.boruvka()
144     Added edge [0 - 3]
145     Added weight: 5
146     <BLANKLINE>
147     Added edge [0 - 1]
148     Added weight: 10
149     <BLANKLINE>
150     Added edge [2 - 3]
151     Added weight: 4
152     <BLANKLINE>
153     Added edge [4 - 7]
154     Added weight: 5
155     <BLANKLINE>
156     Added edge [4 - 5]
157     Added weight: 10
158     <BLANKLINE>
159     Added edge [6 - 7]
160     Added weight: 4
161     <BLANKLINE>
162     Added edge [3 - 4]
163     Added weight: 8
164     <BLANKLINE>
165     The total weight of the minimal spanning tree is: 46
166     """
167 
168 
169 if __name__ == "__main__":
170     import doctest
171 
172     doctest.testmod()
173
```
--- END FILES ---

Please first localize the bug based on the issue statement, and then generate a patch according to the `git diff` format fenced by three backticks.

Here is an example:

```diff
diff --git a/examples/server_async.py b/examples/server_async.py
--- a/examples/server_async.py
+++ b/examples/server_async.py
@@ -313,4 +313,4 @@
 
 
 if __name__ == "__main__":
-    asyncio.run(run_async_server("."), debug=True)
+    asyncio.run(run_async_server(), debug=True)
diff --git a/examples/server_sync.py b/examples/server_sync.py
--- a/examples/server_sync.py
+++ b/examples/server_sync.py
@@ -313,5 +313,5 @@
 
 
 if __name__ == "__main__":
-    server = run_sync_server(".")
+    server = run_sync_server()
     server.shutdown()

```

diff --git a/graphs/boruvka.py b/graphs/boruvka.py
--- a/graphs/boruvka.py
+++ b/graphs/boruvka.py
@@ -24,6 +24,7 @@
 
     Details: https://en.wikipedia.org/wiki/Bor%C5%AFvka%27s_algorithm
 """
+from __future__ import annotations
 
 
 class Graph:
@@ -39,8 +40,8 @@
         """
 
         self.m_num_of_nodes = num_of_nodes
-        self.m_edges = []
-        self.m_component = {}
+        self.m_edges: list[list[int]] = []
+        self.m_component: dict[int, int] = {}
 
     def add_edge(self, u_node: int, v_node: int, weight: int) -> None:
         """Adds an edge in the format [first, second, edge weight] to graph."""
@@ -83,7 +84,7 @@
         component_size = []
         mst_weight = 0
 
-        minimum_weight_edge = [-1] * self.m_num_of_nodes
+        minimum_weight_edge: list[int] = [-1] * self.m_num_of_nodes
 
         # A list of components (initialized to all of the nodes)
         for node in range(self.m_num_of_nodes):

{"golden_diff": "diff --git a/graphs/boruvka.py b/graphs/boruvka.py\n--- a/graphs/boruvka.py\n+++ b/graphs/boruvka.py\n@@ -24,6 +24,7 @@\n \n     Details: https://en.wikipedia.org/wiki/Bor%C5%AFvka%27s_algorithm\n \"\"\"\n+from __future__ import annotations\n \n \n class Graph:\n@@ -39,8 +40,8 @@\n         \"\"\"\n \n         self.m_num_of_nodes = num_of_nodes\n-        self.m_edges = []\n-        self.m_component = {}\n+        self.m_edges: list[list[int]] = []\n+        self.m_component: dict[int, int] = {}\n \n     def add_edge(self, u_node: int, v_node: int, weight: int) -> None:\n         \"\"\"Adds an edge in the format [first, second, edge weight] to graph.\"\"\"\n@@ -83,7 +84,7 @@\n         component_size = []\n         mst_weight = 0\n \n-        minimum_weight_edge = [-1] * self.m_num_of_nodes\n+        minimum_weight_edge: list[int] = [-1] * self.m_num_of_nodes\n \n         # A list of components (initialized to all of the nodes)\n         for node in range(self.m_num_of_nodes):\n", "issue": "[mypy] Need help to fix all `mypy` errors in the codebase\n# Just one left to fix...\r\nhttps://github.com/TheAlgorithms/Python/blob/master/mypy.ini#L5\r\n* [x] other/least_recently_used.py\r\n* [x] other/lfu_cache.py #5755\r\n* [x] other/lru_cache.py #5755\r\n\r\n---\r\n\r\n__UPDATE:__ Our GitHub Actions now run `mypy --ignore-missing-imports` excluding those directories that fail that test.\r\n* https://github.com/TheAlgorithms/Python/blob/master/mypy.ini#L5\r\n\r\nCurrently, we are not running `mypy` in our regular CI tests as there are a lot of errors in the entire codebase, which needs to be fixed. This won't be a one-person job, so we are asking for help from you. I cannot paste the entire message in here as there are around 600 of them, so here's just a gist of it:\r\n\r\n```console\r\n$ mypy --ignore-missing-imports .\r\nstrings/word_occurrence.py:17: error: Need type annotation for 'occurrence'\r\nstrings/min_cost_string_conversion.py:36: error: No overload variant of \"__setitem__\" of \"list\" matches argument types \"int\", \"str\"\r\nstrings/min_cost_string_conversion.py:36: note: Possible overload variants:\r\nstrings/min_cost_string_conversion.py:36: note:     def __setitem__(self, int, int) -> None\r\nstrings/min_cost_string_conversion.py:36: note:     def __setitem__(self, slice, Iterable[int]) -> None\r\nstrings/min_cost_string_conversion.py:40: error: No overload variant of \"__setitem__\" of \"list\" matches argument types \"int\", \"str\"\r\nstrings/min_cost_string_conversion.py:40: note: Possible overload variants:\r\nstrings/min_cost_string_conversion.py:40: note:     def __setitem__(self, int, int) -> None\r\nstrings/min_cost_string_conversion.py:40: note:     def __setitem__(self, slice, Iterable[int]) -> None\r\n...\r\nbacktracking/n_queens_math.py:109: error: List comprehension has incompatible type List[str]; expected List[int]\r\nbacktracking/n_queens_math.py:110: error: Argument 1 to \"append\" of \"list\" has incompatible type \"List[int]\"; expected \"List[str]\"\r\nbacktracking/n_queens_math.py:149: error: Need type annotation for 'boards' (hint: \"boards: List[<type>] = ...\")\r\nbacktracking/minimax.py:15: error: \"list\" is not subscriptable, use \"typing.List\" instead\r\nbacktracking/knight_tour.py:6: error: \"tuple\" is not subscriptable, use \"typing.Tuple\" instead\r\nbacktracking/knight_tour.py:6: error: \"list\" is not subscriptable, use \"typing.List\" instead\r\n...\r\n```\r\n\r\n# Guidelines to follow:\r\n\r\n- Please make sure you read the [Contributing Guidelines](https://github.com/TheAlgorithms/Python/blob/master/CONTRIBUTING.md) first.\r\n- Please submit a fix for a maximum of 3 files at a time (1 file is also acceptable).\r\n- As we are not running `mypy` in our CI tests, the user who is submitting a pull request should run it on their local machine and ensure there are no errors in their submission.\r\n- Please ensure your pull request title contains the word `mypy` in it. If possible use this template for your pull request title:\r\n```\r\n[mypy] Fix type annotations for <filenames>\r\n```\r\n\r\n### Which errors to fix?\r\n\r\nPlease follow the below steps to produce all the errors in this library:\r\n- Fork this repository if you haven't already.\r\n- Clone the forked repository on your local machine using the command:\r\n\r\n```\r\ngit clone --depth 1 https://github.com/TheAlgorithms/Python.git\r\n```\r\nThen you need to install all the necessary requirements:\r\n```\r\ncd python/\r\npython -m pip install --upgrade pip\r\npython -m pip install -r requirements.txt\r\npython -m pip install mypy\r\n```\r\nThen run either of the two commands:\r\n- `mypy --ignore-missing-imports .` -> To produce all the error messages for the entire codebase.\r\n- `mypy --ignore-missing-imports <filepath1> <filepath2> ...` -> To produce error messages for the mentioned file.\r\n\r\n### How to fix the errors?\r\n\r\n- Make a separate branch for your fix with the command: \r\n```\r\ngit checkout -b mypy-fix\r\n```\r\n- Make changes to the selected files.\r\n- Push it to your forked copy and open a pull request with the appropriate title as mentioned above.\r\n\r\n### Focus on one directory at a time:\r\n\r\n```\r\n.\r\n\u251c\u2500\u2500 [x] arithmetic_analysis\r\n\u251c\u2500\u2500 [x] backtracking\r\n\u251c\u2500\u2500 [x] bit_manipulation\r\n\u251c\u2500\u2500 [x] blockchain\r\n\u251c\u2500\u2500 [x] boolean_algebra\r\n\u251c\u2500\u2500 [x] cellular_automata\r\n\u251c\u2500\u2500 [x] ciphers\r\n\u251c\u2500\u2500 [x] compression\r\n\u251c\u2500\u2500 [x] computer_vision\r\n\u251c\u2500\u2500 [x] conversions\r\n\u251c\u2500\u2500 [ ] data_structures\r\n\u251c\u2500\u2500 [x] digital_image_processing\r\n\u251c\u2500\u2500 [x] divide_and_conquer\r\n\u251c\u2500\u2500 [ ] dynamic_programming\r\n\u251c\u2500\u2500 [x] electronics\r\n\u251c\u2500\u2500 [x] file_transfer\r\n\u251c\u2500\u2500 [x] fractals\r\n\u251c\u2500\u2500 [x] fuzzy_logic\r\n\u251c\u2500\u2500 [x] genetic_algorithm\r\n\u251c\u2500\u2500 [x] geodesy\r\n\u251c\u2500\u2500 [x] graphics\r\n\u251c\u2500\u2500 [ ] graphs\r\n\u251c\u2500\u2500 [x] hashes\r\n\u251c\u2500\u2500 [x] knapsack\r\n\u251c\u2500\u2500 [x] linear_algebra\r\n\u251c\u2500\u2500 [x] machine_learning\r\n\u251c\u2500\u2500 [ ] maths\r\n\u251c\u2500\u2500 [ ] matrix\r\n\u251c\u2500\u2500 [x] networking_flow\r\n\u251c\u2500\u2500 [x] neural_network\r\n\u251c\u2500\u2500 [ ] other\r\n\u251c\u2500\u2500 [ ] project_euler\r\n\u251c\u2500\u2500 [x] quantum\r\n\u251c\u2500\u2500 [x] scheduling\r\n\u251c\u2500\u2500 [x] scripts\r\n\u251c\u2500\u2500 [ ] searches\r\n\u251c\u2500\u2500 [x] sorts\r\n\u251c\u2500\u2500 [ ] strings\r\n\u2514\u2500\u2500 [x] web_programming\r\n```\r\n\r\n### Pre-requisites:\r\n- You should be familiar with `mypy`: https://mypy.readthedocs.io\r\n- You should be familiar with Python type hints: https://docs.python.org/3/library/typing.html\n", "before_files": [{"content": "\"\"\"Bor\u016fvka's algorithm.\n\n    Determines the minimum spanning tree (MST) of a graph using the Bor\u016fvka's algorithm.\n    Bor\u016fvka's algorithm is a greedy algorithm for finding a minimum spanning tree in a\n    connected graph, or a minimum spanning forest if a graph that is not connected.\n\n    The time complexity of this algorithm is O(ELogV), where E represents the number\n    of edges, while V represents the number of nodes.\n    O(number_of_edges Log number_of_nodes)\n\n    The space complexity of this algorithm is O(V + E), since we have to keep a couple\n    of lists whose sizes are equal to the number of nodes, as well as keep all the\n    edges of a graph inside of the data structure itself.\n\n    Bor\u016fvka's algorithm gives us pretty much the same result as other MST Algorithms -\n    they all find the minimum spanning tree, and the time complexity is approximately\n    the same.\n\n    One advantage that Bor\u016fvka's algorithm has compared to the alternatives is that it\n    doesn't need to presort the edges or maintain a priority queue in order to find the\n    minimum spanning tree.\n    Even though that doesn't help its complexity, since it still passes the edges logE\n    times, it is a bit simpler to code.\n\n    Details: https://en.wikipedia.org/wiki/Bor%C5%AFvka%27s_algorithm\n\"\"\"\n\n\nclass Graph:\n    def __init__(self, num_of_nodes: int) -> None:\n        \"\"\"\n        Arguments:\n            num_of_nodes - the number of nodes in the graph\n        Attributes:\n            m_num_of_nodes - the number of nodes in the graph.\n            m_edges - the list of edges.\n            m_component - the dictionary which stores the index of the component which\n            a node belongs to.\n        \"\"\"\n\n        self.m_num_of_nodes = num_of_nodes\n        self.m_edges = []\n        self.m_component = {}\n\n    def add_edge(self, u_node: int, v_node: int, weight: int) -> None:\n        \"\"\"Adds an edge in the format [first, second, edge weight] to graph.\"\"\"\n\n        self.m_edges.append([u_node, v_node, weight])\n\n    def find_component(self, u_node: int) -> int:\n        \"\"\"Propagates a new component throughout a given component.\"\"\"\n\n        if self.m_component[u_node] == u_node:\n            return u_node\n        return self.find_component(self.m_component[u_node])\n\n    def set_component(self, u_node: int) -> None:\n        \"\"\"Finds the component index of a given node\"\"\"\n\n        if self.m_component[u_node] != u_node:\n            for k in self.m_component:\n                self.m_component[k] = self.find_component(k)\n\n    def union(self, component_size: list, u_node: int, v_node: int) -> None:\n        \"\"\"Union finds the roots of components for two nodes, compares the components\n        in terms of size, and attaches the smaller one to the larger one to form\n        single component\"\"\"\n\n        if component_size[u_node] <= component_size[v_node]:\n            self.m_component[u_node] = v_node\n            component_size[v_node] += component_size[u_node]\n            self.set_component(u_node)\n\n        elif component_size[u_node] >= component_size[v_node]:\n            self.m_component[v_node] = self.find_component(u_node)\n            component_size[u_node] += component_size[v_node]\n            self.set_component(v_node)\n\n    def boruvka(self) -> None:\n        \"\"\"Performs Bor\u016fvka's algorithm to find MST.\"\"\"\n\n        # Initialize additional lists required to algorithm.\n        component_size = []\n        mst_weight = 0\n\n        minimum_weight_edge = [-1] * self.m_num_of_nodes\n\n        # A list of components (initialized to all of the nodes)\n        for node in range(self.m_num_of_nodes):\n            self.m_component.update({node: node})\n            component_size.append(1)\n\n        num_of_components = self.m_num_of_nodes\n\n        while num_of_components > 1:\n            for edge in self.m_edges:\n                u, v, w = edge\n\n                u_component = self.m_component[u]\n                v_component = self.m_component[v]\n\n                if u_component != v_component:\n                    \"\"\"If the current minimum weight edge of component u doesn't\n                    exist (is -1), or if it's greater than the edge we're\n                    observing right now, we will assign the value of the edge\n                    we're observing to it.\n\n                    If the current minimum weight edge of component v doesn't\n                    exist (is -1), or if it's greater than the edge we're\n                    observing right now, we will assign the value of the edge\n                    we're observing to it\"\"\"\n\n                    for component in (u_component, v_component):\n                        if (\n                            minimum_weight_edge[component] == -1\n                            or minimum_weight_edge[component][2] > w\n                        ):\n                            minimum_weight_edge[component] = [u, v, w]\n\n            for edge in minimum_weight_edge:\n                if edge != -1:\n                    u, v, w = edge\n\n                    u_component = self.m_component[u]\n                    v_component = self.m_component[v]\n\n                    if u_component != v_component:\n                        mst_weight += w\n                        self.union(component_size, u_component, v_component)\n                        print(f\"Added edge [{u} - {v}]\\nAdded weight: {w}\\n\")\n                        num_of_components -= 1\n\n            minimum_weight_edge = [-1] * self.m_num_of_nodes\n        print(f\"The total weight of the minimal spanning tree is: {mst_weight}\")\n\n\ndef test_vector() -> None:\n    \"\"\"\n    >>> g = Graph(8)\n    >>> for u_v_w in ((0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4),\n    ...    (3, 4, 8), (4, 5, 10), (4, 6, 6), (4, 7, 5), (5, 7, 15), (6, 7, 4)):\n    ...        g.add_edge(*u_v_w)\n    >>> g.boruvka()\n    Added edge [0 - 3]\n    Added weight: 5\n    <BLANKLINE>\n    Added edge [0 - 1]\n    Added weight: 10\n    <BLANKLINE>\n    Added edge [2 - 3]\n    Added weight: 4\n    <BLANKLINE>\n    Added edge [4 - 7]\n    Added weight: 5\n    <BLANKLINE>\n    Added edge [4 - 5]\n    Added weight: 10\n    <BLANKLINE>\n    Added edge [6 - 7]\n    Added weight: 4\n    <BLANKLINE>\n    Added edge [3 - 4]\n    Added weight: 8\n    <BLANKLINE>\n    The total weight of the minimal spanning tree is: 46\n    \"\"\"\n\n\nif __name__ == \"__main__\":\n    import doctest\n\n    doctest.testmod()\n", "path": "graphs/boruvka.py"}], "after_files": [{"content": "\"\"\"Bor\u016fvka's algorithm.\n\n    Determines the minimum spanning tree (MST) of a graph using the Bor\u016fvka's algorithm.\n    Bor\u016fvka's algorithm is a greedy algorithm for finding a minimum spanning tree in a\n    connected graph, or a minimum spanning forest if a graph that is not connected.\n\n    The time complexity of this algorithm is O(ELogV), where E represents the number\n    of edges, while V represents the number of nodes.\n    O(number_of_edges Log number_of_nodes)\n\n    The space complexity of this algorithm is O(V + E), since we have to keep a couple\n    of lists whose sizes are equal to the number of nodes, as well as keep all the\n    edges of a graph inside of the data structure itself.\n\n    Bor\u016fvka's algorithm gives us pretty much the same result as other MST Algorithms -\n    they all find the minimum spanning tree, and the time complexity is approximately\n    the same.\n\n    One advantage that Bor\u016fvka's algorithm has compared to the alternatives is that it\n    doesn't need to presort the edges or maintain a priority queue in order to find the\n    minimum spanning tree.\n    Even though that doesn't help its complexity, since it still passes the edges logE\n    times, it is a bit simpler to code.\n\n    Details: https://en.wikipedia.org/wiki/Bor%C5%AFvka%27s_algorithm\n\"\"\"\nfrom __future__ import annotations\n\n\nclass Graph:\n    def __init__(self, num_of_nodes: int) -> None:\n        \"\"\"\n        Arguments:\n            num_of_nodes - the number of nodes in the graph\n        Attributes:\n            m_num_of_nodes - the number of nodes in the graph.\n            m_edges - the list of edges.\n            m_component - the dictionary which stores the index of the component which\n            a node belongs to.\n        \"\"\"\n\n        self.m_num_of_nodes = num_of_nodes\n        self.m_edges: list[list[int]] = []\n        self.m_component: dict[int, int] = {}\n\n    def add_edge(self, u_node: int, v_node: int, weight: int) -> None:\n        \"\"\"Adds an edge in the format [first, second, edge weight] to graph.\"\"\"\n\n        self.m_edges.append([u_node, v_node, weight])\n\n    def find_component(self, u_node: int) -> int:\n        \"\"\"Propagates a new component throughout a given component.\"\"\"\n\n        if self.m_component[u_node] == u_node:\n            return u_node\n        return self.find_component(self.m_component[u_node])\n\n    def set_component(self, u_node: int) -> None:\n        \"\"\"Finds the component index of a given node\"\"\"\n\n        if self.m_component[u_node] != u_node:\n            for k in self.m_component:\n                self.m_component[k] = self.find_component(k)\n\n    def union(self, component_size: list, u_node: int, v_node: int) -> None:\n        \"\"\"Union finds the roots of components for two nodes, compares the components\n        in terms of size, and attaches the smaller one to the larger one to form\n        single component\"\"\"\n\n        if component_size[u_node] <= component_size[v_node]:\n            self.m_component[u_node] = v_node\n            component_size[v_node] += component_size[u_node]\n            self.set_component(u_node)\n\n        elif component_size[u_node] >= component_size[v_node]:\n            self.m_component[v_node] = self.find_component(u_node)\n            component_size[u_node] += component_size[v_node]\n            self.set_component(v_node)\n\n    def boruvka(self) -> None:\n        \"\"\"Performs Bor\u016fvka's algorithm to find MST.\"\"\"\n\n        # Initialize additional lists required to algorithm.\n        component_size = []\n        mst_weight = 0\n\n        minimum_weight_edge: list[int] = [-1] * self.m_num_of_nodes\n\n        # A list of components (initialized to all of the nodes)\n        for node in range(self.m_num_of_nodes):\n            self.m_component.update({node: node})\n            component_size.append(1)\n\n        num_of_components = self.m_num_of_nodes\n\n        while num_of_components > 1:\n            for edge in self.m_edges:\n                u, v, w = edge\n\n                u_component = self.m_component[u]\n                v_component = self.m_component[v]\n\n                if u_component != v_component:\n                    \"\"\"If the current minimum weight edge of component u doesn't\n                    exist (is -1), or if it's greater than the edge we're\n                    observing right now, we will assign the value of the edge\n                    we're observing to it.\n\n                    If the current minimum weight edge of component v doesn't\n                    exist (is -1), or if it's greater than the edge we're\n                    observing right now, we will assign the value of the edge\n                    we're observing to it\"\"\"\n\n                    for component in (u_component, v_component):\n                        if (\n                            minimum_weight_edge[component] == -1\n                            or minimum_weight_edge[component][2] > w\n                        ):\n                            minimum_weight_edge[component] = [u, v, w]\n\n            for edge in minimum_weight_edge:\n                if edge != -1:\n                    u, v, w = edge\n\n                    u_component = self.m_component[u]\n                    v_component = self.m_component[v]\n\n                    if u_component != v_component:\n                        mst_weight += w\n                        self.union(component_size, u_component, v_component)\n                        print(f\"Added edge [{u} - {v}]\\nAdded weight: {w}\\n\")\n                        num_of_components -= 1\n\n            minimum_weight_edge = [-1] * self.m_num_of_nodes\n        print(f\"The total weight of the minimal spanning tree is: {mst_weight}\")\n\n\ndef test_vector() -> None:\n    \"\"\"\n    >>> g = Graph(8)\n    >>> for u_v_w in ((0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4),\n    ...    (3, 4, 8), (4, 5, 10), (4, 6, 6), (4, 7, 5), (5, 7, 15), (6, 7, 4)):\n    ...        g.add_edge(*u_v_w)\n    >>> g.boruvka()\n    Added edge [0 - 3]\n    Added weight: 5\n    <BLANKLINE>\n    Added edge [0 - 1]\n    Added weight: 10\n    <BLANKLINE>\n    Added edge [2 - 3]\n    Added weight: 4\n    <BLANKLINE>\n    Added edge [4 - 7]\n    Added weight: 5\n    <BLANKLINE>\n    Added edge [4 - 5]\n    Added weight: 10\n    <BLANKLINE>\n    Added edge [6 - 7]\n    Added weight: 4\n    <BLANKLINE>\n    Added edge [3 - 4]\n    Added weight: 8\n    <BLANKLINE>\n    The total weight of the minimal spanning tree is: 46\n    \"\"\"\n\n\nif __name__ == \"__main__\":\n    import doctest\n\n    doctest.testmod()\n", "path": "graphs/boruvka.py"}]}