Partition.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": []
    },
    "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.11.2"
    }
  },
  "cells": [
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "6pfNNa4fqwMy"
      },
      "outputs": [],
      "source": [
        "!pip install mip"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RWFnDilGqp48"
      },
      "source": [
        "## Partitioning\n",
        "\n",
        "* Kernighan Lin Algorithm for bi-partitioning ($V'$) :\n",
        "  + $G=(V,E)$\n",
        "  + $A$, $B$ $\\subset V$\n",
        "  + $A \\cup B = V$\n",
        "  + $A\\cap B = ∅$\n",
        "  + $|A| = |B| = \\dfrac{|V|}{2}$\n",
        "  + Flowchart:\n",
        "\n",
        "    <img src=\"https://raw.githubusercontent.com/srini229/EE5333_tutorials/master/part/fig/KL_flowchart.jpg\" width=698 height=612 />\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "mRdE46JJsBI9"
      },
      "outputs": [],
      "source": [
        "# Vertex class to hold the partition index, neighbours, EA, EB and D values\n",
        "class Vertex:\n",
        "  def __init__(self, i, part):\n",
        "    self._id = i\n",
        "    self._nbrs = []\n",
        "    self._part = part\n",
        "    self._ea = 0\n",
        "    self._eb = 0\n",
        "    self._d  = 0\n",
        "  def reset(self, part):\n",
        "    (self._part, self._ea, self._eb, self._d) = (part, 0, 0, 0)\n",
        "  def __str__(self):\n",
        "    return '(' + str(self._id) + ',' + str(self._part) + ',' + str(self._ea) + ',' + str(self._eb) + ',' + str(self._d) + ',' + str([i._id for i in self._nbrs]) + ')'\n",
        "  def __repr__(self):\n",
        "    return str(self)\n",
        "\n",
        "# clear the partition, EA, EB and D values\n",
        "# do this at the beginning of every iteration\n",
        "def reset(V, A, B):\n",
        "  for j in range(2):\n",
        "    partition = A if (0 == j) else B\n",
        "    for i in partition:\n",
        "      V[i].reset(j)\n",
        "  for v in V:\n",
        "    assert(v._part == 0 or v._part == 1)\n",
        "    for n in v._nbrs:\n",
        "      if n._part == 0:\n",
        "        v._ea += 1\n",
        "      else:\n",
        "        v._eb += 1\n",
        "  for v in V:\n",
        "    v._d = (v._ea - v._eb) if (v._part == 1) else (v._eb - v._ea)\n",
        "\n",
        "# Choose the pair whose swap has the maximum gain in number of cuts\n",
        "def findMaxGain(V, Ap, Bp, E):\n",
        "  (amax, bmax, gmax) = (-1, -1, -2 * len(E) - 1)\n",
        "  for a in Ap:\n",
        "    for b in Bp:\n",
        "      g = V[a]._d + V[b]._d - (2 if (min(a,b), max(a,b)) in E else 0)\n",
        "      if gmax < g:\n",
        "        (amax, bmax, gmax) = (a, b, g)\n",
        "  assert(amax >= 0 and bmax >= 0)\n",
        "  return (amax, bmax, gmax)\n",
        "\n",
        "# update the E and D for only the affected neighbours of a and b\n",
        "def updateED(V, a, b):\n",
        "  V[a]._part = 1\n",
        "  V[b]._part = 0\n",
        "  for i in [a,b]:\n",
        "    for n in V[i]._nbrs:\n",
        "      if i == a:\n",
        "        n._ea -= 1\n",
        "        n._eb += 1\n",
        "      else:\n",
        "        n._ea += 1\n",
        "        n._eb -= 1\n",
        "      n._d = (n._ea - n._eb) if (n._part == 1) else (n._eb - n._ea)\n",
        "\n",
        "# N is the number of vertices; vertices are {0, 1,... N-1}\n",
        "# E is the list of edges\n",
        "# E : list of edges; edge = unordered pair of vertices\n",
        "# Return value : two sets A, B and the count of number of cuts\n",
        "def KLPart(N, E):\n",
        "  if N%2: N+= 1 # make N even if its odd by adding a single no-neighbour vertex\n",
        "  V = [Vertex(i, -1) for i in range(N)]\n",
        "  for e in E:\n",
        "    if e[0] > e[1]: e = (e[1], e[0])\n",
        "    else: e = (e[0], e[1])\n",
        "  E = set(E)\n",
        "  for e in E:\n",
        "    V[e[0]]._nbrs.append(V[e[1]])\n",
        "    V[e[1]]._nbrs.append(V[e[0]])\n",
        "  import random\n",
        "  Vc = V[:]\n",
        "  partLen = N//2\n",
        "  random.shuffle(Vc) # randomly initialize A and B\n",
        "\n",
        "  A = {Vc[i]._id for i in range(partLen)}\n",
        "  B = {Vc[i]._id for i in range(partLen, N)}\n",
        "\n",
        "  print(A)\n",
        "  print(B)\n",
        "  maxGain = 1\n",
        "  while maxGain >= 0:\n",
        "    Ap, Bp= A.copy(), B.copy()\n",
        "    reset(V, A, B)\n",
        "    G, S = [], []\n",
        "    for p in range(partLen):\n",
        "      (a, b, g) = findMaxGain(V, Ap, Bp, E)\n",
        "      updateED(V, a, b)\n",
        "      Ap.remove(a)\n",
        "      Bp.remove(b)\n",
        "      G.append(g)\n",
        "      S.append((a, b))\n",
        "    for i in range(1, len(G)):\n",
        "      G[i] += G[i-1]\n",
        "    maxGain = max(G)\n",
        "    maxIndex = G.index(maxGain)\n",
        "    if maxGain > 0:\n",
        "      for (a, b) in S[0:maxIndex + 1]:\n",
        "        A.remove(a)\n",
        "        B.remove(b)\n",
        "        A.add(b)\n",
        "        B.add(a)\n",
        "    else:\n",
        "      break\n",
        "\n",
        "  cut = 0\n",
        "  for a in A:\n",
        "    for b in B:\n",
        "      if (min(a, b), max(a,b)) in E:\n",
        "        cut += 1\n",
        "  return (A, B, cut)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "TDx6x3GsuxKa",
        "outputId": "c602820c-276e-4367-bafc-9c5070ccbd2a"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "{3, 4, 5, 6}\n",
            "{0, 1, 2, 7}\n",
            "({2, 3, 6, 7}, {0, 1, 4, 5}, 1)\n"
          ]
        }
      ],
      "source": [
        "print(KLPart(8, [(0,1), (0,4), (0,5), (1,4), (1,5), (4,5), (2,3), (2,6), (2,7), (3,6), (3,7), (6,7), (2,5)]))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "iXlhpb6Qy6Wr"
      },
      "source": [
        "## Bipartitioning using ILP\n",
        "+ $x_v$ is the indicator variable for $v$ being in $A$\n",
        "+ $x_{u,v}$ is the indicator variable for $(u,v)\\in E$ being cut\n",
        "+ <ul>\n",
        "$\\begin{align}\n",
        "        x_{u,v} = x_u \\oplus x_v\n",
        "\\end{align}$\n",
        "</ul>\n",
        "\n",
        "+ Objective: $\\min\\limits_{x_v, x_{u,v}} \\sum\\limits_{(u,v)\\in E}x_{u,v}$\n",
        "+ Subject to constraints:\n",
        "<ul>\n",
        "$\\begin{align}\n",
        "\\sum_{v\\in V} x_v&=\\frac{|V|}{2}\\\\\n",
        "x_u - x_v &\\leq x_{u,v}, &\\forall (u,v) \\in E\\\\\n",
        "x_v - x_u &\\leq x_{u,v}, &\\forall (u,v) \\in E\\\\\n",
        "x_u + x_v &\\geq x_{u,v}, &\\forall (u,v) \\in E\\\\\n",
        "x_u + x_v + x_{u,v} &\\leq 2, &\\forall (u,v) \\in E\\\\\n",
        "x_v &\\in \\{0, 1\\}, &\\forall v \\in V\\\\\n",
        "x_{u,v} &\\in \\{0, 1\\}, &\\forall (u,v) \\in E\n",
        "\\end{align}$\n",
        "</ul>\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "5J5avrLbvGiv"
      },
      "outputs": [],
      "source": [
        "def bipartition(N, E):\n",
        "  import mip\n",
        "  model = mip.Model(\"Bi-partition\")\n",
        "  x = [model.add_var(f\"x_{u}\", var_type = mip.BINARY) for u in range(N)]\n",
        "  x_uv = [model.add_var(f\"x_{u}_{v}\", var_type = mip.BINARY) for u,v in E]\n",
        "  model.verbose = 0\n",
        "  model.objective = mip.minimize(mip.xsum(x_uv))\n",
        "  model += (mip.xsum(x) == N//2)\n",
        "  for e, (u,v) in enumerate(E):\n",
        "  # xor constraints\n",
        "    model += (x[u] - x[v] <= x_uv[e])\n",
        "    model += (x[v] - x[u] <= x_uv[e])\n",
        "    model += (x[u] + x[v] >= x_uv[e])\n",
        "    model += (x[u] + x[v] + x_uv[e] <= 2)\n",
        "\n",
        "  model.write(\"bipartition.lp\")\n",
        "  model.optimize()\n",
        "  if model.status == mip.OptimizationStatus.OPTIMAL:\n",
        "    A = [i for i in range(N) if x[i].x >= 0.9]\n",
        "    B = [i for i in range(N) if x[i].x < 0.9]\n",
        "    return (A, B, model.objective.x)\n",
        "  return None\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "8FNdUsrs-vn9",
        "outputId": "303a7ec0-920a-489b-a90d-dc76d647a785"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "([2, 3, 6, 7], [0, 1, 4, 5], 1.0)\n"
          ]
        }
      ],
      "source": [
        "print(bipartition(8, [(0,1), (0,4), (0,5), (1,4), (1,5), (4,5), (2,3), (2,6), (2,7), (3,6), (3,7), (6,7), (2,5)]))"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "nd93RnYwxVjq"
      },
      "outputs": [],
      "source": [
        "def random_graph(N, fns):\n",
        "  import networkx as nx\n",
        "  import time\n",
        "  g = nx.erdos_renyi_graph(N, 0.4)\n",
        "  G = []\n",
        "  for fn in fns:\n",
        "    t = time.time()\n",
        "    (A,B,c) = fn(N, g.edges)\n",
        "    print(\"runtime : \", time.time() - t, 'cut size : ', c)\n",
        "    import graphviz\n",
        "    gv = graphviz.Graph()\n",
        "    A = list(A)\n",
        "    B = list(B)\n",
        "    for i in range(len(A)):\n",
        "      gv.node(str(A[i]), color='red', shape='circle')\n",
        "    for i in range(len(B)):\n",
        "      gv.node(str(B[i]), color='blue', shape='circle')\n",
        "    for e in g.edges:\n",
        "      gv.edge(str(e[0]), str(e[1]), splines='line')\n",
        "    #gv.engine = 'patchwork'\n",
        "    G.append(gv)\n",
        "  return G"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "XJrIsWs02hjm",
        "outputId": "cf686a9e-e035-456a-e6ff-619b86e6de4e"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "{0, 1, 3, 7, 9}\n",
            "{2, 4, 5, 6, 8}\n",
            "runtime :  0.001611948013305664 cut size :  5\n",
            "runtime :  0.43203282356262207 cut size :  5.0\n"
          ]
        },
        {
          "output_type": "display_data",
          "data": {
            "image/svg+xml": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Generated by graphviz version 2.43.0 (0)\n -->\n<!-- Title: %3 Pages: 1 -->\n<svg width=\"300pt\" height=\"404pt\"\n viewBox=\"0.00 0.00 299.74 404.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 400)\">\n<title>%3</title>\n<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-400 295.74,-400 295.74,4 -4,4\"/>\n<!-- 0 -->\n<g id=\"node1\" class=\"node\">\n<title>0</title>\n<ellipse fill=\"none\" stroke=\"red\" cx=\"117\" cy=\"-234\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"117\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">0</text>\n</g>\n<!-- 7 -->\n<g id=\"node4\" class=\"node\">\n<title>7</title>\n<ellipse fill=\"none\" stroke=\"red\" cx=\"224\" cy=\"-162\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"224\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">7</text>\n</g>\n<!-- 0&#45;&#45;7 -->\n<g id=\"edge2\" class=\"edge\">\n<title>0&#45;&#45;7</title>\n<path fill=\"none\" stroke=\"black\" d=\"M131.88,-223.27C152.32,-209.89 188.87,-185.98 209.25,-172.65\"/>\n</g>\n<!-- 8 -->\n<g id=\"node5\" class=\"node\">\n<title>8</title>\n<ellipse fill=\"none\" stroke=\"red\" cx=\"156\" cy=\"-90\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"156\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">8</text>\n</g>\n<!-- 0&#45;&#45;8 -->\n<g id=\"edge3\" class=\"edge\">\n<title>0&#45;&#45;8</title>\n<path fill=\"none\" stroke=\"black\" d=\"M121.55,-216.43C129.07,-189.07 143.98,-134.75 151.48,-107.46\"/>\n</g>\n<!-- 1 -->\n<g id=\"node6\" class=\"node\">\n<title>1</title>\n<ellipse fill=\"none\" stroke=\"blue\" cx=\"56\" cy=\"-162\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"56\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n</g>\n<!-- 0&#45;&#45;1 -->\n<g id=\"edge1\" class=\"edge\">\n<title>0&#45;&#45;1</title>\n<path fill=\"none\" stroke=\"black\" d=\"M105.53,-219.83C94.62,-207.32 78.31,-188.6 67.42,-176.11\"/>\n</g>\n<!-- 9 -->\n<g id=\"node10\" class=\"node\">\n<title>9</title>\n<ellipse fill=\"none\" stroke=\"blue\" cx=\"140\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"140\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\">9</text>\n</g>\n<!-- 0&#45;&#45;9 -->\n<g id=\"edge4\" class=\"edge\">\n<title>0&#45;&#45;9</title>\n<path fill=\"none\" stroke=\"black\" d=\"M117.54,-216C118.64,-186.55 121.67,-124.18 129,-72 130.73,-59.72 133.6,-46.01 135.97,-35.61\"/>\n</g>\n<!-- 4 -->\n<g id=\"node2\" class=\"node\">\n<title>4</title>\n<ellipse fill=\"none\" stroke=\"red\" cx=\"212\" cy=\"-306\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"212\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\">4</text>\n</g>\n<!-- 6 -->\n<g id=\"node3\" class=\"node\">\n<title>6</title>\n<ellipse fill=\"none\" stroke=\"red\" cx=\"262\" cy=\"-234\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"262\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">6</text>\n</g>\n<!-- 4&#45;&#45;6 -->\n<g id=\"edge11\" class=\"edge\">\n<title>4&#45;&#45;6</title>\n<path fill=\"none\" stroke=\"black\" d=\"M222.12,-290.83C230.79,-278.69 243.23,-261.28 251.9,-249.14\"/>\n</g>\n<!-- 4&#45;&#45;7 -->\n<g id=\"edge12\" class=\"edge\">\n<title>4&#45;&#45;7</title>\n<path fill=\"none\" stroke=\"black\" d=\"M213.45,-287.87C215.75,-260.58 220.24,-207.52 222.55,-180.19\"/>\n</g>\n<!-- 4&#45;&#45;8 -->\n<g id=\"edge13\" class=\"edge\">\n<title>4&#45;&#45;8</title>\n<path fill=\"none\" stroke=\"black\" d=\"M207.61,-288.21C197.14,-248.2 170.82,-147.64 160.37,-107.71\"/>\n</g>\n<!-- 6&#45;&#45;7 -->\n<g id=\"edge15\" class=\"edge\">\n<title>6&#45;&#45;7</title>\n<path fill=\"none\" stroke=\"black\" d=\"M253.75,-217.81C247.38,-206.07 238.6,-189.89 232.23,-178.16\"/>\n</g>\n<!-- 7&#45;&#45;8 -->\n<g id=\"edge16\" class=\"edge\">\n<title>7&#45;&#45;8</title>\n<path fill=\"none\" stroke=\"black\" d=\"M211.84,-148.49C199.47,-135.74 180.39,-116.11 168.05,-103.41\"/>\n</g>\n<!-- 7&#45;&#45;9 -->\n<g id=\"edge17\" class=\"edge\">\n<title>7&#45;&#45;9</title>\n<path fill=\"none\" stroke=\"black\" d=\"M218.02,-144.95C210.88,-126.65 198.01,-96.12 183,-72 173.86,-57.31 161.16,-42.14 151.93,-31.81\"/>\n</g>\n<!-- 8&#45;&#45;9 -->\n<g id=\"edge18\" class=\"edge\">\n<title>8&#45;&#45;9</title>\n<path fill=\"none\" stroke=\"black\" d=\"M152.13,-72.05C149.61,-61.05 146.35,-46.76 143.84,-35.79\"/>\n</g>\n<!-- 5 -->\n<g id=\"node9\" class=\"node\">\n<title>5</title>\n<ellipse fill=\"none\" stroke=\"blue\" cx=\"18\" cy=\"-90\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"18\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">5</text>\n</g>\n<!-- 1&#45;&#45;5 -->\n<g id=\"edge5\" class=\"edge\">\n<title>1&#45;&#45;5</title>\n<path fill=\"none\" stroke=\"black\" d=\"M47.75,-145.81C41.38,-134.07 32.6,-117.89 26.23,-106.16\"/>\n</g>\n<!-- 1&#45;&#45;9 -->\n<g id=\"edge6\" class=\"edge\">\n<title>1&#45;&#45;9</title>\n<path fill=\"none\" stroke=\"black\" d=\"M59.71,-144.29C64.36,-125.65 73.51,-95.09 88,-72 98.42,-55.4 114.8,-39.83 126.38,-29.92\"/>\n</g>\n<!-- 2 -->\n<g id=\"node7\" class=\"node\">\n<title>2</title>\n<ellipse fill=\"none\" stroke=\"blue\" cx=\"136\" cy=\"-378\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"136\" y=\"-374.3\" font-family=\"Times,serif\" font-size=\"14.00\">2</text>\n</g>\n<!-- 3 -->\n<g id=\"node8\" class=\"node\">\n<title>3</title>\n<ellipse fill=\"none\" stroke=\"blue\" cx=\"266\" cy=\"-306\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"266\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\">3</text>\n</g>\n<!-- 2&#45;&#45;3 -->\n<g id=\"edge7\" class=\"edge\">\n<title>2&#45;&#45;3</title>\n<path fill=\"none\" stroke=\"black\" d=\"M151.93,-369.34C172.37,-359.39 208.78,-341.24 239,-324 243.04,-321.69 247.34,-319.07 251.29,-316.59\"/>\n</g>\n<!-- 2&#45;&#45;5 -->\n<g id=\"edge8\" class=\"edge\">\n<title>2&#45;&#45;5</title>\n<path fill=\"none\" stroke=\"black\" d=\"M125.97,-363.02C104.19,-331.88 52.65,-253.75 29,-180 21.25,-155.83 18.91,-126.36 18.23,-108.14\"/>\n</g>\n<!-- 3&#45;&#45;6 -->\n<g id=\"edge9\" class=\"edge\">\n<title>3&#45;&#45;6</title>\n<path fill=\"none\" stroke=\"black\" d=\"M265.01,-287.7C264.39,-276.85 263.6,-262.92 262.98,-252.1\"/>\n</g>\n<!-- 3&#45;&#45;9 -->\n<g id=\"edge10\" class=\"edge\">\n<title>3&#45;&#45;9</title>\n<path fill=\"none\" stroke=\"black\" d=\"M274.6,-289.79C279.91,-279.48 286.23,-265.36 289,-252 292.25,-236.33 292.85,-231.53 289,-216 271.24,-144.3 255.06,-127.22 206,-72 190.58,-54.64 169.05,-38.52 154.83,-28.72\"/>\n</g>\n<!-- 5&#45;&#45;9 -->\n<g id=\"edge14\" class=\"edge\">\n<title>5&#45;&#45;9</title>\n<path fill=\"none\" stroke=\"black\" d=\"M33.45,-80.13C56.92,-66.67 101.28,-41.22 124.67,-27.79\"/>\n</g>\n</g>\n</svg>\n",
            "text/plain": [
              "<graphviz.graphs.Graph at 0x7dc60c2f8e20>"
            ]
          },
          "metadata": {}
        },
        {
          "output_type": "display_data",
          "data": {
            "image/svg+xml": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Generated by graphviz version 2.43.0 (0)\n -->\n<!-- Title: %3 Pages: 1 -->\n<svg width=\"280pt\" height=\"404pt\"\n viewBox=\"0.00 0.00 280.12 404.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 400)\">\n<title>%3</title>\n<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-400 276.12,-400 276.12,4 -4,4\"/>\n<!-- 1 -->\n<g id=\"node1\" class=\"node\">\n<title>1</title>\n<ellipse fill=\"none\" stroke=\"red\" cx=\"110\" cy=\"-162\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"110\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n</g>\n<!-- 5 -->\n<g id=\"node4\" class=\"node\">\n<title>5</title>\n<ellipse fill=\"none\" stroke=\"red\" cx=\"18\" cy=\"-90\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"18\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">5</text>\n</g>\n<!-- 1&#45;&#45;5 -->\n<g id=\"edge5\" class=\"edge\">\n<title>1&#45;&#45;5</title>\n<path fill=\"none\" stroke=\"black\" d=\"M96.03,-150.37C78.74,-137.21 49.46,-114.93 32.1,-101.73\"/>\n</g>\n<!-- 9 -->\n<g id=\"node5\" class=\"node\">\n<title>9</title>\n<ellipse fill=\"none\" stroke=\"red\" cx=\"135\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"135\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\">9</text>\n</g>\n<!-- 1&#45;&#45;9 -->\n<g id=\"edge6\" class=\"edge\">\n<title>1&#45;&#45;9</title>\n<path fill=\"none\" stroke=\"black\" d=\"M112.97,-144.15C117.78,-116.82 127.23,-63.14 132.04,-35.82\"/>\n</g>\n<!-- 2 -->\n<g id=\"node2\" class=\"node\">\n<title>2</title>\n<ellipse fill=\"none\" stroke=\"red\" cx=\"41\" cy=\"-378\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"41\" y=\"-374.3\" font-family=\"Times,serif\" font-size=\"14.00\">2</text>\n</g>\n<!-- 3 -->\n<g id=\"node3\" class=\"node\">\n<title>3</title>\n<ellipse fill=\"none\" stroke=\"red\" cx=\"64\" cy=\"-306\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"64\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\">3</text>\n</g>\n<!-- 2&#45;&#45;3 -->\n<g id=\"edge7\" class=\"edge\">\n<title>2&#45;&#45;3</title>\n<path fill=\"none\" stroke=\"black\" d=\"M46.33,-360.76C50,-349.62 54.84,-334.87 58.53,-323.63\"/>\n</g>\n<!-- 2&#45;&#45;5 -->\n<g id=\"edge8\" class=\"edge\">\n<title>2&#45;&#45;5</title>\n<path fill=\"none\" stroke=\"black\" d=\"M39.63,-359.97C35.55,-309.22 23.5,-159.41 19.39,-108.31\"/>\n</g>\n<!-- 3&#45;&#45;9 -->\n<g id=\"edge10\" class=\"edge\">\n<title>3&#45;&#45;9</title>\n<path fill=\"none\" stroke=\"black\" d=\"M64.48,-287.79C65.64,-258.02 69.61,-195.19 83,-144 93.77,-102.84 115.3,-57.4 127,-34.3\"/>\n</g>\n<!-- 6 -->\n<g id=\"node8\" class=\"node\">\n<title>6</title>\n<ellipse fill=\"none\" stroke=\"blue\" cx=\"206\" cy=\"-234\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"206\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">6</text>\n</g>\n<!-- 3&#45;&#45;6 -->\n<g id=\"edge9\" class=\"edge\">\n<title>3&#45;&#45;6</title>\n<path fill=\"none\" stroke=\"black\" d=\"M80.32,-298.27C102.91,-288.78 144.79,-270.55 179,-252 183.09,-249.78 187.4,-247.19 191.35,-244.71\"/>\n</g>\n<!-- 5&#45;&#45;9 -->\n<g id=\"edge14\" class=\"edge\">\n<title>5&#45;&#45;9</title>\n<path fill=\"none\" stroke=\"black\" d=\"M33.3,-79.85C55.72,-66.43 97.28,-41.57 119.7,-28.15\"/>\n</g>\n<!-- 0 -->\n<g id=\"node6\" class=\"node\">\n<title>0</title>\n<ellipse fill=\"none\" stroke=\"blue\" cx=\"152\" cy=\"-234\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"152\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">0</text>\n</g>\n<!-- 0&#45;&#45;1 -->\n<g id=\"edge1\" class=\"edge\">\n<title>0&#45;&#45;1</title>\n<path fill=\"none\" stroke=\"black\" d=\"M143.09,-218.15C135.97,-206.28 126.02,-189.7 118.89,-177.82\"/>\n</g>\n<!-- 0&#45;&#45;9 -->\n<g id=\"edge4\" class=\"edge\">\n<title>0&#45;&#45;9</title>\n<path fill=\"none\" stroke=\"black\" d=\"M150.64,-215.85C147.45,-175.78 139.56,-76.38 136.37,-36.23\"/>\n</g>\n<!-- 7 -->\n<g id=\"node9\" class=\"node\">\n<title>7</title>\n<ellipse fill=\"none\" stroke=\"blue\" cx=\"240\" cy=\"-162\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"240\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">7</text>\n</g>\n<!-- 0&#45;&#45;7 -->\n<g id=\"edge2\" class=\"edge\">\n<title>0&#45;&#45;7</title>\n<path fill=\"none\" stroke=\"black\" d=\"M165.75,-222.06C182.28,-208.91 209.86,-186.98 226.35,-173.86\"/>\n</g>\n<!-- 8 -->\n<g id=\"node10\" class=\"node\">\n<title>8</title>\n<ellipse fill=\"none\" stroke=\"blue\" cx=\"240\" cy=\"-90\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"240\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">8</text>\n</g>\n<!-- 0&#45;&#45;8 -->\n<g id=\"edge3\" class=\"edge\">\n<title>0&#45;&#45;8</title>\n<path fill=\"none\" stroke=\"black\" d=\"M161.09,-218.34C177.95,-191.13 213.91,-133.11 230.83,-105.79\"/>\n</g>\n<!-- 4 -->\n<g id=\"node7\" class=\"node\">\n<title>4</title>\n<ellipse fill=\"none\" stroke=\"blue\" cx=\"252\" cy=\"-306\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"252\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\">4</text>\n</g>\n<!-- 4&#45;&#45;6 -->\n<g id=\"edge11\" class=\"edge\">\n<title>4&#45;&#45;6</title>\n<path fill=\"none\" stroke=\"black\" d=\"M242.47,-290.5C234.57,-278.48 223.41,-261.49 215.52,-249.49\"/>\n</g>\n<!-- 4&#45;&#45;7 -->\n<g id=\"edge12\" class=\"edge\">\n<title>4&#45;&#45;7</title>\n<path fill=\"none\" stroke=\"black\" d=\"M250.55,-287.87C248.25,-260.58 243.76,-207.52 241.45,-180.19\"/>\n</g>\n<!-- 4&#45;&#45;8 -->\n<g id=\"edge13\" class=\"edge\">\n<title>4&#45;&#45;8</title>\n<path fill=\"none\" stroke=\"black\" d=\"M257.09,-288.29C265.31,-258.76 279.38,-195.59 267,-144 263.67,-130.14 256.09,-115.82 249.8,-105.57\"/>\n</g>\n<!-- 6&#45;&#45;7 -->\n<g id=\"edge15\" class=\"edge\">\n<title>6&#45;&#45;7</title>\n<path fill=\"none\" stroke=\"black\" d=\"M213.55,-217.46C219.18,-205.86 226.85,-190.08 232.48,-178.49\"/>\n</g>\n<!-- 7&#45;&#45;9 -->\n<g id=\"edge17\" class=\"edge\">\n<title>7&#45;&#45;9</title>\n<path fill=\"none\" stroke=\"black\" d=\"M229.74,-147.13C209.72,-120.05 165.64,-60.43 145.46,-33.14\"/>\n</g>\n<!-- 7&#45;&#45;8 -->\n<g id=\"edge16\" class=\"edge\">\n<title>7&#45;&#45;8</title>\n<path fill=\"none\" stroke=\"black\" d=\"M240,-143.7C240,-132.85 240,-118.92 240,-108.1\"/>\n</g>\n<!-- 8&#45;&#45;9 -->\n<g id=\"edge18\" class=\"edge\">\n<title>8&#45;&#45;9</title>\n<path fill=\"none\" stroke=\"black\" d=\"M225.4,-79.27C205.45,-65.97 169.87,-42.25 149.81,-28.88\"/>\n</g>\n</g>\n</svg>\n",
            "text/plain": [
              "<graphviz.graphs.Graph at 0x7dc60c2f8f40>"
            ]
          },
          "metadata": {}
        }
      ],
      "source": [
        "G = random_graph(10, [KLPart, bipartition])\n",
        "from IPython.display import display\n",
        "display(G[0], G[1])"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "bYe2eC01VgeC",
        "outputId": "f9911bad-0f58-41c8-b724-ffaf511924c1"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "\\Problem name: Bi-partition\n",
            "\n",
            "Minimize\n",
            "OBJROW: x_0_1 + x_0_4 + x_0_5 + x_1_4 + x_1_5 + x_1_6 + x_2_3 + x_2_6 + x_2_7 + x_3_6\n",
            " + x_3_7 + x_4_5 + x_6_7\n",
            "Subject To\n",
            "constr(0):  x_0 + x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 = 4\n",
            "constr(1):  x_0 - x_1 - x_0_1 <= -0\n",
            "constr(2):  - x_0 + x_1 - x_0_1 <= -0\n",
            "constr(3):  x_0 + x_1 - x_0_1 >= -0\n",
            "constr(4):  x_0 + x_1 + x_0_1 <= 2\n",
            "constr(5):  x_0 - x_4 - x_0_4 <= -0\n",
            "constr(6):  - x_0 + x_4 - x_0_4 <= -0\n",
            "constr(7):  x_0 + x_4 - x_0_4 >= -0\n",
            "constr(8):  x_0 + x_4 + x_0_4 <= 2\n",
            "constr(9):  x_0 - x_5 - x_0_5 <= -0\n",
            "constr(10):  - x_0 + x_5 - x_0_5 <= -0\n",
            "constr(11):  x_0 + x_5 - x_0_5 >= -0\n",
            "constr(12):  x_0 + x_5 + x_0_5 <= 2\n",
            "constr(13):  x_1 - x_4 - x_1_4 <= -0\n",
            "constr(14):  - x_1 + x_4 - x_1_4 <= -0\n",
            "constr(15):  x_1 + x_4 - x_1_4 >= -0\n",
            "constr(16):  x_1 + x_4 + x_1_4 <= 2\n",
            "constr(17):  x_1 - x_5 - x_1_5 <= -0\n",
            "constr(18):  - x_1 + x_5 - x_1_5 <= -0\n",
            "constr(19):  x_1 + x_5 - x_1_5 >= -0\n",
            "constr(20):  x_1 + x_5 + x_1_5 <= 2\n",
            "constr(21):  x_1 - x_6 - x_1_6 <= -0\n",
            "constr(22):  - x_1 + x_6 - x_1_6 <= -0\n",
            "constr(23):  x_1 + x_6 - x_1_6 >= -0\n",
            "constr(24):  x_1 + x_6 + x_1_6 <= 2\n",
            "constr(25):  x_2 - x_3 - x_2_3 <= -0\n",
            "constr(26):  - x_2 + x_3 - x_2_3 <= -0\n",
            "constr(27):  x_2 + x_3 - x_2_3 >= -0\n",
            "constr(28):  x_2 + x_3 + x_2_3 <= 2\n",
            "constr(29):  x_2 - x_6 - x_2_6 <= -0\n",
            "constr(30):  - x_2 + x_6 - x_2_6 <= -0\n",
            "constr(31):  x_2 + x_6 - x_2_6 >= -0\n",
            "constr(32):  x_2 + x_6 + x_2_6 <= 2\n",
            "constr(33):  x_2 - x_7 - x_2_7 <= -0\n",
            "constr(34):  - x_2 + x_7 - x_2_7 <= -0\n",
            "constr(35):  x_2 + x_7 - x_2_7 >= -0\n",
            "constr(36):  x_2 + x_7 + x_2_7 <= 2\n",
            "constr(37):  x_3 - x_6 - x_3_6 <= -0\n",
            "constr(38):  - x_3 + x_6 - x_3_6 <= -0\n",
            "constr(39):  x_3 + x_6 - x_3_6 >= -0\n",
            "constr(40):  x_3 + x_6 + x_3_6 <= 2\n",
            "constr(41):  x_3 - x_7 - x_3_7 <= -0\n",
            "constr(42):  - x_3 + x_7 - x_3_7 <= -0\n",
            "constr(43):  x_3 + x_7 - x_3_7 >= -0\n",
            "constr(44):  x_3 + x_7 + x_3_7 <= 2\n",
            "constr(45):  x_4 - x_5 - x_4_5 <= -0\n",
            "constr(46):  - x_4 + x_5 - x_4_5 <= -0\n",
            "constr(47):  x_4 + x_5 - x_4_5 >= -0\n",
            "constr(48):  x_4 + x_5 + x_4_5 <= 2\n",
            "constr(49):  x_6 - x_7 - x_6_7 <= -0\n",
            "constr(50):  - x_6 + x_7 - x_6_7 <= -0\n",
            "constr(51):  x_6 + x_7 - x_6_7 >= -0\n",
            "constr(52):  x_6 + x_7 + x_6_7 <= 2\n",
            "Bounds\n",
            " 0 <= x_0 <= 1\n",
            " 0 <= x_1 <= 1\n",
            " 0 <= x_2 <= 1\n",
            " 0 <= x_3 <= 1\n",
            " 0 <= x_4 <= 1\n",
            " 0 <= x_5 <= 1\n",
            " 0 <= x_6 <= 1\n",
            " 0 <= x_7 <= 1\n",
            " 0 <= x_0_1 <= 1\n",
            " 0 <= x_0_4 <= 1\n",
            " 0 <= x_0_5 <= 1\n",
            " 0 <= x_1_4 <= 1\n",
            " 0 <= x_1_5 <= 1\n",
            " 0 <= x_1_6 <= 1\n",
            " 0 <= x_2_3 <= 1\n",
            " 0 <= x_2_6 <= 1\n",
            " 0 <= x_2_7 <= 1\n",
            " 0 <= x_3_6 <= 1\n",
            " 0 <= x_3_7 <= 1\n",
            " 0 <= x_4_5 <= 1\n",
            " 0 <= x_6_7 <= 1\n",
            "Integers\n",
            "x_0 x_1 x_2 x_3 x_4 x_5 x_6 x_7 x_0_1 x_0_4 \n",
            "x_0_5 x_1_4 x_1_5 x_1_6 x_2_3 x_2_6 x_2_7 x_3_6 x_3_7 x_4_5 \n",
            "x_6_7 \n",
            "End\n"
          ]
        }
      ],
      "source": [
        "!cat bipartition.lp"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "G = random_graph(40, [KLPart, bipartition])\n",
        "from IPython.display import display\n",
        "display(G[0], G[1], G[2])"
      ],
      "metadata": {
        "id": "hawqhl8xXRD_"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "## LEF DEF Parsing\n",
        "\n",
        "- Install the LEFDEFParser from the the wheel file : [LEFDEFParser-0.1-cp310-cp310-linux_x86_64.whl](https://github.com/srini229/EE5333_tutorials/blob/master/parser/LEFDEFParser-0.1-cp310-cp310-linux_x86_64.whl)\n",
        "- Download example LEF and DEF files: [Nangate.lef](https://github.com/srini229/EE5333_tutorials/blob/master/parser/Nangate.lef) and [example.def](https://github.com/srini229/EE5333_tutorials/blob/master/parser/example.def)\n",
        "\n",
        "    <img src=\"https://raw.githubusercontent.com/srini229/EE5333_tutorials/master/part/fig/example_cir.png\" width=340 height=195 />\n",
        "\n"
      ],
      "metadata": {
        "id": "9b8l7WIsKTOC"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "!pip install --break-system-packages https://raw.githubusercontent.com/srini229/EE5333_tutorials/master/parser/LEFDEFParser-0.1-cp311-cp311-linux_x86_64.whl\n",
        "!rm *.{lef,def}\n",
        "!wget https://raw.githubusercontent.com/srini229/EE5333_tutorials/master/parser/{Nangate.lef,example.def}\n",
        "!wget https://raw.githubusercontent.com/srini229/EE5333_tutorials/master/parser/sample.{lef,def}"
      ],
      "metadata": {
        "id": "yZMKB51YKRme",
        "outputId": "f9663587-2524-46ce-dbb2-c141585d5c69",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Collecting LEFDEFParser==0.1\n",
            "  Downloading https://raw.githubusercontent.com/srini229/EE5333_tutorials/master/parser/LEFDEFParser-0.1-cp310-cp310-linux_x86_64.whl (562 kB)\n",
            "\u001b[2K     \u001b[90m━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\u001b[0m \u001b[32m562.0/562.0 kB\u001b[0m \u001b[31m6.3 MB/s\u001b[0m eta \u001b[36m0:00:00\u001b[0m\n",
            "\u001b[?25hInstalling collected packages: LEFDEFParser\n",
            "Successfully installed LEFDEFParser-0.1\n",
            "--2024-01-25 10:43:01--  https://raw.githubusercontent.com/srini229/EE5333_tutorials/master/parser/example.def\n",
            "Resolving raw.githubusercontent.com (raw.githubusercontent.com)... 185.199.108.133, 185.199.109.133, 185.199.110.133, ...\n",
            "Connecting to raw.githubusercontent.com (raw.githubusercontent.com)|185.199.108.133|:443... connected.\n",
            "HTTP request sent, awaiting response... 200 OK\n",
            "Length: 899 [text/plain]\n",
            "Saving to: ‘example.def.2’\n",
            "\n",
            "example.def.2       100%[===================>]     899  --.-KB/s    in 0s      \n",
            "\n",
            "2024-01-25 10:43:01 (27.8 MB/s) - ‘example.def.2’ saved [899/899]\n",
            "\n",
            "VERSION 5.8 ;\n",
            "DIVIDERCHAR \"/\" ;\n",
            "BUSBITCHARS \"[]\" ;\n",
            "DESIGN example ;\n",
            "UNITS DISTANCE MICRONS 2000 ;\n",
            "\n",
            "DIEAREA ( 83600 71820 ) ( 104400 91200 ) ;\n",
            "\n",
            "COMPONENTS 6 ;\n",
            "- a NAND2_X1 ;\n",
            "- b NAND2_X1 ;\n",
            "- c NAND2_X1 ;\n",
            "- d NAND2_X1 ;\n",
            "- e NAND2_X1 ;\n",
            "- f INV_X1 ;\n",
            "END COMPONENTS\n",
            "\n",
            "PINS 0 ;\n",
            "- n1 + NET n1 + DIRECTION INPUT ;\n",
            "- n2 + NET n2 + DIRECTION INPUT ;\n",
            "- n3 + NET n3 + DIRECTION INPUT ;\n",
            "- n4 + NET n4 + DIRECTION INPUT ;\n",
            "- n5 + NET n5 + DIRECTION INPUT ;\n",
            "- n10 + NET n10 + DIRECTION OUTPUT ;\n",
            "- n11 + NET n11 + DIRECTION OUTPUT ;\n",
            "END PINS\n",
            "\n",
            "NETS 11 ;\n",
            "- n1\n",
            "  ( PIN n1 ) ( a A1 )\n",
            " ;\n",
            "- n2\n",
            "  ( PIN n2 ) ( a A2 ) ( b A1 )\n",
            " ;\n",
            "- n3\n",
            "  ( PIN n3 ) ( b A2 )\n",
            " ;\n",
            "- n4\n",
            "  ( PIN n4 ) ( c A2 )\n",
            " ;\n",
            "- n5\n",
            "  ( PIN n5 ) ( d A2 )\n",
            " ;\n",
            "- n6\n",
            "  ( a ZN ) ( e A1 )\n",
            " ;\n",
            "- n7\n",
            "  ( b ZN ) ( c A1 ) ( d A1 )\n",
            " ;\n",
            "- n8\n",
            "  ( c ZN ) ( e A2 )\n",
            " ;\n",
            "- n9\n",
            "  ( d ZN ) ( f A )\n",
            " ;\n",
            "- n10\n",
            "  ( e ZN ) ( PIN n10 )\n",
            " ;\n",
            "- n11\n",
            "  ( f ZN ) ( PIN n11 )\n",
            " ;\n",
            "END NETS\n",
            "\n",
            "END DESIGN\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "V,E = loadNetlist('Nangate.lef', 'example.def')\n",
        "Atotal = sum(V[u]._area for u in V)\n",
        "maxCellArea = max(V[u]._area for u in V)\n",
        "print(Atotal, round(maxCellArea,2))"
      ],
      "metadata": {
        "id": "sdy6ddx9cSRO"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "V,E = loadNetlist('sample.lef', 'sample.def')\n",
        "Atotal = sum(V[u]._area for u in V)\n",
        "maxCellArea = max(V[u]._area for u in V)\n",
        "print(Atotal, round(maxCellArea,2))"
      ],
      "metadata": {
        "id": "4a6bTl_XcaPD"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}