






"""simple docstring"""


from collections import deque



def    lowerCAmelCase							(       __UpperCamelCase					):




  """simple docstring"""







  return input(__UpperCamelCase					).strip().split(''' '''					)



def    lowerCAmelCase							(       __UpperCamelCase						,			__UpperCamelCase					):




  """simple docstring"""







  __A		     =					{}
  for i in range(__UpperCamelCase					):
    __A		     =					[]

  for e in range(__UpperCamelCase					):
    __A     ,       __A		     =					(int(__UpperCamelCase					) for i in _input(f'Edge {e + 1}: <node1> <node2> '					))
    graph[x].append(__UpperCamelCase					)
  return graph



def    lowerCAmelCase							(       __UpperCamelCase						,			__UpperCamelCase					):




  """simple docstring"""







  __A		     =					{}
  for i in range(__UpperCamelCase					):
    __A		     =					[]

  for e in range(__UpperCamelCase					):
    __A     ,       __A		     =					(int(__UpperCamelCase					) for i in _input(f'Edge {e + 1}: <node1> <node2> '					))
    graph[x].append(__UpperCamelCase					)
    graph[y].append(__UpperCamelCase					)
  return graph



def    lowerCAmelCase							(       __UpperCamelCase						,			__UpperCamelCase					):




  """simple docstring"""







  __A		     =					{}
  for i in range(__UpperCamelCase					):
    __A		     =					[]

  for e in range(__UpperCamelCase					):
    __A     ,       __A     ,       __A		     =					(int(__UpperCamelCase					) for i in _input(f'Edge {e + 1}: <node1> <node2> <weight> '					))
    graph[x].append((y, w)					)
    graph[y].append((x, w)					)
  return graph


if __name__ == "__main__":
       lowercase_	,						lowercase_								=	(int(i) for i in _input('Number of nodes and edges: '))

       lowercase_								=	int(
           _input(
               'Press 1 or 2 or 3 \n'
               '1. Unweighted directed \n'
               '2. Unweighted undirected \n'
               '3. Weighted undirected \n'
           )[0]
       )

       lowercase_								=	{
           1: initialize_unweighted_directed_graph,
           2: initialize_unweighted_undirected_graph,
           3: initialize_weighted_undirected_graph,
       }[graph_choice](n, m)



def    lowerCAmelCase							(       __UpperCamelCase						,			__UpperCamelCase					):




  """simple docstring"""







  __A     ,       __A		     =					{s}, [s]
  print(__UpperCamelCase					)
  while _s:
    __A		     =					0
    for i in g[_s[-1]]:
      if i not in vis:
        _s.append(__UpperCamelCase					)
        vis.add(__UpperCamelCase					)
        __A		     =					1
        print(__UpperCamelCase					)
        break
    if not flag:
      _s.pop()



def    lowerCAmelCase							(       __UpperCamelCase						,			__UpperCamelCase					):




  """simple docstring"""







  __A     ,       __A		     =					{s}, deque([s]					)
  print(__UpperCamelCase					)
  while q:
    __A		     =					q.popleft()
    for v in g[u]:
      if v not in vis:
        vis.add(__UpperCamelCase					)
        q.append(__UpperCamelCase					)
        print(__UpperCamelCase					)



def    lowerCAmelCase							(       __UpperCamelCase						,			__UpperCamelCase					):




  """simple docstring"""







  __A     ,       __A     ,       __A		     =					{s: 0}, set(), {s: 0}
  while True:
    if len(__UpperCamelCase					) == len(__UpperCamelCase					) - 1:
      break
    __A		     =					1_0_0_0_0_0
    for i in dist:
      if i not in known and dist[i] < mini:
        __A		     =					dist[i]
        __A		     =					i
    known.add(__UpperCamelCase					)
    for v in g[u]:
      if v[0] not in known and dist[u] + v[1] < dist.get(v[0]						,			1_0_0_0_0_0					):
        __A		     =					dist[u] + v[1]
        __A		     =					u
  for i in dist:
    if i != s:
      print(dist[i]					)



def    lowerCAmelCase							(       __UpperCamelCase						,			__UpperCamelCase=None						,			__UpperCamelCase=None					):




  """simple docstring"""







  if q is None:
    __A		     =					[1]
  if ind is None:
    __A		     =					[0] * (len(__UpperCamelCase					) + 1)  # SInce oth Index is ignored
    for u in g:
      for v in g[u]:
        ind[v] += 1
    __A		     =					deque()
    for i in g:
      if ind[i] == 0:
        q.append(__UpperCamelCase					)
  if len(__UpperCamelCase					) == 0:
    return
  __A		     =					q.popleft()
  print(__UpperCamelCase					)
  for w in g[v]:
    ind[w] -= 1
    if ind[w] == 0:
      q.append(__UpperCamelCase					)
  topo(__UpperCamelCase						,			__UpperCamelCase						,			__UpperCamelCase					)



def    lowerCAmelCase							(       ):




  """simple docstring"""







  __A		     =					input().strip()
  __A		     =					[]
  for _ in range(__UpperCamelCase					):
    a.append(map(__UpperCamelCase						,			input().strip().split()					)					)
  return a, n



def    lowerCAmelCase							(       __UpperCamelCase					):




  """simple docstring"""







  ((__A)     ,       (__A))		     =					a_and_n
  __A		     =					list(__UpperCamelCase					)
  __A		     =					[[0] * n for i in range(__UpperCamelCase					)]
  for k in range(__UpperCamelCase					):
    for i in range(__UpperCamelCase					):
      for j in range(__UpperCamelCase					):
        if dist[i][j] > dist[i][k] + dist[k][j]:
          __A		     =					dist[i][k] + dist[k][j]
          __A		     =					k
  print(__UpperCamelCase					)



