

from __future__ import annotations

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

_UpperCamelCase     =    {
    '''A''': ['''B''', '''C'''],
    '''B''': ['''A''', '''D''', '''E'''],
    '''C''': ['''A''', '''F'''],
    '''D''': ['''B'''],
    '''E''': ['''B''', '''F'''],
    '''F''': ['''C''', '''E'''],
}
def 		UpperCamelCase_(    snake_case__:						dict						,					snake_case__:						str     ) ->				list[str]:
 UpperCAmelCase__           =       {start}
 UpperCAmelCase__           =       [start]
 UpperCAmelCase__           =       Queue()
 queue.put(snake_case__     )
 while not queue.empty():
  UpperCAmelCase__           =       queue.get()
  for w in graph[v]:
   if w not in explored:
    explored.add(snake_case__     )
    result.append(snake_case__     )
    queue.put(snake_case__     )
 return result
def 		UpperCamelCase_(    snake_case__:						dict						,					snake_case__:						str     ) ->				list[str]:
 UpperCAmelCase__           =       {start}
 UpperCAmelCase__           =       [start]
 UpperCAmelCase__           =       deque([start]     )
 while queue:
  UpperCAmelCase__           =       queue.popleft()
  for child in graph[v]:
   if child not in visited:
    visited.add(snake_case__     )
    result.append(snake_case__     )
    queue.append(snake_case__     )
 return result
def 		UpperCamelCase_(    snake_case__:						str     ) ->				None:
 UpperCAmelCase__           =       f"from __main__ import G, {name}"
 UpperCAmelCase__           =       1_00_00
 UpperCAmelCase__           =       timeit(f"{name}(G, 'A')"						,					setup=snake_case__						,					number=snake_case__     )
 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 random
import unittest

import numpy as np

from transformers.testing_utils import require_torch, require_vision
from transformers.utils import is_torch_available, is_vision_available

from ...test_image_processing_common import ImageProcessingSavingTestMixin, prepare_image_inputs


if is_torch_available():
 import torch

if is_vision_available():
 import PIL

 from transformers import FlavaImageProcessor
 from transformers.image_utils import PILImageResampling
 from transformers.models.flava.image_processing_flava import (
     FLAVA_CODEBOOK_MEAN,
     FLAVA_CODEBOOK_STD,
     FLAVA_IMAGE_MEAN,
     FLAVA_IMAGE_STD,
 )
else:
 _UpperCamelCase     =    _UpperCamelCase     =    _UpperCamelCase     =    _UpperCamelCase     =    None



