from __future__ import annotations
class 							a_					:






 '''simple docstring'''






 def __init__(     self   :    Optional[Any]     ,       lowercase__   :    int):







        '''simple docstring'''



        lowerCAmelCase__	      =   vertices
        lowerCAmelCase__	      =   [[0] * vertices for _ in range(lowercase__)]




 def 						__snake_case		(     self   :    Union[str, Any]     ,       lowercase__   :    list[int]):







        '''simple docstring'''



        print('Vertex \t Distance from Source')
        for vertex in range(self.vertices):
               print(lowercase__     ,       '\t\t'     ,       distances_from_source[vertex])




 def 						__snake_case		(     self   :    Union[str, Any]     ,       lowercase__   :    list[int]     ,       lowercase__   :    list[bool]):







        '''simple docstring'''



        lowerCAmelCase__	      =   1e7
        lowerCAmelCase__	      =   0

        # Search not nearest vertex not in the shortest path tree
        for vertex in range(self.vertices):
               if distances_from_source[vertex] < minimum and visited[vertex] is False:
                      lowerCAmelCase__	      =   distances_from_source[vertex]
                      lowerCAmelCase__	      =   vertex
        return min_index




 def 						__snake_case		(     self   :    Optional[Any]     ,       lowercase__   :    int):







        '''simple docstring'''



        lowerCAmelCase__	      =   [int(1e7)] * self.vertices  # distances from the source
        lowerCAmelCase__	      =   0
        lowerCAmelCase__	      =   [False] * self.vertices

        for _ in range(self.vertices):
               lowerCAmelCase__	      =   self.minimum_distance(lowercase__     ,       lowercase__)
               lowerCAmelCase__	      =   True

               # Update dist value of the adjacent vertices
               # of the picked vertex only if the current
               # distance is greater than new distance and
               # the vertex in not in the shortest path tree
               for v in range(self.vertices):
                      if (
                          self.graph[u][v] > 0
                          and visited[v] is False
                          and distances[v] > distances[u] + self.graph[u][v]
                      ):
                             lowerCAmelCase__	      =   distances[u] + self.graph[u][v]

        self.print_solution(lowercase__)


if __name__ == "__main__":
    lowerCAmelCase__      		=					Graph(9)
    lowerCAmelCase__      		=					[
        [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],
    ]
    graph.dijkstra(0)

import unittest

from cer import CER


