{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "91cf9d18",
   "metadata": {},
   "source": [
    "# Graph-Clear\n",
    "\n",
    "In a graph-clear problem, we are given a floormap represented by an undirected graph $(N, E)$, where $N = \\{ 0, ..., n - 1 \\}$ is the set of nodes, and $E \\subseteq N \\times N$ is the set of edges.\n",
    "Each node corresponds to a room, and edges are corridors connecting two rooms.\n",
    "We want to clear intruders in the floor using robots.\n",
    "At each time step, we can clear a node $i$ using $a_i$ robots to sweep the room and use $b_{ij}$ robots to block each incident edge $\\{ i, j \\}$.\n",
    "At the beginning, all nodes are contaminated, i.e., potentially include intruders.\n",
    "Even if a node is swept, if there exists a non-blocked path from a contaminated node to that node, it become contaminated again in the next time step.\n",
    "Therefore, we may want to block edges that are not directly connected to the currently swept node.\n",
    "We want to find a schedule over time steps to clear all nodes while minimizing the maximum number of robots used at a time.\n",
    "\n",
    "## DP Formulation\n",
    "\n",
    "It is proved that there exists an optimal schedule where an already swept node never becomes contaminated again.\n",
    "We just need to clear a node one by one while blocking all edges connected to already swept nodes.\n",
    "Let $C \\subseteq N$ be the set of already swept nodes, and assume that $b_{ij} = 0$ if $\\{ i, j \\} \\notin E$.\n",
    "To clear node $c \\in \\overline{C} = N \\setminus C$, we need to use $a_c$ robots to sweep $c$, $\\sum_{i \\in N} b_{ci}$ robots to block the edges incident to $c$, and $\\sum_{i \\in C} \\sum_{j \\in \\overline{C} \\setminus \\{ c \\}} b_{ij}$ robots to block the edges connected to already swept nodes.\n",
    "Therefore,\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "    \\text{compute } & V(\\emptyset) \\\\\n",
    "    & V(C) = \\begin{cases}\n",
    "        \\min\\limits_{c \\in \\overline{C}} \\max\\left\\{ a_c + \\sum\\limits_{i \\in N} b_{ci} + \\sum\\limits_{i \\in C} \\sum\\limits_{j \\in \\overline{C} \\setminus \\{ c \\}} b_{ij}, V(C \\cup \\{ c \\}) \\right\\} & \\text{if } C \\neq N \\\\\n",
    "        0 & \\text{if } C = N\n",
    "    \\end{cases} \\\\\n",
    "    & V(C) \\geq 0.\n",
    "\\end{align}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fb4c99fe",
   "metadata": {},
   "source": [
    "## Install DIDPPy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "76e28461",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Requirement already satisfied: didppy in /home/kuro/tidel/code/didp-rs/didppy/.venv/lib/python3.10/site-packages (0.7.1)\r\n"
     ]
    }
   ],
   "source": [
    "!pip install didppy"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "311b05a5",
   "metadata": {},
   "source": [
    "## Data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "3207593a",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Number of nodes\n",
    "n = 4\n",
    "# Node weights\n",
    "a = [1, 2, 2, 3]\n",
    "# Edge weights\n",
    "b = [\n",
    "    [0, 2, 3, 0],\n",
    "    [2, 0, 0, 1],\n",
    "    [3, 0, 0, 2],\n",
    "    [0, 1, 2, 0],\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f2bfcdef",
   "metadata": {},
   "source": [
    "## Modeling"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "2abdf4f3",
   "metadata": {},
   "outputs": [],
   "source": [
    "import didppy as dp\n",
    "\n",
    "model = dp.Model()\n",
    "\n",
    "node = model.add_object_type(number=n)\n",
    "\n",
    "# C\n",
    "clean = model.add_set_var(object_type=node, target=[])\n",
    "\n",
    "all_nodes = model.create_set_const(object_type=node, value=list(range(n)))\n",
    "node_weight = model.add_int_table(a)\n",
    "edge_weight = model.add_int_table(b)\n",
    "\n",
    "model.add_base_case([clean == all_nodes])\n",
    "\n",
    "for c in range(n):\n",
    "    contaminated = clean.complement().remove(c)\n",
    "    sweep = dp.Transition(\n",
    "        name=\"sweep {}\".format(c),\n",
    "        cost=dp.max(\n",
    "            dp.IntExpr.state_cost(),\n",
    "            node_weight[c] + edge_weight[c, all_nodes] + edge_weight[clean, contaminated],\n",
    "        ),\n",
    "        effects=[(clean, clean.add(c))],\n",
    "        preconditions=[~clean.contains(c)],\n",
    "    )\n",
    "    model.add_transition(sweep)\n",
    "\n",
    "model.add_dual_bound(0)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fab59b79",
   "metadata": {},
   "source": [
    "## Solving"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "2148a80e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Transitions to apply:\n",
      "\n",
      "sweep 1\n",
      "sweep 0\n",
      "sweep 2\n",
      "sweep 3\n",
      "\n",
      "Cost: 8\n"
     ]
    }
   ],
   "source": [
    "solver = dp.CABS(model, f_operator=dp.FOperator.Max, quiet=True)\n",
    "solution = solver.search()\n",
    "\n",
    "print(\"Transitions to apply:\")\n",
    "print(\"\")\n",
    "\n",
    "for t in solution.transitions:\n",
    "    print(t.name)\n",
    "\n",
    "print(\"\")\n",
    "print(\"Cost: {}\".format(solution.cost))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": ".venv",
   "language": "python",
   "name": ".venv"
  },
  "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.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}