





import numpy as np

import datasets


SCREAMING_SNAKE_CASE_						       =	"""
Compute the Mahalanobis Distance

Mahalonobis distance is the distance between a point and a distribution.
And not between two distinct points. It is effectively a multivariate equivalent of the Euclidean distance.
It was introduced by Prof. P. C. Mahalanobis in 1936
and has been used in various statistical applications ever since
[source: https://www.machinelearningplus.com/statistics/mahalanobis-distance/]
"""

SCREAMING_SNAKE_CASE_						       =	"""\
@article{de2000mahalanobis,
  title={The mahalanobis distance},
  author={De Maesschalck, Roy and Jouan-Rimbaud, Delphine and Massart, D{\'e}sir{\'e} L},
  journal={Chemometrics and intelligent laboratory systems},
  volume={50},
  number={1},
  pages={1--18},
  year={2000},
  publisher={Elsevier}
}
"""

SCREAMING_SNAKE_CASE_						       =	"""
Args:
    X: List of datapoints to be compared with the `reference_distribution`.
    reference_distribution: List of datapoints from the reference distribution we want to compare to.
Returns:
    mahalanobis: The Mahalonobis distance for each datapoint in `X`.
Examples:

    >>> mahalanobis_metric = datasets.load_metric(\"mahalanobis\")
    >>> results = mahalanobis_metric.compute(reference_distribution=[[0, 1], [1, 0]], X=[[0, 1]])
    >>> print(results)
    {'mahalanobis': array([0.5])}
"""

@datasets.utils.file_utils.add_start_docstrings(_DESCRIPTION							,				_KWARGS_DESCRIPTION       )
class 		UpperCamelCase__			(				datasets.Metric       ):



     '''simple docstring'''

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




           '''simple docstring'''


           return datasets.MetricInfo(
               description=_DESCRIPTION						,citation=_CITATION						,inputs_description=_KWARGS_DESCRIPTION						,features=datasets.Features(
                   {
                       """X""": datasets.Sequence(datasets.Value("""float"""						,id="""sequence"""	)						,id="""X"""	),
                   }	)						,)






     def     SCREAMING_SNAKE_CASE__  (							self						:   Tuple						,lowerCamelCase__						:   Union[str, Any]						,lowerCamelCase__						:   Tuple	)					->		int:




           '''simple docstring'''


           SCREAMING_SNAKE_CASE		=						np.array(lowerCamelCase__	)
           SCREAMING_SNAKE_CASE		=						np.array(lowerCamelCase__	)

           # Assert that arrays are 2D
           if len(X.shape	) != 2:
                 raise ValueError("""Expected `X` to be a 2D vector"""	)
           if len(reference_distribution.shape	) != 2:
                 raise ValueError("""Expected `reference_distribution` to be a 2D vector"""	)
           if reference_distribution.shape[0] < 2:
                 raise ValueError(
                     """Expected `reference_distribution` to be a 2D vector with more than one element in the first dimension"""	)

           # Get mahalanobis distance for each prediction
           SCREAMING_SNAKE_CASE		=						X - np.mean(lowerCamelCase__	)
           SCREAMING_SNAKE_CASE		=						np.cov(reference_distribution.T	)
           try:
                 SCREAMING_SNAKE_CASE		=						np.linalg.inv(lowerCamelCase__	)
           except np.linalg.LinAlgError:
                 SCREAMING_SNAKE_CASE		=						np.linalg.pinv(lowerCamelCase__	)
           SCREAMING_SNAKE_CASE		=						np.dot(lowerCamelCase__						,lowerCamelCase__	)
           SCREAMING_SNAKE_CASE		=						np.dot(lowerCamelCase__						,X_minus_mu.T	).diagonal()

           return {"mahalanobis": mahal_dist}









class 		UpperCamelCase__			:



     '''simple docstring'''

     def __init__(							self						:   int	)					->		str:




           '''simple docstring'''


           SCREAMING_SNAKE_CASE		=						{}






     def     SCREAMING_SNAKE_CASE__  (							self						:   List[Any]	)					->		None:




           '''simple docstring'''


           print(self.vertex	)
           for i in self.vertex:
                 print(lowerCamelCase__						,""" -> """						,""" -> """.join([str(lowerCamelCase__	) for j in self.vertex[i]]	)	)






     def     SCREAMING_SNAKE_CASE__  (							self						:   List[Any]						,lowerCamelCase__						:   int						,lowerCamelCase__						:   int	)					->		None:




           '''simple docstring'''


           if from_vertex in self.vertex:
                 self.vertex[from_vertex].append(lowerCamelCase__	)
           else:
                 # else make a new vertex
                 SCREAMING_SNAKE_CASE		=						[to_vertex]






     def     SCREAMING_SNAKE_CASE__  (							self						:   str	)					->		None:




           '''simple docstring'''


           SCREAMING_SNAKE_CASE		=						[False] * len(self.vertex	)

           # call the recursive helper function
           for i in range(len(self.vertex	)	):
                 if not visited[i]:
                       self.dfs_recursive(lowerCamelCase__						,lowerCamelCase__	)






     def     SCREAMING_SNAKE_CASE__  (							self						:   Any						,lowerCamelCase__						:   int						,lowerCamelCase__						:   list	)					->		None:




           '''simple docstring'''


           SCREAMING_SNAKE_CASE		=						True

           print(lowerCamelCase__						,end=""" """	)

           # Recur for all the vertices that are adjacent to this node
           for i in self.vertex:
                 if not visited[i]:
                       self.dfs_recursive(lowerCamelCase__						,lowerCamelCase__	)


if __name__ == "__main__":
      SCREAMING_SNAKE_CASE_						       =	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()
      print("""DFS:""")
      g.dfs()

      # OUTPUT:
      # 0  ->  1 -> 2
      # 1  ->  2
      # 2  ->  0 -> 3
      # 3  ->  3
      # DFS:
      #  0 1 2 3


