


'''simple docstring'''


import warnings

import numpy as np
import pandas as pd
from matplotlib import pyplot as plt
from sklearn.metrics import pairwise_distances

warnings.filterwarnings("""ignore""")

_UpperCamelCase          =     """K-MEANS-CLUST/ """


def 		_lowercase   (SCREAMING_SNAKE_CASE					,				SCREAMING_SNAKE_CASE					,				SCREAMING_SNAKE_CASE=None       ):




     '''simple docstring'''





     if seed is not None:  # useful for obtaining consistent results
          np.random.seed(lowercase_       )
     __A  :					Dict						     =       data.shape[0]  # number of data points

     # Pick K indices from range [0, N).
     __A  :					List[str]						     =       np.random.randint(0					,				lowercase_					,				lowercase_       )

     # Keep centroids as dense format, as many entries will be nonzero due to averaging.
     # As long as at least one document in a cluster contains a word,
     # it will carry a nonzero weight in the TF-IDF vector of the centroid.
     __A  :					str						     =       data[rand_indices, :]

     return centroids


def 		_lowercase   (SCREAMING_SNAKE_CASE					,				SCREAMING_SNAKE_CASE       ):




     '''simple docstring'''





     return pairwise_distances(lowercase_					,				lowercase_					,				metric="euclidean"       )


def 		_lowercase   (SCREAMING_SNAKE_CASE					,				SCREAMING_SNAKE_CASE       ):




     '''simple docstring'''





     __A  :					Optional[int]						     =       centroid_pairwise_dist(lowercase_					,				lowercase_       )

     # Compute cluster assignments for each data point:
     # Fill in the blank (RHS only)
     __A  :					Optional[Any]						     =       np.argmin(lowercase_					,				axis=1       )

     return cluster_assignment


def 		_lowercase   (SCREAMING_SNAKE_CASE					,				SCREAMING_SNAKE_CASE					,				SCREAMING_SNAKE_CASE       ):




     '''simple docstring'''





     __A  :					Dict						     =       []
     for i in range(lowercase_       ):
          # Select all data points that belong to cluster i. Fill in the blank (RHS only)
          __A  :					str						     =       data[cluster_assignment == i]
          # Compute the mean of the data points. Fill in the blank (RHS only)
          __A  :					Optional[int]						     =       member_data_points.mean(axis=0       )
          new_centroids.append(lowercase_       )
     __A  :					Tuple						     =       np.array(lowercase_       )

     return new_centroids


def 		_lowercase   (SCREAMING_SNAKE_CASE					,				SCREAMING_SNAKE_CASE					,				SCREAMING_SNAKE_CASE					,				SCREAMING_SNAKE_CASE       ):




     '''simple docstring'''





     __A  :					Dict						     =       0.0
     for i in range(lowercase_       ):
          # Select all data points that belong to cluster i. Fill in the blank (RHS only)
          __A  :					Union[str, Any]						     =       data[cluster_assignment == i, :]

          if member_data_points.shape[0] > 0:  # check if i-th cluster is non-empty
               # Compute distances from centroid to data points (RHS only)
               __A  :					Tuple						     =       pairwise_distances(
                   lowercase_					,				[centroids[i]]					,				metric="euclidean"       )
               __A  :					str						     =       distances**2
               heterogeneity += np.sum(lowercase_       )

     return heterogeneity


def 		_lowercase   (SCREAMING_SNAKE_CASE					,				SCREAMING_SNAKE_CASE       ):




     '''simple docstring'''





     plt.figure(figsize=(7, 4)       )
     plt.plot(lowercase_					,				linewidth=4       )
     plt.xlabel("# Iterations"       )
     plt.ylabel("Heterogeneity"       )
     plt.title(f"Heterogeneity of clustering over time, K={k:d}"       )
     plt.rcParams.update({"font.size": 16}       )
     plt.show()


def 		_lowercase   (SCREAMING_SNAKE_CASE					,				SCREAMING_SNAKE_CASE					,				SCREAMING_SNAKE_CASE					,				SCREAMING_SNAKE_CASE=500					,				SCREAMING_SNAKE_CASE=None					,				SCREAMING_SNAKE_CASE=False       ):




     '''simple docstring'''





     __A  :					List[Any]						     =       initial_centroids[:]
     __A  :					List[str]						     =       None

     for itr in range(lowercase_       ):
          if verbose:
               print(lowercase_					,				end=""       )

          # 1. Make cluster assignments using nearest centroids
          __A  :					Dict						     =       assign_clusters(lowercase_					,				lowercase_       )

          # 2. Compute a new centroid for each of the k clusters, averaging all data
          #    points assigned to that cluster.
          __A  :					Tuple						     =       revise_centroids(lowercase_					,				lowercase_					,				lowercase_       )

          # Check for convergence: if none of the assignments changed, stop
          if (
              prev_cluster_assignment is not None
              and (prev_cluster_assignment == cluster_assignment).all()
          ):
               break

          # Print number of new assignments
          if prev_cluster_assignment is not None:
               __A  :					Dict						     =       np.sum(prev_cluster_assignment != cluster_assignment       )
               if verbose:
                    print(
                        f"    {num_changed:5d} elements changed their cluster assignment."       )

        # Record heterogeneity convergence metric
          if record_heterogeneity is not None:
               # YOUR CODE HERE
               __A  :					Optional[Any]						     =       compute_heterogeneity(lowercase_					,				lowercase_					,				lowercase_					,				lowercase_       )
               record_heterogeneity.append(lowercase_       )

          __A  :					List[str]						     =       cluster_assignment[:]

     return centroids, cluster_assignment


