




from __future__ import annotations

from collections import deque
from queue import Queue
from timeit import timeit

a_ 		=  {
    '''A''': ['''B''', '''C'''],
    '''B''': ['''A''', '''D''', '''E'''],
    '''C''': ['''A''', '''F'''],
    '''D''': ['''B'''],
    '''E''': ['''B''', '''F'''],
    '''F''': ['''C''', '''E'''],
}




def        __SCREAMING_SNAKE_CASE (	lowercase_       ,  lowercase_   )							->						list[str]:

    """simple docstring"""


    __UpperCamelCase			=    {start}
    __UpperCamelCase			=    [start]
    __UpperCamelCase			=    Queue()
    queue.put(_UpperCAmelCase   )
    while not queue.empty():
        __UpperCamelCase			=    queue.get()
        for w in graph[v]:
            if w not in explored:
                explored.add(_UpperCAmelCase   )
                result.append(_UpperCAmelCase   )
                queue.put(_UpperCAmelCase   )
    return result




def        __SCREAMING_SNAKE_CASE (	lowercase_       ,  lowercase_   )							->						list[str]:

    """simple docstring"""


    __UpperCamelCase			=    {start}
    __UpperCamelCase			=    [start]
    __UpperCamelCase			=    deque([start]   )
    while queue:
        __UpperCamelCase			=    queue.popleft()
        for child in graph[v]:
            if child not in visited:
                visited.add(_UpperCAmelCase   )
                result.append(_UpperCAmelCase   )
                queue.append(_UpperCAmelCase   )
    return result




def        __SCREAMING_SNAKE_CASE (	lowercase_   )							->						None:

    """simple docstring"""


    __UpperCamelCase			=    F"from __main__ import G, {name}"
    __UpperCamelCase			=    1_00_00
    __UpperCamelCase			=    timeit(F"{name}(G, 'A')"       ,  setup=_UpperCAmelCase       ,  number=_UpperCAmelCase   )
    print(F"{name:<35} finished {number} runs in {res:.5f} seconds"   )


if __name__ == "__main__":
 import doctest

 doctest.testmod()

 benchmark_function("breadth_first_search")
 benchmark_function("breadth_first_search_with_deque")
 # breadth_first_search                finished 10000 runs in 0.20999 seconds
 # breadth_first_search_with_deque     finished 10000 runs in 0.01421 seconds













import os
import pickle
import unittest
from collections import UserDict, namedtuple

import torch

from accelerate.test_utils.testing import require_cuda, require_torch_min_version
from accelerate.test_utils.training import RegressionModel
from accelerate.utils import (
    convert_outputs_to_fpaa,
    extract_model_from_parallel,
    find_device,
    listify,
    patch_environment,
    recursively_apply,
    send_to_device,
)


UpperCAmelCase__    :      List[Any]       					=namedtuple('''ExampleNamedTuple''', '''a b c''')

