1599_forkfulkerson.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyOR32XkljJTHnmyse9U74uA",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/lmcanavals/acomplex/blob/main/1599_forkfulkerson.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "import math\n",
        "import numpy as np"
      ],
      "metadata": {
        "id": "JyHYCl89Vljl"
      },
      "execution_count": 4,
      "outputs": []
    },
    {
      "cell_type": "code",
      "execution_count": 9,
      "metadata": {
        "id": "MZhf6G7qRcxo"
      },
      "outputs": [],
      "source": [
        "def dfs(G, s, t):\n",
        "    n = len(G)\n",
        "    visited = [False]*n\n",
        "    path = [-1]*n\n",
        "    stack = [s]\n",
        "    while stack:\n",
        "        u = stack.pop()\n",
        "        if u == t:\n",
        "            break\n",
        "        if not visited[u]:\n",
        "            visited[u] = True\n",
        "            for v in reversed(range(n)):\n",
        "                if G[u][v] > 0 and not visited[v]:\n",
        "                    stack.append(v)\n",
        "                    path[v] = u\n",
        "\n",
        "    p = [t]\n",
        "    bottleneck = math.inf\n",
        "    while path[t] != -1:\n",
        "        if G[path[t]][t] < bottleneck:\n",
        "            bottleneck = G[path[t]][t]\n",
        "        t = path[t]\n",
        "        p.append(t)\n",
        "\n",
        "    return p, bottleneck"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "%%file graph.x\n",
        "0 6 4 1 0 0 0\n",
        "0 0 0 0 4 0 0\n",
        "0 0 0 3 1 3 0\n",
        "0 0 0 0 0 4 0\n",
        "0 0 0 0 0 0 4\n",
        "0 0 0 0 0 0 9\n",
        "0 0 0 0 0 0 0"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "hZAVIjDWV9Uc",
        "outputId": "30c626bd-b714-42d0-eb0d-08527c78bc8c"
      },
      "execution_count": 3,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Writing graph.x\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "G = np.loadtxt(\"graph.x\", dtype=int, delimiter=\" \")\n",
        "G"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "9NkvRTu8XVFE",
        "outputId": "0963dee7-205c-4e92-9f04-c27a456780ae"
      },
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[0, 6, 4, 1, 0, 0, 0],\n",
              "       [0, 0, 0, 0, 4, 0, 0],\n",
              "       [0, 0, 0, 3, 1, 3, 0],\n",
              "       [0, 0, 0, 0, 0, 4, 0],\n",
              "       [0, 0, 0, 0, 0, 0, 4],\n",
              "       [0, 0, 0, 0, 0, 0, 9],\n",
              "       [0, 0, 0, 0, 0, 0, 0]])"
            ]
          },
          "metadata": {},
          "execution_count": 5
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "labels = ['I', 'A', 'B', 'C', 'D', 'E', 'F']"
      ],
      "metadata": {
        "id": "2v8CARJWXj24"
      },
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "path, bn = dfs(G, 0, 6)\n",
        "[labels[x] for x in reversed(path)], bn"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "DiNkhpAYXyKM",
        "outputId": "7c5a0fd4-5879-410b-b946-101a49950578"
      },
      "execution_count": 19,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "(['I', 'A', 'D', 'F'], 4)"
            ]
          },
          "metadata": {},
          "execution_count": 19
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "#import pdb\n",
        "\n",
        "def fordFulkerson(G, s, t):\n",
        "    Gr = np.zeros_like(G)\n",
        "    Gf = np.zeros_like(G)\n",
        "\n",
        "    Gr = G.copy()\n",
        "    while True:\n",
        "        #pdb.set_trace()\n",
        "        apath, bn = dfs(Gr, s, t)\n",
        "        if bn == math.inf:\n",
        "            break\n",
        "\n",
        "        v = apath[0]\n",
        "        for u in apath[1:]:\n",
        "            Gr[u, v] -= bn\n",
        "            Gr[v, u] += bn\n",
        "            Gf[u, v] += bn\n",
        "            v = u\n",
        "\n",
        "    return Gf"
      ],
      "metadata": {
        "id": "1i7ibB14X12T"
      },
      "execution_count": 22,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "fordFulkerson(G, 0, 6)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "bV1EP5iXZoVB",
        "outputId": "10b94a96-2178-4fd4-f1bd-1bb1aca454dc"
      },
      "execution_count": 23,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[0, 4, 4, 1, 0, 0, 0],\n",
              "       [0, 0, 0, 0, 4, 0, 0],\n",
              "       [0, 0, 0, 3, 0, 2, 0],\n",
              "       [0, 0, 1, 0, 0, 3, 0],\n",
              "       [0, 0, 0, 0, 0, 0, 4],\n",
              "       [0, 0, 0, 0, 0, 0, 5],\n",
              "       [0, 0, 0, 0, 0, 0, 0]])"
            ]
          },
          "metadata": {},
          "execution_count": 23
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "%%file 1.2\n",
        "0 9 12 0 0 0 0\n",
        "0 0 6 9 4 3 0\n",
        "0 0 0 2 6 3 0\n",
        "0 0 0 0 2 0 7\n",
        "0 0 0 0 0 2 8\n",
        "0 0 0 0 0 0 5\n",
        "0 0 0 0 0 0 0"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "I09SaE8DZr7F",
        "outputId": "7665bcf1-e786-488a-d222-fc7fe0972428"
      },
      "execution_count": 26,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Overwriting 1.2\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "G = np.loadtxt(\"1.2\", dtype=int, delimiter=\" \")\n",
        "G"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Pos-pEgAizqF",
        "outputId": "4867097c-fe7e-4e5c-f6df-9882b14be438"
      },
      "execution_count": 27,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[ 0,  9, 12,  0,  0,  0,  0],\n",
              "       [ 0,  0,  6,  9,  4,  3,  0],\n",
              "       [ 0,  0,  0,  2,  6,  3,  0],\n",
              "       [ 0,  0,  0,  0,  2,  0,  7],\n",
              "       [ 0,  0,  0,  0,  0,  2,  8],\n",
              "       [ 0,  0,  0,  0,  0,  0,  5],\n",
              "       [ 0,  0,  0,  0,  0,  0,  0]])"
            ]
          },
          "metadata": {},
          "execution_count": 27
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "fordFulkerson(G, 0, 6)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "dNxb6Di-i6OG",
        "outputId": "2b38b192-fea0-4446-a4e8-cc30d0dd37be"
      },
      "execution_count": 28,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[ 0,  9, 11,  0,  0,  0,  0],\n",
              "       [ 0,  0,  6,  9,  3,  1,  0],\n",
              "       [ 0,  6,  0,  4,  7,  3,  0],\n",
              "       [ 0,  2,  2,  0,  4,  0,  7],\n",
              "       [ 0,  1,  1,  2,  0,  2,  8],\n",
              "       [ 0,  1,  0,  0,  0,  0,  5],\n",
              "       [ 0,  0,  0,  0,  0,  0,  0]])"
            ]
          },
          "metadata": {},
          "execution_count": 28
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "oBgmV-LkjBI4"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}