




"""simple docstring"""


import inspect
import logging
import os
import random
import shutil
import tempfile
import unittest

import pytest
import torch
from torch import nn
from torch.utils.data import DataLoader, TensorDataset

from accelerate import Accelerator
from accelerate.test_utils import execute_subprocess_async, require_cuda
from accelerate.utils import ProjectConfiguration, set_seed


A_						=				logging.getLogger(__name__)


def 					UpperCAmelCase__       (snake_case__							:					str=2		,   snake_case__							:					Dict=3		,   snake_case__							:					str=16		,   snake_case__							:					Union[str, Any] = 10		,   snake_case__							:					Optional[Any] = 2    ):
  """simple docstring"""

  def get_dataset(snake_case__							:					Tuple    ):
    _snake_case							:		str								=  torch.randn(batch_size * n_batches		,   1    )
    return TensorDataset(__snake_case		,   a * x + b + 0.1 * torch.randn(batch_size * n_batches		,   1    )    )

  _snake_case							:		Optional[int]								=  get_dataset(__snake_case    )
  _snake_case							:		Dict								=  get_dataset(__snake_case    )
  _snake_case							:		Dict								=  DataLoader(__snake_case		,   shuffle=__snake_case		,   batch_size=__snake_case		,   num_workers=4    )
  _snake_case							:		Any								=  DataLoader(__snake_case		,   shuffle=__snake_case		,   batch_size=__snake_case		,   num_workers=4    )
  return (train_dataloader, valid_dataloader)


def 					UpperCAmelCase__       (snake_case__							:					str		,   snake_case__							:					Any		,   snake_case__							:					List[Any]		,   snake_case__							:					Optional[int]		,   snake_case__							:					int		,   snake_case__							:					Union[str, Any]=None    ):
  """simple docstring"""

  _snake_case							:		Optional[int]								=  []
  for epoch in range(__snake_case    ):
    # Train quickly
    model.train()
    for batch in dataloader:
      _snake_case		,					_snake_case							:		Union[str, Any]								=  batch
      _snake_case							:		List[str]								=  model(__snake_case    )
      _snake_case							:		List[Any]								=  torch.nn.functional.mse_loss(__snake_case		,   __snake_case    )
      accelerator.backward(__snake_case    )
      optimizer.step()
      optimizer.zero_grad()
    rands.append(random.random()    )  # Introduce some randomness
    if scheduler is not None:
      scheduler.step()
  return rands






class 					lowercase(     nn.Module ):







 '''simple docstring'''





 def __init__(				self:		Optional[int]		):




   '''simple docstring'''



   super().__init__()
   _snake_case							:		Dict								=  nn.Parameter(torch.randn(1		)		)
   _snake_case							:		Optional[int]								=  nn.Parameter(torch.randn(1		)		)


 def  UpperCamelCase_   (				self:		Dict,      a_:		Optional[Any]		):




   '''simple docstring'''



   return x * self.a + self.b