class    __A  (    unittest.TestCase     ):


				def _snake_case							(		self				):
								lowerCamelCase									=torch.randn(5 ,			2				)
								lowerCamelCase									=torch.device("""cuda"""				) if torch.cuda.is_available() else torch.device("""cpu"""				)

								lowerCamelCase									=send_to_device(UpperCAmelCase_ ,			UpperCAmelCase_				)
								self.assertTrue(torch.equal(resulta.cpu() ,			UpperCAmelCase_				)				)

								lowerCamelCase									=send_to_device((tensor, [tensor, tensor], 1) ,			UpperCAmelCase_				)
								self.assertIsInstance(UpperCAmelCase_ ,			UpperCAmelCase_				)
								self.assertTrue(torch.equal(resulta[0].cpu() ,			UpperCAmelCase_				)				)
								self.assertIsInstance(resulta[1] ,			UpperCAmelCase_				)
								self.assertTrue(torch.equal(resulta[1][0].cpu() ,			UpperCAmelCase_				)				)
								self.assertTrue(torch.equal(resulta[1][1].cpu() ,			UpperCAmelCase_				)				)
								self.assertEqual(resulta[2] ,			1				)

								lowerCamelCase									=send_to_device({"""a""": tensor, """b""": [tensor, tensor], """c""": 1} ,			UpperCAmelCase_				)
								self.assertIsInstance(UpperCAmelCase_ ,			UpperCAmelCase_				)
								self.assertTrue(torch.equal(resulta["""a"""].cpu() ,			UpperCAmelCase_				)				)
								self.assertIsInstance(resulta["""b"""] ,			UpperCAmelCase_				)
								self.assertTrue(torch.equal(resulta["""b"""][0].cpu() ,			UpperCAmelCase_				)				)
								self.assertTrue(torch.equal(resulta["""b"""][1].cpu() ,			UpperCAmelCase_				)				)
								self.assertEqual(resulta["""c"""] ,			1				)

								lowerCamelCase									=send_to_device(ExampleNamedTuple(a=UpperCAmelCase_ ,			b=[tensor, tensor] ,			c=1				) ,			UpperCAmelCase_				)
								self.assertIsInstance(UpperCAmelCase_ ,			UpperCAmelCase_				)
								self.assertTrue(torch.equal(resulta.a.cpu() ,			UpperCAmelCase_				)				)
								self.assertIsInstance(resulta.b ,			UpperCAmelCase_				)
								self.assertTrue(torch.equal(resulta.b[0].cpu() ,			UpperCAmelCase_				)				)
								self.assertTrue(torch.equal(resulta.b[1].cpu() ,			UpperCAmelCase_				)				)
								self.assertEqual(resulta.c ,			1				)

								lowerCamelCase									=send_to_device(UserDict({"""a""": tensor, """b""": [tensor, tensor], """c""": 1}				) ,			UpperCAmelCase_				)
								self.assertIsInstance(UpperCAmelCase_ ,			UpperCAmelCase_				)
								self.assertTrue(torch.equal(resulta["""a"""].cpu() ,			UpperCAmelCase_				)				)
								self.assertIsInstance(resulta["""b"""] ,			UpperCAmelCase_				)
								self.assertTrue(torch.equal(resulta["""b"""][0].cpu() ,			UpperCAmelCase_				)				)
								self.assertTrue(torch.equal(resulta["""b"""][1].cpu() ,			UpperCAmelCase_				)				)
								self.assertEqual(resulta["""c"""] ,			1				)


				def _snake_case							(		self				):
								with self.assertRaises(UpperCAmelCase_				) as cm:
												lowerCamelCase									=recursively_apply(torch.tensor ,			(torch.tensor(1				), 1) ,			error_on_other_type=UpperCAmelCase_				)
								self.assertEqual(
								    str(cm.exception				) ,			"""Unsupported types (<class 'int'>) passed to `tensor`. Only nested list/tuple/dicts of objects that are valid for `is_torch_tensor` should be passed.""" ,			)


				def _snake_case							(		self				):
								lowerCamelCase									=torch.tensor([1, 2, 3, 4, 5]				)
								self.assertEqual(listify(UpperCAmelCase_				) ,			[1, 2, 3, 4, 5]				)

								lowerCamelCase									=torch.tensor([[1, 2, 3, 4, 5], [6, 7, 8, 9, 10]]				)
								self.assertEqual(listify(UpperCAmelCase_				) ,			[[1, 2, 3, 4, 5], [6, 7, 8, 9, 10]]				)

								lowerCamelCase									=torch.tensor([[[1, 2, 3, 4, 5], [6, 7, 8, 9, 10]], [[11, 12, 13, 14, 15], [16, 17, 18, 19, 20]]]				)
								self.assertEqual(
								    listify(UpperCAmelCase_				) ,			[[[1, 2, 3, 4, 5], [6, 7, 8, 9, 10]], [[11, 12, 13, 14, 15], [16, 17, 18, 19, 20]]]				)


				def _snake_case							(		self				):
								with patch_environment(aa=1 ,			BB=2				):
												self.assertEqual(os.environ.get("""AA"""				) ,			"""1"""				)
												self.assertEqual(os.environ.get("""BB"""				) ,			"""2"""				)

								self.assertNotIn("""AA""" ,			os.environ				)
								self.assertNotIn("""BB""" ,			os.environ				)


				def _snake_case							(		self				):
								lowerCamelCase									=RegressionModel()
								lowerCamelCase									=model.forward
								lowerCamelCase									=convert_outputs_to_fpaa(model.forward				)
								lowerCamelCase									=extract_model_from_parallel(UpperCAmelCase_ ,			keep_fpaa_wrapper=UpperCAmelCase_				)
								lowerCamelCase									=pickle.dumps(UpperCAmelCase_				)


				@require_cuda
				def _snake_case							(		self				):
								lowerCamelCase									=RegressionModel()
								lowerCamelCase									=model.forward
								lowerCamelCase									=torch.cuda.amp.autocast(dtype=torch.floataa				)(model.forward				)
								lowerCamelCase									=convert_outputs_to_fpaa(model.forward				)
								lowerCamelCase									=extract_model_from_parallel(UpperCAmelCase_ ,			keep_fpaa_wrapper=UpperCAmelCase_				)
								lowerCamelCase									=pickle.dumps(UpperCAmelCase_				)


				@require_cuda
				@require_torch_min_version(version="""2.0"""				)
				def _snake_case							(		self				):
								lowerCamelCase									=RegressionModel()
								lowerCamelCase									=model.forward
								lowerCamelCase									=torch.cuda.amp.autocast(dtype=torch.floataa				)(model.forward				)
								lowerCamelCase									=convert_outputs_to_fpaa(model.forward				)
								lowerCamelCase									=torch.compile(model.forward ,			backend="""inductor"""				)
								lowerCamelCase									=torch.randn(4 ,			10				).cuda()
								lowerCamelCase									=model(UpperCAmelCase_				)


				def _snake_case							(		self				):
								lowerCamelCase									=RegressionModel()
								# could also do a test with DistributedDataParallel, but difficult to run on CPU or single GPU
								lowerCamelCase									=torch.nn.parallel.DataParallel(UpperCAmelCase_				)
								lowerCamelCase									=extract_model_from_parallel(UpperCAmelCase_				)

								self.assertEqual(UpperCAmelCase_ ,			UpperCAmelCase_				)


				@require_torch_min_version(version="""2.0"""				)
				def _snake_case							(		self				):
								lowerCamelCase									=RegressionModel()
								lowerCamelCase									=torch.compile(UpperCAmelCase_				)

								# could also do a test with DistributedDataParallel, but difficult to run on CPU or single GPU
								lowerCamelCase									=torch.nn.parallel.DataParallel(UpperCAmelCase_				)
								lowerCamelCase									=torch.compile(UpperCAmelCase_				)
								lowerCamelCase									=extract_model_from_parallel(UpperCAmelCase_				)

								self.assertEqual(compiled_model._orig_mod ,			compiled_model_unwrapped._orig_mod				)


				def _snake_case							(		self				):
								self.assertEqual(find_device([1, """a""", torch.tensor([1, 2, 3]				)]				) ,			torch.device("""cpu"""				)				)
								self.assertEqual(find_device({"""a""": 1, """b""": torch.tensor([1, 2, 3]				)}				) ,			torch.device("""cpu"""				)				)
								self.assertIsNone(find_device([1, """a"""]				)				)





