

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						:Dict      =			"""K-MEANS-CLUST/ """




def        lowerCAmelCase(	SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_=None       )->		Union[str, Any]:



    """simple docstring"""






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

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

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

    return centroids




def        lowerCAmelCase(	SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_       )->		Any:



    """simple docstring"""






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




def        lowerCAmelCase(	SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_       )->		Union[str, Any]:



    """simple docstring"""






    UpperCamelCase_          =		centroid_pairwise_dist(SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_       )

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

    return cluster_assignment




def        lowerCAmelCase(	SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_       )->		int:



    """simple docstring"""






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

    return new_centroids




def        lowerCAmelCase(	SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_       )->		Any:



    """simple docstring"""






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

    return heterogeneity




def        lowerCAmelCase(	SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_       )->		Optional[Any]:



    """simple docstring"""






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




def        lowerCAmelCase(	SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_=5_0_0       ,		SCREAMING_SNAKE_CASE_=None       ,		SCREAMING_SNAKE_CASE_=False       )->		List[str]:



    """simple docstring"""






    UpperCamelCase_          =		initial_centroids[:]
    UpperCamelCase_          =		None

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

        # 1. Make cluster assignments using nearest centroids
        UpperCamelCase_          =		assign_clusters(SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_       )

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

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

        UpperCamelCase_          =		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						:str      =			ds.load_iris()
 SCREAMING_SNAKE_CASE						:Optional[Any]      =			3
 SCREAMING_SNAKE_CASE						:List[str]      =			[]
 SCREAMING_SNAKE_CASE						:str      =			get_initial_centroids(dataset["""data"""], k, seed=0)
 SCREAMING_SNAKE_CASE     ,				SCREAMING_SNAKE_CASE						:List[Any]      =			kmeans(
     dataset["""data"""],
     k,
     initial_centroids,
     maxiter=400,
     record_heterogeneity=heterogeneity,
     verbose=True,
 )
 plot_heterogeneity(heterogeneity, k)




def        lowerCAmelCase(	SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_=None       )->		pd.DataFrame:



    """simple docstring"""






    if fill_missing_report:
        UpperCamelCase_          =		df.fillna(value=SCREAMING_SNAKE_CASE_       )
    UpperCamelCase_          =		1
    UpperCamelCase_          =		df.select_dtypes(np.number       ).columns
    UpperCamelCase_          =		(
        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(SCREAMING_SNAKE_CASE_       )       )),
                ("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(SCREAMING_SNAKE_CASE_       )[
                                round(len(SCREAMING_SNAKE_CASE_       ) * 2_5 / 1_0_0       ) : round(len(SCREAMING_SNAKE_CASE_       ) * 7_5 / 1_0_0       )
                            ]       )       ),
                ),
                ("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=SCREAMING_SNAKE_CASE_       ,		columns={"level_0": "Features", "level_1": "Type"}       )
    )  # rename columns
    # calculate the size of cluster(count of clientID's)
    UpperCamelCase_          =		report[
        (report["Features"] == "dummy") & (report["Type"] == "count")
    ].copy()  # avoid SettingWithCopyWarning
    UpperCamelCase_          =		(
        "ClusterSize"  # rename created cluster df to match report column names
    )
    UpperCamelCase_          =		"# of Customers"
    UpperCamelCase_          =		pd.DataFrame(
        clustersize.iloc[:, 2:].values
        / clustersize.iloc[:, 2:].values.sum()       )
    UpperCamelCase_          =		"% of Customers"  # rename created cluster df to match report column names
    UpperCamelCase_          =		"ClusterProportion"
    UpperCamelCase_          =		clusterproportion.columns.tolist()
    UpperCamelCase_          =		cols[-2:] + cols[:-2]
    UpperCamelCase_          =		clusterproportion[cols]  # rearrange columns to match report
    UpperCamelCase_          =		report.columns
    UpperCamelCase_          =		pd.DataFrame(
        abs(
            report[report["Type"] == "count"].iloc[:, 2:].values
            - clustersize.iloc[:, 2:].values       )       )  # generating df with count of nan values
    UpperCamelCase_          =		0
    UpperCamelCase_          =		"# of nan"
    UpperCamelCase_          =		report[
        report["Type"] == "count"
    ].Features.tolist()  # filling values in order to match report
    UpperCamelCase_          =		a.columns.tolist()
    UpperCamelCase_          =		cols[-2:] + cols[:-2]
    UpperCamelCase_          =		a[cols]  # rearrange columns to match report
    UpperCamelCase_          =		report.columns  # rename columns to match report
    UpperCamelCase_          =		report.drop(
        report[report.Type == "count"].index       )  # drop count values except cluster size
    UpperCamelCase_          =		pd.concat(
        [report, a, clustersize, clusterproportion]       ,		axis=0       )  # concat report with clustert size and nan values
    UpperCamelCase_          =		report["Features"].isin(SCREAMING_SNAKE_CASE_       )
    UpperCamelCase_          =		report.columns.tolist()
    UpperCamelCase_          =		cols[0:2] + cols[-1:] + cols[2:-1]
    UpperCamelCase_          =		report[cols]
    UpperCamelCase_          =		{
        "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,
    }
    UpperCamelCase_          =		(
        report.assign(
            Sortera=lambda SCREAMING_SNAKE_CASE_       : x.Type.map(SCREAMING_SNAKE_CASE_       )       ,		Sortera=lambda SCREAMING_SNAKE_CASE_       : list(reversed(range(len(SCREAMING_SNAKE_CASE_       )       )       )       )       ,		)
        .sort_values(["Sorter1", "Mark", "Sorter2"]       ,		ascending=SCREAMING_SNAKE_CASE_       )
        .drop(["Sorter1", "Sorter2"]       ,		axis=1       )
    )
    UpperCamelCase_          =		""
    UpperCamelCase_          =		report.reset_index()
    UpperCamelCase_          =		report.drop(columns=["index"]       )
    return report


