





'''simple docstring'''



from __future__ import annotations

from queue import Queue





class       lowerCAmelCase				:


       def __init__(				self					) ->					None:



            '''simple docstring'''




            __snake_case         =					{}


       def  lowerCAmelCase (				self					) ->					None:



            '''simple docstring'''




            for i in self.vertices:
                 print(__SCREAMING_SNAKE_CASE      ,					''' : '''      ,					''' -> '''.join([str(__SCREAMING_SNAKE_CASE					) for j in self.vertices[i]]					)					)


       def  lowerCAmelCase (				self      ,					__SCREAMING_SNAKE_CASE      ,					__SCREAMING_SNAKE_CASE					) ->					None:



            '''simple docstring'''




            if from_vertex in self.vertices:
                 self.vertices[from_vertex].append(__SCREAMING_SNAKE_CASE					)
            else:
                 __snake_case         =					[to_vertex]




       def  lowerCAmelCase (				self      ,					__SCREAMING_SNAKE_CASE					) ->					set[int]:



            '''simple docstring'''




            __snake_case         =					set()

            # create a first in first out queue to store all the vertices for BFS
            __snake_case         =					Queue()

            # mark the source node as visited and enqueue it
            visited.add(__SCREAMING_SNAKE_CASE					)
            queue.put(__SCREAMING_SNAKE_CASE					)

            while not queue.empty():
                 __snake_case         =					queue.get()

                 # loop through all adjacent vertex and enqueue it if not yet visited
                 for adjacent_vertex in self.vertices[vertex]:
                      if adjacent_vertex not in visited:
                           queue.put(__SCREAMING_SNAKE_CASE					)
                           visited.add(__SCREAMING_SNAKE_CASE					)
            return visited


if __name__ == "__main__":
     from doctest import testmod

     testmod(verbose=True)

     UpperCAmelCase_    :					Any					      =						Graph()
     g.add_edge(0, 1)
     g.add_edge(0, 2)
     g.add_edge(1, 2)
     g.add_edge(2, 0)
     g.add_edge(2, 3)
     g.add_edge(3, 3)

     g.print_graph()
     # 0  :  1 -> 2
     # 1  :  2
     # 2  :  0 -> 3
     # 3  :  3

     assert sorted(g.bfs(2)) == [0, 1, 2, 3]












'''simple docstring'''



import tempfile
import unittest

from transformers import DPRConfig, is_torch_available
from transformers.testing_utils import require_torch, slow, torch_device

from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, ids_tensor, random_attention_mask
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
     import torch

     from transformers import DPRContextEncoder, DPRQuestionEncoder, DPRReader, DPRReaderTokenizer
     from transformers.models.dpr.modeling_dpr import (
         DPR_CONTEXT_ENCODER_PRETRAINED_MODEL_ARCHIVE_LIST,
         DPR_QUESTION_ENCODER_PRETRAINED_MODEL_ARCHIVE_LIST,
         DPR_READER_PRETRAINED_MODEL_ARCHIVE_LIST,
     )





