


"""simple docstring"""







from typing import Dict, Iterable, Optional, Union

import numpy as np

from ...image_processing_utils import BaseImageProcessor, BatchFeature, get_size_dict
from ...image_transforms import normalize, rescale, resize, to_channel_dimension_format, to_pil_image
from ...image_utils import (
    IMAGENET_STANDARD_MEAN,
    IMAGENET_STANDARD_STD,
    ChannelDimension,
    ImageInput,
    PILImageResampling,
    make_list_of_images,
    to_numpy_array,
    valid_images,
)
from ...utils import TensorType, is_pytesseract_available, is_vision_available, logging, requires_backends


if is_vision_available():
		import PIL

# soft dependency
if is_pytesseract_available():
		import pytesseract

a__    :							int            =					logging.get_logger(__name__)




def        UpperCAmelCase__	(lowerCAmelCase_  ,						lowerCAmelCase_  ,						lowerCAmelCase_       ):




					'''simple docstring'''


					return [
					    int(1000 * (box[0] / width)       ),
					    int(1000 * (box[1] / height)       ),
					    int(1000 * (box[2] / width)       ),
					    int(1000 * (box[3] / height)       ),
					]




def        UpperCAmelCase__	(lowerCAmelCase_  ,						lowerCAmelCase_  ,						lowerCAmelCase_       ):




					'''simple docstring'''


					__SCREAMING_SNAKE_CASE						       =    to_pil_image(lowerCAmelCase_       )
					__SCREAMING_SNAKE_CASE       ,  __SCREAMING_SNAKE_CASE						       =    pil_image.size
					__SCREAMING_SNAKE_CASE						       =    pytesseract.image_to_data(lowerCAmelCase_  ,						lang=lowerCAmelCase_  ,						output_type="dict"  ,						config=lowerCAmelCase_       )
					__SCREAMING_SNAKE_CASE       ,  __SCREAMING_SNAKE_CASE       ,  __SCREAMING_SNAKE_CASE       ,  __SCREAMING_SNAKE_CASE       ,  __SCREAMING_SNAKE_CASE						       =    data["text"], data["left"], data["top"], data["width"], data["height"]

					# filter empty words and corresponding coordinates
					__SCREAMING_SNAKE_CASE						       =    [idx for idx, word in enumerate(lowerCAmelCase_       ) if not word.strip()]
					__SCREAMING_SNAKE_CASE						       =    [word for idx, word in enumerate(lowerCAmelCase_       ) if idx not in irrelevant_indices]
					__SCREAMING_SNAKE_CASE						       =    [coord for idx, coord in enumerate(lowerCAmelCase_       ) if idx not in irrelevant_indices]
					__SCREAMING_SNAKE_CASE						       =    [coord for idx, coord in enumerate(lowerCAmelCase_       ) if idx not in irrelevant_indices]
					__SCREAMING_SNAKE_CASE						       =    [coord for idx, coord in enumerate(lowerCAmelCase_       ) if idx not in irrelevant_indices]
					__SCREAMING_SNAKE_CASE						       =    [coord for idx, coord in enumerate(lowerCAmelCase_       ) if idx not in irrelevant_indices]

					# turn coordinates into (left, top, left+width, top+height) format
					__SCREAMING_SNAKE_CASE						       =    []
					for x, y, w, h in zip(lowerCAmelCase_  ,						lowerCAmelCase_  ,						lowerCAmelCase_  ,						lowerCAmelCase_       ):
										__SCREAMING_SNAKE_CASE						       =    [x, y, x + w, y + h]
										actual_boxes.append(lowerCAmelCase_       )

					# finally, normalize the bounding boxes
					__SCREAMING_SNAKE_CASE						       =    []
					for box in actual_boxes:
										normalized_boxes.append(normalize_box(lowerCAmelCase_  ,						lowerCAmelCase_  ,						lowerCAmelCase_       )       )

					assert len(lowerCAmelCase_       ) == len(lowerCAmelCase_       ), "Not as many words as there are bounding boxes"

					return words, normalized_boxes