# Mock test below
if False:  # change to true to run this test case.
      from sklearn import datasets as ds

      _UpperCamelCase          =     ds.load_iris()
      _UpperCamelCase          =     3
      _UpperCamelCase          =     []
      _UpperCamelCase          =     get_initial_centroids(dataset["""data"""], k, seed=0)
      _UpperCamelCase       ,      _UpperCamelCase          =     kmeans(
          dataset["""data"""],
          k,
          initial_centroids,
          maxiter=400,
          record_heterogeneity=heterogeneity,
          verbose=True,
      )
      plot_heterogeneity(heterogeneity, k)


def 		_lowercase   (SCREAMING_SNAKE_CASE					,				SCREAMING_SNAKE_CASE					,				SCREAMING_SNAKE_CASE=None       ):




     '''simple docstring'''





     if fill_missing_report:
          __A  :					Tuple						     =       df.fillna(value=lowercase_       )
     __A  :					Tuple						     =       1
     __A  :					Dict						     =       df.select_dtypes(np.number       ).columns
     __A  :					int						     =       (
         df.groupby(["Cluster"]       )[  # construct report dataframe
             numeric_cols
         ]  # group by cluster number
         .agg(
             [
                 ("sum", np.sum),
                 ("mean_with_zeros", lambda SCREAMING_SNAKE_CASE       : np.mean(np.nan_to_num(lowercase_       )       )),
                 ("mean_without_zeros", lambda SCREAMING_SNAKE_CASE       : x.replace(0					,				np.NaN       ).mean()),
                 (
                     "mean_25-75",
                     lambda SCREAMING_SNAKE_CASE       : np.mean(
                         np.nan_to_num(
                             sorted(lowercase_       )[
                                 round(len(lowercase_       ) * 25 / 100       ) : round(len(lowercase_       ) * 75 / 100       )
                             ]       )       ),
                 ),
                 ("mean_with_na", np.mean),
                 ("min", lambda SCREAMING_SNAKE_CASE       : x.min()),
                 ("5%", lambda SCREAMING_SNAKE_CASE       : x.quantile(0.05       )),
                 ("25%", lambda SCREAMING_SNAKE_CASE       : x.quantile(0.25       )),
                 ("50%", lambda SCREAMING_SNAKE_CASE       : x.quantile(0.50       )),
                 ("75%", lambda SCREAMING_SNAKE_CASE       : x.quantile(0.75       )),
                 ("95%", lambda SCREAMING_SNAKE_CASE       : x.quantile(0.95       )),
                 ("max", lambda SCREAMING_SNAKE_CASE       : x.max()),
                 ("count", lambda SCREAMING_SNAKE_CASE       : x.count()),
                 ("stdev", lambda SCREAMING_SNAKE_CASE       : x.std()),
                 ("mode", lambda SCREAMING_SNAKE_CASE       : x.mode()[0]),
                 ("median", lambda SCREAMING_SNAKE_CASE       : x.median()),
                 ("# > 0", lambda SCREAMING_SNAKE_CASE       : (x > 0).sum()),
             ]       )
         .T.reset_index()
         .rename(index=lowercase_					,				columns={"level_0": "Features", "level_1": "Type"}       )
     )  # rename columns
     # calculate the size of cluster(count of clientID's)
     __A  :					Dict						     =       report[
         (report['''Features'''] == '''dummy''') & (report['''Type'''] == '''count''')
     ].copy()  # avoid SettingWithCopyWarning
     __A  :					List[str]						     =       (
         '''ClusterSize'''  # rename created cluster df to match report column names
     )
     __A  :					Optional[Any]						     =       '''# of Customers'''
     __A  :					str						     =       pd.DataFrame(
         clustersize.iloc[:, 2:].values
         / clustersize.iloc[:, 2:].values.sum()       )
     __A  :					Tuple						     =       '''% of Customers'''  # rename created cluster df to match report column names
     __A  :					Tuple						     =       '''ClusterProportion'''
     __A  :					List[Any]						     =       clusterproportion.columns.tolist()
     __A  :					Dict						     =       cols[-2:] + cols[:-2]
     __A  :					Union[str, Any]						     =       clusterproportion[cols]  # rearrange columns to match report
     __A  :					Dict						     =       report.columns
     __A  :					Optional[Any]						     =       pd.DataFrame(
         abs(
             report[report["Type"] == "count"].iloc[:, 2:].values
             - clustersize.iloc[:, 2:].values       )       )  # generating df with count of nan values
     __A  :					List[str]						     =       0
     __A  :					int						     =       '''# of nan'''
     __A  :					List[str]						     =       report[
         report['''Type'''] == '''count'''
     ].Features.tolist()  # filling values in order to match report
     __A  :					Tuple						     =       a.columns.tolist()
     __A  :					List[str]						     =       cols[-2:] + cols[:-2]
     __A  :					List[Any]						     =       a[cols]  # rearrange columns to match report
     __A  :					Dict						     =       report.columns  # rename columns to match report
     __A  :					Optional[int]						     =       report.drop(
         report[report.Type == "count"].index       )  # drop count values except cluster size
     __A  :					List[str]						     =       pd.concat(
         [report, a, clustersize, clusterproportion]					,				axis=0       )  # concat report with clustert size and nan values
     __A  :					List[Any]						     =       report['''Features'''].isin(lowercase_       )
     __A  :					Tuple						     =       report.columns.tolist()
     __A  :					Any						     =       cols[0:2] + cols[-1:] + cols[2:-1]
     __A  :					List[str]						     =       report[cols]
     __A  :					List[Any]						     =       {
         '''ClusterSize''': 9,
         '''ClusterProportion''': 8,
         '''mean_with_zeros''': 7,
         '''mean_with_na''': 6,
         '''max''': 5,
         '''50%''': 4,
         '''min''': 3,
         '''25%''': 2,
         '''75%''': 1,
         '''# of nan''': 0,
         '''# > 0''': -1,
         '''sum_with_na''': -2,
     }
     __A  :					Optional[Any]						     =       (
         report.assign(
             Sortera=lambda SCREAMING_SNAKE_CASE       : x.Type.map(lowercase_       )					,				Sortera=lambda SCREAMING_SNAKE_CASE       : list(reversed(range(len(lowercase_       )       )       )       )					,				)
         .sort_values(["Sorter1", "Mark", "Sorter2"]					,				ascending=lowercase_       )
         .drop(["Sorter1", "Sorter2"]					,				axis=1       )
     )
     __A  :					Tuple						     =       ''''''
     __A  :					List[str]						     =       report.reset_index()
     __A  :					List[str]						     =       report.drop(columns=["index"]       )
     return report


