
from typing import TYPE_CHECKING

from ..utils import OptionalDependencyNotAvailable, _LazyModule, is_flax_available, is_tf_available, is_torch_available


__lowerCamelCase							= {
    """configuration_utils""": ["""GenerationConfig"""],
    """streamers""": ["""TextIteratorStreamer""", """TextStreamer"""],
}

try:
   if not is_torch_available():
      raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
   pass
else:
   __lowerCamelCase							= [
       """Constraint""",
       """ConstraintListState""",
       """DisjunctiveConstraint""",
       """PhrasalConstraint""",
   ]
   __lowerCamelCase							= [
       """BeamHypotheses""",
       """BeamScorer""",
       """BeamSearchScorer""",
       """ConstrainedBeamSearchScorer""",
   ]
   __lowerCamelCase							= [
       """EpsilonLogitsWarper""",
       """EtaLogitsWarper""",
       """ForcedBOSTokenLogitsProcessor""",
       """ForcedEOSTokenLogitsProcessor""",
       """HammingDiversityLogitsProcessor""",
       """InfNanRemoveLogitsProcessor""",
       """LogitsProcessor""",
       """LogitsProcessorList""",
       """LogitsWarper""",
       """MinLengthLogitsProcessor""",
       """MinNewTokensLengthLogitsProcessor""",
       """NoBadWordsLogitsProcessor""",
       """NoRepeatNGramLogitsProcessor""",
       """PrefixConstrainedLogitsProcessor""",
       """RepetitionPenaltyLogitsProcessor""",
       """SequenceBiasLogitsProcessor""",
       """EncoderRepetitionPenaltyLogitsProcessor""",
       """TemperatureLogitsWarper""",
       """TopKLogitsWarper""",
       """TopPLogitsWarper""",
       """TypicalLogitsWarper""",
       """EncoderNoRepeatNGramLogitsProcessor""",
       """ExponentialDecayLengthPenalty""",
       """LogitNormalization""",
   ]
   __lowerCamelCase							= [
       """MaxNewTokensCriteria""",
       """MaxLengthCriteria""",
       """MaxTimeCriteria""",
       """StoppingCriteria""",
       """StoppingCriteriaList""",
       """validate_stopping_criteria""",
   ]
   __lowerCamelCase							= [
       """GenerationMixin""",
       """top_k_top_p_filtering""",
       """GreedySearchEncoderDecoderOutput""",
       """GreedySearchDecoderOnlyOutput""",
       """SampleEncoderDecoderOutput""",
       """SampleDecoderOnlyOutput""",
       """BeamSearchEncoderDecoderOutput""",
       """BeamSearchDecoderOnlyOutput""",
       """BeamSampleEncoderDecoderOutput""",
       """BeamSampleDecoderOnlyOutput""",
       """ContrastiveSearchEncoderDecoderOutput""",
       """ContrastiveSearchDecoderOnlyOutput""",
   ]

try:
   if not is_tf_available():
      raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
   pass
else:
   __lowerCamelCase							= [
       """TFForcedBOSTokenLogitsProcessor""",
       """TFForcedEOSTokenLogitsProcessor""",
       """TFLogitsProcessor""",
       """TFLogitsProcessorList""",
       """TFLogitsWarper""",
       """TFMinLengthLogitsProcessor""",
       """TFNoBadWordsLogitsProcessor""",
       """TFNoRepeatNGramLogitsProcessor""",
       """TFRepetitionPenaltyLogitsProcessor""",
       """TFTemperatureLogitsWarper""",
       """TFTopKLogitsWarper""",
       """TFTopPLogitsWarper""",
       """TFForceTokensLogitsProcessor""",
       """TFSuppressTokensAtBeginLogitsProcessor""",
       """TFSuppressTokensLogitsProcessor""",
   ]
   __lowerCamelCase							= [
       """TFGenerationMixin""",
       """tf_top_k_top_p_filtering""",
       """TFGreedySearchDecoderOnlyOutput""",
       """TFGreedySearchEncoderDecoderOutput""",
       """TFSampleEncoderDecoderOutput""",
       """TFSampleDecoderOnlyOutput""",
       """TFBeamSearchEncoderDecoderOutput""",
       """TFBeamSearchDecoderOnlyOutput""",
       """TFBeamSampleEncoderDecoderOutput""",
       """TFBeamSampleDecoderOnlyOutput""",
       """TFContrastiveSearchEncoderDecoderOutput""",
       """TFContrastiveSearchDecoderOnlyOutput""",
   ]