class 					lowercase(     unittest.TestCase ):







 '''simple docstring'''





 def  UpperCamelCase_   (				self:		str		):




   '''simple docstring'''



   with tempfile.TemporaryDirectory() as tmpdir:
     set_seed(42		)
     _snake_case							:		Union[str, Any]								=  DummyModel()
     _snake_case							:		Tuple								=  torch.optim.Adam(params=model.parameters(),      lr=1E-3		)
     _snake_case		,					_snake_case							:		int								=  dummy_dataloaders()
     _snake_case							:		Optional[int]								=  ProjectConfiguration(total_limit=1,      project_dir=__a,      automatic_checkpoint_naming=__a		)
     # Train baseline
     _snake_case							:		Any								=  Accelerator(project_config=__a		)
     _snake_case		,					_snake_case		,					_snake_case		,					_snake_case							:		Union[str, Any]								=  accelerator.prepare(
         __a,      __a,      __a,      __a		)
     # Save initial
     accelerator.save_state()

     # Save second state
     accelerator.save_state()
     self.assertEqual(len(os.listdir(accelerator.project_dir		)		),      1		)


 def  UpperCamelCase_   (				self:		Tuple		):




   '''simple docstring'''



   with tempfile.TemporaryDirectory() as tmpdir:
     set_seed(42		)
     _snake_case							:		Dict								=  DummyModel()
     _snake_case							:		Optional[int]								=  torch.optim.Adam(params=model.parameters(),      lr=1E-3		)
     _snake_case		,					_snake_case							:		List[str]								=  dummy_dataloaders()
     # Train baseline
     _snake_case							:		List[Any]								=  Accelerator()
     _snake_case		,					_snake_case		,					_snake_case		,					_snake_case							:		Dict								=  accelerator.prepare(
         __a,      __a,      __a,      __a		)
     # Save initial
     _snake_case							:		Any								=  os.path.join(__a,      """initial"""		)
     accelerator.save_state(__a		)
     ((_snake_case)		,					(_snake_case))							:		str								=  model.a.item(), model.b.item()
     _snake_case							:		int								=  optimizer.state_dict()
     _snake_case							:		Optional[int]								=  train(3,      __a,      __a,      __a,      __a		)
     ((_snake_case)		,					(_snake_case))							:		int								=  model.a.item(), model.b.item()
     _snake_case							:		Tuple								=  optimizer.state_dict()

     # Train partially
     set_seed(42		)
     _snake_case							:		Tuple								=  DummyModel()
     _snake_case							:		Union[str, Any]								=  torch.optim.Adam(params=model.parameters(),      lr=1E-3		)
     _snake_case		,					_snake_case							:		Tuple								=  dummy_dataloaders()
     _snake_case							:		Any								=  Accelerator()
     _snake_case		,					_snake_case		,					_snake_case		,					_snake_case							:		Any								=  accelerator.prepare(
         __a,      __a,      __a,      __a		)
     accelerator.load_state(__a		)
     ((_snake_case)		,					(_snake_case))							:		List[Any]								=  model.a.item(), model.b.item()
     _snake_case							:		List[Any]								=  optimizer.state_dict()
     self.assertEqual(__a,      __a		)
     self.assertEqual(__a,      __a		)
     self.assertEqual(__a,      __a		)

     _snake_case							:		int								=  train(2,      __a,      __a,      __a,      __a		)
     # Save everything
     _snake_case							:		Union[str, Any]								=  os.path.join(__a,      """checkpoint"""		)
     accelerator.save_state(__a		)

     # Load everything back in and make sure all states work
     accelerator.load_state(__a		)
     test_rands += train(1,      __a,      __a,      __a,      __a		)
     ((_snake_case)		,					(_snake_case))							:		Union[str, Any]								=  model.a.item(), model.b.item()
     _snake_case							:		str								=  optimizer.state_dict()
     self.assertEqual(__a,      __a		)
     self.assertEqual(__a,      __a		)
     self.assertEqual(__a,      __a		)
     self.assertEqual(__a,      __a		)


 def  UpperCamelCase_   (				self:		Tuple		):




   '''simple docstring'''



   with tempfile.TemporaryDirectory() as tmpdir:
     set_seed(42		)
     _snake_case							:		int								=  DummyModel()
     _snake_case							:		Optional[Any]								=  torch.optim.Adam(params=model.parameters(),      lr=1E-3		)
     _snake_case		,					_snake_case							:		List[str]								=  dummy_dataloaders()
     _snake_case							:		Tuple								=  ProjectConfiguration(automatic_checkpoint_naming=__a		)

     # Train baseline
     _snake_case							:		Dict								=  Accelerator(project_dir=__a,      project_config=__a		)
     _snake_case		,					_snake_case		,					_snake_case		,					_snake_case							:		List[str]								=  accelerator.prepare(
         __a,      __a,      __a,      __a		)
     # Save initial
     accelerator.save_state()
     ((_snake_case)		,					(_snake_case))							:		Dict								=  model.a.item(), model.b.item()
     _snake_case							:		Dict								=  optimizer.state_dict()
     _snake_case							:		int								=  train(3,      __a,      __a,      __a,      __a		)
     ((_snake_case)		,					(_snake_case))							:		str								=  model.a.item(), model.b.item()
     _snake_case							:		Optional[int]								=  optimizer.state_dict()

     # Train partially
     set_seed(42		)
     _snake_case							:		str								=  DummyModel()
     _snake_case							:		List[str]								=  torch.optim.Adam(params=model.parameters(),      lr=1E-3		)
     _snake_case		,					_snake_case							:		Optional[Any]								=  dummy_dataloaders()
     _snake_case							:		Optional[Any]								=  ProjectConfiguration(iteration=1,      automatic_checkpoint_naming=__a		)
     _snake_case							:		int								=  Accelerator(project_dir=__a,      project_config=__a		)
     _snake_case		,					_snake_case		,					_snake_case		,					_snake_case							:		List[str]								=  accelerator.prepare(
         __a,      __a,      __a,      __a		)
     accelerator.load_state(os.path.join(__a,      """checkpoints""",      """checkpoint_0"""		)		)
     ((_snake_case)		,					(_snake_case))							:		Dict								=  model.a.item(), model.b.item()
     _snake_case							:		str								=  optimizer.state_dict()
     self.assertEqual(__a,      __a		)
     self.assertEqual(__a,      __a		)
     self.assertEqual(__a,      __a		)

     _snake_case							:		Dict								=  train(2,      __a,      __a,      __a,      __a		)
     # Save everything
     accelerator.save_state()

     # Load everything back in and make sure all states work
     accelerator.load_state(os.path.join(__a,      """checkpoints""",      """checkpoint_1"""		)		)
     test_rands += train(1,      __a,      __a,      __a,      __a		)
     ((_snake_case)		,					(_snake_case))							:		Dict								=  model.a.item(), model.b.item()
     _snake_case							:		int								=  optimizer.state_dict()
     self.assertEqual(__a,      __a		)
     self.assertEqual(__a,      __a		)
     self.assertEqual(__a,      __a		)
     self.assertEqual(__a,      __a		)


 def  UpperCamelCase_   (				self:		Tuple		):




   '''simple docstring'''



   _snake_case							:		Optional[Any]								=  torch.tensor([1, 2, 3]		)
   _snake_case							:		int								=  torch.tensor([2, 3, 4]		)
   _snake_case							:		Any								=  DummyModel()
   _snake_case							:		Tuple								=  torch.optim.Adam(net.parameters()		)
   _snake_case							:		Optional[Any]								=  Accelerator()
   with self.assertRaises(__a		) as ve:
     accelerator.register_for_checkpointing(__a,      __a,      __a,      __a		)
   _snake_case							:		Dict								=  str(ve.exception		)
   self.assertTrue("""Item at index 0""" in message		)
   self.assertTrue("""Item at index 1""" in message		)
   self.assertFalse("""Item at index 2""" in message		)
   self.assertFalse("""Item at index 3""" in message		)


 def  UpperCamelCase_   (				self:		Optional[int]		):




   '''simple docstring'''



   with tempfile.TemporaryDirectory() as tmpdir:
     set_seed(42		)
     _snake_case							:		Any								=  DummyModel()
     _snake_case							:		List[Any]								=  torch.optim.Adam(params=model.parameters(),      lr=1E-3		)
     _snake_case							:		int								=  torch.optim.lr_scheduler.StepLR(__a,      step_size=1,      gamma=0.99		)
     _snake_case		,					_snake_case							:		Union[str, Any]								=  dummy_dataloaders()
     _snake_case							:		int								=  ProjectConfiguration(automatic_checkpoint_naming=__a		)
     # Train baseline
     _snake_case							:		Optional[int]								=  Accelerator(project_dir=__a,      project_config=__a		)
     _snake_case		,					_snake_case		,					_snake_case		,					_snake_case		,					_snake_case							:		Dict								=  accelerator.prepare(
         __a,      __a,      __a,      __a,      __a		)
     # Save initial
     accelerator.save_state()
     _snake_case							:		Optional[int]								=  scheduler.state_dict()
     train(3,      __a,      __a,      __a,      __a,      __a		)
     self.assertNotEqual(__a,      scheduler.state_dict()		)

     # Load everything back in and make sure all states work
     accelerator.load_state(os.path.join(__a,      """checkpoints""",      """checkpoint_0"""		)		)
     self.assertEqual(__a,      scheduler.state_dict()		)


 def  UpperCamelCase_   (				self:		int		):




   '''simple docstring'''



   with tempfile.TemporaryDirectory() as tmpdir:
     set_seed(42		)
     _snake_case							:		Optional[int]								=  DummyModel()
     _snake_case							:		Optional[int]								=  ProjectConfiguration(automatic_checkpoint_naming=__a,      total_limit=2		)
     # Train baseline
     _snake_case							:		str								=  Accelerator(project_dir=__a,      project_config=__a		)
     _snake_case							:		Any								=  accelerator.prepare(__a		)
     # Save 3 states:
     for _ in range(11		):
       accelerator.save_state()
     self.assertTrue(not os.path.exists(os.path.join(__a,      """checkpoints""",      """checkpoint_0"""		)		)		)
     self.assertTrue(os.path.exists(os.path.join(__a,      """checkpoints""",      """checkpoint_9"""		)		)		)
     self.assertTrue(os.path.exists(os.path.join(__a,      """checkpoints""",      """checkpoint_10"""		)		)		)


 @require_cuda
 def  UpperCamelCase_   (				self:		Dict		):




   '''simple docstring'''



   _snake_case							:		str								=  ["""torchrun""", f"--nproc_per_node={torch.cuda.device_count()}", inspect.getfile(self.__class__		)]
   execute_subprocess_async(__a,      env=os.environ.copy()		)