class       lowerCAmelCase				:


       def __init__(				self      ,					__SCREAMING_SNAKE_CASE      ,					__SCREAMING_SNAKE_CASE=13      ,					__SCREAMING_SNAKE_CASE=7      ,					__SCREAMING_SNAKE_CASE=False      ,					__SCREAMING_SNAKE_CASE=True      ,					__SCREAMING_SNAKE_CASE=True      ,					__SCREAMING_SNAKE_CASE=True      ,					__SCREAMING_SNAKE_CASE=99      ,					__SCREAMING_SNAKE_CASE=32      ,					__SCREAMING_SNAKE_CASE=5      ,					__SCREAMING_SNAKE_CASE=4      ,					__SCREAMING_SNAKE_CASE=37      ,					__SCREAMING_SNAKE_CASE="gelu"      ,					__SCREAMING_SNAKE_CASE=0.1      ,					__SCREAMING_SNAKE_CASE=0.1      ,					__SCREAMING_SNAKE_CASE=512      ,					__SCREAMING_SNAKE_CASE=16      ,					__SCREAMING_SNAKE_CASE=2      ,					__SCREAMING_SNAKE_CASE=0.02      ,					__SCREAMING_SNAKE_CASE=3      ,					__SCREAMING_SNAKE_CASE=4      ,					__SCREAMING_SNAKE_CASE=None      ,					__SCREAMING_SNAKE_CASE=0      ,					) ->					str:



            '''simple docstring'''




            __snake_case         =					parent
            __snake_case         =					batch_size
            __snake_case         =					seq_length
            __snake_case         =					is_training
            __snake_case         =					use_input_mask
            __snake_case         =					use_token_type_ids
            __snake_case         =					use_labels
            __snake_case         =					vocab_size
            __snake_case         =					hidden_size
            __snake_case         =					num_hidden_layers
            __snake_case         =					num_attention_heads
            __snake_case         =					intermediate_size
            __snake_case         =					hidden_act
            __snake_case         =					hidden_dropout_prob
            __snake_case         =					attention_probs_dropout_prob
            __snake_case         =					max_position_embeddings
            __snake_case         =					type_vocab_size
            __snake_case         =					type_sequence_label_size
            __snake_case         =					initializer_range
            __snake_case         =					num_labels
            __snake_case         =					num_choices
            __snake_case         =					scope
            __snake_case         =					projection_dim


       def  lowerCAmelCase (				self					) ->					List[str]:



            '''simple docstring'''




            __snake_case         =					ids_tensor([self.batch_size, self.seq_length]      ,					self.vocab_size					)

            __snake_case         =					None
            if self.use_input_mask:
                 __snake_case         =					random_attention_mask([self.batch_size, self.seq_length]					)

            __snake_case         =					None
            if self.use_token_type_ids:
                 __snake_case         =					ids_tensor([self.batch_size, self.seq_length]      ,					self.type_vocab_size					)

            __snake_case         =					None
            __snake_case         =					None
            __snake_case         =					None
            if self.use_labels:
                 __snake_case         =					ids_tensor([self.batch_size]      ,					self.type_sequence_label_size					)
                 __snake_case         =					ids_tensor([self.batch_size, self.seq_length]      ,					self.num_labels					)
                 __snake_case         =					ids_tensor([self.batch_size]      ,					self.num_choices					)

            __snake_case         =					self.get_config()

            return config, input_ids, token_type_ids, input_mask, sequence_labels, token_labels, choice_labels


       def  lowerCAmelCase (				self					) ->					Union[str, Any]:



            '''simple docstring'''




            return DPRConfig(
                projection_dim=self.projection_dim      ,					vocab_size=self.vocab_size      ,					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      ,					max_position_embeddings=self.max_position_embeddings      ,					type_vocab_size=self.type_vocab_size      ,					initializer_range=self.initializer_range      ,					)


       def  lowerCAmelCase (				self      ,					__SCREAMING_SNAKE_CASE      ,					__SCREAMING_SNAKE_CASE      ,					__SCREAMING_SNAKE_CASE      ,					__SCREAMING_SNAKE_CASE      ,					__SCREAMING_SNAKE_CASE      ,					__SCREAMING_SNAKE_CASE      ,					__SCREAMING_SNAKE_CASE					) ->					Any:



            '''simple docstring'''




            __snake_case         =					DPRContextEncoder(config=__SCREAMING_SNAKE_CASE					)
            model.to(__SCREAMING_SNAKE_CASE					)
            model.eval()
            __snake_case         =					model(__SCREAMING_SNAKE_CASE      ,					attention_mask=__SCREAMING_SNAKE_CASE      ,					token_type_ids=__SCREAMING_SNAKE_CASE					)
            __snake_case         =					model(__SCREAMING_SNAKE_CASE      ,					token_type_ids=__SCREAMING_SNAKE_CASE					)
            __snake_case         =					model(__SCREAMING_SNAKE_CASE					)
            self.parent.assertEqual(result.pooler_output.shape      ,					(self.batch_size, self.projection_dim or self.hidden_size)					)


       def  lowerCAmelCase (				self      ,					__SCREAMING_SNAKE_CASE      ,					__SCREAMING_SNAKE_CASE      ,					__SCREAMING_SNAKE_CASE      ,					__SCREAMING_SNAKE_CASE      ,					__SCREAMING_SNAKE_CASE      ,					__SCREAMING_SNAKE_CASE      ,					__SCREAMING_SNAKE_CASE					) ->					Any:



            '''simple docstring'''




            __snake_case         =					DPRQuestionEncoder(config=__SCREAMING_SNAKE_CASE					)
            model.to(__SCREAMING_SNAKE_CASE					)
            model.eval()
            __snake_case         =					model(__SCREAMING_SNAKE_CASE      ,					attention_mask=__SCREAMING_SNAKE_CASE      ,					token_type_ids=__SCREAMING_SNAKE_CASE					)
            __snake_case         =					model(__SCREAMING_SNAKE_CASE      ,					token_type_ids=__SCREAMING_SNAKE_CASE					)
            __snake_case         =					model(__SCREAMING_SNAKE_CASE					)
            self.parent.assertEqual(result.pooler_output.shape      ,					(self.batch_size, self.projection_dim or self.hidden_size)					)


       def  lowerCAmelCase (				self      ,					__SCREAMING_SNAKE_CASE      ,					__SCREAMING_SNAKE_CASE      ,					__SCREAMING_SNAKE_CASE      ,					__SCREAMING_SNAKE_CASE      ,					__SCREAMING_SNAKE_CASE      ,					__SCREAMING_SNAKE_CASE      ,					__SCREAMING_SNAKE_CASE					) ->					Tuple:



            '''simple docstring'''




            __snake_case         =					DPRReader(config=__SCREAMING_SNAKE_CASE					)
            model.to(__SCREAMING_SNAKE_CASE					)
            model.eval()
            __snake_case         =					model(
                __SCREAMING_SNAKE_CASE      ,					attention_mask=__SCREAMING_SNAKE_CASE      ,					)

            self.parent.assertEqual(result.start_logits.shape      ,					(self.batch_size, self.seq_length)					)
            self.parent.assertEqual(result.end_logits.shape      ,					(self.batch_size, self.seq_length)					)
            self.parent.assertEqual(result.relevance_logits.shape      ,					(self.batch_size,)					)




       def  lowerCAmelCase (				self					) ->					str:



            '''simple docstring'''




            __snake_case         =					self.prepare_config_and_inputs()
            (
                (
                __snake_case
            )   ,      (
                __snake_case
            )   ,      (
                __snake_case
            )   ,      (
                __snake_case
            )   ,      (
                __snake_case
            )   ,      (
                __snake_case
            )   ,      (
                __snake_case
            )   ,      
            )         =					config_and_inputs
            __snake_case         =					{'''input_ids''': input_ids}
            return config, inputs_dict





