{
    "nbformat": 4,
    "nbformat_minor": 5,
    "metadata": {
        "kernelspec": {
            "display_name": "Python",
            "language": "python",
            "name": "python"
        },
        "language_info": {
            "name": "python"
        }
    },
    "cells": [
        {
            "id": "d9cfe165",
            "cell_type": "markdown",
            "source": "<div class='alert alert-warning'>\n\nSciPy's interactive examples with Jupyterlite are experimental and may not always work as expected. Execution of cells containing imports may result in large downloads (up to 60MB of content for the first import from SciPy). Load times when importing from SciPy may take roughly 10-20 seconds. If you notice any problems, feel free to open an [issue](https://github.com/scipy/scipy/issues/new/choose).\n\n</div>",
            "metadata": {}
        },
        {
            "id": "1eb6f2f6",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "from scipy.cluster.hierarchy import DisjointSet",
            "outputs": []
        },
        {
            "id": "b39178da",
            "cell_type": "markdown",
            "source": "Initialize a disjoint set:\n",
            "metadata": {}
        },
        {
            "id": "af9155e7",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "disjoint_set = DisjointSet([1, 2, 3, 'a', 'b'])",
            "outputs": []
        },
        {
            "id": "026cdb9a",
            "cell_type": "markdown",
            "source": "Merge some subsets:\n",
            "metadata": {}
        },
        {
            "id": "ee058e6b",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "disjoint_set.merge(1, 2)",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "True"
                    },
                    "execution_count": null
                }
            ]
        },
        {
            "id": "cb7565db",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "disjoint_set.merge(3, 'a')",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "True"
                    },
                    "execution_count": null
                }
            ]
        },
        {
            "id": "9ae84dd5",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "disjoint_set.merge('a', 'b')",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "True"
                    },
                    "execution_count": null
                }
            ]
        },
        {
            "id": "d3fee819",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "disjoint_set.merge('b', 'b')",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "False"
                    },
                    "execution_count": null
                }
            ]
        },
        {
            "id": "5200e054",
            "cell_type": "markdown",
            "source": "Find root elements:\n",
            "metadata": {}
        },
        {
            "id": "7193427f",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "disjoint_set[2]",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "1"
                    },
                    "execution_count": null
                }
            ]
        },
        {
            "id": "8cbd2bf9",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "disjoint_set['b']",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "3"
                    },
                    "execution_count": null
                }
            ]
        },
        {
            "id": "f495ae6d",
            "cell_type": "markdown",
            "source": "Test connectivity:\n",
            "metadata": {}
        },
        {
            "id": "4e1493cd",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "disjoint_set.connected(1, 2)",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "True"
                    },
                    "execution_count": null
                }
            ]
        },
        {
            "id": "2d949aaa",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "disjoint_set.connected(1, 'b')",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "False"
                    },
                    "execution_count": null
                }
            ]
        },
        {
            "id": "6cd7de6f",
            "cell_type": "markdown",
            "source": "List elements in disjoint set:\n",
            "metadata": {}
        },
        {
            "id": "7b53edb5",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "list(disjoint_set)",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "[1, 2, 3, 'a', 'b']"
                    },
                    "execution_count": null
                }
            ]
        },
        {
            "id": "8ca2df01",
            "cell_type": "markdown",
            "source": "Get the subset containing 'a':\n",
            "metadata": {}
        },
        {
            "id": "467aab83",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "disjoint_set.subset('a')",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "{'a', 3, 'b'}"
                    },
                    "execution_count": null
                }
            ]
        },
        {
            "id": "e7b6244b",
            "cell_type": "markdown",
            "source": "Get the size of the subset containing 'a' (without actually instantiating\nthe subset):\n",
            "metadata": {}
        },
        {
            "id": "7090dcdc",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "disjoint_set.subset_size('a')",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "3"
                    },
                    "execution_count": null
                }
            ]
        },
        {
            "id": "109614f6",
            "cell_type": "markdown",
            "source": "Get all subsets in the disjoint set:\n",
            "metadata": {}
        },
        {
            "id": "55249d07",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "disjoint_set.subsets()",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "[{1, 2}, {'a', 3, 'b'}]"
                    },
                    "execution_count": null
                }
            ]
        }
    ]
}