

import inspect
import unittest

from transformers import YolosConfig
from transformers.testing_utils import require_torch, require_vision, slow, torch_device
from transformers.utils import cached_property, is_torch_available, is_vision_available

from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, floats_tensor
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
						import torch
						from torch import nn

						from transformers import YolosForObjectDetection, YolosModel
						from transformers.models.yolos.modeling_yolos import YOLOS_PRETRAINED_MODEL_ARCHIVE_LIST


if is_vision_available():
						from PIL import Image

						from transformers import AutoImageProcessor



class   __lowercase    :




			"""simple docstring"""







			def __init__(			self  :					Tuple       ,						lowerCAmelCase__  :					Optional[Any]       ,						lowerCAmelCase__  :					Tuple=13       ,						lowerCAmelCase__  :					Tuple=[30, 30]       ,						lowerCAmelCase__  :					Dict=2       ,						lowerCAmelCase__  :					List[Any]=3       ,						lowerCAmelCase__  :					List[Any]=True       ,						lowerCAmelCase__  :					Tuple=True       ,						lowerCAmelCase__  :					Dict=32       ,						lowerCAmelCase__  :					str=5       ,						lowerCAmelCase__  :					Tuple=4       ,						lowerCAmelCase__  :					Optional[int]=37       ,						lowerCAmelCase__  :					Dict="gelu"       ,						lowerCAmelCase__  :					List[str]=0.1       ,						lowerCAmelCase__  :					List[Any]=0.1       ,						lowerCAmelCase__  :					str=10       ,						lowerCAmelCase__  :					Dict=0.02       ,						lowerCAmelCase__  :					Optional[int]=3       ,						lowerCAmelCase__  :					List[str]=None       ,						lowerCAmelCase__  :					Union[str, Any]=8       ,						lowerCAmelCase__  :					str=10       ,						):
									SCREAMING_SNAKE_CASE_:			str  		=	parent
									SCREAMING_SNAKE_CASE_:			Any  		=	batch_size
									SCREAMING_SNAKE_CASE_:			List[str]  		=	image_size
									SCREAMING_SNAKE_CASE_:			Any  		=	patch_size
									SCREAMING_SNAKE_CASE_:			Dict  		=	num_channels
									SCREAMING_SNAKE_CASE_:			Any  		=	is_training
									SCREAMING_SNAKE_CASE_:			List[Any]  		=	use_labels
									SCREAMING_SNAKE_CASE_:			Tuple  		=	hidden_size
									SCREAMING_SNAKE_CASE_:			Any  		=	num_hidden_layers
									SCREAMING_SNAKE_CASE_:			Optional[Any]  		=	num_attention_heads
									SCREAMING_SNAKE_CASE_:			str  		=	intermediate_size
									SCREAMING_SNAKE_CASE_:			Any  		=	hidden_act
									SCREAMING_SNAKE_CASE_:			List[Any]  		=	hidden_dropout_prob
									SCREAMING_SNAKE_CASE_:			Tuple  		=	attention_probs_dropout_prob
									SCREAMING_SNAKE_CASE_:			List[str]  		=	type_sequence_label_size
									SCREAMING_SNAKE_CASE_:			Dict  		=	initializer_range
									SCREAMING_SNAKE_CASE_:			Tuple  		=	num_labels
									SCREAMING_SNAKE_CASE_:			List[Any]  		=	scope
									SCREAMING_SNAKE_CASE_:			str  		=	n_targets
									SCREAMING_SNAKE_CASE_:			Optional[int]  		=	num_detection_tokens
									# we set the expected sequence length (which is used in several tests)
									# expected sequence length = num_patches + 1 (we add 1 for the [CLS] token) + num_detection_tokens
									SCREAMING_SNAKE_CASE_:			Optional[Any]  		=	(image_size[1] // patch_size) * (image_size[0] // patch_size)
									SCREAMING_SNAKE_CASE_:			Any  		=	num_patches + 1 + self.num_detection_tokens



			def 	_SCREAMING_SNAKE_CASE      (			self  :					Optional[Any]):
									SCREAMING_SNAKE_CASE_:			Optional[int]  		=	floats_tensor([self.batch_size, self.num_channels, self.image_size[0], self.image_size[1]])

									SCREAMING_SNAKE_CASE_:			Optional[Any]  		=	None
									if self.use_labels:
															# labels is a list of Dict (each Dict being the labels for a given example in the batch)
															SCREAMING_SNAKE_CASE_:			Tuple  		=	[]
															for i in range(self.batch_size):
																					SCREAMING_SNAKE_CASE_:			Optional[int]  		=	{}
																					SCREAMING_SNAKE_CASE_:			Union[str, Any]  		=	torch.randint(
																					    high=self.num_labels       ,						size=(self.n_targets,)       ,						device=__lowerCAmelCase)
																					SCREAMING_SNAKE_CASE_:			Union[str, Any]  		=	torch.rand(self.n_targets       ,						4       ,						device=__lowerCAmelCase)
																					labels.append(__lowerCAmelCase)

									SCREAMING_SNAKE_CASE_:			List[str]  		=	self.get_config()

									return config, pixel_values, labels



			def 	_SCREAMING_SNAKE_CASE      (			self  :					List[str]):
									return YolosConfig(
									    image_size=self.image_size       ,						patch_size=self.patch_size       ,						num_channels=self.num_channels       ,						hidden_size=self.hidden_size       ,						num_hidden_layers=self.num_hidden_layers       ,						num_attention_heads=self.num_attention_heads       ,						intermediate_size=self.intermediate_size       ,						hidden_act=self.hidden_act       ,						hidden_dropout_prob=self.hidden_dropout_prob       ,						attention_probs_dropout_prob=self.attention_probs_dropout_prob       ,						is_decoder=__lowerCAmelCase       ,						initializer_range=self.initializer_range       ,						num_detection_tokens=self.num_detection_tokens       ,						num_labels=self.num_labels       ,						)



			def 	_SCREAMING_SNAKE_CASE      (			self  :					Optional[Any]       ,						lowerCAmelCase__  :					int       ,						lowerCAmelCase__  :					List[str]       ,						lowerCAmelCase__  :					Union[str, Any]):
									SCREAMING_SNAKE_CASE_:			int  		=	YolosModel(config=__lowerCAmelCase)
									model.to(__lowerCAmelCase)
									model.eval()
									SCREAMING_SNAKE_CASE_:			Any  		=	model(__lowerCAmelCase)
									self.parent.assertEqual(
									    result.last_hidden_state.shape       ,						(self.batch_size, self.expected_seq_len, self.hidden_size))



			def 	_SCREAMING_SNAKE_CASE      (			self  :					Dict       ,						lowerCAmelCase__  :					Optional[int]       ,						lowerCAmelCase__  :					List[Any]       ,						lowerCAmelCase__  :					Any):
									SCREAMING_SNAKE_CASE_:			Any  		=	YolosForObjectDetection(__lowerCAmelCase)
									model.to(__lowerCAmelCase)
									model.eval()

									SCREAMING_SNAKE_CASE_:			Any  		=	model(pixel_values=__lowerCAmelCase)
									SCREAMING_SNAKE_CASE_:			Any  		=	model(__lowerCAmelCase)

									self.parent.assertEqual(result.logits.shape       ,						(self.batch_size, self.num_detection_tokens, self.num_labels + 1))
									self.parent.assertEqual(result.pred_boxes.shape       ,						(self.batch_size, self.num_detection_tokens, 4))

									SCREAMING_SNAKE_CASE_:			List[Any]  		=	model(pixel_values=__lowerCAmelCase       ,						labels=__lowerCAmelCase)

									self.parent.assertEqual(result.loss.shape       ,						())
									self.parent.assertEqual(result.logits.shape       ,						(self.batch_size, self.num_detection_tokens, self.num_labels + 1))
									self.parent.assertEqual(result.pred_boxes.shape       ,						(self.batch_size, self.num_detection_tokens, 4))




			def 	_SCREAMING_SNAKE_CASE      (			self  :					Optional[int]):
									SCREAMING_SNAKE_CASE_:			Tuple  		=	self.prepare_config_and_inputs()
									SCREAMING_SNAKE_CASE_		,   SCREAMING_SNAKE_CASE_		,   SCREAMING_SNAKE_CASE_:			List[Any]  		=	config_and_inputs
									SCREAMING_SNAKE_CASE_:			Optional[Any]  		=	{"pixel_values": pixel_values}
									return config, inputs_dict







@require_torch
class   __lowercase    (			_a		,	_a		,	unittest.TestCase     ):




			"""simple docstring"""







			_UpperCAmelCase       :							Union[str, Any]      							=					(YolosModel, YolosForObjectDetection) if is_torch_available() else ()
			_UpperCAmelCase       :							Union[str, Any]      							=					(
			    {"""feature-extraction""": YolosModel, """object-detection""": YolosForObjectDetection} if is_torch_available() else {}
			)

			_UpperCAmelCase       :							Optional[Any]      							=					False
			_UpperCAmelCase       :							List[str]      							=					False
			_UpperCAmelCase       :							Dict      							=					False
			_UpperCAmelCase       :							List[Any]      							=					False



			def 	_SCREAMING_SNAKE_CASE      (			self  :					Union[str, Any]       ,						lowerCAmelCase__  :					Any       ,						lowerCAmelCase__  :					List[Any]       ,						lowerCAmelCase__  :					Any=False):
									SCREAMING_SNAKE_CASE_:			Any  		=	super()._prepare_for_class(__lowerCAmelCase       ,						__lowerCAmelCase       ,						return_labels=__lowerCAmelCase)

									if return_labels:
															if model_class.__name__ == "YolosForObjectDetection":
																					SCREAMING_SNAKE_CASE_:			Union[str, Any]  		=	[]
																					for i in range(self.model_tester.batch_size):
																											SCREAMING_SNAKE_CASE_:			Optional[Any]  		=	{}
																											SCREAMING_SNAKE_CASE_:			int  		=	torch.ones(
																											    size=(self.model_tester.n_targets,)       ,						device=__lowerCAmelCase       ,						dtype=torch.long)
																											SCREAMING_SNAKE_CASE_:			List[str]  		=	torch.ones(
																											    self.model_tester.n_targets       ,						4       ,						device=__lowerCAmelCase       ,						dtype=torch.float)
																											labels.append(__lowerCAmelCase)
																					SCREAMING_SNAKE_CASE_:			Union[str, Any]  		=	labels

									return inputs_dict



			def 	_SCREAMING_SNAKE_CASE      (			self  :					Dict):
									SCREAMING_SNAKE_CASE_:			Optional[int]  		=	YolosModelTester(self)
									SCREAMING_SNAKE_CASE_:			Optional[int]  		=	ConfigTester(self       ,						config_class=__lowerCAmelCase       ,						has_text_modality=__lowerCAmelCase       ,						hidden_size=37)



			def 	_SCREAMING_SNAKE_CASE      (			self  :					Optional[Any]):
									self.config_tester.run_common_tests()



			def 	_SCREAMING_SNAKE_CASE      (			self  :					Any):
									# YOLOS does not use inputs_embeds
									pass



			def 	_SCREAMING_SNAKE_CASE      (			self  :					Optional[int]):
									SCREAMING_SNAKE_CASE_		,   SCREAMING_SNAKE_CASE_:			int  		=	self.model_tester.prepare_config_and_inputs_for_common()

									for model_class in self.all_model_classes:
															SCREAMING_SNAKE_CASE_:			List[Any]  		=	model_class(__lowerCAmelCase)
															self.assertIsInstance(model.get_input_embeddings()       ,						(nn.Module))
															SCREAMING_SNAKE_CASE_:			int  		=	model.get_output_embeddings()
															self.assertTrue(x is None or isinstance(__lowerCAmelCase       ,						nn.Linear))



			def 	_SCREAMING_SNAKE_CASE      (			self  :					Any):
									SCREAMING_SNAKE_CASE_		,   SCREAMING_SNAKE_CASE_:			Optional[int]  		=	self.model_tester.prepare_config_and_inputs_for_common()

									for model_class in self.all_model_classes:
															SCREAMING_SNAKE_CASE_:			Union[str, Any]  		=	model_class(__lowerCAmelCase)
															SCREAMING_SNAKE_CASE_:			Any  		=	inspect.signature(model.forward)
															# signature.parameters is an OrderedDict => so arg_names order is deterministic
															SCREAMING_SNAKE_CASE_:			Dict  		=	[*signature.parameters.keys()]

															SCREAMING_SNAKE_CASE_:			str  		=	["pixel_values"]
															self.assertListEqual(arg_names[:1]       ,						__lowerCAmelCase)



			def 	_SCREAMING_SNAKE_CASE      (			self  :					List[Any]):
									SCREAMING_SNAKE_CASE_:			Any  		=	self.model_tester.prepare_config_and_inputs()
									self.model_tester.create_and_check_model(*__lowerCAmelCase)



			def 	_SCREAMING_SNAKE_CASE      (			self  :					List[Any]):
									SCREAMING_SNAKE_CASE_		,   SCREAMING_SNAKE_CASE_:			List[Any]  		=	self.model_tester.prepare_config_and_inputs_for_common()
									SCREAMING_SNAKE_CASE_:			Union[str, Any]  		=	True

									# in YOLOS, the seq_len is different
									SCREAMING_SNAKE_CASE_:			List[Any]  		=	self.model_tester.expected_seq_len
									for model_class in self.all_model_classes:
															SCREAMING_SNAKE_CASE_:			Optional[Any]  		=	True
															SCREAMING_SNAKE_CASE_:			List[str]  		=	False
															SCREAMING_SNAKE_CASE_:			Tuple  		=	True
															SCREAMING_SNAKE_CASE_:			int  		=	model_class(__lowerCAmelCase)
															model.to(__lowerCAmelCase)
															model.eval()
															with torch.no_grad():
																					SCREAMING_SNAKE_CASE_:			List[str]  		=	model(**self._prepare_for_class(__lowerCAmelCase       ,						__lowerCAmelCase))
															SCREAMING_SNAKE_CASE_:			List[str]  		=	outputs.attentions
															self.assertEqual(len(__lowerCAmelCase)       ,						self.model_tester.num_hidden_layers)

															# check that output_attentions also work using config
															del inputs_dict["output_attentions"]
															SCREAMING_SNAKE_CASE_:			List[Any]  		=	True
															SCREAMING_SNAKE_CASE_:			Dict  		=	model_class(__lowerCAmelCase)
															model.to(__lowerCAmelCase)
															model.eval()
															with torch.no_grad():
																					SCREAMING_SNAKE_CASE_:			Any  		=	model(**self._prepare_for_class(__lowerCAmelCase       ,						__lowerCAmelCase))
															SCREAMING_SNAKE_CASE_:			str  		=	outputs.attentions
															self.assertEqual(len(__lowerCAmelCase)       ,						self.model_tester.num_hidden_layers)

															self.assertListEqual(
															    list(attentions[0].shape[-3:])       ,						[self.model_tester.num_attention_heads, seq_len, seq_len]       ,						)
															SCREAMING_SNAKE_CASE_:			Dict  		=	len(__lowerCAmelCase)

															# Check attention is always last and order is fine
															SCREAMING_SNAKE_CASE_:			Any  		=	True
															SCREAMING_SNAKE_CASE_:			str  		=	True
															SCREAMING_SNAKE_CASE_:			Union[str, Any]  		=	model_class(__lowerCAmelCase)
															model.to(__lowerCAmelCase)
															model.eval()
															with torch.no_grad():
																					SCREAMING_SNAKE_CASE_:			Optional[int]  		=	model(**self._prepare_for_class(__lowerCAmelCase       ,						__lowerCAmelCase))

															SCREAMING_SNAKE_CASE_:			List[str]  		=	1
															self.assertEqual(out_len + added_hidden_states       ,						len(__lowerCAmelCase))

															SCREAMING_SNAKE_CASE_:			Optional[int]  		=	outputs.attentions

															self.assertEqual(len(__lowerCAmelCase)       ,						self.model_tester.num_hidden_layers)
															self.assertListEqual(
															    list(self_attentions[0].shape[-3:])       ,						[self.model_tester.num_attention_heads, seq_len, seq_len]       ,						)



			def 	_SCREAMING_SNAKE_CASE      (			self  :					Union[str, Any]):
									def check_hidden_states_output(lowerCAmelCase__  :					Optional[Any]       ,						lowerCAmelCase__  :					List[Any]       ,						lowerCAmelCase__  :					Any):
															SCREAMING_SNAKE_CASE_:			str  		=	model_class(__lowerCAmelCase)
															model.to(__lowerCAmelCase)
															model.eval()

															with torch.no_grad():
																					SCREAMING_SNAKE_CASE_:			Tuple  		=	model(**self._prepare_for_class(__lowerCAmelCase       ,						__lowerCAmelCase))

															SCREAMING_SNAKE_CASE_:			List[Any]  		=	outputs.hidden_states

															SCREAMING_SNAKE_CASE_:			List[Any]  		=	getattr(
															    self.model_tester       ,						"expected_num_hidden_layers"       ,						self.model_tester.num_hidden_layers + 1)
															self.assertEqual(len(__lowerCAmelCase)       ,						__lowerCAmelCase)

															# YOLOS has a different seq_length
															SCREAMING_SNAKE_CASE_:			Dict  		=	self.model_tester.expected_seq_len

															self.assertListEqual(
															    list(hidden_states[0].shape[-2:])       ,						[seq_length, self.model_tester.hidden_size]       ,						)

									SCREAMING_SNAKE_CASE_		,   SCREAMING_SNAKE_CASE_:			List[Any]  		=	self.model_tester.prepare_config_and_inputs_for_common()

									for model_class in self.all_model_classes:
															SCREAMING_SNAKE_CASE_:			Optional[Any]  		=	True
															check_hidden_states_output(__lowerCAmelCase       ,						__lowerCAmelCase       ,						__lowerCAmelCase)

															# check that output_hidden_states also work using config
															del inputs_dict["output_hidden_states"]
															SCREAMING_SNAKE_CASE_:			List[str]  		=	True

															check_hidden_states_output(__lowerCAmelCase       ,						__lowerCAmelCase       ,						__lowerCAmelCase)



			def 	_SCREAMING_SNAKE_CASE      (			self  :					int):
									SCREAMING_SNAKE_CASE_:			Optional[Any]  		=	self.model_tester.prepare_config_and_inputs()
									self.model_tester.create_and_check_for_object_detection(*__lowerCAmelCase)




			@slow
			def 	_SCREAMING_SNAKE_CASE      (			self  :					int):
									for model_name in YOLOS_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
															SCREAMING_SNAKE_CASE_:			Union[str, Any]  		=	YolosModel.from_pretrained(__lowerCAmelCase)
															self.assertIsNotNone(__lowerCAmelCase)







def       A_				(   ):
						SCREAMING_SNAKE_CASE_:			Dict  		=	Image.open("./tests/fixtures/tests_samples/COCO/000000039769.png"   )
						return image



@require_torch
@require_vision
class   __lowercase    (			unittest.TestCase     ):




			"""simple docstring"""







			@cached_property
			def 	_SCREAMING_SNAKE_CASE      (			self  :					List[Any]):
									return AutoImageProcessor.from_pretrained("hustvl/yolos-small") if is_vision_available() else None




			@slow
			def 	_SCREAMING_SNAKE_CASE      (			self  :					Tuple):
									SCREAMING_SNAKE_CASE_:			Optional[Any]  		=	YolosForObjectDetection.from_pretrained("hustvl/yolos-small").to(__lowerCAmelCase)

									SCREAMING_SNAKE_CASE_:			int  		=	self.default_image_processor
									SCREAMING_SNAKE_CASE_:			Optional[int]  		=	prepare_img()
									SCREAMING_SNAKE_CASE_:			Optional[int]  		=	image_processor(images=__lowerCAmelCase       ,						return_tensors="pt").to(__lowerCAmelCase)

									# forward pass
									with torch.no_grad():
															SCREAMING_SNAKE_CASE_:			Optional[Any]  		=	model(inputs.pixel_values)

									# verify outputs
									SCREAMING_SNAKE_CASE_:			List[str]  		=	torch.Size((1, 100, 92))
									self.assertEqual(outputs.logits.shape       ,						__lowerCAmelCase)

									SCREAMING_SNAKE_CASE_:			Optional[Any]  		=	torch.tensor(
									    [[-24.0248, -10.3024, -14.8290], [-42.0392, -16.8200, -27.4334], [-27.2743, -11.8154, -18.7148]]       ,						device=__lowerCAmelCase       ,						)
									SCREAMING_SNAKE_CASE_:			List[Any]  		=	torch.tensor(
									    [[0.2559, 0.5455, 0.4706], [0.2989, 0.7279, 0.1875], [0.7732, 0.4017, 0.4462]]       ,						device=__lowerCAmelCase)
									self.assertTrue(torch.allclose(outputs.logits[0, :3, :3]       ,						__lowerCAmelCase       ,						atol=1E-4))
									self.assertTrue(torch.allclose(outputs.pred_boxes[0, :3, :3]       ,						__lowerCAmelCase       ,						atol=1E-4))

									# verify postprocessing
									SCREAMING_SNAKE_CASE_:			Union[str, Any]  		=	image_processor.post_process_object_detection(
									    __lowerCAmelCase       ,						threshold=0.3       ,						target_sizes=[image.size[::-1]])[0]
									SCREAMING_SNAKE_CASE_:			List[str]  		=	torch.tensor([0.9994, 0.9790, 0.9964, 0.9972, 0.9861]).to(__lowerCAmelCase)
									SCREAMING_SNAKE_CASE_:			int  		=	[75, 75, 17, 63, 17]
									SCREAMING_SNAKE_CASE_:			Optional[int]  		=	torch.tensor([335.0609, 79.3848, 375.4216, 187.2495]).to(__lowerCAmelCase)

									self.assertEqual(len(results["scores"])       ,						5)
									self.assertTrue(torch.allclose(results["scores"]       ,						__lowerCAmelCase       ,						atol=1E-4))
									self.assertSequenceEqual(results["labels"].tolist()       ,						__lowerCAmelCase)
									self.assertTrue(torch.allclose(results["boxes"][0, :]       ,						__lowerCAmelCase))








from __future__ import annotations

from collections import deque
from collections.abc import Iterator
from dataclasses import dataclass



@dataclass
class   __lowercase    :




			"""simple docstring"""







			_UpperCAmelCase       :							int
			_UpperCAmelCase       :							int







class   __lowercase    :




			"""simple docstring"""







			def __init__(			self  :					Any       ,						lowerCAmelCase__  :					int):
									SCREAMING_SNAKE_CASE_:			list[list[Edge]]  		=	[[] for _ in range(lowerCAmelCase__)]
									SCREAMING_SNAKE_CASE_:			Dict  		=	size



			def __getitem__(			self  :					Dict       ,						lowerCAmelCase__  :					int):
									return iter(self._graph[vertex])



			@property
			def 	_SCREAMING_SNAKE_CASE      (			self  :					Tuple):
									return self._size



			def 	_SCREAMING_SNAKE_CASE      (			self  :					Dict       ,						lowerCAmelCase__  :					int       ,						lowerCAmelCase__  :					int       ,						lowerCAmelCase__  :					int):
									if weight not in (0, 1):
															raise ValueError("Edge weight must be either 0 or 1.")

									if to_vertex < 0 or to_vertex >= self.size:
															raise ValueError("Vertex indexes must be in [0; size).")

									self._graph[from_vertex].append(Edge(lowerCAmelCase__       ,						lowerCAmelCase__))




			def 	_SCREAMING_SNAKE_CASE      (			self  :					List[Any]       ,						lowerCAmelCase__  :					int       ,						lowerCAmelCase__  :					int):
									SCREAMING_SNAKE_CASE_:			Optional[int]  		=	deque([start_vertex])
									SCREAMING_SNAKE_CASE_:			list[int | None]  		=	[None] * self.size
									SCREAMING_SNAKE_CASE_:			List[Any]  		=	0

									while queue:
															SCREAMING_SNAKE_CASE_:			int  		=	queue.popleft()
															SCREAMING_SNAKE_CASE_:			str  		=	distances[current_vertex]
															if current_distance is None:
																					continue

															for edge in self[current_vertex]:
																					SCREAMING_SNAKE_CASE_:			Optional[int]  		=	current_distance + edge.weight
																					SCREAMING_SNAKE_CASE_:			str  		=	distances[edge.destination_vertex]
																					if (
																					    isinstance(lowerCAmelCase__       ,						lowerCAmelCase__)
																					    and new_distance >= dest_vertex_distance
																					):
																											continue
																					SCREAMING_SNAKE_CASE_:			Any  		=	new_distance
																					if edge.weight == 0:
																											queue.appendleft(edge.destination_vertex)
																					else:
																											queue.append(edge.destination_vertex)

									if distances[finish_vertex] is None:
															raise ValueError("No path from start_vertex to finish_vertex.")

									return distances[finish_vertex]


if __name__ == "__main__":
						import doctest

						doctest.testmod()






