




from __future__ import annotations

__SCREAMING_SNAKE_CASE 						={
    """A""": ["""B""", """C""", """E"""],
    """B""": ["""A""", """D""", """E"""],
    """C""": ["""A""", """F""", """G"""],
    """D""": ["""B"""],
    """E""": ["""A""", """B""", """D"""],
    """F""": ["""C"""],
    """G""": ["""C"""],
}






class  __magic_name__						:
				'''simple docstring'''







				def __init__(							self:   List[Any]		,					_lowerCamelCase:   dict[str, list[str]]		,					_lowerCamelCase:   str		):
											SCREAMING_SNAKE_CASE_   	=    graph
											# mapping node to its parent in resulting breadth first tree
											SCREAMING_SNAKE_CASE_   	=    {}
											SCREAMING_SNAKE_CASE_   	=    source_vertex


				def     _A							(							self:   Tuple		):
											SCREAMING_SNAKE_CASE_   	=    {self.source_vertex}
											SCREAMING_SNAKE_CASE_   	=    None
											SCREAMING_SNAKE_CASE_   	=    [self.source_vertex]  # first in first out queue

											while queue:
																		SCREAMING_SNAKE_CASE_   	=    queue.pop(0		)
																		for adjacent_vertex in self.graph[vertex]:
																									if adjacent_vertex not in visited:
																																visited.add(_lowerCamelCase		)
																																SCREAMING_SNAKE_CASE_   	=    vertex
																																queue.append(_lowerCamelCase		)





				def     _A							(							self:   List[str]		,					_lowerCamelCase:   str		):
											if target_vertex == self.source_vertex:
																		return self.source_vertex

											SCREAMING_SNAKE_CASE_   	=    self.parent.get(_lowerCamelCase		)
											if target_vertex_parent is None:
																		SCREAMING_SNAKE_CASE_   	=    (
																		    f"No path from vertex: {self.source_vertex} to vertex: {target_vertex}"
																		)
																		raise ValueError(_lowerCamelCase		)

											return self.shortest_path(_lowerCamelCase		) + f"->{target_vertex}"


if __name__ == "__main__":
			__SCREAMING_SNAKE_CASE 						=Graph(graph, """G""")
			g.breath_first_search()
			print(g.shortest_path("""D"""))
			print(g.shortest_path("""G"""))
			print(g.shortest_path("""Foo"""))








import re
import string

import numpy as np

import datasets


__SCREAMING_SNAKE_CASE 						="""
Returns the rate at which the input predicted strings exactly match their references, ignoring any strings input as part of the regexes_to_ignore list.
"""

__SCREAMING_SNAKE_CASE 						="""
Args:
    predictions: List of predicted texts.
    references: List of reference texts.
    regexes_to_ignore: List, defaults to None. Regex expressions of characters to
        ignore when calculating the exact matches. Note: these regexes are removed
        from the input data before the changes based on the options below (e.g. ignore_case,
        ignore_punctuation, ignore_numbers) are applied.
    ignore_case: Boolean, defaults to False. If true, turns everything
        to lowercase so that capitalization differences are ignored.
    ignore_punctuation: Boolean, defaults to False. If true, removes all punctuation before
        comparing predictions and references.
    ignore_numbers: Boolean, defaults to False. If true, removes all punctuation before
        comparing predictions and references.
Returns:
    exact_match: Dictionary containing exact_match rate. Possible values are between 0.0 and 100.0, inclusive.
Examples:
    >>> exact_match = datasets.load_metric(\"exact_match\")
    >>> refs = [\"the cat\", \"theater\", \"YELLING\", \"agent007\"]
    >>> preds = [\"cat?\", \"theater\", \"yelling\", \"agent\"]
    >>> results = exact_match.compute(references=refs, predictions=preds)
    >>> print(round(results[\"exact_match\"], 1))
    25.0

    >>> exact_match = datasets.load_metric(\"exact_match\")
    >>> refs = [\"the cat\", \"theater\", \"YELLING\", \"agent007\"]
    >>> preds = [\"cat?\", \"theater\", \"yelling\", \"agent\"]
    >>> results = exact_match.compute(references=refs, predictions=preds, regexes_to_ignore=[\"the \", \"yell\"], ignore_case=True, ignore_punctuation=True)
    >>> print(round(results[\"exact_match\"], 1))
    50.0


    >>> exact_match = datasets.load_metric(\"exact_match\")
    >>> refs = [\"the cat\", \"theater\", \"YELLING\", \"agent007\"]
    >>> preds = [\"cat?\", \"theater\", \"yelling\", \"agent\"]
    >>> results = exact_match.compute(references=refs, predictions=preds, regexes_to_ignore=[\"the \", \"yell\", \"YELL\"], ignore_case=True, ignore_punctuation=True)
    >>> print(round(results[\"exact_match\"], 1))
    75.0

    >>> exact_match = datasets.load_metric(\"exact_match\")
    >>> refs = [\"the cat\", \"theater\", \"YELLING\", \"agent007\"]
    >>> preds = [\"cat?\", \"theater\", \"yelling\", \"agent\"]
    >>> results = exact_match.compute(references=refs, predictions=preds, regexes_to_ignore=[\"the \", \"yell\", \"YELL\"], ignore_case=True, ignore_punctuation=True, ignore_numbers=True)
    >>> print(round(results[\"exact_match\"], 1))
    100.0

    >>> exact_match = datasets.load_metric(\"exact_match\")
    >>> refs = [\"The cat sat on the mat.\", \"Theaters are great.\", \"It's like comparing oranges and apples.\"]
    >>> preds = [\"The cat sat on the mat?\", \"Theaters are great.\", \"It's like comparing apples and oranges.\"]
    >>> results = exact_match.compute(references=refs, predictions=preds)
    >>> print(round(results[\"exact_match\"], 1))
    33.3

"""

