


"""simple docstring"""

import os
import tempfile
from functools import partial
from unittest import TestCase
from unittest.mock import patch

import datasets
import datasets.config

from .utils import require_beam





class  lowerCamelCase__    (		datasets.BeamBasedBuilder     ):
      def SCREAMING_SNAKE_CASE_						(		self						:						Optional[int]				):






       '''simple docstring'''


       return datasets.DatasetInfo(
           features=datasets.Features({"""content""": datasets.Value("""string"""				)}				)   ,							supervised_keys=A_   ,							)
      def SCREAMING_SNAKE_CASE_						(		self						:						Any   ,							A_						:						Union[str, Any]   ,							A_						:						Optional[Any]				):






       '''simple docstring'''


       return [datasets.SplitGenerator(name=datasets.Split.TRAIN   ,							gen_kwargs={"""examples""": get_test_dummy_examples()}				)]






      def SCREAMING_SNAKE_CASE_						(		self						:						Optional[Any]   ,							A_						:						int   ,							A_						:						List[Any]				):






       '''simple docstring'''


       import apache_beam as beam

       return pipeline | "Load Examples" >> beam.Create(A_				)






class  lowerCamelCase__    (		datasets.BeamBasedBuilder     ):
      def SCREAMING_SNAKE_CASE_						(		self						:						Tuple				):






       '''simple docstring'''


       return datasets.DatasetInfo(
           features=datasets.Features({"""a""": datasets.Sequence({"""b""": datasets.Value("""string"""				)}				)}				)   ,							supervised_keys=A_   ,							)
      def SCREAMING_SNAKE_CASE_						(		self						:						Optional[int]   ,							A_						:						List[str]   ,							A_						:						List[Any]				):






       '''simple docstring'''


       return [
           datasets.SplitGenerator(name=datasets.Split.TRAIN   ,							gen_kwargs={"""examples""": get_test_nested_examples()}				)
       ]






      def SCREAMING_SNAKE_CASE_						(		self						:						Dict   ,							A_						:						Optional[int]   ,							A_						:						List[Any]				):






       '''simple docstring'''


       import apache_beam as beam

       return pipeline | "Load Examples" >> beam.Create(A_				)






def lowerCAmelCase_   (					):






 """simple docstring"""







 return [(i, {"content": content}) for i, content in enumerate(["""foo""", """bar""", """foobar"""]			)]


def lowerCAmelCase_   (					):






 """simple docstring"""







 return [(i, {"a": {"b": [content]}}) for i, content in enumerate(["""foo""", """bar""", """foobar"""]			)]