if __name__ == "__main__":
     A_						=				'''/tmp/accelerate/state_checkpointing'''
     A_						=				DummyModel()
     A_						=				torch.optim.Adam(params=model.parameters(), lr=1E-3)
     A_						=				torch.optim.lr_scheduler.StepLR(optimizer, step_size=1, gamma=0.99)
     A_	,    A_						=				dummy_dataloaders()
     A_						=				ProjectConfiguration(automatic_checkpoint_naming=True)
     # Train baseline
     A_						=				Accelerator(project_dir=savedir, project_config=project_config, mixed_precision='''no''')
     if accelerator.process_index == 0:
          if os.path.exists(savedir):
               shutil.rmtree(savedir)
          os.makedirs(savedir)
     A_	,    A_	,    A_	,    A_	,    A_						=				accelerator.prepare(
         model, optimizer, train_dataloader, valid_dataloader, scheduler
     )
     A_	,    A_						=				accelerator.prepare(model, optimizer)
     train(3, model, train_dataloader, optimizer, accelerator, scheduler)
     # Check that the intial optimizer is loaded on the GPU
     for group in optimizer.param_groups:
          A_						=				group['''params'''][0].device
          break
     assert param_device.type == accelerator.device.type
     A_						=				model.cpu()
     accelerator.wait_for_everyone()
     accelerator.save_state()
     accelerator.wait_for_everyone()

     # Check CPU state
     accelerator.load_state(os.path.join(savedir, '''checkpoints''', '''checkpoint_0'''), map_location='''cpu''')
     for group in optimizer.param_groups:
          A_						=				group['''params'''][0].device
          break
     assert (
         param_device.type == torch.device('''cpu''').type
     ), F"Loaded optimizer states did not match, expected to be loaded on the CPU but got {param_device}"

     # Check device state
     model.to(accelerator.device)
     accelerator.load_state(os.path.join(savedir, '''checkpoints''', '''checkpoint_0'''), map_location='''on_device''')
     for group in optimizer.param_groups:
          A_						=				group['''params'''][0].device
          break
     assert (
         param_device.type == accelerator.device.type
     ), F"Loaded optimizer states did not match, expected to be loaded on {accelerator.device} but got {param_device}"

     # Check error
     with pytest.raises(TypeError, match='''Unsupported optimizer map location passed'''):
          accelerator.load_state(os.path.join(savedir, '''checkpoints''', '''checkpoint_0'''), map_location='''invalid''')
     accelerator.wait_for_everyone()
     if accelerator.process_index == 0:
          shutil.rmtree(savedir)
     accelerator.wait_for_everyone()




