code: 
  
  
  
  
  
  
  """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
  lowercase__      =				{
      """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 	__lowerCamelCase			(						__UpperCamelCase )		->					set[tuple[str, str]]:
  
  		"""simple docstring"""
  
  
  
  
  
  
  
  		lowerCAmelCase_     :							Union[str, Any]             =    {node: {node} for node in graph}
  
  		lowerCAmelCase_     :							List[str]             =    {node: graph[node][:] for node in graph}
  
  		while len(__UpperCamelCase ) > 2:
  				# Choose a random edge.
  				lowerCAmelCase_     :							int             =    random.choice(list(graph_copy.keys() ) )
  				lowerCAmelCase_     :							Any             =    random.choice(graph_copy[u] )
  
  				# Contract edge (u, v) to new node uv
  				lowerCAmelCase_     :							Union[str, Any]             =    u + v
  				lowerCAmelCase_     :							List[Any]             =    list(set(graph_copy[u] + graph_copy[v] ) )
  				uv_neighbors.remove(__UpperCamelCase )
  				uv_neighbors.remove(__UpperCamelCase )
  				lowerCAmelCase_     :							str             =    uv_neighbors
  				for neighbor in uv_neighbors:
  						graph_copy[neighbor].append(__UpperCamelCase )
  
  				lowerCAmelCase_     :							Optional[int]             =    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(__UpperCamelCase )
  						if v in graph_copy[neighbor]:
  								graph_copy[neighbor].remove(__UpperCamelCase )
  
      # Find cutset.
  		lowerCAmelCase_     :							Union[str, Any]             =    [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))
  
  
  
  