try:
   if not is_flax_available():
      raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
   pass
else:
   __lowerCamelCase							= [
       """FlaxForcedBOSTokenLogitsProcessor""",
       """FlaxForcedEOSTokenLogitsProcessor""",
       """FlaxLogitsProcessor""",
       """FlaxLogitsProcessorList""",
       """FlaxLogitsWarper""",
       """FlaxMinLengthLogitsProcessor""",
       """FlaxTemperatureLogitsWarper""",
       """FlaxTopKLogitsWarper""",
       """FlaxTopPLogitsWarper""",
   ]
   __lowerCamelCase							= [
       """FlaxGenerationMixin""",
       """FlaxGreedySearchOutput""",
       """FlaxSampleOutput""",
       """FlaxBeamSearchOutput""",
   ]

if TYPE_CHECKING:
   from .configuration_utils import GenerationConfig
   from .streamers import TextIteratorStreamer, TextStreamer

   try:
      if not is_torch_available():
         raise OptionalDependencyNotAvailable()
   except OptionalDependencyNotAvailable:
      pass
   else:
      from .beam_constraints import Constraint, ConstraintListState, DisjunctiveConstraint, PhrasalConstraint
      from .beam_search import BeamHypotheses, BeamScorer, BeamSearchScorer, ConstrainedBeamSearchScorer
      from .logits_process import (
          EncoderNoRepeatNGramLogitsProcessor,
          EncoderRepetitionPenaltyLogitsProcessor,
          EpsilonLogitsWarper,
          EtaLogitsWarper,
          ExponentialDecayLengthPenalty,
          ForcedBOSTokenLogitsProcessor,
          ForcedEOSTokenLogitsProcessor,
          HammingDiversityLogitsProcessor,
          InfNanRemoveLogitsProcessor,
          LogitNormalization,
          LogitsProcessor,
          LogitsProcessorList,
          LogitsWarper,
          MinLengthLogitsProcessor,
          MinNewTokensLengthLogitsProcessor,
          NoBadWordsLogitsProcessor,
          NoRepeatNGramLogitsProcessor,
          PrefixConstrainedLogitsProcessor,
          RepetitionPenaltyLogitsProcessor,
          SequenceBiasLogitsProcessor,
          TemperatureLogitsWarper,
          TopKLogitsWarper,
          TopPLogitsWarper,
          TypicalLogitsWarper,
      )
      from .stopping_criteria import (
          MaxLengthCriteria,
          MaxNewTokensCriteria,
          MaxTimeCriteria,
          StoppingCriteria,
          StoppingCriteriaList,
          validate_stopping_criteria,
      )
      from .utils import (
          BeamSampleDecoderOnlyOutput,
          BeamSampleEncoderDecoderOutput,
          BeamSearchDecoderOnlyOutput,
          BeamSearchEncoderDecoderOutput,
          ContrastiveSearchDecoderOnlyOutput,
          ContrastiveSearchEncoderDecoderOutput,
          GenerationMixin,
          GreedySearchDecoderOnlyOutput,
          GreedySearchEncoderDecoderOutput,
          SampleDecoderOnlyOutput,
          SampleEncoderDecoderOutput,
          top_k_top_p_filtering,
      )

   try:
      if not is_tf_available():
         raise OptionalDependencyNotAvailable()
   except OptionalDependencyNotAvailable:
      pass
   else:
      from .tf_logits_process import (
          TFForcedBOSTokenLogitsProcessor,
          TFForcedEOSTokenLogitsProcessor,
          TFForceTokensLogitsProcessor,
          TFLogitsProcessor,
          TFLogitsProcessorList,
          TFLogitsWarper,
          TFMinLengthLogitsProcessor,
          TFNoBadWordsLogitsProcessor,
          TFNoRepeatNGramLogitsProcessor,
          TFRepetitionPenaltyLogitsProcessor,
          TFSuppressTokensAtBeginLogitsProcessor,
          TFSuppressTokensLogitsProcessor,
          TFTemperatureLogitsWarper,
          TFTopKLogitsWarper,
          TFTopPLogitsWarper,
      )
      from .tf_utils import (
          TFBeamSampleDecoderOnlyOutput,
          TFBeamSampleEncoderDecoderOutput,
          TFBeamSearchDecoderOnlyOutput,
          TFBeamSearchEncoderDecoderOutput,
          TFContrastiveSearchDecoderOnlyOutput,
          TFContrastiveSearchEncoderDecoderOutput,
          TFGenerationMixin,
          TFGreedySearchDecoderOnlyOutput,
          TFGreedySearchEncoderDecoderOutput,
          TFSampleDecoderOnlyOutput,
          TFSampleEncoderDecoderOutput,
          tf_top_k_top_p_filtering,
      )

   try:
      if not is_flax_available():
         raise OptionalDependencyNotAvailable()
   except OptionalDependencyNotAvailable:
      pass
   else:
      from .flax_logits_process import (
          FlaxForcedBOSTokenLogitsProcessor,
          FlaxForcedEOSTokenLogitsProcessor,
          FlaxLogitsProcessor,
          FlaxLogitsProcessorList,
          FlaxLogitsWarper,
          FlaxMinLengthLogitsProcessor,
          FlaxTemperatureLogitsWarper,
          FlaxTopKLogitsWarper,
          FlaxTopPLogitsWarper,
      )
      from .flax_utils import FlaxBeamSearchOutput, FlaxGenerationMixin, FlaxGreedySearchOutput, FlaxSampleOutput
