{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "3b6fc4e9",
   "metadata": {},
   "source": [
    "# Setup"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0dcca96e",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "import gurobipy as grb\n",
    "import matplotlib.pyplot as plt\n",
    "import matplotlib.cm as cm\n",
    "import networkx as nx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "dc341ae5",
   "metadata": {},
   "outputs": [],
   "source": [
    "pos = {'s': (0, 1), 'a': (1, 2), 'b': (3, 2), 'c': (2, 1),\n",
    "       'd': (1, 0), 'e': (3, 0), 't': (4, 1)}\n",
    "c = {('a', 'b'): 13, ('c', 'b'):  2, ('b', 't'):  8,\n",
    "     ('a', 'c'):  3, ('c', 'e'):  8, ('d', 'c'):  7,\n",
    "     ('d', 'e'):  5, ('e', 't'): 12, ('s', 'a'):  6,\n",
    "     ('s', 'c'):  7, ('s', 'd'): 11}\n",
    "V = list(pos)\n",
    "E = list(c)\n",
    "E_hat = E + [('t', 's')]\n",
    "Vp_hat = defaultdict(set)\n",
    "Vm_hat = defaultdict(set)\n",
    "for (i, j) in E_hat:\n",
    "    Vp_hat[j].add(i)\n",
    "    Vm_hat[i].add(j)\n",
    "\n",
    "graph = nx.DiGraph()\n",
    "graph.add_edges_from(E)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "49ca1e12",
   "metadata": {},
   "source": [
    "# LP Implementations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "46c122f6",
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "maxflow = grb.Model()\n",
    "x = maxflow.addVars(E_hat)\n",
    "con_z = maxflow.addConstrs(\n",
    "    (sum(x[j, i] for j in Vp_hat[i])\n",
    "     - sum(x[i, j] for j in Vm_hat[i]) == 0)\n",
    "    for i in V\n",
    ")\n",
    "con_y = maxflow.addConstrs(x[i, j] <= c[i, j] for (i, j) in E)\n",
    "maxflow.setObjective(x['t', 's'], grb.GRB.MAXIMIZE)\n",
    "maxflow.optimize()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7e3193b8",
   "metadata": {},
   "outputs": [],
   "source": [
    "mincut = grb.Model()\n",
    "y = mincut.addVars(E)\n",
    "z = mincut.addVars(V, lb=-grb.GRB.INFINITY, ub=grb.GRB.INFINITY)\n",
    "con_x = mincut.addConstrs(\n",
    "    y[i, j] >= z[i] - z[j]\n",
    "    for (i, j) in E\n",
    ")\n",
    "z['s'].lb = z['s'].ub = 1\n",
    "z['t'].lb = z['t'].ub = 0\n",
    "mincut.setObjective(sum(c[i, j] * y[i, j] for (i, j) in E), grb.GRB.MINIMIZE)\n",
    "mincut.optimize()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fe71558d",
   "metadata": {},
   "source": [
    "# Optimal Solution Illustrations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "97669392",
   "metadata": {},
   "outputs": [],
   "source": [
    "fig, ax = plt.subplots(figsize=(9, 5))\n",
    "ax.set_xlim([-0.25, 4.25])\n",
    "ax.set_ylim([-0.25, 2.25])\n",
    "\n",
    "node_size = 2000\n",
    "edgecolors = 'black'\n",
    "arrowsize = 15\n",
    "node_color = ['#49AF64' if con_z[i].Pi == con_z['s'].Pi else '#FE3F1C'\n",
    "              for i in V]\n",
    "style = [(0, (5, 5)) if con_y[i, j].Pi else '-'\n",
    "         for (i, j) in E]\n",
    "edge_color = [cm.binary(0.1 + 0.9 * x[(i, j)].X / c[i, j])\n",
    "              for (i, j) in E]\n",
    "edge_labels = {(i, j): '{}/{}'.format(int(x[i, j].X), c[i, j])\n",
    "               for (i, j) in E}\n",
    "\n",
    "nx.draw_networkx(graph, ax=ax, pos=pos, nodelist=V, edgelist=[],\n",
    "                 node_color=node_color, edgecolors=edgecolors,\n",
    "                 node_size=node_size)\n",
    "nx.draw_networkx_edges(graph, ax=ax, pos=pos, edgelist=E,\n",
    "                       edge_color=edge_color, style=style,\n",
    "                       node_size=node_size, arrowsize=arrowsize)\n",
    "nx.draw_networkx_edge_labels(graph, ax=ax, pos=pos,\n",
    "                             edge_labels=edge_labels)\n",
    "ax.axis('off')\n",
    "plt.savefig('maxflow-optimal.jpg', dpi=400)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "40825032",
   "metadata": {},
   "outputs": [],
   "source": [
    "fig, ax = plt.subplots(figsize=(9, 9 * 15 / 23))\n",
    "ax.set_xlim([-0.25, 4.25])\n",
    "ax.set_ylim([1 - 9 * 15 / 23 / 4, 1 + 9 * 15 / 23 / 4])\n",
    "\n",
    "nx.draw_networkx(graph, ax=ax, pos=pos, nodelist=V, edgelist=[],\n",
    "                 node_color=node_color, edgecolors=edgecolors,\n",
    "                 node_size=node_size)\n",
    "nx.draw_networkx_edges(graph, ax=ax, pos=pos, edgelist=E,\n",
    "                       edge_color=edge_color, style=style,\n",
    "                       node_size=node_size, arrowsize=arrowsize)\n",
    "nx.draw_networkx_edge_labels(graph, ax=ax, pos=pos,\n",
    "                             edge_labels=edge_labels)\n",
    "ax.axis('off')\n",
    "plt.savefig('maxflow-optimal.webp', format='webp', dpi=2300/9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "56e7b284",
   "metadata": {},
   "outputs": [],
   "source": [
    "fig, ax = plt.subplots(figsize=(9, 5))\n",
    "ax.set_xlim([-0.25, 4.25])\n",
    "ax.set_ylim([-0.25, 2.25])\n",
    "\n",
    "node_size = 2000\n",
    "edgecolors = 'black'\n",
    "arrowsize = 15\n",
    "node_color = ['#49AF64' if z[i].X == z['s'].X else '#FE3F1C'\n",
    "              for i in V]\n",
    "style = [(0, (5, 5)) if y[i, j].X == 1 else '-'\n",
    "         for (i, j) in E]\n",
    "edge_color = [cm.binary(0.1 + 0.9 * con_x[(i, j)].Pi / c[i, j])\n",
    "              for (i, j) in E]\n",
    "edge_labels = {(i, j): '{}/{}'.format(int(con_x[i, j].Pi), c[i, j])\n",
    "               for (i, j) in E}\n",
    "\n",
    "nx.draw_networkx(graph, ax=ax, pos=pos, nodelist=V, edgelist=[],\n",
    "                 node_color=node_color, edgecolors=edgecolors,\n",
    "                 node_size=node_size)\n",
    "nx.draw_networkx_edges(graph, ax=ax, pos=pos, edgelist=E,\n",
    "                       edge_color=edge_color, style=style,\n",
    "                       node_size=node_size, arrowsize=arrowsize)\n",
    "nx.draw_networkx_edge_labels(graph, ax=ax, pos=pos,\n",
    "                             edge_labels=edge_labels)\n",
    "ax.axis('off')\n",
    "plt.savefig('mincut-optimal.jpg', dpi=400)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a9fbf902",
   "metadata": {},
   "outputs": [],
   "source": [
    "fig, ax = plt.subplots(figsize=(9, 9 * 15 / 23))\n",
    "ax.set_xlim([-0.25, 4.25])\n",
    "ax.set_ylim([1 - 9 * 15 / 23 / 4, 1 + 9 * 15 / 23 / 4])\n",
    "\n",
    "nx.draw_networkx(graph, ax=ax, pos=pos, nodelist=V, edgelist=[],\n",
    "                 node_color=node_color, edgecolors=edgecolors,\n",
    "                 node_size=node_size)\n",
    "nx.draw_networkx_edges(graph, ax=ax, pos=pos, edgelist=E,\n",
    "                       edge_color=edge_color, style=style,\n",
    "                       node_size=node_size, arrowsize=arrowsize)\n",
    "nx.draw_networkx_edge_labels(graph, ax=ax, pos=pos,\n",
    "                             edge_labels=edge_labels)\n",
    "ax.axis('off')\n",
    "plt.savefig('mincut-optimal.webp', format='webp', dpi=2300/9)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}