{
    "nbformat": 4,
    "nbformat_minor": 5,
    "metadata": {
        "kernelspec": {
            "display_name": "Python",
            "language": "python",
            "name": "python"
        },
        "language_info": {
            "name": "python"
        }
    },
    "cells": [
        {
            "id": "a392aa45",
            "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": "9235f9ac",
            "cell_type": "markdown",
            "source": "Perhaps the simplest flow problem is that of a graph of only two vertices\nwith an edge from source (0) to sink (1)\n```\n\n(0) --5--> (1)\n\n```\nHere, the maximum flow is simply the capacity of the edge:\n",
            "metadata": {}
        },
        {
            "id": "f76b9562",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "import numpy as np\nfrom scipy.sparse import csr_array\nfrom scipy.sparse.csgraph import maximum_flow\ngraph = csr_array([[0, 5], [0, 0]])\nmaximum_flow(graph, 0, 1).flow_value",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "5"
                    },
                    "execution_count": null
                }
            ]
        },
        {
            "id": "e594800c",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "maximum_flow(graph, 0, 1, method='edmonds_karp').flow_value",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "5"
                    },
                    "execution_count": null
                }
            ]
        },
        {
            "id": "ecc31fed",
            "cell_type": "markdown",
            "source": "If, on the other hand, there is a bottleneck between source and sink, that\ncan reduce the maximum flow\n```\n\n(0) --5--> (1) --3--> (2)\n\n```",
            "metadata": {}
        },
        {
            "id": "326da95b",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "graph = csr_array([[0, 5, 0], [0, 0, 3], [0, 0, 0]])\nmaximum_flow(graph, 0, 2).flow_value",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "3"
                    },
                    "execution_count": null
                }
            ]
        },
        {
            "id": "266e664f",
            "cell_type": "markdown",
            "source": "A less trivial example is given in [2], Chapter 26.1:\n",
            "metadata": {}
        },
        {
            "id": "a692b906",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "graph = csr_array([[0, 16, 13,  0,  0,  0],\n                   [0,  0, 10, 12,  0,  0],\n                   [0,  4,  0,  0, 14,  0],\n                   [0,  0,  9,  0,  0, 20],\n                   [0,  0,  0,  7,  0,  4],\n                   [0,  0,  0,  0,  0,  0]])\nmaximum_flow(graph, 0, 5).flow_value",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "23"
                    },
                    "execution_count": null
                }
            ]
        },
        {
            "id": "15bbd19a",
            "cell_type": "markdown",
            "source": "It is possible to reduce the problem of finding a maximum matching in a\nbipartite graph to a maximum flow problem: Let $G = ((U, V), E)$ be a\nbipartite graph. Then, add to the graph a source vertex with edges to every\nvertex in $U$ and a sink vertex with edges from every vertex in\n$V$. Finally, give every edge in the resulting graph a capacity of 1.\nThen, a maximum flow in the new graph gives a maximum matching in the\noriginal graph consisting of the edges in $E$ whose flow is positive.\n\nAssume that the edges are represented by a\n$\\lvert U \\rvert \\times \\lvert V \\rvert$ matrix in CSR format whose\n$(i, j)$'th entry is 1 if there is an edge from $i \\in U$ to\n$j \\in V$ and 0 otherwise; that is, the input is of the form required\nby :func:`maximum_bipartite_matching`. Then the CSR representation of the\ngraph constructed above contains this matrix as a block. Here's an example:\n",
            "metadata": {}
        },
        {
            "id": "7fbd4e5e",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "graph = csr_array([[0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 1, 0]])\nprint(graph.toarray())",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "[[0 1 0 1]\n [1 0 1 0]\n [0 1 1 0]]"
                    },
                    "execution_count": null
                }
            ]
        },
        {
            "id": "18e140b6",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "i, j = graph.shape\nn = graph.nnz\nindptr = np.concatenate([[0],\n                         graph.indptr + i,\n                         np.arange(n + i + 1, n + i + j + 1),\n                         [n + i + j]])\nindices = np.concatenate([np.arange(1, i + 1),\n                          graph.indices + i + 1,\n                          np.repeat(i + j + 1, j)])\ndata = np.ones(n + i + j, dtype=int)\n\ngraph_flow = csr_array((data, indices, indptr))\nprint(graph_flow.toarray())",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "[[0 1 1 1 0 0 0 0 0]\n [0 0 0 0 0 1 0 1 0]\n [0 0 0 0 1 0 1 0 0]\n [0 0 0 0 0 1 1 0 0]\n [0 0 0 0 0 0 0 0 1]\n [0 0 0 0 0 0 0 0 1]\n [0 0 0 0 0 0 0 0 1]\n [0 0 0 0 0 0 0 0 1]\n [0 0 0 0 0 0 0 0 0]]"
                    },
                    "execution_count": null
                }
            ]
        },
        {
            "id": "f3bc2c84",
            "cell_type": "markdown",
            "source": "At this point, we can find the maximum flow between the added sink and the\nadded source and the desired matching can be obtained by restricting the\nflow function to the block corresponding to the original graph:\n",
            "metadata": {}
        },
        {
            "id": "5d5789ca",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "result = maximum_flow(graph_flow, 0, i+j+1, method='dinic')\nmatching = result.flow[1:i+1, i+1:i+j+1]\nprint(matching.toarray())",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "[[0 1 0 0]\n [1 0 0 0]\n [0 0 1 0]]"
                    },
                    "execution_count": null
                }
            ]
        },
        {
            "id": "9d277410",
            "cell_type": "markdown",
            "source": "This tells us that the first, second, and third vertex in $U$ are\nmatched with the second, first, and third vertex in $V$ respectively.\n\nWhile this solves the maximum bipartite matching problem in general, note\nthat algorithms specialized to that problem, such as\n:func:`maximum_bipartite_matching`, will generally perform better.\n\nThis approach can also be used to solve various common generalizations of\nthe maximum bipartite matching problem. If, for instance, some vertices can\nbe matched with more than one other vertex, this may be handled by\nmodifying the capacities of the new graph appropriately.",
            "metadata": {}
        }
    ]
}