if __name__ == "__main__":
      import doctest

      doctest.testmod()






'''simple docstring'''


from __future__ import annotations

import random

# Adjacency list representation of this graph:
# https://en.wikipedia.org/wiki/File:Single_run_of_Karger%E2%80%99s_Mincut_algorithm.svg
_UpperCamelCase          =     {
    """1""": ["""2""", """3""", """4""", """5"""],
    """2""": ["""1""", """3""", """4""", """5"""],
    """3""": ["""1""", """2""", """4""", """5""", """10"""],
    """4""": ["""1""", """2""", """3""", """5""", """6"""],
    """5""": ["""1""", """2""", """3""", """4""", """7"""],
    """6""": ["""7""", """8""", """9""", """10""", """4"""],
    """7""": ["""6""", """8""", """9""", """10""", """5"""],
    """8""": ["""6""", """7""", """9""", """10"""],
    """9""": ["""6""", """7""", """8""", """10"""],
    """10""": ["""6""", """7""", """8""", """9""", """3"""],
}


def 		_lowercase   (SCREAMING_SNAKE_CASE       ):




     '''simple docstring'''





     __A  :					Any						     =       {node: {node} for node in graph}

     __A  :					List[str]						     =       {node: graph[node][:] for node in graph}

     while len(SCREAMING_SNAKE_CASE       ) > 2:
          # Choose a random edge.
          __A  :					Tuple						     =       random.choice(list(graph_copy.keys()       )       )
          __A  :					Any						     =       random.choice(graph_copy[u]       )

          # Contract edge (u, v) to new node uv
          __A  :					str						     =       u + v
          __A  :					Any						     =       list(set(graph_copy[u] + graph_copy[v]       )       )
          uv_neighbors.remove(SCREAMING_SNAKE_CASE       )
          uv_neighbors.remove(SCREAMING_SNAKE_CASE       )
          __A  :					Any						     =       uv_neighbors
          for neighbor in uv_neighbors:
               graph_copy[neighbor].append(SCREAMING_SNAKE_CASE       )

          __A  :					str						     =       set(contracted_nodes[u].union(contracted_nodes[v]       )       )

          # Remove nodes u and v.
          del graph_copy[u]
          del graph_copy[v]
          for neighbor in uv_neighbors:
               if u in graph_copy[neighbor]:
                    graph_copy[neighbor].remove(SCREAMING_SNAKE_CASE       )
               if v in graph_copy[neighbor]:
                    graph_copy[neighbor].remove(SCREAMING_SNAKE_CASE       )

    # Find cutset.
     __A  :					int						     =       [contracted_nodes[node] for node in graph_copy]
     return {
         (node, neighbor)
         for node in groups[0]
         for neighbor in graph[node]
         if neighbor in groups[1]
     }


if __name__ == "__main__":
      print(partition_graph(TEST_GRAPH))