style_context: 
  
  
  
  
  
  
  """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""")
  
  lowercase__      =				"""K-MEANS-CLUST/ """
  
  def 	__lowerCamelCase			(						__UpperCamelCase   , __UpperCamelCase   , __UpperCamelCase=None )		->					Optional[Any]:
  
  		"""simple docstring"""
  
  
  
  
  
  
  
  		if seed is not None:  # useful for obtaining consistent results
  				np.random.seed(__UpperCamelCase )
  		lowerCAmelCase_     :							List[Any]             =    data.shape[0]  # number of data points
  
  		# Pick K indices from range [0, N).
  		lowerCAmelCase_     :							Optional[Any]             =    np.random.randint(0   , __UpperCamelCase   , __UpperCamelCase )
  
  		# 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.
  		lowerCAmelCase_     :							List[str]             =    data[rand_indices, :]
  
  		return centroids
  
  def 	__lowerCamelCase			(						__UpperCamelCase   , __UpperCamelCase )		->					Dict:
  
  		"""simple docstring"""
  
  
  
  
  
  
  
  		return pairwise_distances(__UpperCamelCase   , __UpperCamelCase   , metric="euclidean" )
  
  def 	__lowerCamelCase			(						__UpperCamelCase   , __UpperCamelCase )		->					List[str]:
  
  		"""simple docstring"""
  
  
  
  
  
  
  
  		lowerCAmelCase_     :							Optional[Any]             =    centroid_pairwise_dist(__UpperCamelCase   , __UpperCamelCase )
  
  		# Compute cluster assignments for each data point:
  		# Fill in the blank (RHS only)
  		lowerCAmelCase_     :							str             =    np.argmin(__UpperCamelCase   , axis=1 )
  
  		return cluster_assignment
  
  def 	__lowerCamelCase			(						__UpperCamelCase   , __UpperCamelCase   , __UpperCamelCase )		->					Dict:
  
  		"""simple docstring"""
  
  
  
  
  
  
  
  		lowerCAmelCase_     :							Tuple             =    []
  		for i in range(__UpperCamelCase ):
  				# Select all data points that belong to cluster i. Fill in the blank (RHS only)
  				lowerCAmelCase_     :							List[Any]             =    data[cluster_assignment == i]
  				# Compute the mean of the data points. Fill in the blank (RHS only)
  				lowerCAmelCase_     :							List[str]             =    member_data_points.mean(axis=0 )
  				new_centroids.append(__UpperCamelCase )
  		lowerCAmelCase_     :							Tuple             =    np.array(__UpperCamelCase )
  
  		return new_centroids
  
  def 	__lowerCamelCase			(						__UpperCamelCase   , __UpperCamelCase   , __UpperCamelCase   , __UpperCamelCase )		->					int:
  
  		"""simple docstring"""
  
  
  
  
  
  
  
  		lowerCAmelCase_     :							Union[str, Any]             =    0.0
  		for i in range(__UpperCamelCase ):
  				# Select all data points that belong to cluster i. Fill in the blank (RHS only)
  				lowerCAmelCase_     :							List[str]             =    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)
  						lowerCAmelCase_     :							int             =    pairwise_distances(
  						    __UpperCamelCase   , [centroids[i]]   , metric="euclidean" )
  						lowerCAmelCase_     :							Optional[int]             =    distances**2
  						heterogeneity += np.sum(__UpperCamelCase )
  
  		return heterogeneity
  
  def 	__lowerCamelCase			(						__UpperCamelCase   , __UpperCamelCase )		->					Dict:
  
  		"""simple docstring"""
  
  
  
  
  
  
  
  		plt.figure(figsize=(7, 4) )
  		plt.plot(__UpperCamelCase   , 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 	__lowerCamelCase			(						__UpperCamelCase   , __UpperCamelCase   , __UpperCamelCase   , __UpperCamelCase=500   , __UpperCamelCase=None   , __UpperCamelCase=False )		->					List[Any]:
  
  		"""simple docstring"""
  
  
  
  
  
  
  
  		lowerCAmelCase_     :							Dict             =    initial_centroids[:]
  		lowerCAmelCase_     :							Optional[int]             =    None
  
  		for itr in range(__UpperCamelCase ):
  				if verbose:
  						print(__UpperCamelCase   , end="" )
  
  				# 1. Make cluster assignments using nearest centroids
  				lowerCAmelCase_     :							Optional[Any]             =    assign_clusters(__UpperCamelCase   , __UpperCamelCase )
  
  				# 2. Compute a new centroid for each of the k clusters, averaging all data
  				#    points assigned to that cluster.
  				lowerCAmelCase_     :							Tuple             =    revise_centroids(__UpperCamelCase   , __UpperCamelCase   , __UpperCamelCase )
  
  				# 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:
  						lowerCAmelCase_     :							Union[str, Any]             =    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
  						lowerCAmelCase_     :							Tuple             =    compute_heterogeneity(__UpperCamelCase   , __UpperCamelCase   , __UpperCamelCase   , __UpperCamelCase )
  						record_heterogeneity.append(__UpperCamelCase )
  
  				lowerCAmelCase_     :							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
  
  					lowercase__      =				ds.load_iris()
  					lowercase__      =				3
  					lowercase__      =				[]
  					lowercase__      =				get_initial_centroids(dataset["""data"""], k, seed=0)
  					lowercase__ ,     lowercase__      =				kmeans(
  					    dataset["""data"""],
  					    k,
  					    initial_centroids,
  					    maxiter=400,
  					    record_heterogeneity=heterogeneity,
  					    verbose=True,
  					)
  					plot_heterogeneity(heterogeneity, k)
  
  def 	__lowerCamelCase			(						__UpperCamelCase   , __UpperCamelCase   , __UpperCamelCase=None )		->					pd.DataFrame:
  
  		"""simple docstring"""
  
  
  
  
  
  
  
  		if fill_missing_report:
  				lowerCAmelCase_     :							str             =    df.fillna(value=__UpperCamelCase )
  		lowerCAmelCase_     :							Optional[int]             =    1
  		lowerCAmelCase_     :							Optional[int]             =    df.select_dtypes(np.number ).columns
  		lowerCAmelCase_     :							Dict             =    (
  		    df.groupby(["Cluster"] )[  # construct report dataframe
  		        numeric_cols
  		    ]  # group by cluster number
  		    .agg(
  		        [
  		            ("sum", np.sum),
  		            ("mean_with_zeros", lambda __UpperCamelCase : np.mean(np.nan_to_num(__UpperCamelCase ) )),
  		            ("mean_without_zeros", lambda __UpperCamelCase : x.replace(0   , np.NaN ).mean()),
  		            (
  		                "mean_25-75",
  		                lambda __UpperCamelCase : np.mean(
  		                    np.nan_to_num(
  		                        sorted(__UpperCamelCase )[
  		                            round(len(__UpperCamelCase ) * 25 / 100 ) : round(len(__UpperCamelCase ) * 75 / 100 )
  		                        ] ) ),
  		            ),
  		            ("mean_with_na", np.mean),
  		            ("min", lambda __UpperCamelCase : x.min()),
  		            ("5%", lambda __UpperCamelCase : x.quantile(0.05 )),
  		            ("25%", lambda __UpperCamelCase : x.quantile(0.25 )),
  		            ("50%", lambda __UpperCamelCase : x.quantile(0.50 )),
  		            ("75%", lambda __UpperCamelCase : x.quantile(0.75 )),
  		            ("95%", lambda __UpperCamelCase : x.quantile(0.95 )),
  		            ("max", lambda __UpperCamelCase : x.max()),
  		            ("count", lambda __UpperCamelCase : x.count()),
  		            ("stdev", lambda __UpperCamelCase : x.std()),
  		            ("mode", lambda __UpperCamelCase : x.mode()[0]),
  		            ("median", lambda __UpperCamelCase : x.median()),
  		            ("# > 0", lambda __UpperCamelCase : (x > 0).sum()),
  		        ] )
  		    .T.reset_index()
  		    .rename(index=__UpperCamelCase   , columns={"level_0": "Features", "level_1": "Type"} )
  		)  # rename columns
  		# calculate the size of cluster(count of clientID's)
  		lowerCAmelCase_     :							Optional[Any]             =    report[
  		    (report["Features"] == "dummy") & (report["Type"] == "count")
  		].copy()  # avoid SettingWithCopyWarning
  		lowerCAmelCase_     :							List[Any]             =    (
  		    "ClusterSize"  # rename created cluster df to match report column names
  		)
  		lowerCAmelCase_     :							Dict             =    "# of Customers"
  		lowerCAmelCase_     :							List[str]             =    pd.DataFrame(
  		    clustersize.iloc[:, 2:].values
  		    / clustersize.iloc[:, 2:].values.sum() )
  		lowerCAmelCase_     :							Optional[Any]             =    "% of Customers"  # rename created cluster df to match report column names
  		lowerCAmelCase_     :							Dict             =    "ClusterProportion"
  		lowerCAmelCase_     :							Optional[Any]             =    clusterproportion.columns.tolist()
  		lowerCAmelCase_     :							Optional[Any]             =    cols[-2:] + cols[:-2]
  		lowerCAmelCase_     :							Dict             =    clusterproportion[cols]  # rearrange columns to match report
  		lowerCAmelCase_     :							Union[str, Any]             =    report.columns
  		lowerCAmelCase_     :							Dict             =    pd.DataFrame(
  		    abs(
  		        report[report["Type"] == "count"].iloc[:, 2:].values
  		        - clustersize.iloc[:, 2:].values ) )  # generating df with count of nan values
  		lowerCAmelCase_     :							Union[str, Any]             =    0
  		lowerCAmelCase_     :							Any             =    "# of nan"
  		lowerCAmelCase_     :							Dict             =    report[
  		    report["Type"] == "count"
  		].Features.tolist()  # filling values in order to match report
  		lowerCAmelCase_     :							Optional[Any]             =    a.columns.tolist()
  		lowerCAmelCase_     :							Optional[Any]             =    cols[-2:] + cols[:-2]
  		lowerCAmelCase_     :							str             =    a[cols]  # rearrange columns to match report
  		lowerCAmelCase_     :							Tuple             =    report.columns  # rename columns to match report
  		lowerCAmelCase_     :							List[str]             =    report.drop(
  		    report[report.Type == "count"].index )  # drop count values except cluster size
  		lowerCAmelCase_     :							Tuple             =    pd.concat(
  		    [report, a, clustersize, clusterproportion]   , axis=0 )  # concat report with clustert size and nan values
  		lowerCAmelCase_     :							List[Any]             =    report["Features"].isin(__UpperCamelCase )
  		lowerCAmelCase_     :							Tuple             =    report.columns.tolist()
  		lowerCAmelCase_     :							List[str]             =    cols[0:2] + cols[-1:] + cols[2:-1]
  		lowerCAmelCase_     :							List[str]             =    report[cols]
  		lowerCAmelCase_     :							str             =    {
  		    "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,
  		}
  		lowerCAmelCase_     :							List[str]             =    (
  		    report.assign(
  		        Sortera=lambda __UpperCamelCase : x.Type.map(__UpperCamelCase )   , Sortera=lambda __UpperCamelCase : list(reversed(range(len(__UpperCamelCase ) ) ) )   , )
  		    .sort_values(["Sorter1", "Mark", "Sorter2"]   , ascending=__UpperCamelCase )
  		    .drop(["Sorter1", "Sorter2"]   , axis=1 )
  		)
  		lowerCAmelCase_     :							str             =    ""
  		lowerCAmelCase_     :							Any             =    report.reset_index()
  		lowerCAmelCase_     :							Any             =    report.drop(columns=["index"] )
  		return report
  
  
  if __name__ == "__main__":
  					import doctest
  
  					doctest.testmod()
  