





'''simple docstring'''



import unittest

from parameterized import parameterized

from transformers import OpenLlamaConfig, is_torch_available, set_seed
from transformers.testing_utils import require_torch, torch_device

from ...generation.test_utils import GenerationTesterMixin
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 OpenLlamaForCausalLM, OpenLlamaForSequenceClassification, OpenLlamaModel






class 							__lowercase    :







	'''simple docstring'''

	def __init__(self       ,_lowerCamelCase       ,_lowerCamelCase=13       ,_lowerCamelCase=7       ,_lowerCamelCase=True       ,_lowerCamelCase=True       ,_lowerCamelCase=False       ,_lowerCamelCase=True       ,_lowerCamelCase=99       ,_lowerCamelCase=32       ,_lowerCamelCase=5       ,_lowerCamelCase=4       ,_lowerCamelCase=37       ,_lowerCamelCase="gelu"       ,_lowerCamelCase=0.1       ,_lowerCamelCase=0.1       ,_lowerCamelCase=512       ,_lowerCamelCase=16       ,_lowerCamelCase=2       ,_lowerCamelCase=0.0_2       ,_lowerCamelCase=3       ,_lowerCamelCase=4       ,_lowerCamelCase=None       ,)							->							Optional[int]:







				'''simple docstring'''





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


	def   _UpperCAmelCase       (self	)							->							str:







				'''simple docstring'''





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

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

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

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

				__lowercase			  =							self.get_config()

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


	def   _UpperCAmelCase       (self	)							->							Dict:







				'''simple docstring'''





				return OpenLlamaConfig(
				    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       ,is_decoder=_lowerCamelCase       ,initializer_range=self.initializer_range       ,use_stable_embedding=_lowerCamelCase       ,)


	def   _UpperCAmelCase       (self       ,_lowerCamelCase       ,_lowerCamelCase       ,_lowerCamelCase       ,_lowerCamelCase       ,_lowerCamelCase       ,_lowerCamelCase       ,_lowerCamelCase	)							->							Any:







				'''simple docstring'''





				__lowercase			  =							OpenLlamaModel(config=_lowerCamelCase	)
				model.to(_lowerCamelCase	)
				model.eval()
				__lowercase			  =							model(_lowerCamelCase       ,attention_mask=_lowerCamelCase	)
				__lowercase			  =							model(_lowerCamelCase	)
				self.parent.assertEqual(result.last_hidden_state.shape       ,(self.batch_size, self.seq_length, self.hidden_size)	)


	def   _UpperCAmelCase       (self       ,_lowerCamelCase       ,_lowerCamelCase       ,_lowerCamelCase       ,_lowerCamelCase       ,_lowerCamelCase       ,_lowerCamelCase       ,_lowerCamelCase       ,_lowerCamelCase       ,_lowerCamelCase       ,)							->							int:







				'''simple docstring'''





				__lowercase			  =							True
				__lowercase			  =							OpenLlamaModel(_lowerCamelCase	)
				model.to(_lowerCamelCase	)
				model.eval()
				__lowercase			  =							model(
				    _lowerCamelCase       ,attention_mask=_lowerCamelCase       ,encoder_hidden_states=_lowerCamelCase       ,encoder_attention_mask=_lowerCamelCase       ,)
				__lowercase			  =							model(
				    _lowerCamelCase       ,attention_mask=_lowerCamelCase       ,encoder_hidden_states=_lowerCamelCase       ,)
				__lowercase			  =							model(_lowerCamelCase       ,attention_mask=_lowerCamelCase	)
				self.parent.assertEqual(result.last_hidden_state.shape       ,(self.batch_size, self.seq_length, self.hidden_size)	)


	def   _UpperCAmelCase       (self       ,_lowerCamelCase       ,_lowerCamelCase       ,_lowerCamelCase       ,_lowerCamelCase       ,_lowerCamelCase       ,_lowerCamelCase       ,_lowerCamelCase       ,_lowerCamelCase       ,_lowerCamelCase       ,)							->							Dict:







				'''simple docstring'''





				__lowercase			  =							OpenLlamaForCausalLM(config=_lowerCamelCase	)
				model.to(_lowerCamelCase	)
				model.eval()
				__lowercase			  =							model(_lowerCamelCase       ,attention_mask=_lowerCamelCase       ,labels=_lowerCamelCase	)
				self.parent.assertEqual(result.logits.shape       ,(self.batch_size, self.seq_length, self.vocab_size)	)


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







				'''simple docstring'''





				__lowercase			  =							True
				__lowercase			  =							True
				__lowercase			  =							OpenLlamaForCausalLM(config=_lowerCamelCase	)
				model.to(_lowerCamelCase	)
				model.eval()

				# first forward pass
				__lowercase			  =							model(
				    _lowerCamelCase       ,attention_mask=_lowerCamelCase       ,encoder_hidden_states=_lowerCamelCase       ,encoder_attention_mask=_lowerCamelCase       ,use_cache=_lowerCamelCase       ,)
				__lowercase			  =							outputs.past_key_values

				# create hypothetical multiple next token and extent to next_input_ids
				__lowercase			  =							ids_tensor((self.batch_size, 3)       ,config.vocab_size	)
				__lowercase			  =							ids_tensor((self.batch_size, 3)       ,vocab_size=2	)

				# append to next input_ids and
				__lowercase			  =							torch.cat([input_ids, next_tokens]       ,dim=-1	)
				__lowercase			  =							torch.cat([input_mask, next_mask]       ,dim=-1	)

				__lowercase			  =							model(
				    _lowerCamelCase       ,attention_mask=_lowerCamelCase       ,encoder_hidden_states=_lowerCamelCase       ,encoder_attention_mask=_lowerCamelCase       ,output_hidden_states=_lowerCamelCase       ,)['''hidden_states'''][0]
				__lowercase			  =							model(
				    _lowerCamelCase       ,attention_mask=_lowerCamelCase       ,encoder_hidden_states=_lowerCamelCase       ,encoder_attention_mask=_lowerCamelCase       ,past_key_values=_lowerCamelCase       ,output_hidden_states=_lowerCamelCase       ,)['''hidden_states'''][0]

				# select random slice
				__lowercase			  =							ids_tensor((1,)       ,output_from_past.shape[-1]	).item()
				__lowercase			  =							output_from_no_past[:, -3:, random_slice_idx].detach()
				__lowercase			  =							output_from_past[:, :, random_slice_idx].detach()

				self.parent.assertTrue(output_from_past_slice.shape[1] == next_tokens.shape[1]	)

				# test that outputs are equal for slice
				self.parent.assertTrue(torch.allclose(_lowerCamelCase       ,_lowerCamelCase       ,atol=1E-3	)	)


	def   _UpperCAmelCase       (self	)							->							Any:







				'''simple docstring'''





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






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







	'''simple docstring'''

	a     =    (
	    (OpenLlamaModel, OpenLlamaForCausalLM, OpenLlamaForSequenceClassification) if is_torch_available() else ()
	)
	a     =    (OpenLlamaForCausalLM,) if is_torch_available() else ()
	a     =    (
	    {
	        "feature-extraction": OpenLlamaModel,
	        "text-classification": OpenLlamaForSequenceClassification,
	        "text-generation": OpenLlamaForCausalLM,
	        "zero-shot": OpenLlamaForSequenceClassification,
	    }
	    if is_torch_available()
	    else {}
	)
	a     =    False
	a     =    False


	def   _UpperCAmelCase       (self	)							->							Tuple:







				'''simple docstring'''





				__lowercase			  =							OpenLlamaModelTester(self	)
				__lowercase			  =							ConfigTester(self       ,config_class=_lowerCamelCase       ,hidden_size=37	)


	def   _UpperCAmelCase       (self	)							->							Optional[int]:







				'''simple docstring'''





				self.config_tester.run_common_tests()


	def   _UpperCAmelCase       (self	)							->							int:







				'''simple docstring'''





				__lowercase			  =							self.model_tester.prepare_config_and_inputs()
				self.model_tester.create_and_check_model(*_lowerCamelCase	)


	def   _UpperCAmelCase       (self	)							->							List[Any]:







				'''simple docstring'''





				__lowercase			  =							self.model_tester.prepare_config_and_inputs()
				for type in ["absolute", "relative_key", "relative_key_query"]:
							__lowercase			  =							type
							self.model_tester.create_and_check_model(*_lowerCamelCase	)


	def   _UpperCAmelCase       (self	)							->							Dict:







				'''simple docstring'''





				__lowercase  ,						__lowercase			  =							self.model_tester.prepare_config_and_inputs_for_common()
				__lowercase			  =							3
				__lowercase			  =							input_dict['''input_ids''']
				__lowercase			  =							input_ids.ne(1	).to(_lowerCamelCase	)
				__lowercase			  =							ids_tensor([self.model_tester.batch_size]       ,self.model_tester.type_sequence_label_size	)
				__lowercase			  =							OpenLlamaForSequenceClassification(_lowerCamelCase	)
				model.to(_lowerCamelCase	)
				model.eval()
				__lowercase			  =							model(_lowerCamelCase       ,attention_mask=_lowerCamelCase       ,labels=_lowerCamelCase	)
				self.assertEqual(result.logits.shape       ,(self.model_tester.batch_size, self.model_tester.num_labels)	)


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







				'''simple docstring'''





				__lowercase  ,						__lowercase			  =							self.model_tester.prepare_config_and_inputs_for_common()
				__lowercase			  =							3
				__lowercase			  =							'''single_label_classification'''
				__lowercase			  =							input_dict['''input_ids''']
				__lowercase			  =							input_ids.ne(1	).to(_lowerCamelCase	)
				__lowercase			  =							ids_tensor([self.model_tester.batch_size]       ,self.model_tester.type_sequence_label_size	)
				__lowercase			  =							OpenLlamaForSequenceClassification(_lowerCamelCase	)
				model.to(_lowerCamelCase	)
				model.eval()
				__lowercase			  =							model(_lowerCamelCase       ,attention_mask=_lowerCamelCase       ,labels=_lowerCamelCase	)
				self.assertEqual(result.logits.shape       ,(self.model_tester.batch_size, self.model_tester.num_labels)	)


	def   _UpperCAmelCase       (self	)							->							List[Any]:







				'''simple docstring'''





				__lowercase  ,						__lowercase			  =							self.model_tester.prepare_config_and_inputs_for_common()
				__lowercase			  =							3
				__lowercase			  =							'''multi_label_classification'''
				__lowercase			  =							input_dict['''input_ids''']
				__lowercase			  =							input_ids.ne(1	).to(_lowerCamelCase	)
				__lowercase			  =							ids_tensor(
				    [self.model_tester.batch_size, config.num_labels]       ,self.model_tester.type_sequence_label_size	).to(torch.float	)
				__lowercase			  =							OpenLlamaForSequenceClassification(_lowerCamelCase	)
				model.to(_lowerCamelCase	)
				model.eval()
				__lowercase			  =							model(_lowerCamelCase       ,attention_mask=_lowerCamelCase       ,labels=_lowerCamelCase	)
				self.assertEqual(result.logits.shape       ,(self.model_tester.batch_size, self.model_tester.num_labels)	)


	@unittest.skip('''Open-Llama buffers include complex numbers, which breaks this test'''	)
	def   _UpperCAmelCase       (self	)							->							Union[str, Any]:







				'''simple docstring'''





				pass


	@parameterized.expand([('''linear''',), ('''dynamic''',)]	)
	def   _UpperCAmelCase       (self       ,_lowerCamelCase	)							->							Optional[int]:







				'''simple docstring'''





				__lowercase  ,						__lowercase			  =							self.model_tester.prepare_config_and_inputs_for_common()
				__lowercase			  =							ids_tensor([1, 10]       ,config.vocab_size	)
				__lowercase			  =							ids_tensor([1, int(config.max_position_embeddings * 1.5	)]       ,config.vocab_size	)

				set_seed(42	)  # Fixed seed at init time so the two models get the same random weights
				__lowercase			  =							OpenLlamaModel(_lowerCamelCase	)
				original_model.to(_lowerCamelCase	)
				original_model.eval()
				__lowercase			  =							original_model(_lowerCamelCase	).last_hidden_state
				__lowercase			  =							original_model(_lowerCamelCase	).last_hidden_state

				set_seed(42	)  # Fixed seed at init time so the two models get the same random weights
				__lowercase			  =							{'''type''': scaling_type, '''factor''': 10.0}
				__lowercase			  =							OpenLlamaModel(_lowerCamelCase	)
				scaled_model.to(_lowerCamelCase	)
				scaled_model.eval()
				__lowercase			  =							scaled_model(_lowerCamelCase	).last_hidden_state
				__lowercase			  =							scaled_model(_lowerCamelCase	).last_hidden_state

				# Dynamic scaling does not change the RoPE embeddings until it receives an input longer than the original
				# maximum sequence length, so the outputs for the short input should match.
				if scaling_type == "dynamic":
							self.assertTrue(torch.allclose(_lowerCamelCase       ,_lowerCamelCase       ,atol=1E-5	)	)
				else:
							self.assertFalse(torch.allclose(_lowerCamelCase       ,_lowerCamelCase       ,atol=1E-5	)	)

				# The output should be different for long inputs
				self.assertFalse(torch.allclose(_lowerCamelCase       ,_lowerCamelCase       ,atol=1E-5	)	)