class  lowerCamelCase__    (		_a     ):
      @require_beam
      def SCREAMING_SNAKE_CASE_						(		self						:						str				):






       '''simple docstring'''


       __lowercase						=						len(get_test_dummy_examples()				)
       with tempfile.TemporaryDirectory() as tmp_cache_dir:
        __lowercase						=						DummyBeamDataset(cache_dir=A_   ,							beam_runner="""DirectRunner"""				)
        builder.download_and_prepare()
        self.assertTrue(
            os.path.exists(
                os.path.join(A_   ,							builder.name   ,							"""default"""   ,							"""0.0.0"""   ,							F'''{builder.name}-train.arrow'''				)				)				)
        self.assertDictEqual(builder.info.features   ,							datasets.Features({"""content""": datasets.Value("""string"""				)}				)				)
        __lowercase						=						builder.as_dataset()
        self.assertEqual(dset["""train"""].num_rows   ,							A_				)
        self.assertEqual(dset["""train"""].info.splits["""train"""].num_examples   ,							A_				)
        self.assertDictEqual(dset["""train"""][0]   ,							get_test_dummy_examples()[0][1]				)
        self.assertDictEqual(
            dset["""train"""][expected_num_examples - 1]   ,							get_test_dummy_examples()[expected_num_examples - 1][1]				)
        self.assertTrue(
            os.path.exists(os.path.join(A_   ,							builder.name   ,							"""default"""   ,							"""0.0.0"""   ,							"""dataset_info.json"""				)				)				)
        del dset
      @require_beam
      def SCREAMING_SNAKE_CASE_						(		self						:						Any				):






       '''simple docstring'''


       import apache_beam as beam

       __lowercase						=						beam.io.parquetio.WriteToParquet

       __lowercase						=						len(get_test_dummy_examples()				)
       with tempfile.TemporaryDirectory() as tmp_cache_dir:
        __lowercase						=						DummyBeamDataset(cache_dir=A_   ,							beam_runner="""DirectRunner"""				)
        with patch("""apache_beam.io.parquetio.WriteToParquet"""				) as write_parquet_mock:
         __lowercase						=						partial(A_   ,							num_shards=2				)
         builder.download_and_prepare()
        self.assertTrue(
            os.path.exists(
                os.path.join(
                    A_   ,							builder.name   ,							"""default"""   ,							"""0.0.0"""   ,							F'''{builder.name}-train-00000-of-00002.arrow'''				)				)				)
        self.assertTrue(
            os.path.exists(
                os.path.join(
                    A_   ,							builder.name   ,							"""default"""   ,							"""0.0.0"""   ,							F'''{builder.name}-train-00000-of-00002.arrow'''				)				)				)
        self.assertDictEqual(builder.info.features   ,							datasets.Features({"""content""": datasets.Value("""string"""				)}				)				)
        __lowercase						=						builder.as_dataset()
        self.assertEqual(dset["""train"""].num_rows   ,							A_				)
        self.assertEqual(dset["""train"""].info.splits["""train"""].num_examples   ,							A_				)
        # Order is not preserved when sharding, so we just check that all the elements are there
        self.assertListEqual(sorted(dset["""train"""]["""content"""]				)   ,							sorted(["""foo""", """bar""", """foobar"""]				)				)
        self.assertTrue(
            os.path.exists(os.path.join(A_   ,							builder.name   ,							"""default"""   ,							"""0.0.0"""   ,							"""dataset_info.json"""				)				)				)
        del dset
      @require_beam
      def SCREAMING_SNAKE_CASE_						(		self						:						Optional[Any]				):






       '''simple docstring'''


       with tempfile.TemporaryDirectory() as tmp_cache_dir:
        __lowercase						=						DummyBeamDataset(cache_dir=A_				)
        self.assertRaises(datasets.builder.MissingBeamOptions   ,							builder.download_and_prepare				)






      @require_beam
      def SCREAMING_SNAKE_CASE_						(		self						:						List[Any]				):






       '''simple docstring'''


       __lowercase						=						len(get_test_nested_examples()				)
       with tempfile.TemporaryDirectory() as tmp_cache_dir:
        __lowercase						=						NestedBeamDataset(cache_dir=A_   ,							beam_runner="""DirectRunner"""				)
        builder.download_and_prepare()
        self.assertTrue(
            os.path.exists(
                os.path.join(A_   ,							builder.name   ,							"""default"""   ,							"""0.0.0"""   ,							F'''{builder.name}-train.arrow'''				)				)				)
        self.assertDictEqual(
            builder.info.features   ,							datasets.Features({"""a""": datasets.Sequence({"""b""": datasets.Value("""string"""				)}				)}				)				)
        __lowercase						=						builder.as_dataset()
        self.assertEqual(dset["""train"""].num_rows   ,							A_				)
        self.assertEqual(dset["""train"""].info.splits["""train"""].num_examples   ,							A_				)
        self.assertDictEqual(dset["""train"""][0]   ,							get_test_nested_examples()[0][1]				)
        self.assertDictEqual(
            dset["""train"""][expected_num_examples - 1]   ,							get_test_nested_examples()[expected_num_examples - 1][1]				)
        self.assertTrue(
            os.path.exists(os.path.join(A_   ,							builder.name   ,							"""default"""   ,							"""0.0.0"""   ,							"""dataset_info.json"""				)				)				)
        del dset




"""simple docstring"""

from __future__ import annotations


def lowerCAmelCase_   (					UpperCamelCase__						:			list[float]					, UpperCamelCase__						:			Any			):






 """simple docstring"""







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


def lowerCAmelCase_   (					UpperCamelCase__						:			list[dict[str, int]]					, UpperCamelCase__						:			list[float]					, UpperCamelCase__						:			int			):






 """simple docstring"""







 for j in range(UpperCamelCase__			):
  __lowercase				,		__lowercase				,		__lowercase						=						(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 lowerCAmelCase_   (					UpperCamelCase__						:			list[dict[str, int]]					, UpperCamelCase__						:			int					, UpperCamelCase__						:			int					, UpperCamelCase__						:			int			):






 """simple docstring"""







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

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

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

 __lowercase						=						check_negative_cycle(UpperCamelCase__					, UpperCamelCase__					, UpperCamelCase__			)
 if negative_cycle_exists:
  raise Exception("""Negative cycle found"""			)

 return distance


if __name__ == "__main__":
       import doctest

       doctest.testmod()

       UpperCAmelCase__					=int(input("Enter number of vertices: ").strip())
       UpperCAmelCase__					=int(input("Enter number of edges: ").strip())

       UpperCAmelCase__					=[{} for _ in range(E)]

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

       UpperCAmelCase__					=int(input("\nEnter shortest path source:").strip())
       UpperCAmelCase__					=bellman_ford(graph, V, E, source)
       print_distance(shortest_distance, 0)