class 			UpperCamelCase_     (			UpperCamelCase):

	"""simple docstring"""





	snake_case__    :  Optional[Any]    =      ["pixel_values"]




	def __init__(			self      :    Dict      ,      UpperCAmelCase__      :    bool = True      ,      UpperCAmelCase__      :    Dict[str, int] = None      ,      UpperCAmelCase__      :    PILImageResampling = PILImageResampling.BILINEAR      ,      UpperCAmelCase__      :    bool = True      ,      UpperCAmelCase__      :    float = 1 / 2_5_5      ,      UpperCAmelCase__      :    bool = True      ,      UpperCAmelCase__      :    Union[float, Iterable[float]] = None      ,      UpperCAmelCase__      :    Union[float, Iterable[float]] = None      ,      UpperCAmelCase__      :    bool = True      ,      UpperCAmelCase__      :    Optional[str] = None      ,      UpperCAmelCase__      :    Optional[str] = ""      ,      **UpperCAmelCase__      :    Optional[Any]      ,      )	->     None:
						super().__init__(**UpperCAmelCase__       )
						__SCREAMING_SNAKE_CASE						       =    size if size is not None else {"height": 2_2_4, "width": 2_2_4}
						__SCREAMING_SNAKE_CASE						       =    get_size_dict(UpperCAmelCase__       )

						__SCREAMING_SNAKE_CASE						       =    do_resize
						__SCREAMING_SNAKE_CASE						       =    size
						__SCREAMING_SNAKE_CASE						       =    resample
						__SCREAMING_SNAKE_CASE						       =    do_rescale
						__SCREAMING_SNAKE_CASE						       =    rescale_value
						__SCREAMING_SNAKE_CASE						       =    do_normalize
						__SCREAMING_SNAKE_CASE						       =    image_mean if image_mean is not None else IMAGENET_STANDARD_MEAN
						__SCREAMING_SNAKE_CASE						       =    image_std if image_std is not None else IMAGENET_STANDARD_STD
						__SCREAMING_SNAKE_CASE						       =    apply_ocr
						__SCREAMING_SNAKE_CASE						       =    ocr_lang
						__SCREAMING_SNAKE_CASE						       =    tesseract_config




	def   UpperCAmelCase_				(			self      :    Any      ,      UpperCAmelCase__      :    np.ndarray      ,      UpperCAmelCase__      :    Dict[str, int]      ,      UpperCAmelCase__      :    PILImageResampling = PILImageResampling.BILINEAR      ,      UpperCAmelCase__      :    Optional[Union[str, ChannelDimension]] = None      ,      **UpperCAmelCase__      :    Union[str, Any]      ,      )	->     np.ndarray:
						__SCREAMING_SNAKE_CASE						       =    get_size_dict(UpperCAmelCase__       )
						if "height" not in size or "width" not in size:
											raise ValueError(F"""The size dictionary must contain the keys 'height' and 'width'. Got {size.keys()}"""       )
						__SCREAMING_SNAKE_CASE						       =    (size["height"], size["width"])
						return resize(UpperCAmelCase__      ,      size=UpperCAmelCase__      ,      resample=UpperCAmelCase__      ,      data_format=UpperCAmelCase__      ,      **UpperCAmelCase__       )




	def   UpperCAmelCase_				(			self      :    Optional[Any]      ,      UpperCAmelCase__      :    np.ndarray      ,      UpperCAmelCase__      :    Union[int, float]      ,      UpperCAmelCase__      :    Optional[Union[str, ChannelDimension]] = None      ,      **UpperCAmelCase__      :    List[Any]      ,      )	->     np.ndarray:
						return rescale(UpperCAmelCase__      ,      scale=UpperCAmelCase__      ,      data_format=UpperCAmelCase__      ,      **UpperCAmelCase__       )




	def   UpperCAmelCase_				(			self      :    str      ,      UpperCAmelCase__      :    np.ndarray      ,      UpperCAmelCase__      :    Union[float, Iterable[float]]      ,      UpperCAmelCase__      :    Union[float, Iterable[float]]      ,      UpperCAmelCase__      :    Optional[Union[str, ChannelDimension]] = None      ,      **UpperCAmelCase__      :    Optional[int]      ,      )	->     np.ndarray:
						return normalize(UpperCAmelCase__      ,      mean=UpperCAmelCase__      ,      std=UpperCAmelCase__      ,      data_format=UpperCAmelCase__      ,      **UpperCAmelCase__       )




	def   UpperCAmelCase_				(			self      :    Union[str, Any]      ,      UpperCAmelCase__      :    ImageInput      ,      UpperCAmelCase__      :    bool = None      ,      UpperCAmelCase__      :    Dict[str, int] = None      ,      UpperCAmelCase__      :    List[str]=None      ,      UpperCAmelCase__      :    bool = None      ,      UpperCAmelCase__      :    float = None      ,      UpperCAmelCase__      :    bool = None      ,      UpperCAmelCase__      :    Union[float, Iterable[float]] = None      ,      UpperCAmelCase__      :    Union[float, Iterable[float]] = None      ,      UpperCAmelCase__      :    bool = None      ,      UpperCAmelCase__      :    Optional[str] = None      ,      UpperCAmelCase__      :    Optional[str] = None      ,      UpperCAmelCase__      :    Optional[Union[str, TensorType]] = None      ,      UpperCAmelCase__      :    ChannelDimension = ChannelDimension.FIRST      ,      **UpperCAmelCase__      :    List[Any]      ,      )	->     PIL.Image.Image:
						__SCREAMING_SNAKE_CASE						       =    do_resize if do_resize is not None else self.do_resize
						__SCREAMING_SNAKE_CASE						       =    size if size is not None else self.size
						__SCREAMING_SNAKE_CASE						       =    get_size_dict(UpperCAmelCase__       )
						__SCREAMING_SNAKE_CASE						       =    resample if resample is not None else self.resample
						__SCREAMING_SNAKE_CASE						       =    do_rescale if do_rescale is not None else self.do_rescale
						__SCREAMING_SNAKE_CASE						       =    rescale_factor if rescale_factor is not None else self.rescale_factor
						__SCREAMING_SNAKE_CASE						       =    do_normalize if do_normalize is not None else self.do_normalize
						__SCREAMING_SNAKE_CASE						       =    image_mean if image_mean is not None else self.image_mean
						__SCREAMING_SNAKE_CASE						       =    image_std if image_std is not None else self.image_std
						__SCREAMING_SNAKE_CASE						       =    apply_ocr if apply_ocr is not None else self.apply_ocr
						__SCREAMING_SNAKE_CASE						       =    ocr_lang if ocr_lang is not None else self.ocr_lang
						__SCREAMING_SNAKE_CASE						       =    tesseract_config if tesseract_config is not None else self.tesseract_config

						__SCREAMING_SNAKE_CASE						       =    make_list_of_images(UpperCAmelCase__       )

						if not valid_images(UpperCAmelCase__       ):
											raise ValueError(
											    "Invalid image type. Must be of type PIL.Image.Image, numpy.ndarray, "
											    "torch.Tensor, tf.Tensor or jax.ndarray."       )

						if do_resize and size is None:
											raise ValueError("Size must be specified if do_resize is True."       )

						if do_rescale and rescale_factor is None:
											raise ValueError("Rescale factor must be specified if do_rescale is True."       )

						if do_normalize and (image_mean is None or image_std is None):
											raise ValueError("If do_normalize is True, image_mean and image_std must be specified."       )

						# All transformations expect numpy arrays.
						__SCREAMING_SNAKE_CASE						       =    [to_numpy_array(UpperCAmelCase__       ) for image in images]

						# Tesseract OCR to get words + normalized bounding boxes
						if apply_ocr:
											requires_backends(self      ,      "pytesseract"       )
											__SCREAMING_SNAKE_CASE						       =    []
											__SCREAMING_SNAKE_CASE						       =    []
											for image in images:
																__SCREAMING_SNAKE_CASE       ,  __SCREAMING_SNAKE_CASE						       =    apply_tesseract(UpperCAmelCase__      ,      UpperCAmelCase__      ,      UpperCAmelCase__       )
																words_batch.append(UpperCAmelCase__       )
																boxes_batch.append(UpperCAmelCase__       )

						if do_resize:
											__SCREAMING_SNAKE_CASE						       =    [self.resize(image=UpperCAmelCase__      ,      size=UpperCAmelCase__      ,      resample=UpperCAmelCase__       ) for image in images]

						if do_rescale:
											__SCREAMING_SNAKE_CASE						       =    [self.rescale(image=UpperCAmelCase__      ,      scale=UpperCAmelCase__       ) for image in images]

						if do_normalize:
											__SCREAMING_SNAKE_CASE						       =    [self.normalize(image=UpperCAmelCase__      ,      mean=UpperCAmelCase__      ,      std=UpperCAmelCase__       ) for image in images]

						__SCREAMING_SNAKE_CASE						       =    [to_channel_dimension_format(UpperCAmelCase__      ,      UpperCAmelCase__       ) for image in images]

						__SCREAMING_SNAKE_CASE						       =    BatchFeature(data={"pixel_values": images}      ,      tensor_type=UpperCAmelCase__       )

						if apply_ocr:
											__SCREAMING_SNAKE_CASE						       =    words_batch
											__SCREAMING_SNAKE_CASE						       =    boxes_batch
						return data