__SCREAMING_SNAKE_CASE 						="""
"""






@datasets.utils.file_utils.add_start_docstrings(_DESCRIPTION    ,  _KWARGS_DESCRIPTION)
class  __magic_name__						(  datasets.Metric):
				'''simple docstring'''







				def     _A							(							self:   Optional[int]		):
											return datasets.MetricInfo(
											    description=_DESCRIPTION		,					citation=_CITATION		,					inputs_description=_KWARGS_DESCRIPTION		,					features=datasets.Features(
											        {
											            '''predictions''': datasets.Value('''string'''		,					id='''sequence'''		),
											            '''references''': datasets.Value('''string'''		,					id='''sequence'''		),
											        }		)		,					reference_urls=[]		,					)





				def     _A							(							self:   Tuple		,					_lowerCamelCase:   int		,					_lowerCamelCase:   int		,					_lowerCamelCase:   Tuple=None		,					_lowerCamelCase:   str=False		,					_lowerCamelCase:   List[str]=False		,					_lowerCamelCase:   List[str]=False		,					):
											if regexes_to_ignore is not None:
																		for s in regexes_to_ignore:
																									SCREAMING_SNAKE_CASE_   	=    np.array([re.sub(_lowerCamelCase		,					''''''		,					_lowerCamelCase		) for x in predictions]		)
																									SCREAMING_SNAKE_CASE_   	=    np.array([re.sub(_lowerCamelCase		,					''''''		,					_lowerCamelCase		) for x in references]		)
											else:
																		SCREAMING_SNAKE_CASE_   	=    np.asarray(_lowerCamelCase		)
																		SCREAMING_SNAKE_CASE_   	=    np.asarray(_lowerCamelCase		)

											if ignore_case:
																		SCREAMING_SNAKE_CASE_   	=    np.char.lower(_lowerCamelCase		)
																		SCREAMING_SNAKE_CASE_   	=    np.char.lower(_lowerCamelCase		)

											if ignore_punctuation:
																		SCREAMING_SNAKE_CASE_   	=    string.punctuation.maketrans(''''''		,					''''''		,					string.punctuation		)
																		SCREAMING_SNAKE_CASE_   	=    np.char.translate(_lowerCamelCase		,					table=_lowerCamelCase		)
																		SCREAMING_SNAKE_CASE_   	=    np.char.translate(_lowerCamelCase		,					table=_lowerCamelCase		)

											if ignore_numbers:
																		SCREAMING_SNAKE_CASE_   	=    string.digits.maketrans(''''''		,					''''''		,					string.digits		)
																		SCREAMING_SNAKE_CASE_   	=    np.char.translate(_lowerCamelCase		,					table=_lowerCamelCase		)
																		SCREAMING_SNAKE_CASE_   	=    np.char.translate(_lowerCamelCase		,					table=_lowerCamelCase		)

											SCREAMING_SNAKE_CASE_   	=    predictions == references

											return {"exact_match": np.mean(_lowerCamelCase		) * 1_00}