def    lowerCAmelCase							(       __UpperCamelCase						,			__UpperCamelCase					):




  """simple docstring"""







  __A     ,       __A     ,       __A		     =					{s: 0}, set(), {s: 0}
  while True:
    if len(__UpperCamelCase					) == len(__UpperCamelCase					) - 1:
      break
    __A		     =					1_0_0_0_0_0
    for i in dist:
      if i not in known and dist[i] < mini:
        __A		     =					dist[i]
        __A		     =					i
    known.add(__UpperCamelCase					)
    for v in g[u]:
      if v[0] not in known and v[1] < dist.get(v[0]						,			1_0_0_0_0_0					):
        __A		     =					v[1]
        __A		     =					u
  return dist



def    lowerCAmelCase							(       ):




  """simple docstring"""







  __A     ,       __A		     =					map(__UpperCamelCase						,			input().split(''' '''					)					)
  __A		     =					[]
  for _ in range(__UpperCamelCase					):
    edges.append(map(__UpperCamelCase						,			input().split(''' '''					)					)					)
  return edges, n



def    lowerCAmelCase							(       __UpperCamelCase					):




  """simple docstring"""







  ((__A)     ,       (__A))		     =					e_and_n
  e.sort(reverse=__UpperCamelCase						,			key=lambda __UpperCamelCase					: x[2]					)
  __A		     =					[{i} for i in range(1						,			n + 1					)]
  while True:
    if len(__UpperCamelCase					) == 1:
      break
    print(__UpperCamelCase					)
    __A		     =					e.pop()
    for i in range(len(__UpperCamelCase					)					):
      if x[0] in s[i]:
        break
    for j in range(len(__UpperCamelCase					)					):
      if x[1] in s[j]:
        if i == j:
          break
        s[j].update(s[i]					)
        s.pop(__UpperCamelCase					)
        break





def    lowerCAmelCase							(       __UpperCamelCase					):




  """simple docstring"""







  __A		     =					[]
  for node in graph:
    if not graph[node]:
      isolated.append(__UpperCamelCase					)
  return isolated








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""")

SCREAMING_SNAKE_CASE__       			=				"""K-MEANS-CLUST/ """




def SCREAMING_SNAKE_CASE_  (				__lowerCamelCase:		List[str]  ,			__lowerCamelCase:		List[Any]  ,			__lowerCamelCase:		Tuple=None  ):







	'''simple docstring'''



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

	# Pick K indices from range [0, N).
	lowercase_			 = np.random.randint(0  ,			__lowerCamelCase  ,			__lowerCamelCase  )

	# 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.
	lowercase_			 = data[rand_indices, :]

	return centroids




def SCREAMING_SNAKE_CASE_  (				__lowerCamelCase:		Union[str, Any]  ,			__lowerCamelCase:		Union[str, Any]  ):







	'''simple docstring'''



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




def SCREAMING_SNAKE_CASE_  (				__lowerCamelCase:		List[str]  ,			__lowerCamelCase:		int  ):







	'''simple docstring'''



	lowercase_			 = centroid_pairwise_dist(__lowerCamelCase  ,			__lowerCamelCase  )

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

	return cluster_assignment




def SCREAMING_SNAKE_CASE_  (				__lowerCamelCase:		Dict  ,			__lowerCamelCase:		str  ,			__lowerCamelCase:		str  ):







	'''simple docstring'''



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

	return new_centroids




def SCREAMING_SNAKE_CASE_  (				__lowerCamelCase:		str  ,			__lowerCamelCase:		str  ,			__lowerCamelCase:		List[Any]  ,			__lowerCamelCase:		Optional[Any]  ):







	'''simple docstring'''



	lowercase_			 = 0.0
	for i in range(__lowerCamelCase  ):
		# Select all data points that belong to cluster i. Fill in the blank (RHS only)
		lowercase_			 = 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)
			lowercase_			 = pairwise_distances(
			    __lowerCamelCase  ,			[centroids[i]]  ,			metric="euclidean"  )
			lowercase_			 = distances**2
			heterogeneity += np.sum(__lowerCamelCase  )

	return heterogeneity




def SCREAMING_SNAKE_CASE_  (				__lowerCamelCase:		List[Any]  ,			__lowerCamelCase:		Union[str, Any]  ):







	'''simple docstring'''



	plt.figure(figsize=(7, 4)  )
	plt.plot(__lowerCamelCase  ,			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 SCREAMING_SNAKE_CASE_  (				__lowerCamelCase:		int  ,			__lowerCamelCase:		Dict  ,			__lowerCamelCase:		Any  ,			__lowerCamelCase:		str=500  ,			__lowerCamelCase:		Union[str, Any]=None  ,			__lowerCamelCase:		Optional[int]=False  ):







	'''simple docstring'''



	lowercase_			 = initial_centroids[:]
	lowercase_			 = None

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

		# 1. Make cluster assignments using nearest centroids
		lowercase_			 = assign_clusters(__lowerCamelCase  ,			__lowerCamelCase  )

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

		# 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:
			lowercase_			 = 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
			lowercase_			 = compute_heterogeneity(__lowerCamelCase  ,			__lowerCamelCase  ,			__lowerCamelCase  ,			__lowerCamelCase  )
			record_heterogeneity.append(__lowerCamelCase  )

		lowercase_			 = 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

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




def SCREAMING_SNAKE_CASE_  (				__lowerCamelCase:		pd.DataFrame  ,			__lowerCamelCase:		np.ndarray  ,			__lowerCamelCase:		str=None  ):







	'''simple docstring'''



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


if __name__ == "__main__":
							import doctest

							doctest.testmod()