class 					lowercase		( unittest.TestCase      ):



 '''simple docstring'''


 def __init__(self , __a , __a=7 , __a=3 , __a=30 , __a=400 , __a=True , __a=None , __a=True , __a=None , __a=None , __a=True , __a=1 / 255 , __a=True , __a=FLAVA_IMAGE_MEAN , __a=FLAVA_IMAGE_STD , __a=14 , __a=75 , __a=None , __a=16 , __a=0.3 , __a=None , __a=True , __a=None , __a=None , __a=True , __a=None , __a=True , __a=True , __a=FLAVA_CODEBOOK_MEAN , __a=FLAVA_CODEBOOK_STD , )				->      Optional[int]:






  """simple docstring"""





  UpperCAmelCase__           =       size if size is not None else {'height': 224, 'width': 224}
  UpperCAmelCase__           =       crop_size if crop_size is not None else {'height': 224, 'width': 224}
  UpperCAmelCase__           =       codebook_size if codebook_size is not None else {'height': 112, 'width': 112}
  UpperCAmelCase__           =       codebook_crop_size if codebook_crop_size is not None else {'height': 112, 'width': 112}

  UpperCAmelCase__           =       parent
  UpperCAmelCase__           =       batch_size
  UpperCAmelCase__           =       num_channels
  UpperCAmelCase__           =       do_resize
  UpperCAmelCase__           =       do_rescale
  UpperCAmelCase__           =       rescale_factor
  UpperCAmelCase__           =       min_resolution
  UpperCAmelCase__           =       max_resolution
  UpperCAmelCase__           =       size
  UpperCAmelCase__           =       resample if resample is not None else PILImageResampling.BICUBIC
  UpperCAmelCase__           =       do_normalize
  UpperCAmelCase__           =       image_mean
  UpperCAmelCase__           =       image_std
  UpperCAmelCase__           =       do_center_crop
  UpperCAmelCase__           =       crop_size

  UpperCAmelCase__           =       input_size_patches
  UpperCAmelCase__           =       total_mask_patches
  UpperCAmelCase__           =       mask_group_max_patches
  UpperCAmelCase__           =       mask_group_min_patches
  UpperCAmelCase__           =       mask_group_min_aspect_ratio
  UpperCAmelCase__           =       mask_group_max_aspect_ratio

  UpperCAmelCase__           =       codebook_do_resize
  UpperCAmelCase__           =       codebook_size
  UpperCAmelCase__           =       codebook_resample if codebook_resample is not None else PILImageResampling.LANCZOS
  UpperCAmelCase__           =       codebook_do_center_crop
  UpperCAmelCase__           =       codebook_crop_size
  UpperCAmelCase__           =       codebook_do_map_pixels
  UpperCAmelCase__           =       codebook_do_normalize
  UpperCAmelCase__           =       codebook_image_mean
  UpperCAmelCase__           =       codebook_image_std




 def 						UpperCamelCase__							(self				)				->      Any:






  """simple docstring"""





  return {
      "image_mean": self.image_mean,
      "image_std": self.image_std,
      "do_normalize": self.do_normalize,
      "do_resize": self.do_resize,
      "size": self.size,
      "resample": self.resample,
      "do_rescale": self.do_rescale,
      "rescale_factor": self.rescale_factor,
      "do_center_crop": self.do_center_crop,
      "crop_size": self.crop_size,
      "input_size_patches": self.input_size_patches,
      "total_mask_patches": self.total_mask_patches,
      "mask_group_max_patches": self.mask_group_max_patches,
      "mask_group_min_patches": self.mask_group_min_patches,
      "mask_group_min_aspect_ratio": self.mask_group_min_aspect_ratio,
      "mask_group_max_aspect_ratio": self.mask_group_min_aspect_ratio,
      "codebook_do_resize": self.codebook_do_resize,
      "codebook_size": self.codebook_size,
      "codebook_resample": self.codebook_resample,
      "codebook_do_center_crop": self.codebook_do_center_crop,
      "codebook_crop_size": self.codebook_crop_size,
      "codebook_do_map_pixels": self.codebook_do_map_pixels,
      "codebook_do_normalize": self.codebook_do_normalize,
      "codebook_image_mean": self.codebook_image_mean,
      "codebook_image_std": self.codebook_image_std,
  }




 def 						UpperCamelCase__							(self				)				->      int:






  """simple docstring"""





  return (self.size["height"], self.size["width"])




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






  """simple docstring"""





  return (
      (self.input_size_patches, self.input_size_patches)
      if not isinstance(self.input_size_patches , __a				)
      else self.input_size_patches
  )




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






  """simple docstring"""





  return (self.codebook_size["height"], self.codebook_size["width"])