lowerCAmelCase__      		=					CER()
class 							a_					(		unittest.TestCase		):






 '''simple docstring'''






 def 						__snake_case		(     self   :    Any):







        '''simple docstring'''



        lowerCAmelCase__	      =   ['White House']
        lowerCAmelCase__	      =   ['white house']
        # S = 2, D = 0, I = 0, N = 11, CER = 2 / 11
        lowerCAmelCase__	      =   cer.compute(predictions=lowercase__     ,       references=lowercase__)
        self.assertTrue(abs(char_error_rate - 0.1_818_181_818) < 1e-6)




 def 						__snake_case		(     self   :    List[Any]):







        '''simple docstring'''



        lowerCAmelCase__	      =   ['were wolf']
        lowerCAmelCase__	      =   ['werewolf']
        # S = 0, D = 0, I = 1, N = 9, CER = 1 / 9
        lowerCAmelCase__	      =   cer.compute(predictions=lowercase__     ,       references=lowercase__)
        self.assertTrue(abs(char_error_rate - 0.1_111_111) < 1e-6)

        lowerCAmelCase__	      =   ['werewolf']
        lowerCAmelCase__	      =   ['weae     wolf']
        # S = 1, D = 1, I = 0, N = 8, CER = 0.25
        lowerCAmelCase__	      =   cer.compute(predictions=lowercase__     ,       references=lowercase__)
        self.assertTrue(abs(char_error_rate - 0.25) < 1e-6)

        # consecutive whitespaces case 1
        lowerCAmelCase__	      =   ['were wolf']
        lowerCAmelCase__	      =   ['were               wolf']
        # S = 0, D = 0, I = 0, N = 9, CER = 0
        lowerCAmelCase__	      =   cer.compute(predictions=lowercase__     ,       references=lowercase__)
        self.assertTrue(abs(char_error_rate - 0.0) < 1e-6)

        # consecutive whitespaces case 2
        lowerCAmelCase__	      =   ['were   wolf']
        lowerCAmelCase__	      =   ['were               wolf']
        # S = 0, D = 0, I = 0, N = 9, CER = 0
        lowerCAmelCase__	      =   cer.compute(predictions=lowercase__     ,       references=lowercase__)
        self.assertTrue(abs(char_error_rate - 0.0) < 1e-6)




 def 						__snake_case		(     self   :    Optional[Any]):







        '''simple docstring'''



        lowerCAmelCase__	      =   ['werewolf']
        lowerCAmelCase__	      =   ['weaewolf']
        # S = 1, D = 0, I = 0, N = 8, CER = 0.125
        lowerCAmelCase__	      =   cer.compute(predictions=lowercase__     ,       references=lowercase__)
        self.assertTrue(abs(char_error_rate - 0.125) < 1e-6)




 def 						__snake_case		(     self   :    Tuple):







        '''simple docstring'''



        lowerCAmelCase__	      =   ['werewolf']
        lowerCAmelCase__	      =   ['wereawolf']
        # S = 0, D = 1, I = 0, N = 8, CER = 0.125
        lowerCAmelCase__	      =   cer.compute(predictions=lowercase__     ,       references=lowercase__)
        self.assertTrue(abs(char_error_rate - 0.125) < 1e-6)




 def 						__snake_case		(     self   :    Optional[int]):







        '''simple docstring'''



        lowerCAmelCase__	      =   ['werewolf']
        lowerCAmelCase__	      =   ['wereolf']
        # S = 0, D = 0, I = 1, N = 8, CER = 0.125
        lowerCAmelCase__	      =   cer.compute(predictions=lowercase__     ,       references=lowercase__)
        self.assertTrue(abs(char_error_rate - 0.125) < 1e-6)




 def 						__snake_case		(     self   :    str):







        '''simple docstring'''



        lowerCAmelCase__	      =   ['werewolf']
        lowerCAmelCase__	      =   cer.compute(predictions=lowercase__     ,       references=lowercase__)
        self.assertEqual(lowercase__     ,       0.0)




 def 						__snake_case		(     self   :    Tuple):







        '''simple docstring'''



        lowerCAmelCase__	      =   ['werewolf', 'I am your father']
        lowerCAmelCase__	      =   cer.compute(predictions=lowercase__     ,       references=lowercase__)
        self.assertEqual(lowercase__     ,       0.0)

        lowerCAmelCase__	      =   ['werewolf', 'I am your father', 'doge']
        lowerCAmelCase__	      =   ['werxwolf', 'I       am your father', 'doge']
        # S = 1, D = 0, I = 0, N = 28, CER = 1 / 28
        lowerCAmelCase__	      =   cer.compute(predictions=lowercase__     ,       references=lowercase__)
        self.assertTrue(abs(char_error_rate - 0.03_571_428) < 1e-6)




 def 						__snake_case		(     self   :    Tuple):







        '''simple docstring'''



        lowerCAmelCase__	      =   ['My hovercraft', 'is full of eels']
        lowerCAmelCase__	      =   ['My hovercraft is full', ' of eels']
        # S = 0, D = 0, I = 2, N = 28, CER = 2 / 28
        # whitespace at the front of " of eels" will be strip during preporcessing
        # so need to insert 2 whitespaces
        lowerCAmelCase__	      =   cer.compute(predictions=lowercase__     ,       references=lowercase__     ,       concatenate_texts=lowercase__)
        self.assertTrue(abs(char_error_rate - 0.071_428) < 1e-6)




 def 						__snake_case		(     self   :    Dict):







        '''simple docstring'''



        lowerCAmelCase__	      =   ['我能吞下玻璃而不伤身体']
        lowerCAmelCase__	      =   [' 能吞虾玻璃而 不霜身体啦']
        # S = 3, D = 2, I = 0, N = 11, CER = 5 / 11
        lowerCAmelCase__	      =   cer.compute(predictions=lowercase__     ,       references=lowercase__)
        self.assertTrue(abs(char_error_rate - 0.4_545_454_545) < 1e-6)

        lowerCAmelCase__	      =   ['我能吞下玻璃', '而不伤身体']
        lowerCAmelCase__	      =   ['我    能 吞 下 玻 璃', '而不伤身体']
        # S = 0, D = 5, I = 0, N = 11, CER = 5 / 11
        lowerCAmelCase__	      =   cer.compute(predictions=lowercase__     ,       references=lowercase__)
        self.assertTrue(abs(char_error_rate - 0.454_545_454_545) < 1e-6)

        lowerCAmelCase__	      =   ['我能吞下玻璃而不伤身体']
        lowerCAmelCase__	      =   cer.compute(predictions=lowercase__     ,       references=lowercase__)
        self.assertFalse(lowercase__     ,       0.0)




 def 						__snake_case		(     self   :    Dict):







        '''simple docstring'''



        lowerCAmelCase__	      =   ['']
        lowerCAmelCase__	      =   ['Hypothesis']
        with self.assertRaises(lowercase__):
               cer.compute(predictions=lowercase__     ,       references=lowercase__)


if __name__ == "__main__":
    unittest.main()
