{
    "nbformat": 4,
    "nbformat_minor": 5,
    "metadata": {
        "kernelspec": {
            "display_name": "Python",
            "language": "python",
            "name": "python"
        },
        "language_info": {
            "name": "python"
        }
    },
    "cells": [
        {
            "id": "31d1eecc",
            "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": "9912bf14",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "from scipy.sparse import csr_array\nfrom scipy.sparse.csgraph import maximum_bipartite_matching",
            "outputs": []
        },
        {
            "id": "96ed339d",
            "cell_type": "markdown",
            "source": "As a simple example, consider a bipartite graph in which the partitions\ncontain 2 and 3 elements respectively. Suppose that one partition contains\nvertices labelled 0 and 1, and that the other partition contains vertices\nlabelled A, B, and C. Suppose that there are edges connecting 0 and C,\n1 and A, and 1 and B. This graph would then be represented by the following\nsparse array:\n",
            "metadata": {}
        },
        {
            "id": "7ae6da83",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "graph = csr_array([[0, 0, 1], [1, 1, 0]])",
            "outputs": []
        },
        {
            "id": "1abb0cb5",
            "cell_type": "markdown",
            "source": "Here, the 1s could be anything, as long as they end up being stored as\nelements in the sparse array. We can now calculate maximum matchings as\nfollows:\n",
            "metadata": {}
        },
        {
            "id": "c408b913",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "print(maximum_bipartite_matching(graph, perm_type='column'))",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "[2 0]"
                    },
                    "execution_count": null
                }
            ]
        },
        {
            "id": "83423577",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "print(maximum_bipartite_matching(graph, perm_type='row'))",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "[ 1 -1  0]"
                    },
                    "execution_count": null
                }
            ]
        },
        {
            "id": "02cf5cdb",
            "cell_type": "markdown",
            "source": "The first output tells us that 1 and 2 are matched with C and A\nrespectively, and the second output tells us that A, B, and C are matched\nwith 1, nothing, and 0 respectively.\n\nNote that explicit zeros are still converted to edges. This means that a\ndifferent way to represent the above graph is by using the CSR structure\ndirectly as follows:\n",
            "metadata": {}
        },
        {
            "id": "c6fd70d1",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "data = [0, 0, 0]\nindices = [2, 0, 1]\nindptr = [0, 1, 3]\ngraph = csr_array((data, indices, indptr))\nprint(maximum_bipartite_matching(graph, perm_type='column'))",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "[2 0]"
                    },
                    "execution_count": null
                }
            ]
        },
        {
            "id": "b9086af4",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "print(maximum_bipartite_matching(graph, perm_type='row'))",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "[ 1 -1  0]"
                    },
                    "execution_count": null
                }
            ]
        },
        {
            "id": "00bf6c4b",
            "cell_type": "markdown",
            "source": "When one or both of the partitions are empty, the matching is empty as\nwell:\n",
            "metadata": {}
        },
        {
            "id": "9a6da54c",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "graph = csr_array((2, 0))\nprint(maximum_bipartite_matching(graph, perm_type='column'))",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "[-1 -1]"
                    },
                    "execution_count": null
                }
            ]
        },
        {
            "id": "854e46f3",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "print(maximum_bipartite_matching(graph, perm_type='row'))",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "[]"
                    },
                    "execution_count": null
                }
            ]
        },
        {
            "id": "3e4e1b9e",
            "cell_type": "markdown",
            "source": "When the input array is square, and the graph is known to admit a perfect\nmatching, i.e. a matching with the property that every vertex in the graph\nbelongs to some edge in the matching, then one can view the output as the\npermutation of rows (or columns) turning the input array into one with the\nproperty that all diagonal elements are non-empty:\n",
            "metadata": {}
        },
        {
            "id": "fd7e0856",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "a = [[0, 1, 2, 0], [1, 0, 0, 1], [2, 0, 0, 3], [0, 1, 3, 0]]\ngraph = csr_array(a)\nperm = maximum_bipartite_matching(graph, perm_type='row')\nprint(graph[perm].toarray())",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "[[1 0 0 1]\n [0 1 2 0]\n [0 1 3 0]\n [2 0 0 3]]"
                    },
                    "execution_count": null
                }
            ]
        }
    ]
}