'''simple docstring'''



import heapq




def 				_lowerCAmelCase  (			lowerCamelCase_     :					dict			):
			__lowercase			  =							[]

			# for each node and his adjacency list add them and the rank of the node to queue
			# using heapq module the queue will be filled like a Priority Queue
			# heapq works with a min priority queue, so I used -1*len(v) to build it
			for key, value in graph.items():
						# O(log(n))
						heapq.heappush(lowerCamelCase_						,    [-1 * len(lowerCamelCase_			), (key, value)]			)

			# chosen_vertices = set of chosen vertices
			__lowercase			  =							set()

			# while queue isn't empty and there are still edges
			#   (queue[0][0] is the rank of the node with max rank)
			while queue and queue[0][0] != 0:
						# extract vertex with max rank from queue and add it to chosen_vertices
						__lowercase			  =							heapq.heappop(lowerCamelCase_			)[1][0]
						chosen_vertices.add(lowerCamelCase_			)

						# Remove all arcs adjacent to argmax
						for elem in queue:
									# if v haven't adjacent node, skip
									if elem[0] == 0:
												continue
									# if argmax is reachable from elem
									# remove argmax from elem's adjacent list and update his rank
									if argmax in elem[1][1]:
												__lowercase			  =							elem[1][1].index(lowerCamelCase_			)
												del elem[1][1][index]
												elem[0] += 1
        # re-order the queue
						heapq.heapify(lowerCamelCase_			)
			return chosen_vertices


if __name__ == "__main__":
	import doctest

	doctest.testmod()

	_SCREAMING_SNAKE_CASE   =      {0: [1, 3], 1: [0, 3], 2: [0, 3, 4], 3: [0, 1, 2], 4: [2, 3]}
	print(f'''Minimum vertex cover:\n{greedy_min_vertex_cover(graph)}''')