"""simple docstring"""







from __future__ import annotations




def        UpperCAmelCase__	(lowerCAmelCase_  ,						lowerCAmelCase_       ):




					'''simple docstring'''


					print(f"""Vertex\tShortest Distance from vertex {src}"""       )
					for i, d in enumerate(lowerCAmelCase_       ):
										print(f"""{i}\t\t{d}"""       )




def        UpperCAmelCase__	(lowerCAmelCase_  ,						lowerCAmelCase_  ,						lowerCAmelCase_       ):




					'''simple docstring'''


					for j in range(lowerCAmelCase_       ):
										__SCREAMING_SNAKE_CASE       ,  __SCREAMING_SNAKE_CASE       ,  __SCREAMING_SNAKE_CASE						       =    (graph[j][k] for k in ["src", "dst", "weight"])
										if distance[u] != float("inf"       ) and distance[u] + w < distance[v]:
															return True
					return False




def        UpperCAmelCase__	(lowerCAmelCase_  ,						lowerCAmelCase_  ,						lowerCAmelCase_  ,						lowerCAmelCase_       ):




					'''simple docstring'''


					__SCREAMING_SNAKE_CASE						       =    [float("inf"       )] * vertex_count
					__SCREAMING_SNAKE_CASE						       =    0.0

					for _ in range(vertex_count - 1       ):
										for j in range(lowerCAmelCase_       ):
															__SCREAMING_SNAKE_CASE       ,  __SCREAMING_SNAKE_CASE       ,  __SCREAMING_SNAKE_CASE						       =    (graph[j][k] for k in ["src", "dst", "weight"])

															if distance[u] != float("inf"       ) and distance[u] + w < distance[v]:
																				__SCREAMING_SNAKE_CASE						       =    distance[u] + w

					__SCREAMING_SNAKE_CASE						       =    check_negative_cycle(lowerCAmelCase_  ,						lowerCAmelCase_  ,						lowerCAmelCase_       )
					if negative_cycle_exists:
										raise Exception("Negative cycle found"       )

					return distance


if __name__ == "__main__":
		import doctest

		doctest.testmod()

		a__    :							Union[str, Any]            =					int(input('''Enter number of vertices: ''').strip())
		a__    :							Any            =					int(input('''Enter number of edges: ''').strip())

		a__    :							list[dict[str, int]]            =					[{} for _ in range(E)]

		for i in range(E):
				print('''Edge ''', i + 1)
				a__      ,					a__      ,					a__    :							str            =					(
				    int(x)
				    for x in input('''Enter source, destination, weight: ''').strip().split(''' ''')
				)
				a__    :							str            =					{'''src''': src, '''dst''': dest, '''weight''': weight}

		a__    :							str            =					int(input('''\nEnter shortest path source:''').strip())
		a__    :							List[Any]            =					bellman_ford(graph, V, E, source)
		print_distance(shortest_distance, 0)
