docs/tutorials/notebooks/KnapsackProblem.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "<a href=\"https://colab.research.google.com/github/conjure-cp/conjure/blob/main/docs/tutorials/notebooks/KnapsackProblem.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Q-O7ivbPHtqI"
      },
      "source": [
        "# The Knapsack problem"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5I6cwwqhH19R"
      },
      "source": [
        "Original [The Knapsack Problem](https://conjure.readthedocs.io/en/latest/tutorials/knapsack.html) by Saad Attieh and Christopher Stone. Adapted by Alex Gallagher."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZkJHUbaIFon"
      },
      "source": [
        "The Knapsack problem is a classical combinatorial optimisation problem, often used in areas of resource allocation. A basic variant of the Knapsack problem is defined as follows:\n",
        "\n",
        "**Given:**\n",
        "1. A set of items, each with a weight and a value,\n",
        "2. A maximum weight which we call capacity,\n",
        "\n",
        "**find a set of the items such that**\n",
        "1. The sum of the weights of the items in our set is less than or equal to the capacity, and\n",
        "2. The sum of the values of the items is maximised.\n",
        "\n",
        "Informally, think about putting items in a sack such that we maximise the total value of the sack whilst not going over the sack’s weight limit.\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 138
        },
        "id": "A35VMVlIMe_g",
        "outputId": "528e870d-f70d-49cd-b7d9-2f19c82aa693"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Installing Conjure version v2.5.1 and Conjure Notebook version v0.0.9...\n",
            "Downloading...\n",
            "Conjure: The Automated Constraint Modelling Tool\n",
            "Release version 2.5.0\n",
            "Repository version c94cde5 (2023-11-06 17:43:12 +0000)\n"
          ]
        },
        {
          "data": {
            "application/javascript": "\"use strict\";\n\nCodeMirror.defineMode(\"text/conjure\", function (config) {\n\n    var isOperatorChar = /[+\\-*=<>%^\\/]/;\n\n    var keywords = {\n        \"forall\": true,\n        \"allDifferent\": true,\n        \"allDiff\": true,\n        \"alldifferent_except\": true,\n        \"dim\": true,\n        \"toSet\": true,\n        \"toMSet\": true,\n        \"toRelation\": true,\n        \"maximising\": true,\n        \"minimising\": true,\n        \"forAll\": true,\n        \"exists\": true,\n        \"toInt\": true,\n        \"sum\": true,\n        \"be\": true,\n        \"bijective\": true,\n        \"bool\": true,\n        \"by\": true,\n        \"complete\": true,\n        \"defined\": true,\n        \"domain\": true,\n        \"in\": true,\n        \"or\": true,\n        \"and\": true,\n        \"false\": true,\n        \"find\": true,\n        \"from\": true,\n        \"function\": true,\n        \"given\": true,\n        \"image\": true,\n        \"indexed\": true,\n        \"injective\": true,\n        \"int\": true,\n        \"intersect\": true,\n        \"freq\": true,\n        \"lambda\": true,\n        \"language\": true,\n        \"letting\": true,\n        \"matrix\": true,\n        \"maxNumParts\": true,\n        \"maxOccur\": true,\n        \"maxPartSize\": true,\n        \"maxSize\": true,\n        \"minNumParts\": true,\n        \"minOccur\": true,\n        \"minPartSize\": true,\n        \"minSize\": true,\n        \"mset\": true,\n        \"numParts\": true,\n        \"of\": true,\n        \"partial\": true,\n        \"partition\": true,\n        \"partSize\": true,\n        \"preImage\": true,\n        \"quantifier\": true,\n        \"range\": true,\n        \"regular\": true,\n        \"relation\": true,\n        \"representation\": true,\n        \"set\": true,\n        \"size\": true,\n        \"subset\": true,\n        \"subsetEq\": true,\n        \"such\": true,\n        \"supset\": true,\n        \"supsetEq\": true,\n        \"surjective\": true,\n        \"that\": true,\n        \"together\": true,\n        \"enum\": true,\n        \"total\": true,\n        \"true\": true,\n        \"new\": true,\n        \"type\": true,\n        \"tuple\": true,\n        \"union\": true,\n        \"where\": true,\n        \"branching\": true,\n        \"on\": true\n    };  \n    var punc = \":;,.(){}[]\";\n\n    function tokenBase(stream, state) {\n        var ch = stream.next();\n        if (ch == '\"') {\n            state.tokenize.push(tokenString);\n            return tokenString(stream, state);\n        }\n        if (/[\\d\\.]/.test(ch)) {\n            if (ch == \".\") {\n                stream.match(/^[0-9]+([eE][\\-+]?[0-9]+)?/);\n            } else if (ch == \"0\") {\n                stream.match(/^[xX][0-9a-fA-F]+/) || stream.match(/^0[0-7]+/);\n            } else {\n                stream.match(/^[0-9]*\\.?[0-9]*([eE][\\-+]?[0-9]+)?/);\n            }\n            return \"number\";\n        }\n        if (ch == \"/\") {\n            if (stream.eat(\"*\")) {\n                state.tokenize.push(tokenComment);\n                return tokenComment(stream, state);\n            }\n        }\n        if (ch == \"$\") {\n            stream.skipToEnd();\n            return \"comment\";\n        }\n        if (isOperatorChar.test(ch)) {\n            stream.eatWhile(isOperatorChar);\n            return \"operator\";\n        }\n        if (punc.indexOf(ch) > -1) {\n            return \"punctuation\";\n        }\n        stream.eatWhile(/[\\w\\$_\\xa1-\\uffff]/);\n        var cur = stream.current();\n        \n        if (keywords.propertyIsEnumerable(cur)) {\n            return \"keyword\";\n        }\n        return \"variable\";\n    }\n\n    function tokenComment(stream, state) {\n        var maybeEnd = false, ch;\n        while (ch = stream.next()) {\n            if (ch == \"/\" && maybeEnd) {\n                state.tokenize.pop();\n                break;\n            }\n            maybeEnd = (ch == \"*\");\n        }\n        return \"comment\";\n    }\n\n    function tokenUntilClosingParen() {\n        var depth = 0;\n        return function (stream, state, prev) {\n            var inner = tokenBase(stream, state, prev);\n            console.log(\"untilClosing\", inner, stream.current());\n            if (inner == \"punctuation\") {\n                if (stream.current() == \"(\") {\n                    ++depth;\n                } else if (stream.current() == \")\") {\n                    if (depth == 0) {\n                        stream.backUp(1)\n                        state.tokenize.pop()\n                        return state.tokenize[state.tokenize.length - 1](stream, state)\n                    } else {\n                        --depth;\n                    }\n                }\n            }\n            return inner;\n        }\n    }\n\n    function tokenString(stream, state) {\n        var escaped = false, next, end = false;\n        while ((next = stream.next()) != null) {\n            if (next == '(' && escaped) {\n                state.tokenize.push(tokenUntilClosingParen());\n                return \"string\";\n            }\n            if (next == '\"' && !escaped) { end = true; break; }\n            escaped = !escaped && next == \"\\\\\";\n        }\n        if (end || !escaped)\n            state.tokenize.pop();\n        return \"string\";\n    }\n\n    return {\n        startState: function (basecolumn) {\n            return {\n                tokenize: []\n            };\n        },\n\n        token: function (stream, state) {\n            if (stream.eatSpace()) return null;\n            var style = (state.tokenize[state.tokenize.length - 1] || tokenBase)(stream, state);\n            console.log(\"token\", style);\n            return style;\n        },\n\n        blockCommentStart: \"/*\",\n        blockCommentEnd: \"*/\",\n        lineComment: \"$\"\n    };\n});\n\n\nCodeMirror.defineMIME(\"text/conjure\", \"text/conjure\");\n\nrequire(['notebook/js/codecell'], function (codecell) {\n    codecell.CodeCell.options_default.highlight_modes['magic_text/conjure'] = { 'reg': [/%?%conjure/] };\n    Jupyter.notebook.events.one('kernel_ready.Kernel', function () {\n        Jupyter.notebook.get_cells().map(function (cell) {\n            if (cell.cell_type == 'code') { cell.auto_highlight(); }\n        });\n    });\n});\n\n",
            "text/plain": [
              "<IPython.core.display.Javascript object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        },
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Conjure extension is loaded.\n",
            "For usage help run: %conjure_help\n"
          ]
        }
      ],
      "source": [
        "!source <(curl -s https://raw.githubusercontent.com/conjure-cp/conjure-notebook/v0.0.9/scripts/install-colab.sh)\n",
        "%load_ext conjure\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "fU4y3zCXMNgX"
      },
      "source": [
        "##Model Explained"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vsYVModWMMUU"
      },
      "source": [
        "We begin by showing the entire problem as defined in Essence:\n",
        "\n",
        "`given items new type enum`\n",
        "\n",
        "\n",
        "`given weight : function (total) items --> int`\n",
        "\n",
        "\n",
        "`given gain : function (total) items --> int`\n",
        "\n",
        "\n",
        "`given capacity : int`\n",
        "\n",
        "\n",
        "`find picked : set of items`\n",
        "\n",
        "\n",
        "`maximising sum i in picked . gain(i)`\n",
        "\n",
        "\n",
        "`such that (sum i in picked . weight(i)) <= capacity`"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "S0QHWB3fItZK"
      },
      "source": [
        "Going through the problem line by line:\n",
        "\n",
        "We begin by defining the parameters to the problem. Parameters can be defined outside of the problem, allowing different instances of the same problem to be solved without having to change the specification.\n",
        "\n",
        "Each parameter is denoted with the given keyword."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RR32w1Dd5-mU"
      },
      "source": [
        "`given items new type enum`"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "MCnXSWH_IxnM"
      },
      "source": [
        "This line says that a set of items will be provided as an enum type. Enums are good for labeling items where it makes no sense to attribute a value to each item. So instead of using integers to represent each item, we may just assign names to each item and group the names under an enum type. Below is an example enum declaration, as it would be written in the Conjure Magic cell:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 2,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "id": "SrrZ0nFcI402",
        "outputId": "29375f65-70a6-4191-8eb6-683a5aba8763"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "```json\n",
              "{}\n",
              "```"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "%%conjure\n",
        "letting items be new type enum {a,b,c,d,e}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "CABjHWtbJGk0"
      },
      "source": [
        "`a`, `b`, etc. are just names we have given, they could be anything `bread`, `whiskey`, …"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "b7N-ZDa46JGr"
      },
      "source": [
        "`given weight : function (total) items --> int`"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "-uOA3Q_DJSvM"
      },
      "source": [
        "Another parameter, a function that maps from each item to an integer, we will treat these integers as weights. Since we are describing integers that will be given as parameters, no domain (lower/upper bound) is required. Here is an example function parameter:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 3,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "id": "IKZXLIHlJVF9",
        "outputId": "042ba91c-45de-4333-a351-93d43a27e457"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "```json\n",
              "{}\n",
              "```"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "%%conjure+\n",
        "letting weight be function\n",
        "    ( a --> 15\n",
        "    , b --> 25\n",
        "    , c --> 45\n",
        "    , d --> 50\n",
        "    , e --> 60\n",
        "    )"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "XhUtJP1o6P0q"
      },
      "source": [
        "`given gain : function (total) items --> int`"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "6zkqdEX6tOJU"
      },
      "source": [
        "Just the same as the weight parameter, this parameter is used to denote a mapping from each item to a value. An example value for this parameter as it would be defined in the parameter file is:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 4,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "id": "xgNtA5-4tQxX",
        "outputId": "5fd4d0f6-98c9-432e-d0cb-50588e19c981"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "```json\n",
              "{}\n",
              "```"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "%%conjure+\n",
        "letting gain be function\n",
        "    ( a --> 10\n",
        "    , b --> 20\n",
        "    , c --> 40\n",
        "    , d --> 40\n",
        "    , e --> 50\n",
        "    )"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "X8qMCv8DKio9"
      },
      "source": [
        "The final given:"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "btL2k4bc6Xis"
      },
      "source": [
        "`given capacity : int`"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1C84QOfkKn7Y"
      },
      "source": [
        "The final parameter – a weight limit. Example value:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 5,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "id": "F1rd0BM4Kr6s",
        "outputId": "5fead5d1-3c58-4384-accb-5aa25831cb50"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "```json\n",
              "{}\n",
              "```"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "%%conjure+\n",
        "letting capacity be 80"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tjnxxkh06m8U"
      },
      "source": [
        "`find picked : set of items`"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "PvO14gKeKyLf"
      },
      "source": [
        "The `find` keyword denotes decision variables, these are the variables for which the solver will search for a valid assignment. As is common in Essence problems, our entire problem is modelled using one decision variable named `picked`. Its type is `set of items`; a set of any size whose elements are taken from the `items` domain. Note, the maximum cardinality of the set is implicitly the size of the `items` domain."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "KwTtli4p6qd6"
      },
      "source": [
        "`maximising sum i in picked . gain(i)`"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "a_RSfRhQLAq1"
      },
      "source": [
        "The `maximising` keyword denotes the objective for the solver; a value for the solver to *maximise*. `minimise` is also a valid objective keyword. The expression `sum i in picked .` is a quantifier. The sum says that the values we produce should be summed together. The i in picked says we want to list out every element of the set `picked`. The expression given to the `sum` are described by the expression that follows the full-stop (.). In this case, we are asking for the image of `i` in the `gain` function. That is, for each item in the set, we are looking up the integer value that the item maps to in the `gain` function and summing these integers."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "MqbSkMYu6vIt"
      },
      "source": [
        "`such that (sum i in picked . weight(i)) <= capacity`"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Z9Ug5YKJLWBt"
      },
      "source": [
        "The `such that` keyword denotes a constraint. Here the constraint is formulated in a similar manner to the objective. We are quantifying over the set of chosen items `picked`, looking up the value that the item maps to in the `weights` function and summing these values to together. We enforce that the result of the sum must be less than or equal to the capacity `<= capacity`.\n",
        "\n",
        "Note that you can post multiple constraints either by using commas between each constraint `,` or by reusing the keyword `such that`."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "IQkhfYsfMTzt"
      },
      "source": [
        "## Solving the problem"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "zQdE5f_yMhY8"
      },
      "source": [
        "Having run the earlier definition cells, we can now run the model:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 6,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "id": "PykrdRJYMoO9",
        "outputId": "8f4d094f-fe60-47e8-f456-3f375ca499f8"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "```json\n",
              "{\"picked\": [\"b\", \"d\"]}\n",
              "```"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "%%conjure+\n",
        "find picked : set of items\n",
        "maximising sum i in picked . gain(i)\n",
        "such that (sum i in picked . weight(i)) <= capacity"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Zeb9D96g9C_E"
      },
      "source": [
        "## Visualisations:"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "QKFbX2ryCXyj"
      },
      "source": [
        "We can print the result using python code:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 7,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "zZWJyxyh9HXC",
        "outputId": "5a5c2eb6-18e3-4a3c-f4c3-1c5649744292"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "['b', 'd']\n"
          ]
        }
      ],
      "source": [
        "print(picked)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "rOwOZWoyCeeE"
      },
      "source": [
        "We can also show `picked` as a graph:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 8,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 154
        },
        "id": "tY1u6ZJSDuy8",
        "outputId": "c87a7320-561f-496f-a205-147c1db1c1f9"
      },
      "outputs": [
        {
          "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: parent Pages: 1 -->\n",
              "<svg width=\"166pt\" height=\"99pt\"\n",
              " viewBox=\"0.00 0.00 166.00 99.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 95)\">\n",
              "<title>parent</title>\n",
              "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-95 162,-95 162,4 -4,4\"/>\n",
              "<g id=\"clust1\" class=\"cluster\">\n",
              "<title>clusterx</title>\n",
              "<path fill=\"none\" stroke=\"black\" d=\"M20,-8C20,-8 138,-8 138,-8 144,-8 150,-14 150,-20 150,-20 150,-71 150,-71 150,-77 144,-83 138,-83 138,-83 20,-83 20,-83 14,-83 8,-77 8,-71 8,-71 8,-20 8,-20 8,-14 14,-8 20,-8\"/>\n",
              "<text text-anchor=\"middle\" x=\"79\" y=\"-67.8\" font-family=\"Times,serif\" font-size=\"14.00\">picked</text>\n",
              "</g>\n",
              "<!-- b -->\n",
              "<g id=\"node1\" class=\"node\">\n",
              "<title>b</title>\n",
              "<path fill=\"none\" stroke=\"blue\" d=\"M135.15,-42.72C135.15,-42.72 121.85,-48.85 121.85,-48.85 118.42,-50.42 111.58,-50.42 108.15,-48.85 108.15,-48.85 94.85,-42.72 94.85,-42.72 91.42,-41.14 89.72,-36.21 91.44,-32.85 91.44,-32.85 94.88,-26.15 94.88,-26.15 96.59,-22.79 102.08,-19.44 105.85,-19.44 105.85,-19.44 124.15,-19.44 124.15,-19.44 127.92,-19.44 133.41,-22.79 135.12,-26.15 135.12,-26.15 138.56,-32.85 138.56,-32.85 140.28,-36.21 138.58,-41.14 135.15,-42.72\"/>\n",
              "<text text-anchor=\"middle\" x=\"115\" y=\"-30.3\" font-family=\"Times,serif\" font-size=\"14.00\">b</text>\n",
              "</g>\n",
              "<!-- d -->\n",
              "<g id=\"node2\" class=\"node\">\n",
              "<title>d</title>\n",
              "<path fill=\"none\" stroke=\"blue\" d=\"M63.15,-42.72C63.15,-42.72 49.85,-48.85 49.85,-48.85 46.42,-50.42 39.58,-50.42 36.15,-48.85 36.15,-48.85 22.85,-42.72 22.85,-42.72 19.42,-41.14 17.72,-36.21 19.44,-32.85 19.44,-32.85 22.88,-26.15 22.88,-26.15 24.59,-22.79 30.08,-19.44 33.85,-19.44 33.85,-19.44 52.15,-19.44 52.15,-19.44 55.92,-19.44 61.41,-22.79 63.12,-26.15 63.12,-26.15 66.56,-32.85 66.56,-32.85 68.28,-36.21 66.58,-41.14 63.15,-42.72\"/>\n",
              "<text text-anchor=\"middle\" x=\"43\" y=\"-30.3\" font-family=\"Times,serif\" font-size=\"14.00\">d</text>\n",
              "</g>\n",
              "</g>\n",
              "</svg>\n"
            ],
            "text/plain": [
              "<graphviz.graphs.Digraph at 0x790f947752a0>"
            ]
          },
          "execution_count": 8,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "import graphviz\n",
        "\n",
        "p = graphviz.Digraph('parent')\n",
        "p.attr(compound='true')\n",
        "\n",
        "\n",
        "with p.subgraph(name='clusterx', node_attr={'shape': 'pentagon', 'color': 'blue', 'style':'rounded'}) as c:\n",
        "    for item in picked:\n",
        "      c.node(str(item))\n",
        "    c.attr(label='picked')\n",
        "    c.attr(style='rounded')\n",
        "\n",
        "p"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "provenance": [],
      "toc_visible": true
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}