


"""simple docstring"""







import unittest

from transformers.testing_utils import require_bsa
from transformers.utils import is_bsa_available

from ...test_feature_extraction_common import FeatureExtractionSavingTestMixin


if is_bsa_available():
		from transformers import MarkupLMFeatureExtractor




class 			UpperCamelCase_     (			unittest.TestCase):

	"""simple docstring"""





	def __init__(			self      :    Any      ,      UpperCAmelCase__      :    Optional[Any]       )	->     Tuple:
						__SCREAMING_SNAKE_CASE						       =    parent




	def   UpperCAmelCase_				(			self      :    int       )	->     Tuple:
						return {}






def        UpperCAmelCase__	():




					'''simple docstring'''


					__SCREAMING_SNAKE_CASE						       =    "<HTML>\n\n    <HEAD>\n    <TITLE>sample document</TITLE>\n    </HEAD>\n\n    <BODY BGCOLOR=\"FFFFFF\">\n    <HR>\n    <a href=\"http://google.com\">Goog</a>\n    <H1>This is one header</H1>\n    <H2>This is a another Header</H2>\n    <P>Travel from\n        <P>\n        <B>SFO to JFK</B>\n        <BR>\n        <B><I>on May 2, 2015 at 2:00 pm. For details go to confirm.com </I></B>\n        <HR>\n        <div style=\"color:#0000FF\">\n            <h3>Traveler <b> name </b> is\n            <p> John Doe </p>\n        </div>"

					__SCREAMING_SNAKE_CASE						       =    "\n    <!DOCTYPE html>\n    <html>\n    <body>\n\n    <h1>My First Heading</h1>\n    <p>My first paragraph.</p>\n\n    </body>\n    </html>\n    "

					return [html_string_a, html_string_a]




@require_bsa
class 			UpperCamelCase_     (			UpperCamelCase      ,  unittest.TestCase):

	"""simple docstring"""





	snake_case__    :  Optional[int]    =      MarkupLMFeatureExtractor if is_bsa_available() else None




	def   UpperCAmelCase_				(			self      :    List[Any]       )	->     Any:
						__SCREAMING_SNAKE_CASE						       =    MarkupLMFeatureExtractionTester(self       )




	@property
	def   UpperCAmelCase_				(			self      :    List[str]       )	->     Dict:
						return self.feature_extract_tester.prepare_feat_extract_dict()




	def   UpperCAmelCase_				(			self      :    Union[str, Any]       )	->     Any:
						# Initialize feature_extractor
						__SCREAMING_SNAKE_CASE						       =    self.feature_extraction_class()

						# Test not batched input
						__SCREAMING_SNAKE_CASE						       =    get_html_strings()[0]
						__SCREAMING_SNAKE_CASE						       =    feature_extractor(UpperCAmelCase__       )

						# fmt: off
						__SCREAMING_SNAKE_CASE						       =    [["sample document", "Goog", "This is one header", "This is a another Header", "Travel from", "SFO to JFK", "on May 2, 2015 at 2:00 pm. For details go to confirm.com", "Traveler", "name", "is", "John Doe"]]
						__SCREAMING_SNAKE_CASE						       =    [["/html/head/title", "/html/body/a", "/html/body/h1", "/html/body/h2", "/html/body/p", "/html/body/p/p/b[1]", "/html/body/p/p/b[2]/i", "/html/body/p/p/div/h3", "/html/body/p/p/div/h3/b", "/html/body/p/p/div/h3", "/html/body/p/p/div/h3/p"]]
						# fmt: on

						self.assertEqual(encoding.nodes      ,      UpperCAmelCase__       )
						self.assertEqual(encoding.xpaths      ,      UpperCAmelCase__       )

						# Test batched
						__SCREAMING_SNAKE_CASE						       =    get_html_strings()
						__SCREAMING_SNAKE_CASE						       =    feature_extractor(UpperCAmelCase__       )

						# fmt: off
						__SCREAMING_SNAKE_CASE						       =    expected_nodes + [["My First Heading", "My first paragraph."]]
						__SCREAMING_SNAKE_CASE						       =    expected_xpaths + [["/html/body/h1", "/html/body/p"]]

						self.assertEqual(len(encoding.nodes       )      ,      2       )
						self.assertEqual(len(encoding.xpaths       )      ,      2       )

						self.assertEqual(encoding.nodes      ,      UpperCAmelCase__       )
						self.assertEqual(encoding.xpaths      ,      UpperCAmelCase__       )




"""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)