if __name__ == "__main__":
 import doctest

 doctest.testmod()



from __future__ import annotations

from queue import Queue




def        lowerCAmelCase(	SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_       )->		tuple[int, int]:



    """simple docstring"""






    a ^= b
    b ^= a
    a ^= b
    return a, b




def        lowerCAmelCase(	SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_       )->		list[list[int]]:



    """simple docstring"""






    UpperCamelCase_          =		1
    while (1 << j) < max_node:
        for i in range(1       ,		max_node + 1       ):
            UpperCamelCase_          =		parent[j - 1][parent[j - 1][i]]
        j += 1
    return parent




def        lowerCAmelCase(	SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_       )->		int:



    """simple docstring"""






    if level[u] < level[v]:
        UpperCamelCase_   ,    UpperCamelCase_          =		swap(SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_       )
    # making depth of u same as depth of v
    for i in range(1_8       ,		-1       ,		-1       ):
        if level[u] - (1 << i) >= level[v]:
            UpperCamelCase_          =		parent[i][u]
    # at the same depth if u==v that mean lca is found
    if u == v:
        return u
    # moving both nodes upwards till lca in found
    for i in range(1_8       ,		-1       ,		-1       ):
        if parent[i][u] not in [0, parent[i][v]]:
            UpperCamelCase_   ,    UpperCamelCase_          =		parent[i][u], parent[i][v]
    # returning longest common ancestor of u,v
    return parent[0][u]




def        lowerCAmelCase(	SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_ = 1       ,		)->		tuple[list[int], list[list[int]]]:



    """simple docstring"""






    UpperCamelCase_          =		0
    UpperCamelCase_          =		Queue(maxsize=SCREAMING_SNAKE_CASE_       )
    q.put(SCREAMING_SNAKE_CASE_       )
    while q.qsize() != 0:
        UpperCamelCase_          =		q.get()
        for v in graph[u]:
            if level[v] == -1:
                UpperCamelCase_          =		level[u] + 1
                q.put(SCREAMING_SNAKE_CASE_       )
                UpperCamelCase_          =		u
    return level, parent




def        lowerCAmelCase(	)->		None:



    """simple docstring"""






    UpperCamelCase_          =		1_3
    # initializing with 0
    UpperCamelCase_          =		[[0 for _ in range(max_node + 1_0       )] for _ in range(2_0       )]
    # initializing with -1 which means every node is unvisited
    UpperCamelCase_          =		[-1 for _ in range(max_node + 1_0       )]
    UpperCamelCase_          =		{
        1: [2, 3, 4],
        2: [5],
        3: [6, 7],
        4: [8],
        5: [9, 1_0],
        6: [1_1],
        7: [],
        8: [1_2, 1_3],
        9: [],
        1_0: [],
        1_1: [],
        1_2: [],
        1_3: [],
    }
    UpperCamelCase_   ,    UpperCamelCase_          =		breadth_first_search(SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_       ,		1       )
    UpperCamelCase_          =		create_sparse(SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_       )
    print("LCA of node 1 and 3 is: "       ,		lowest_common_ancestor(1       ,		3       ,		SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_       )       )
    print("LCA of node 5 and 6 is: "       ,		lowest_common_ancestor(5       ,		6       ,		SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_       )       )
    print("LCA of node 7 and 11 is: "       ,		lowest_common_ancestor(7       ,		1_1       ,		SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_       )       )
    print("LCA of node 6 and 7 is: "       ,		lowest_common_ancestor(6       ,		7       ,		SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_       )       )
    print("LCA of node 4 and 12 is: "       ,		lowest_common_ancestor(4       ,		1_2       ,		SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_       )       )
    print("LCA of node 8 and 8 is: "       ,		lowest_common_ancestor(8       ,		8       ,		SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_       )       )


if __name__ == "__main__":
 main()