@require_torch
class       lowerCAmelCase				(	__lowerCAmelCase			,				__lowerCAmelCase			,				unittest.TestCase):
       __lowercase					: Optional[int]	    =     (
           (
               DPRContextEncoder,
               DPRQuestionEncoder,
               DPRReader,
           )
           if is_torch_available()
           else ()
       )
       __lowercase					: Optional[Any]	    =     {'''feature-extraction''': DPRQuestionEncoder} if is_torch_available() else {}

       __lowercase					: Optional[Any]	    =     False
       __lowercase					: List[str]	    =     False  # why?
       __lowercase					: Optional[Any]	    =     False
       __lowercase					: Dict	    =     False


       def  lowerCAmelCase (				self					) ->					Tuple:



            '''simple docstring'''




            __snake_case         =					DPRModelTester(self					)
            __snake_case         =					ConfigTester(self      ,					config_class=__SCREAMING_SNAKE_CASE      ,					hidden_size=37					)


       def  lowerCAmelCase (				self					) ->					Union[str, Any]:



            '''simple docstring'''




            self.config_tester.run_common_tests()


       def  lowerCAmelCase (				self					) ->					Union[str, Any]:



            '''simple docstring'''




            __snake_case         =					self.model_tester.prepare_config_and_inputs()
            self.model_tester.create_and_check_context_encoder(*__SCREAMING_SNAKE_CASE					)


       def  lowerCAmelCase (				self					) ->					str:



            '''simple docstring'''




            __snake_case         =					self.model_tester.prepare_config_and_inputs()
            self.model_tester.create_and_check_question_encoder(*__SCREAMING_SNAKE_CASE					)


       def  lowerCAmelCase (				self					) ->					Union[str, Any]:



            '''simple docstring'''




            __snake_case         =					self.model_tester.prepare_config_and_inputs()
            self.model_tester.create_and_check_reader(*__SCREAMING_SNAKE_CASE					)


       def  lowerCAmelCase (				self					) ->					Any:



            '''simple docstring'''




            __snake_case         =					self.model_tester.prepare_config_and_inputs()[0]

            __snake_case         =					DPRQuestionEncoder(config=__SCREAMING_SNAKE_CASE					)
            model.to(__SCREAMING_SNAKE_CASE					)
            model.eval()

            with tempfile.TemporaryDirectory() as tmp_dirname:
                 model.save_pretrained(__SCREAMING_SNAKE_CASE					)
                 __snake_case         =					DPRQuestionEncoder.from_pretrained(__SCREAMING_SNAKE_CASE      ,					projection_dim=512					)

            self.assertIsNotNone(__SCREAMING_SNAKE_CASE					)




       @slow
       def  lowerCAmelCase (				self					) ->					Tuple:



            '''simple docstring'''




            for model_name in DPR_CONTEXT_ENCODER_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
                 __snake_case         =					DPRContextEncoder.from_pretrained(__SCREAMING_SNAKE_CASE					)
                 self.assertIsNotNone(__SCREAMING_SNAKE_CASE					)

            for model_name in DPR_CONTEXT_ENCODER_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
                 __snake_case         =					DPRContextEncoder.from_pretrained(__SCREAMING_SNAKE_CASE					)
                 self.assertIsNotNone(__SCREAMING_SNAKE_CASE					)

            for model_name in DPR_QUESTION_ENCODER_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
                 __snake_case         =					DPRQuestionEncoder.from_pretrained(__SCREAMING_SNAKE_CASE					)
                 self.assertIsNotNone(__SCREAMING_SNAKE_CASE					)

            for model_name in DPR_READER_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
                 __snake_case         =					DPRReader.from_pretrained(__SCREAMING_SNAKE_CASE					)
                 self.assertIsNotNone(__SCREAMING_SNAKE_CASE					)