"""simple docstring"""





class     _UpperCAmelCase:



		def __init__(					self)       ->       Optional[Any]:






							'''simple docstring'''
							_UpperCamelCase							 =  {}



		def 						UpperCAmelCase							(					self)       ->       None:






							'''simple docstring'''
							print(self.vertex)
							for i in self.vertex:
												print(__a				,		''' -> '''				,		''' -> '''.join([str(__a) for j in self.vertex[i]]))



		def 						UpperCAmelCase							(					self				,		__a				,		__a)       ->       None:






							'''simple docstring'''
							# check if vertex is already present,
							if from_vertex in self.vertex:
												self.vertex[from_vertex].append(__a)
							else:
												# else make a new vertex
												_UpperCamelCase							 =  [to_vertex]



		def 						UpperCAmelCase							(					self)       ->       None:






							'''simple docstring'''
							# visited array for storing already visited nodes
							_UpperCamelCase							 =  [False] * len(self.vertex)

							# call the recursive helper function
							for i in range(len(self.vertex)):
												if not visited[i]:
																	self.dfs_recursive(__a				,		__a)




		def 						UpperCAmelCase							(					self				,		__a				,		__a)       ->       None:






							'''simple docstring'''
							# mark start vertex as visited
							_UpperCamelCase							 =  True

							print(__a				,		end=''' ''')

							# Recur for all the vertices that are adjacent to this node
							for i in self.vertex:
												if not visited[i]:
																	self.dfs_recursive(__a				,		__a)


if __name__ == "__main__":
				_a														=		Graph()
				g.add_edge(0, 1)
				g.add_edge(0, 2)
				g.add_edge(1, 2)
				g.add_edge(2, 0)
				g.add_edge(2, 3)
				g.add_edge(3, 3)

				g.print_graph()
				print("""DFS:""")
				g.dfs()

				# OUTPUT:
				# 0  ->  1 -> 2
				# 1  ->  2
				# 2  ->  0 -> 3
				# 3  ->  3
				# DFS:
				#  0 1 2 3