else:
   import sys

   __lowerCamelCase							= _LazyModule(__name__, globals()["""__file__"""], _import_structure, module_spec=__spec__)







from __future__ import annotations






class 						UpperCAmelCase	:



   def __init__(self	:      List[str]					,		snake_case__	:      int				)	->			None:


          '''simple docstring'''


          snake_case :     Any           =   vertices
          snake_case :     str           =   [[0] * vertices for _ in range(snake_case__				)]



   def        _SCREAMING_SNAKE_CASE     (self	:      str					,		snake_case__	:      list[int]				)	->			None:


          '''simple docstring'''


          print("Vertex \t Distance from Source"				)
          for vertex in range(self.vertices				):
                 print(snake_case__					,		"\t\t"					,		distances_from_source[vertex]				)



   def        _SCREAMING_SNAKE_CASE     (self	:      Optional[int]					,		snake_case__	:      list[int]					,		snake_case__	:      list[bool]				)	->			int:


          '''simple docstring'''


          snake_case :     Union[str, Any]           =   1e7
          snake_case :     Any           =   0

          # Search not nearest vertex not in the shortest path tree
          for vertex in range(self.vertices				):
                 if distances_from_source[vertex] < minimum and visited[vertex] is False:
                        snake_case :     Union[str, Any]           =   distances_from_source[vertex]
                        snake_case :     str           =   vertex
          return min_index



   def        _SCREAMING_SNAKE_CASE     (self	:      Optional[Any]					,		snake_case__	:      int				)	->			None:


          '''simple docstring'''


          snake_case :     Optional[int]           =   [int(1e7				)] * self.vertices  # distances from the source
          snake_case :     Dict           =   0
          snake_case :     Union[str, Any]           =   [False] * self.vertices

          for _ in range(self.vertices				):
                 snake_case :     Dict           =   self.minimum_distance(snake_case__					,		snake_case__				)
                 snake_case :     List[str]           =   True

                 # Update dist value of the adjacent vertices
                 # of the picked vertex only if the current
                 # distance is greater than new distance and
                 # the vertex in not in the shortest path tree
                 for v in range(self.vertices				):
                        if (
                            self.graph[u][v] > 0
                            and visited[v] is False
                            and distances[v] > distances[u] + self.graph[u][v]
                        ):
                               snake_case :     Union[str, Any]           =   distances[u] + self.graph[u][v]

          self.print_solution(snake_case__				)


if __name__ == "__main__":
   __lowerCamelCase							= Graph(9)
   __lowerCamelCase							= [
       [0, 4, 0, 0, 0, 0, 0, 8, 0],
       [4, 0, 8, 0, 0, 0, 0, 11, 0],
       [0, 8, 0, 7, 0, 4, 0, 0, 2],
       [0, 0, 7, 0, 9, 14, 0, 0, 0],
       [0, 0, 0, 9, 0, 10, 0, 0, 0],
       [0, 0, 4, 14, 10, 0, 2, 0, 0],
       [0, 0, 0, 0, 0, 2, 0, 1, 6],
       [8, 11, 0, 0, 0, 0, 1, 0, 7],
       [0, 0, 2, 0, 0, 0, 6, 7, 0],
   ]
   graph.dijkstra(0)