@require_torch
class       lowerCAmelCase				(	unittest.TestCase):


       @slow
       def  lowerCAmelCase (				self					) ->					List[Any]:



            '''simple docstring'''




            __snake_case         =					DPRQuestionEncoder.from_pretrained('''facebook/dpr-question_encoder-single-nq-base'''      ,					return_dict=__SCREAMING_SNAKE_CASE					)
            model.to(__SCREAMING_SNAKE_CASE					)

            __snake_case         =					torch.tensor(
                [[101, 7592, 1010, 2003, 2026, 3899, 1_0140, 1029, 102]]      ,					dtype=torch.long      ,					device=__SCREAMING_SNAKE_CASE					)  # [CLS] hello, is my dog cute? [SEP]
            __snake_case         =					model(__SCREAMING_SNAKE_CASE					)[0]  # embedding shape = (1, 768)
            # compare the actual values for a slice.
            __snake_case         =					torch.tensor(
                [
                    [
                        0.03_236_253,
                        0.12_753_335,
                        0.16_818_509,
                        0.00_279_786,
                        0.3_896_933,
                        0.24_264_945,
                        0.2_178_971,
                        -0.02_335_227,
                        -0.08_481_959,
                        -0.14_324_117,
                    ]
                ]      ,					dtype=torch.float      ,					device=__SCREAMING_SNAKE_CASE      ,					)
            self.assertTrue(torch.allclose(output[:, :10]      ,					__SCREAMING_SNAKE_CASE      ,					atol=1E-4					)					)




       @slow
       def  lowerCAmelCase (				self					) ->					Any:



            '''simple docstring'''




            __snake_case         =					DPRReaderTokenizer.from_pretrained('''facebook/dpr-reader-single-nq-base'''					)
            __snake_case         =					DPRReader.from_pretrained('''facebook/dpr-reader-single-nq-base'''					)
            model.to(__SCREAMING_SNAKE_CASE					)

            __snake_case         =					tokenizer(
                questions='''What is love ?'''      ,					titles='''Haddaway'''      ,					texts='''What Is Love is a song recorded by the artist Haddaway'''      ,					padding=__SCREAMING_SNAKE_CASE      ,					return_tensors='''pt'''      ,					)
            encoded_inputs.to(__SCREAMING_SNAKE_CASE					)

            __snake_case         =					model(**__SCREAMING_SNAKE_CASE					)

            # compare the actual values for a slice.
            __snake_case         =					torch.tensor(
                [[-10.3_005, -10.7_765, -11.4_872, -11.6_841, -11.9_312, -10.3_002, -9.8_544, -11.7_378, -12.0_821, -10.2_975]]      ,					dtype=torch.float      ,					device=__SCREAMING_SNAKE_CASE      ,					)

            __snake_case         =					torch.tensor(
                [[-11.0_684, -11.7_041, -11.5_397, -10.3_465, -10.8_791, -6.8_443, -11.9_959, -11.0_364, -10.0_096, -6.8_405]]      ,					dtype=torch.float      ,					device=__SCREAMING_SNAKE_CASE      ,					)
            self.assertTrue(torch.allclose(outputs.start_logits[:, :10]      ,					__SCREAMING_SNAKE_CASE      ,					atol=1E-4					)					)
            self.assertTrue(torch.allclose(outputs.end_logits[:, :10]      ,					__SCREAMING_SNAKE_CASE      ,					atol=1E-4					)					)