@require_torch
@require_vision
class 					lowercase		( _UpperCamelCase				,       unittest.TestCase      ):



 '''simple docstring'''


 __SCREAMING_SNAKE_CASE      							=       FlavaImageProcessor if is_vision_available() else None
 __SCREAMING_SNAKE_CASE      							=       None




 def 						UpperCamelCase__							(self				)				->      Tuple:






  """simple docstring"""





  UpperCAmelCase__           =       FlavaImageProcessingTester(self				)




 @property
 def 						UpperCamelCase__							(self				)				->      Dict:






  """simple docstring"""





  return self.image_processor_tester.prepare_image_processor_dict()




 def 						UpperCamelCase__							(self				)				->      int:






  """simple docstring"""





  UpperCAmelCase__           =       self.image_processing_class(**self.image_processor_dict				)
  self.assertTrue(hasattr(__a , 'image_mean'				)				)
  self.assertTrue(hasattr(__a , 'image_std'				)				)
  self.assertTrue(hasattr(__a , 'do_normalize'				)				)
  self.assertTrue(hasattr(__a , 'do_resize'				)				)
  self.assertTrue(hasattr(__a , 'resample'				)				)
  self.assertTrue(hasattr(__a , 'crop_size'				)				)
  self.assertTrue(hasattr(__a , 'do_center_crop'				)				)
  self.assertTrue(hasattr(__a , 'do_rescale'				)				)
  self.assertTrue(hasattr(__a , 'rescale_factor'				)				)
  self.assertTrue(hasattr(__a , 'masking_generator'				)				)
  self.assertTrue(hasattr(__a , 'codebook_do_resize'				)				)
  self.assertTrue(hasattr(__a , 'codebook_size'				)				)
  self.assertTrue(hasattr(__a , 'codebook_resample'				)				)
  self.assertTrue(hasattr(__a , 'codebook_do_center_crop'				)				)
  self.assertTrue(hasattr(__a , 'codebook_crop_size'				)				)
  self.assertTrue(hasattr(__a , 'codebook_do_map_pixels'				)				)
  self.assertTrue(hasattr(__a , 'codebook_do_normalize'				)				)
  self.assertTrue(hasattr(__a , 'codebook_image_mean'				)				)
  self.assertTrue(hasattr(__a , 'codebook_image_std'				)				)




 def 						UpperCamelCase__							(self				)				->      Tuple:






  """simple docstring"""





  UpperCAmelCase__           =       self.image_processing_class.from_dict(self.image_processor_dict				)
  self.assertEqual(image_processor.size , {'height': 224, 'width': 224}				)
  self.assertEqual(image_processor.crop_size , {'height': 224, 'width': 224}				)
  self.assertEqual(image_processor.codebook_size , {'height': 112, 'width': 112}				)
  self.assertEqual(image_processor.codebook_crop_size , {'height': 112, 'width': 112}				)

  UpperCAmelCase__           =       self.image_processing_class.from_dict(
      self.image_processor_dict , size=42 , crop_size=84 , codebook_size=33 , codebook_crop_size=66				)
  self.assertEqual(image_processor.size , {'height': 42, 'width': 42}				)
  self.assertEqual(image_processor.crop_size , {'height': 84, 'width': 84}				)
  self.assertEqual(image_processor.codebook_size , {'height': 33, 'width': 33}				)
  self.assertEqual(image_processor.codebook_crop_size , {'height': 66, 'width': 66}				)




 def 						UpperCamelCase__							(self				)				->      Any:






  """simple docstring"""





  pass




 def 						UpperCamelCase__							(self				)				->      List[Any]:






  """simple docstring"""





  UpperCAmelCase__           =       self.image_processing_class(**self.image_processor_dict				)
  # create random PIL images
  UpperCAmelCase__           =       prepare_image_inputs(self.image_processor_tester , equal_resolution=__a				)
  for image in image_inputs:
   self.assertIsInstance(__a , PIL.Image.Image				)

  # Test not batched input
  UpperCAmelCase__           =       image_processing(image_inputs[0] , return_tensors='pt'				)

  # Test no bool masked pos
  self.assertFalse('bool_masked_pos' in encoded_images				)

  UpperCAmelCase__       ,					UpperCAmelCase__           =       self.image_processor_tester.get_expected_image_size()

  self.assertEqual(
      encoded_images.pixel_values.shape , (1, self.image_processor_tester.num_channels, expected_height, expected_width) , )

  # Test batched
  UpperCAmelCase__           =       image_processing(__a , return_tensors='pt'				)
  UpperCAmelCase__       ,					UpperCAmelCase__           =       self.image_processor_tester.get_expected_image_size()

  # Test no bool masked pos
  self.assertFalse('bool_masked_pos' in encoded_images				)

  self.assertEqual(
      encoded_images.pixel_values.shape , (
          self.image_processor_tester.batch_size,
          self.image_processor_tester.num_channels,
          expected_height,
          expected_width,
      ) , )




 def 						UpperCamelCase__							(self , __a , __a				)				->      Any:






  """simple docstring"""





  UpperCAmelCase__           =       self.image_processing_class(**self.image_processor_dict				)
  # create random tensors
  UpperCAmelCase__           =       prepare_image_inputs(self.image_processor_tester , equal_resolution=__a , **__a				)
  for image in image_inputs:
   self.assertIsInstance(__a , __a				)

  # Test not batched input
  UpperCAmelCase__           =       image_processing(image_inputs[0] , return_tensors='pt'				)

  UpperCAmelCase__       ,					UpperCAmelCase__           =       self.image_processor_tester.get_expected_image_size()
  self.assertEqual(
      encoded_images.pixel_values.shape , (1, self.image_processor_tester.num_channels, expected_height, expected_width) , )

  UpperCAmelCase__           =       image_processing(__a , return_image_mask=__a , return_tensors='pt'				)

  UpperCAmelCase__       ,					UpperCAmelCase__           =       self.image_processor_tester.get_expected_image_size()
  self.assertEqual(
      encoded_images.pixel_values.shape , (
          self.image_processor_tester.batch_size,
          self.image_processor_tester.num_channels,
          expected_height,
          expected_width,
      ) , )

  UpperCAmelCase__       ,					UpperCAmelCase__           =       self.image_processor_tester.get_expected_mask_size()
  self.assertEqual(
      encoded_images.bool_masked_pos.shape , (
          self.image_processor_tester.batch_size,
          expected_height,
          expected_width,
      ) , )

  # Test batched
  UpperCAmelCase__           =       image_processing(__a , return_tensors='pt'				).pixel_values

  UpperCAmelCase__       ,					UpperCAmelCase__           =       self.image_processor_tester.get_expected_image_size()
  self.assertEqual(
      encoded_images.shape , (
          self.image_processor_tester.batch_size,
          self.image_processor_tester.num_channels,
          expected_height,
          expected_width,
      ) , )

  # Test masking
  UpperCAmelCase__           =       image_processing(__a , return_image_mask=__a , return_tensors='pt'				)

  UpperCAmelCase__       ,					UpperCAmelCase__           =       self.image_processor_tester.get_expected_image_size()
  self.assertEqual(
      encoded_images.pixel_values.shape , (
          self.image_processor_tester.batch_size,
          self.image_processor_tester.num_channels,
          expected_height,
          expected_width,
      ) , )

  UpperCAmelCase__       ,					UpperCAmelCase__           =       self.image_processor_tester.get_expected_mask_size()
  self.assertEqual(
      encoded_images.bool_masked_pos.shape , (
          self.image_processor_tester.batch_size,
          expected_height,
          expected_width,
      ) , )




 def 						UpperCamelCase__							(self				)				->      Dict:






  """simple docstring"""





  self._test_call_framework(np.ndarray , prepare_kwargs={'numpify': True}				)




 def 						UpperCamelCase__							(self				)				->      int:






  """simple docstring"""





  self._test_call_framework(torch.Tensor , prepare_kwargs={'torchify': True}				)




 def 						UpperCamelCase__							(self				)				->      Dict:






  """simple docstring"""





  random.seed(1234				)
  UpperCAmelCase__           =       self.image_processing_class(**self.image_processor_dict				)
  UpperCAmelCase__           =       prepare_image_inputs(self.image_processor_tester , equal_resolution=__a , torchify=__a				)

  # Test not batched input
  UpperCAmelCase__           =       image_processing(image_inputs[0] , return_image_mask=__a , return_tensors='pt'				)
  self.assertEqual(encoded_images.bool_masked_pos.sum().item() , 75				)




 def 						UpperCamelCase__							(self				)				->      Optional[int]:






  """simple docstring"""





  UpperCAmelCase__           =       self.image_processing_class(**self.image_processor_dict				)
  # create random PIL images
  UpperCAmelCase__           =       prepare_image_inputs(self.image_processor_tester , equal_resolution=__a				)
  for image in image_inputs:
   self.assertIsInstance(__a , PIL.Image.Image				)

  # Test not batched input
  UpperCAmelCase__           =       image_processing(image_inputs[0] , return_codebook_pixels=__a , return_tensors='pt'				)
  UpperCAmelCase__       ,					UpperCAmelCase__           =       self.image_processor_tester.get_expected_codebook_image_size()
  self.assertEqual(
      encoded_images.codebook_pixel_values.shape , (1, self.image_processor_tester.num_channels, expected_height, expected_width) , )

  # Test batched
  UpperCAmelCase__           =       image_processing(__a , return_codebook_pixels=__a , return_tensors='pt'				)
  UpperCAmelCase__       ,					UpperCAmelCase__           =       self.image_processor_tester.get_expected_codebook_image_size()
  self.assertEqual(
      encoded_images.codebook_pixel_values.shape , (
          self.image_processor_tester.batch_size,
          self.image_processor_tester.num_channels,
          expected_height,
          expected_width,
      ) , )



