{
    "nbformat": 4,
    "nbformat_minor": 5,
    "metadata": {
        "kernelspec": {
            "display_name": "Python",
            "language": "python",
            "name": "python"
        },
        "language_info": {
            "name": "python"
        }
    },
    "cells": [
        {
            "id": "d830cdbe",
            "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": "6df1928c",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "from scipy.sparse import csr_array\nfrom scipy.sparse.csgraph import min_weight_full_bipartite_matching",
            "outputs": []
        },
        {
            "id": "9184e370",
            "cell_type": "markdown",
            "source": "Let us first consider an example in which all weights are equal:\n",
            "metadata": {}
        },
        {
            "id": "f50af955",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "biadjacency = csr_array([[1, 1, 1], [1, 0, 0], [0, 1, 0]])",
            "outputs": []
        },
        {
            "id": "4a84d971",
            "cell_type": "markdown",
            "source": "Here, all we get is a perfect matching of the graph:\n",
            "metadata": {}
        },
        {
            "id": "1ca47d1b",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "print(min_weight_full_bipartite_matching(biadjacency)[1])",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "[2 0 1]"
                    },
                    "execution_count": null
                }
            ]
        },
        {
            "id": "a1c925fb",
            "cell_type": "markdown",
            "source": "That is, the first, second, and third rows are matched with the third,\nfirst, and second column respectively. Note that in this example, the 0\nin the input matrix does *not* correspond to an edge with weight 0, but\nrather a pair of vertices not paired by an edge.\n\nNote also that in this case, the output matches the result of applying\n:func:`maximum_bipartite_matching`:\n",
            "metadata": {}
        },
        {
            "id": "94a91452",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "from scipy.sparse.csgraph import maximum_bipartite_matching\nbiadjacency = csr_array([[1, 1, 1], [1, 0, 0], [0, 1, 0]])\nprint(maximum_bipartite_matching(biadjacency, perm_type='column'))",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "[2 0 1]"
                    },
                    "execution_count": null
                }
            ]
        },
        {
            "id": "fcf39bbd",
            "cell_type": "markdown",
            "source": "When multiple edges are available, the ones with lowest weights are\npreferred:\n",
            "metadata": {}
        },
        {
            "id": "de0a78ca",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "biadjacency = csr_array([[3, 3, 6], [4, 3, 5], [10, 1, 8]])\nrow_ind, col_ind = min_weight_full_bipartite_matching(biadjacency)\nprint(col_ind)",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "[0 2 1]"
                    },
                    "execution_count": null
                }
            ]
        },
        {
            "id": "a848a62b",
            "cell_type": "markdown",
            "source": "The total weight in this case is $3 + 5 + 1 = 9$:\n",
            "metadata": {}
        },
        {
            "id": "5b8e9099",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "print(biadjacency[row_ind, col_ind].sum())",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "9"
                    },
                    "execution_count": null
                }
            ]
        },
        {
            "id": "7e195568",
            "cell_type": "markdown",
            "source": "When the matrix is not square, i.e. when the two partitions have different\ncardinalities, the matching is as large as the smaller of the two\npartitions:\n",
            "metadata": {}
        },
        {
            "id": "e22ff0d6",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "biadjacency = csr_array([[0, 1, 1], [0, 2, 3]])\nrow_ind, col_ind = min_weight_full_bipartite_matching(biadjacency)\nprint(row_ind, col_ind)",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "[0 1] [2 1]"
                    },
                    "execution_count": null
                }
            ]
        },
        {
            "id": "b413dbbc",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "biadjacency = csr_array([[0, 1], [3, 1], [1, 4]])\nrow_ind, col_ind = min_weight_full_bipartite_matching(biadjacency)\nprint(row_ind, col_ind)",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "[0 2] [1 0]"
                    },
                    "execution_count": null
                }
            ]
        },
        {
            "id": "b30cf8db",
            "cell_type": "markdown",
            "source": "When one or both of the partitions are empty, the matching is empty as\nwell:\n",
            "metadata": {}
        },
        {
            "id": "190e454e",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "biadjacency = csr_array((2, 0))\nrow_ind, col_ind = min_weight_full_bipartite_matching(biadjacency)\nprint(row_ind, col_ind)",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "[] []"
                    },
                    "execution_count": null
                }
            ]
        },
        {
            "id": "618f3f68",
            "cell_type": "markdown",
            "source": "In general, we will always reach the same sum of weights as if we had used\n:func:`scipy.optimize.linear_sum_assignment` but note that for that one,\nmissing edges are represented by a array entry of ``float('inf')``. Let us\ngenerate a random sparse array with integer entries between 1 and 10:\n",
            "metadata": {}
        },
        {
            "id": "3fc385c0",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "import numpy as np\nfrom scipy.sparse import random_array\nfrom scipy.optimize import linear_sum_assignment\nsparse = random_array((10, 10), rng=42, density=.5, format='coo') * 10\nsparse.data = np.ceil(sparse.data)\ndense = sparse.toarray()\ndense = np.full(sparse.shape, np.inf)\ndense[sparse.row, sparse.col] = sparse.data\nsparse = sparse.tocsr()\nrow_ind, col_ind = linear_sum_assignment(dense)\nprint(dense[row_ind, col_ind].sum())",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "25.0"
                    },
                    "execution_count": null
                }
            ]
        },
        {
            "id": "1b83538c",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "row_ind, col_ind = min_weight_full_bipartite_matching(sparse)\nprint(sparse[row_ind, col_ind].sum())",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "25.0"
                    },
                    "execution_count": null
                }
            ]
        }
    ]
}