{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "3fd2f6b8",
   "metadata": {},
   "outputs": [],
   "source": [
    "class IncidenceListGraph:\n",
    "    def __init__(self):\n",
    "        self._nodes = []  # list of nodes\n",
    "        self._edges = []  # list of edges\n",
    "    \n",
    "    def get_nodes(self):\n",
    "        return self._nodes\n",
    "    def get_edges(self):\n",
    "        return self._edges\n",
    "    \n",
    "    # returns a/the node with the label \"value\", or None, if no such node exist\n",
    "    #\n",
    "    def find_node(self, value):\n",
    "        for v in self._nodes:\n",
    "            if v.get_item() == value:\n",
    "                return v\n",
    "        return None\n",
    "    \n",
    "    # creates and inserts a node with the label \"value\"\n",
    "    # and returns an object reference to that new node\n",
    "    #\n",
    "    def insert_node(self, value):\n",
    "        node = IncidenceListGraphNode(value)\n",
    "        self._nodes.append(node)\n",
    "        return node\n",
    "    \n",
    "    # creates and inserts an edge from the node \"source\" to the node \"target\"\n",
    "    # an object reference to the new edge is returned\n",
    "    #\n",
    "    # \"source\" and \"target\" should be elements of the \"_nodes\" list\n",
    "    # for performance reasons, we do not check this\n",
    "    #\n",
    "    def connect_nodes(self, source, target, value):\n",
    "        edge = IncidenceListGraphEdge(source, target, value)\n",
    "        self._edges.append(edge)\n",
    "        source.insert_outgoing_edge(edge)\n",
    "        target.insert_incoming_edge(edge)\n",
    "    \n",
    "    def output(self):\n",
    "        for v in self._nodes:\n",
    "            print(\"Node labelled \", v.get_item(), \":\", sep=\"\", end=\"\")\n",
    "            for e in v.get_edges_out():\n",
    "                print(\"\\t--[\", e.get_item(), \"]--> \", e.get_target().get_item(), sep=\"\", end=\"\")\n",
    "            print()\n",
    "    \n",
    "class IncidenceListGraphNode:\n",
    "    def __init__(self, value):  # create a node with \"value\" as its label (\"_item\")\n",
    "        self._item = value\n",
    "        self._in = []  # list of incoming edges\n",
    "        self._out = []  # list of outgoing edges\n",
    "    \n",
    "    def get_item(self):   # returns the data item (label) associated with this node\n",
    "        return self._item\n",
    "    def get_edges_in(self):  # returns list of incoming edges\n",
    "        return self._in\n",
    "    def get_edges_out(self):  # returns list of outgoing edges\n",
    "        return self._out\n",
    "    \n",
    "    def insert_outgoing_edge(self, edge):\n",
    "        if edge.get_source() is not self:\n",
    "            print(\"Error: Inconsistent source node specified for a new outgoing edge.\")\n",
    "            return\n",
    "        self._out.append(edge)\n",
    "    def insert_incoming_edge(self, edge):\n",
    "        if edge.get_target() is not self:\n",
    "            print(\"Error: Inconsistent target node specified for a new incoming edge.\")\n",
    "            return\n",
    "        self._in.append(edge)\n",
    "\n",
    "class IncidenceListGraphEdge:\n",
    "    # create an edge connecting node \"source\" to node \"target\",\n",
    "    # with \"value\" as its label (\"_item\")\n",
    "    def __init__(self, source, target, value):\n",
    "        self._item = value\n",
    "        self._source = source\n",
    "        self._target = target\n",
    "    \n",
    "    def get_item(self):  # returns the data item (label) associated with this edge\n",
    "        return self._item\n",
    "    def get_source(self):  # returns the source node of the edge\n",
    "        return self._source\n",
    "    def get_target(self):\n",
    "        return self._target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "0e67fae9",
   "metadata": {},
   "outputs": [],
   "source": [
    "# arguments/precondition:\n",
    "#\n",
    "#  * max_amount is a natural number, expressed in the smallest currency unit\n",
    "#  * coin_types is the list of coin types available, such as [1, 2, 5, 10] or [1, 4, 9, 16]\n",
    "#\n",
    "# the function creates and returns a graph with node labels ranging from 0 to amount,\n",
    "# where edges from a node labelled x to a node labelled y are included whenever\n",
    "# there is a coin with a value such that y = x + value of the coin\n",
    "#\n",
    "# for example, with amount = 12 and coin_types = [1, 2, 5, 10], the node labelled \"7\" would\n",
    "# have three outgoing edges, leading to the nodes labelled 8 (7+1), 9 (7+2), and 12 (7+5);\n",
    "# it would have three incoming edges, coming from the nodes labelled 6 (7-1), 5 (7-2), and 2 (7-5)\n",
    "#\n",
    "def cashier_graph(max_amount, coin_types):\n",
    "    graph = IncidenceListGraph()  # the graph that we are working on\n",
    "    nodes = [graph.insert_node(x) for x in range(max_amount+1)]  # list of nodes\n",
    "    \n",
    "    for x in range(max_amount):\n",
    "        for coin in coin_types:\n",
    "            y = x + coin\n",
    "            if max_amount >= y:\n",
    "                graph.connect_nodes(nodes[x], nodes[y], coin)  # create an edge from x to y, labelled coin\n",
    "    return graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "d637c2e3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Node labelled 0:\t--[1]--> 1\t--[8]--> 8\t--[27]--> 27\t--[64]--> 64\t--[125]--> 125\n",
      "Node labelled 1:\t--[1]--> 2\t--[8]--> 9\t--[27]--> 28\t--[64]--> 65\t--[125]--> 126\n",
      "Node labelled 2:\t--[1]--> 3\t--[8]--> 10\t--[27]--> 29\t--[64]--> 66\t--[125]--> 127\n",
      "Node labelled 3:\t--[1]--> 4\t--[8]--> 11\t--[27]--> 30\t--[64]--> 67\t--[125]--> 128\n",
      "Node labelled 4:\t--[1]--> 5\t--[8]--> 12\t--[27]--> 31\t--[64]--> 68\t--[125]--> 129\n",
      "Node labelled 5:\t--[1]--> 6\t--[8]--> 13\t--[27]--> 32\t--[64]--> 69\t--[125]--> 130\n",
      "Node labelled 6:\t--[1]--> 7\t--[8]--> 14\t--[27]--> 33\t--[64]--> 70\t--[125]--> 131\n",
      "Node labelled 7:\t--[1]--> 8\t--[8]--> 15\t--[27]--> 34\t--[64]--> 71\t--[125]--> 132\n",
      "Node labelled 8:\t--[1]--> 9\t--[8]--> 16\t--[27]--> 35\t--[64]--> 72\t--[125]--> 133\n",
      "Node labelled 9:\t--[1]--> 10\t--[8]--> 17\t--[27]--> 36\t--[64]--> 73\t--[125]--> 134\n",
      "Node labelled 10:\t--[1]--> 11\t--[8]--> 18\t--[27]--> 37\t--[64]--> 74\t--[125]--> 135\n",
      "Node labelled 11:\t--[1]--> 12\t--[8]--> 19\t--[27]--> 38\t--[64]--> 75\t--[125]--> 136\n",
      "Node labelled 12:\t--[1]--> 13\t--[8]--> 20\t--[27]--> 39\t--[64]--> 76\t--[125]--> 137\n",
      "Node labelled 13:\t--[1]--> 14\t--[8]--> 21\t--[27]--> 40\t--[64]--> 77\t--[125]--> 138\n",
      "Node labelled 14:\t--[1]--> 15\t--[8]--> 22\t--[27]--> 41\t--[64]--> 78\t--[125]--> 139\n",
      "Node labelled 15:\t--[1]--> 16\t--[8]--> 23\t--[27]--> 42\t--[64]--> 79\t--[125]--> 140\n",
      "Node labelled 16:\t--[1]--> 17\t--[8]--> 24\t--[27]--> 43\t--[64]--> 80\t--[125]--> 141\n",
      "Node labelled 17:\t--[1]--> 18\t--[8]--> 25\t--[27]--> 44\t--[64]--> 81\t--[125]--> 142\n",
      "Node labelled 18:\t--[1]--> 19\t--[8]--> 26\t--[27]--> 45\t--[64]--> 82\t--[125]--> 143\n",
      "Node labelled 19:\t--[1]--> 20\t--[8]--> 27\t--[27]--> 46\t--[64]--> 83\t--[125]--> 144\n",
      "Node labelled 20:\t--[1]--> 21\t--[8]--> 28\t--[27]--> 47\t--[64]--> 84\t--[125]--> 145\n",
      "Node labelled 21:\t--[1]--> 22\t--[8]--> 29\t--[27]--> 48\t--[64]--> 85\t--[125]--> 146\n",
      "Node labelled 22:\t--[1]--> 23\t--[8]--> 30\t--[27]--> 49\t--[64]--> 86\t--[125]--> 147\n",
      "Node labelled 23:\t--[1]--> 24\t--[8]--> 31\t--[27]--> 50\t--[64]--> 87\t--[125]--> 148\n",
      "Node labelled 24:\t--[1]--> 25\t--[8]--> 32\t--[27]--> 51\t--[64]--> 88\t--[125]--> 149\n",
      "Node labelled 25:\t--[1]--> 26\t--[8]--> 33\t--[27]--> 52\t--[64]--> 89\t--[125]--> 150\n",
      "Node labelled 26:\t--[1]--> 27\t--[8]--> 34\t--[27]--> 53\t--[64]--> 90\t--[125]--> 151\n",
      "Node labelled 27:\t--[1]--> 28\t--[8]--> 35\t--[27]--> 54\t--[64]--> 91\t--[125]--> 152\n",
      "Node labelled 28:\t--[1]--> 29\t--[8]--> 36\t--[27]--> 55\t--[64]--> 92\t--[125]--> 153\n",
      "Node labelled 29:\t--[1]--> 30\t--[8]--> 37\t--[27]--> 56\t--[64]--> 93\t--[125]--> 154\n",
      "Node labelled 30:\t--[1]--> 31\t--[8]--> 38\t--[27]--> 57\t--[64]--> 94\t--[125]--> 155\n",
      "Node labelled 31:\t--[1]--> 32\t--[8]--> 39\t--[27]--> 58\t--[64]--> 95\t--[125]--> 156\n",
      "Node labelled 32:\t--[1]--> 33\t--[8]--> 40\t--[27]--> 59\t--[64]--> 96\t--[125]--> 157\n",
      "Node labelled 33:\t--[1]--> 34\t--[8]--> 41\t--[27]--> 60\t--[64]--> 97\t--[125]--> 158\n",
      "Node labelled 34:\t--[1]--> 35\t--[8]--> 42\t--[27]--> 61\t--[64]--> 98\t--[125]--> 159\n",
      "Node labelled 35:\t--[1]--> 36\t--[8]--> 43\t--[27]--> 62\t--[64]--> 99\t--[125]--> 160\n",
      "Node labelled 36:\t--[1]--> 37\t--[8]--> 44\t--[27]--> 63\t--[64]--> 100\t--[125]--> 161\n",
      "Node labelled 37:\t--[1]--> 38\t--[8]--> 45\t--[27]--> 64\t--[64]--> 101\t--[125]--> 162\n",
      "Node labelled 38:\t--[1]--> 39\t--[8]--> 46\t--[27]--> 65\t--[64]--> 102\t--[125]--> 163\n",
      "Node labelled 39:\t--[1]--> 40\t--[8]--> 47\t--[27]--> 66\t--[64]--> 103\t--[125]--> 164\n",
      "Node labelled 40:\t--[1]--> 41\t--[8]--> 48\t--[27]--> 67\t--[64]--> 104\t--[125]--> 165\n",
      "Node labelled 41:\t--[1]--> 42\t--[8]--> 49\t--[27]--> 68\t--[64]--> 105\t--[125]--> 166\n",
      "Node labelled 42:\t--[1]--> 43\t--[8]--> 50\t--[27]--> 69\t--[64]--> 106\t--[125]--> 167\n",
      "Node labelled 43:\t--[1]--> 44\t--[8]--> 51\t--[27]--> 70\t--[64]--> 107\t--[125]--> 168\n",
      "Node labelled 44:\t--[1]--> 45\t--[8]--> 52\t--[27]--> 71\t--[64]--> 108\t--[125]--> 169\n",
      "Node labelled 45:\t--[1]--> 46\t--[8]--> 53\t--[27]--> 72\t--[64]--> 109\t--[125]--> 170\n",
      "Node labelled 46:\t--[1]--> 47\t--[8]--> 54\t--[27]--> 73\t--[64]--> 110\t--[125]--> 171\n",
      "Node labelled 47:\t--[1]--> 48\t--[8]--> 55\t--[27]--> 74\t--[64]--> 111\t--[125]--> 172\n",
      "Node labelled 48:\t--[1]--> 49\t--[8]--> 56\t--[27]--> 75\t--[64]--> 112\t--[125]--> 173\n",
      "Node labelled 49:\t--[1]--> 50\t--[8]--> 57\t--[27]--> 76\t--[64]--> 113\t--[125]--> 174\n",
      "Node labelled 50:\t--[1]--> 51\t--[8]--> 58\t--[27]--> 77\t--[64]--> 114\t--[125]--> 175\n",
      "Node labelled 51:\t--[1]--> 52\t--[8]--> 59\t--[27]--> 78\t--[64]--> 115\t--[125]--> 176\n",
      "Node labelled 52:\t--[1]--> 53\t--[8]--> 60\t--[27]--> 79\t--[64]--> 116\t--[125]--> 177\n",
      "Node labelled 53:\t--[1]--> 54\t--[8]--> 61\t--[27]--> 80\t--[64]--> 117\t--[125]--> 178\n",
      "Node labelled 54:\t--[1]--> 55\t--[8]--> 62\t--[27]--> 81\t--[64]--> 118\t--[125]--> 179\n",
      "Node labelled 55:\t--[1]--> 56\t--[8]--> 63\t--[27]--> 82\t--[64]--> 119\t--[125]--> 180\n",
      "Node labelled 56:\t--[1]--> 57\t--[8]--> 64\t--[27]--> 83\t--[64]--> 120\t--[125]--> 181\n",
      "Node labelled 57:\t--[1]--> 58\t--[8]--> 65\t--[27]--> 84\t--[64]--> 121\t--[125]--> 182\n",
      "Node labelled 58:\t--[1]--> 59\t--[8]--> 66\t--[27]--> 85\t--[64]--> 122\t--[125]--> 183\n",
      "Node labelled 59:\t--[1]--> 60\t--[8]--> 67\t--[27]--> 86\t--[64]--> 123\t--[125]--> 184\n",
      "Node labelled 60:\t--[1]--> 61\t--[8]--> 68\t--[27]--> 87\t--[64]--> 124\t--[125]--> 185\n",
      "Node labelled 61:\t--[1]--> 62\t--[8]--> 69\t--[27]--> 88\t--[64]--> 125\t--[125]--> 186\n",
      "Node labelled 62:\t--[1]--> 63\t--[8]--> 70\t--[27]--> 89\t--[64]--> 126\t--[125]--> 187\n",
      "Node labelled 63:\t--[1]--> 64\t--[8]--> 71\t--[27]--> 90\t--[64]--> 127\t--[125]--> 188\n",
      "Node labelled 64:\t--[1]--> 65\t--[8]--> 72\t--[27]--> 91\t--[64]--> 128\t--[125]--> 189\n",
      "Node labelled 65:\t--[1]--> 66\t--[8]--> 73\t--[27]--> 92\t--[64]--> 129\t--[125]--> 190\n",
      "Node labelled 66:\t--[1]--> 67\t--[8]--> 74\t--[27]--> 93\t--[64]--> 130\t--[125]--> 191\n",
      "Node labelled 67:\t--[1]--> 68\t--[8]--> 75\t--[27]--> 94\t--[64]--> 131\t--[125]--> 192\n",
      "Node labelled 68:\t--[1]--> 69\t--[8]--> 76\t--[27]--> 95\t--[64]--> 132\t--[125]--> 193\n",
      "Node labelled 69:\t--[1]--> 70\t--[8]--> 77\t--[27]--> 96\t--[64]--> 133\t--[125]--> 194\n",
      "Node labelled 70:\t--[1]--> 71\t--[8]--> 78\t--[27]--> 97\t--[64]--> 134\t--[125]--> 195\n",
      "Node labelled 71:\t--[1]--> 72\t--[8]--> 79\t--[27]--> 98\t--[64]--> 135\t--[125]--> 196\n",
      "Node labelled 72:\t--[1]--> 73\t--[8]--> 80\t--[27]--> 99\t--[64]--> 136\t--[125]--> 197\n",
      "Node labelled 73:\t--[1]--> 74\t--[8]--> 81\t--[27]--> 100\t--[64]--> 137\t--[125]--> 198\n",
      "Node labelled 74:\t--[1]--> 75\t--[8]--> 82\t--[27]--> 101\t--[64]--> 138\t--[125]--> 199\n",
      "Node labelled 75:\t--[1]--> 76\t--[8]--> 83\t--[27]--> 102\t--[64]--> 139\t--[125]--> 200\n",
      "Node labelled 76:\t--[1]--> 77\t--[8]--> 84\t--[27]--> 103\t--[64]--> 140\t--[125]--> 201\n",
      "Node labelled 77:\t--[1]--> 78\t--[8]--> 85\t--[27]--> 104\t--[64]--> 141\t--[125]--> 202\n",
      "Node labelled 78:\t--[1]--> 79\t--[8]--> 86\t--[27]--> 105\t--[64]--> 142\t--[125]--> 203\n",
      "Node labelled 79:\t--[1]--> 80\t--[8]--> 87\t--[27]--> 106\t--[64]--> 143\t--[125]--> 204\n",
      "Node labelled 80:\t--[1]--> 81\t--[8]--> 88\t--[27]--> 107\t--[64]--> 144\t--[125]--> 205\n",
      "Node labelled 81:\t--[1]--> 82\t--[8]--> 89\t--[27]--> 108\t--[64]--> 145\t--[125]--> 206\n",
      "Node labelled 82:\t--[1]--> 83\t--[8]--> 90\t--[27]--> 109\t--[64]--> 146\t--[125]--> 207\n",
      "Node labelled 83:\t--[1]--> 84\t--[8]--> 91\t--[27]--> 110\t--[64]--> 147\t--[125]--> 208\n",
      "Node labelled 84:\t--[1]--> 85\t--[8]--> 92\t--[27]--> 111\t--[64]--> 148\t--[125]--> 209\n",
      "Node labelled 85:\t--[1]--> 86\t--[8]--> 93\t--[27]--> 112\t--[64]--> 149\t--[125]--> 210\n",
      "Node labelled 86:\t--[1]--> 87\t--[8]--> 94\t--[27]--> 113\t--[64]--> 150\t--[125]--> 211\n",
      "Node labelled 87:\t--[1]--> 88\t--[8]--> 95\t--[27]--> 114\t--[64]--> 151\t--[125]--> 212\n",
      "Node labelled 88:\t--[1]--> 89\t--[8]--> 96\t--[27]--> 115\t--[64]--> 152\t--[125]--> 213\n",
      "Node labelled 89:\t--[1]--> 90\t--[8]--> 97\t--[27]--> 116\t--[64]--> 153\t--[125]--> 214\n",
      "Node labelled 90:\t--[1]--> 91\t--[8]--> 98\t--[27]--> 117\t--[64]--> 154\t--[125]--> 215\n",
      "Node labelled 91:\t--[1]--> 92\t--[8]--> 99\t--[27]--> 118\t--[64]--> 155\t--[125]--> 216\n",
      "Node labelled 92:\t--[1]--> 93\t--[8]--> 100\t--[27]--> 119\t--[64]--> 156\t--[125]--> 217\n",
      "Node labelled 93:\t--[1]--> 94\t--[8]--> 101\t--[27]--> 120\t--[64]--> 157\t--[125]--> 218\n",
      "Node labelled 94:\t--[1]--> 95\t--[8]--> 102\t--[27]--> 121\t--[64]--> 158\t--[125]--> 219\n",
      "Node labelled 95:\t--[1]--> 96\t--[8]--> 103\t--[27]--> 122\t--[64]--> 159\t--[125]--> 220\n",
      "Node labelled 96:\t--[1]--> 97\t--[8]--> 104\t--[27]--> 123\t--[64]--> 160\t--[125]--> 221\n",
      "Node labelled 97:\t--[1]--> 98\t--[8]--> 105\t--[27]--> 124\t--[64]--> 161\t--[125]--> 222\n",
      "Node labelled 98:\t--[1]--> 99\t--[8]--> 106\t--[27]--> 125\t--[64]--> 162\t--[125]--> 223\n",
      "Node labelled 99:\t--[1]--> 100\t--[8]--> 107\t--[27]--> 126\t--[64]--> 163\t--[125]--> 224\n",
      "Node labelled 100:\t--[1]--> 101\t--[8]--> 108\t--[27]--> 127\t--[64]--> 164\t--[125]--> 225\n",
      "Node labelled 101:\t--[1]--> 102\t--[8]--> 109\t--[27]--> 128\t--[64]--> 165\t--[125]--> 226\n",
      "Node labelled 102:\t--[1]--> 103\t--[8]--> 110\t--[27]--> 129\t--[64]--> 166\t--[125]--> 227\n",
      "Node labelled 103:\t--[1]--> 104\t--[8]--> 111\t--[27]--> 130\t--[64]--> 167\t--[125]--> 228\n",
      "Node labelled 104:\t--[1]--> 105\t--[8]--> 112\t--[27]--> 131\t--[64]--> 168\t--[125]--> 229\n",
      "Node labelled 105:\t--[1]--> 106\t--[8]--> 113\t--[27]--> 132\t--[64]--> 169\t--[125]--> 230\n",
      "Node labelled 106:\t--[1]--> 107\t--[8]--> 114\t--[27]--> 133\t--[64]--> 170\t--[125]--> 231\n",
      "Node labelled 107:\t--[1]--> 108\t--[8]--> 115\t--[27]--> 134\t--[64]--> 171\t--[125]--> 232\n",
      "Node labelled 108:\t--[1]--> 109\t--[8]--> 116\t--[27]--> 135\t--[64]--> 172\t--[125]--> 233\n",
      "Node labelled 109:\t--[1]--> 110\t--[8]--> 117\t--[27]--> 136\t--[64]--> 173\t--[125]--> 234\n",
      "Node labelled 110:\t--[1]--> 111\t--[8]--> 118\t--[27]--> 137\t--[64]--> 174\t--[125]--> 235\n",
      "Node labelled 111:\t--[1]--> 112\t--[8]--> 119\t--[27]--> 138\t--[64]--> 175\t--[125]--> 236\n",
      "Node labelled 112:\t--[1]--> 113\t--[8]--> 120\t--[27]--> 139\t--[64]--> 176\t--[125]--> 237\n",
      "Node labelled 113:\t--[1]--> 114\t--[8]--> 121\t--[27]--> 140\t--[64]--> 177\t--[125]--> 238\n",
      "Node labelled 114:\t--[1]--> 115\t--[8]--> 122\t--[27]--> 141\t--[64]--> 178\t--[125]--> 239\n",
      "Node labelled 115:\t--[1]--> 116\t--[8]--> 123\t--[27]--> 142\t--[64]--> 179\t--[125]--> 240\n",
      "Node labelled 116:\t--[1]--> 117\t--[8]--> 124\t--[27]--> 143\t--[64]--> 180\t--[125]--> 241\n",
      "Node labelled 117:\t--[1]--> 118\t--[8]--> 125\t--[27]--> 144\t--[64]--> 181\t--[125]--> 242\n",
      "Node labelled 118:\t--[1]--> 119\t--[8]--> 126\t--[27]--> 145\t--[64]--> 182\t--[125]--> 243\n",
      "Node labelled 119:\t--[1]--> 120\t--[8]--> 127\t--[27]--> 146\t--[64]--> 183\t--[125]--> 244\n",
      "Node labelled 120:\t--[1]--> 121\t--[8]--> 128\t--[27]--> 147\t--[64]--> 184\t--[125]--> 245\n",
      "Node labelled 121:\t--[1]--> 122\t--[8]--> 129\t--[27]--> 148\t--[64]--> 185\t--[125]--> 246\n",
      "Node labelled 122:\t--[1]--> 123\t--[8]--> 130\t--[27]--> 149\t--[64]--> 186\t--[125]--> 247\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Node labelled 123:\t--[1]--> 124\t--[8]--> 131\t--[27]--> 150\t--[64]--> 187\t--[125]--> 248\n",
      "Node labelled 124:\t--[1]--> 125\t--[8]--> 132\t--[27]--> 151\t--[64]--> 188\t--[125]--> 249\n",
      "Node labelled 125:\t--[1]--> 126\t--[8]--> 133\t--[27]--> 152\t--[64]--> 189\t--[125]--> 250\n",
      "Node labelled 126:\t--[1]--> 127\t--[8]--> 134\t--[27]--> 153\t--[64]--> 190\n",
      "Node labelled 127:\t--[1]--> 128\t--[8]--> 135\t--[27]--> 154\t--[64]--> 191\n",
      "Node labelled 128:\t--[1]--> 129\t--[8]--> 136\t--[27]--> 155\t--[64]--> 192\n",
      "Node labelled 129:\t--[1]--> 130\t--[8]--> 137\t--[27]--> 156\t--[64]--> 193\n",
      "Node labelled 130:\t--[1]--> 131\t--[8]--> 138\t--[27]--> 157\t--[64]--> 194\n",
      "Node labelled 131:\t--[1]--> 132\t--[8]--> 139\t--[27]--> 158\t--[64]--> 195\n",
      "Node labelled 132:\t--[1]--> 133\t--[8]--> 140\t--[27]--> 159\t--[64]--> 196\n",
      "Node labelled 133:\t--[1]--> 134\t--[8]--> 141\t--[27]--> 160\t--[64]--> 197\n",
      "Node labelled 134:\t--[1]--> 135\t--[8]--> 142\t--[27]--> 161\t--[64]--> 198\n",
      "Node labelled 135:\t--[1]--> 136\t--[8]--> 143\t--[27]--> 162\t--[64]--> 199\n",
      "Node labelled 136:\t--[1]--> 137\t--[8]--> 144\t--[27]--> 163\t--[64]--> 200\n",
      "Node labelled 137:\t--[1]--> 138\t--[8]--> 145\t--[27]--> 164\t--[64]--> 201\n",
      "Node labelled 138:\t--[1]--> 139\t--[8]--> 146\t--[27]--> 165\t--[64]--> 202\n",
      "Node labelled 139:\t--[1]--> 140\t--[8]--> 147\t--[27]--> 166\t--[64]--> 203\n",
      "Node labelled 140:\t--[1]--> 141\t--[8]--> 148\t--[27]--> 167\t--[64]--> 204\n",
      "Node labelled 141:\t--[1]--> 142\t--[8]--> 149\t--[27]--> 168\t--[64]--> 205\n",
      "Node labelled 142:\t--[1]--> 143\t--[8]--> 150\t--[27]--> 169\t--[64]--> 206\n",
      "Node labelled 143:\t--[1]--> 144\t--[8]--> 151\t--[27]--> 170\t--[64]--> 207\n",
      "Node labelled 144:\t--[1]--> 145\t--[8]--> 152\t--[27]--> 171\t--[64]--> 208\n",
      "Node labelled 145:\t--[1]--> 146\t--[8]--> 153\t--[27]--> 172\t--[64]--> 209\n",
      "Node labelled 146:\t--[1]--> 147\t--[8]--> 154\t--[27]--> 173\t--[64]--> 210\n",
      "Node labelled 147:\t--[1]--> 148\t--[8]--> 155\t--[27]--> 174\t--[64]--> 211\n",
      "Node labelled 148:\t--[1]--> 149\t--[8]--> 156\t--[27]--> 175\t--[64]--> 212\n",
      "Node labelled 149:\t--[1]--> 150\t--[8]--> 157\t--[27]--> 176\t--[64]--> 213\n",
      "Node labelled 150:\t--[1]--> 151\t--[8]--> 158\t--[27]--> 177\t--[64]--> 214\n",
      "Node labelled 151:\t--[1]--> 152\t--[8]--> 159\t--[27]--> 178\t--[64]--> 215\n",
      "Node labelled 152:\t--[1]--> 153\t--[8]--> 160\t--[27]--> 179\t--[64]--> 216\n",
      "Node labelled 153:\t--[1]--> 154\t--[8]--> 161\t--[27]--> 180\t--[64]--> 217\n",
      "Node labelled 154:\t--[1]--> 155\t--[8]--> 162\t--[27]--> 181\t--[64]--> 218\n",
      "Node labelled 155:\t--[1]--> 156\t--[8]--> 163\t--[27]--> 182\t--[64]--> 219\n",
      "Node labelled 156:\t--[1]--> 157\t--[8]--> 164\t--[27]--> 183\t--[64]--> 220\n",
      "Node labelled 157:\t--[1]--> 158\t--[8]--> 165\t--[27]--> 184\t--[64]--> 221\n",
      "Node labelled 158:\t--[1]--> 159\t--[8]--> 166\t--[27]--> 185\t--[64]--> 222\n",
      "Node labelled 159:\t--[1]--> 160\t--[8]--> 167\t--[27]--> 186\t--[64]--> 223\n",
      "Node labelled 160:\t--[1]--> 161\t--[8]--> 168\t--[27]--> 187\t--[64]--> 224\n",
      "Node labelled 161:\t--[1]--> 162\t--[8]--> 169\t--[27]--> 188\t--[64]--> 225\n",
      "Node labelled 162:\t--[1]--> 163\t--[8]--> 170\t--[27]--> 189\t--[64]--> 226\n",
      "Node labelled 163:\t--[1]--> 164\t--[8]--> 171\t--[27]--> 190\t--[64]--> 227\n",
      "Node labelled 164:\t--[1]--> 165\t--[8]--> 172\t--[27]--> 191\t--[64]--> 228\n",
      "Node labelled 165:\t--[1]--> 166\t--[8]--> 173\t--[27]--> 192\t--[64]--> 229\n",
      "Node labelled 166:\t--[1]--> 167\t--[8]--> 174\t--[27]--> 193\t--[64]--> 230\n",
      "Node labelled 167:\t--[1]--> 168\t--[8]--> 175\t--[27]--> 194\t--[64]--> 231\n",
      "Node labelled 168:\t--[1]--> 169\t--[8]--> 176\t--[27]--> 195\t--[64]--> 232\n",
      "Node labelled 169:\t--[1]--> 170\t--[8]--> 177\t--[27]--> 196\t--[64]--> 233\n",
      "Node labelled 170:\t--[1]--> 171\t--[8]--> 178\t--[27]--> 197\t--[64]--> 234\n",
      "Node labelled 171:\t--[1]--> 172\t--[8]--> 179\t--[27]--> 198\t--[64]--> 235\n",
      "Node labelled 172:\t--[1]--> 173\t--[8]--> 180\t--[27]--> 199\t--[64]--> 236\n",
      "Node labelled 173:\t--[1]--> 174\t--[8]--> 181\t--[27]--> 200\t--[64]--> 237\n",
      "Node labelled 174:\t--[1]--> 175\t--[8]--> 182\t--[27]--> 201\t--[64]--> 238\n",
      "Node labelled 175:\t--[1]--> 176\t--[8]--> 183\t--[27]--> 202\t--[64]--> 239\n",
      "Node labelled 176:\t--[1]--> 177\t--[8]--> 184\t--[27]--> 203\t--[64]--> 240\n",
      "Node labelled 177:\t--[1]--> 178\t--[8]--> 185\t--[27]--> 204\t--[64]--> 241\n",
      "Node labelled 178:\t--[1]--> 179\t--[8]--> 186\t--[27]--> 205\t--[64]--> 242\n",
      "Node labelled 179:\t--[1]--> 180\t--[8]--> 187\t--[27]--> 206\t--[64]--> 243\n",
      "Node labelled 180:\t--[1]--> 181\t--[8]--> 188\t--[27]--> 207\t--[64]--> 244\n",
      "Node labelled 181:\t--[1]--> 182\t--[8]--> 189\t--[27]--> 208\t--[64]--> 245\n",
      "Node labelled 182:\t--[1]--> 183\t--[8]--> 190\t--[27]--> 209\t--[64]--> 246\n",
      "Node labelled 183:\t--[1]--> 184\t--[8]--> 191\t--[27]--> 210\t--[64]--> 247\n",
      "Node labelled 184:\t--[1]--> 185\t--[8]--> 192\t--[27]--> 211\t--[64]--> 248\n",
      "Node labelled 185:\t--[1]--> 186\t--[8]--> 193\t--[27]--> 212\t--[64]--> 249\n",
      "Node labelled 186:\t--[1]--> 187\t--[8]--> 194\t--[27]--> 213\t--[64]--> 250\n",
      "Node labelled 187:\t--[1]--> 188\t--[8]--> 195\t--[27]--> 214\n",
      "Node labelled 188:\t--[1]--> 189\t--[8]--> 196\t--[27]--> 215\n",
      "Node labelled 189:\t--[1]--> 190\t--[8]--> 197\t--[27]--> 216\n",
      "Node labelled 190:\t--[1]--> 191\t--[8]--> 198\t--[27]--> 217\n",
      "Node labelled 191:\t--[1]--> 192\t--[8]--> 199\t--[27]--> 218\n",
      "Node labelled 192:\t--[1]--> 193\t--[8]--> 200\t--[27]--> 219\n",
      "Node labelled 193:\t--[1]--> 194\t--[8]--> 201\t--[27]--> 220\n",
      "Node labelled 194:\t--[1]--> 195\t--[8]--> 202\t--[27]--> 221\n",
      "Node labelled 195:\t--[1]--> 196\t--[8]--> 203\t--[27]--> 222\n",
      "Node labelled 196:\t--[1]--> 197\t--[8]--> 204\t--[27]--> 223\n",
      "Node labelled 197:\t--[1]--> 198\t--[8]--> 205\t--[27]--> 224\n",
      "Node labelled 198:\t--[1]--> 199\t--[8]--> 206\t--[27]--> 225\n",
      "Node labelled 199:\t--[1]--> 200\t--[8]--> 207\t--[27]--> 226\n",
      "Node labelled 200:\t--[1]--> 201\t--[8]--> 208\t--[27]--> 227\n",
      "Node labelled 201:\t--[1]--> 202\t--[8]--> 209\t--[27]--> 228\n",
      "Node labelled 202:\t--[1]--> 203\t--[8]--> 210\t--[27]--> 229\n",
      "Node labelled 203:\t--[1]--> 204\t--[8]--> 211\t--[27]--> 230\n",
      "Node labelled 204:\t--[1]--> 205\t--[8]--> 212\t--[27]--> 231\n",
      "Node labelled 205:\t--[1]--> 206\t--[8]--> 213\t--[27]--> 232\n",
      "Node labelled 206:\t--[1]--> 207\t--[8]--> 214\t--[27]--> 233\n",
      "Node labelled 207:\t--[1]--> 208\t--[8]--> 215\t--[27]--> 234\n",
      "Node labelled 208:\t--[1]--> 209\t--[8]--> 216\t--[27]--> 235\n",
      "Node labelled 209:\t--[1]--> 210\t--[8]--> 217\t--[27]--> 236\n",
      "Node labelled 210:\t--[1]--> 211\t--[8]--> 218\t--[27]--> 237\n",
      "Node labelled 211:\t--[1]--> 212\t--[8]--> 219\t--[27]--> 238\n",
      "Node labelled 212:\t--[1]--> 213\t--[8]--> 220\t--[27]--> 239\n",
      "Node labelled 213:\t--[1]--> 214\t--[8]--> 221\t--[27]--> 240\n",
      "Node labelled 214:\t--[1]--> 215\t--[8]--> 222\t--[27]--> 241\n",
      "Node labelled 215:\t--[1]--> 216\t--[8]--> 223\t--[27]--> 242\n",
      "Node labelled 216:\t--[1]--> 217\t--[8]--> 224\t--[27]--> 243\n",
      "Node labelled 217:\t--[1]--> 218\t--[8]--> 225\t--[27]--> 244\n",
      "Node labelled 218:\t--[1]--> 219\t--[8]--> 226\t--[27]--> 245\n",
      "Node labelled 219:\t--[1]--> 220\t--[8]--> 227\t--[27]--> 246\n",
      "Node labelled 220:\t--[1]--> 221\t--[8]--> 228\t--[27]--> 247\n",
      "Node labelled 221:\t--[1]--> 222\t--[8]--> 229\t--[27]--> 248\n",
      "Node labelled 222:\t--[1]--> 223\t--[8]--> 230\t--[27]--> 249\n",
      "Node labelled 223:\t--[1]--> 224\t--[8]--> 231\t--[27]--> 250\n",
      "Node labelled 224:\t--[1]--> 225\t--[8]--> 232\n",
      "Node labelled 225:\t--[1]--> 226\t--[8]--> 233\n",
      "Node labelled 226:\t--[1]--> 227\t--[8]--> 234\n",
      "Node labelled 227:\t--[1]--> 228\t--[8]--> 235\n",
      "Node labelled 228:\t--[1]--> 229\t--[8]--> 236\n",
      "Node labelled 229:\t--[1]--> 230\t--[8]--> 237\n",
      "Node labelled 230:\t--[1]--> 231\t--[8]--> 238\n",
      "Node labelled 231:\t--[1]--> 232\t--[8]--> 239\n",
      "Node labelled 232:\t--[1]--> 233\t--[8]--> 240\n",
      "Node labelled 233:\t--[1]--> 234\t--[8]--> 241\n",
      "Node labelled 234:\t--[1]--> 235\t--[8]--> 242\n",
      "Node labelled 235:\t--[1]--> 236\t--[8]--> 243\n",
      "Node labelled 236:\t--[1]--> 237\t--[8]--> 244\n",
      "Node labelled 237:\t--[1]--> 238\t--[8]--> 245\n",
      "Node labelled 238:\t--[1]--> 239\t--[8]--> 246\n",
      "Node labelled 239:\t--[1]--> 240\t--[8]--> 247\n",
      "Node labelled 240:\t--[1]--> 241\t--[8]--> 248\n",
      "Node labelled 241:\t--[1]--> 242\t--[8]--> 249\n",
      "Node labelled 242:\t--[1]--> 243\t--[8]--> 250\n",
      "Node labelled 243:\t--[1]--> 244\n",
      "Node labelled 244:\t--[1]--> 245\n",
      "Node labelled 245:\t--[1]--> 246\n",
      "Node labelled 246:\t--[1]--> 247\n",
      "Node labelled 247:\t--[1]--> 248\n",
      "Node labelled 248:\t--[1]--> 249\n",
      "Node labelled 249:\t--[1]--> 250\n",
      "Node labelled 250:\n"
     ]
    }
   ],
   "source": [
    "max_amount = 250\n",
    "coin_types = [i*i*i for i in range(1, 6)]\n",
    "\n",
    "cubic_cashier_graph = cashier_graph(max_amount, coin_types)\n",
    "cubic_cashier_graph.output()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "a5347acf",
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "# traverse a graph by breadth first search (BFS)\n",
    "#\n",
    "# begin at the node (or a node) labelled \"initial_label\"\n",
    "#\n",
    "# return the depth that the node (or a node) labelled \"search_label\"\n",
    "# has in the BFS spanning tree, in other words, how many links need to\n",
    "# be followed to reach such a node beginning at the initial node\n",
    "#\n",
    "# in other words, we are computing the distance\n",
    "# of a node (the one labelled search_label)\n",
    "# from the initial node (labelled initial_label)\n",
    "#\n",
    "def bfs_depth(graph, initial_label, search_label, debug_output):\n",
    "    \n",
    "    # maintain a set of unvisited nodes\n",
    "    #\n",
    "    unvisited_nodes = {v for v in graph.get_nodes()}\n",
    "    \n",
    "    # find the initial node\n",
    "    #\n",
    "    initial_node = graph.find_node(initial_label)\n",
    "    if initial_node is None:\n",
    "        print(\"Error: Node labelled\", initial_label, \"not found.\")\n",
    "        return math.inf\n",
    "    \n",
    "    # depth 0:\n",
    "    # visit the initial node\n",
    "    #\n",
    "    depth = 0\n",
    "    if search_label == initial_node.get_item():\n",
    "        return depth\n",
    "    present_depth_nodes = [initial_node]\n",
    "    unvisited_nodes.remove(initial_node)  # node is visited now\n",
    "    if debug_output:\n",
    "        print(\"depth\", depth, \"node labels:\", [v.get_item() for v in present_depth_nodes])\n",
    "\n",
    "    #########################################################\n",
    "    #                                                       #\n",
    "    #      *** TRAVERSE THE GRAPH HERE, BEGINNING  ***      #\n",
    "    #      *** WITH THE INITIAL NODE, IN BFS ORDER ***      #\n",
    "    #                                                       #\n",
    "    # *** compute how many edges need to be followed    *** #\n",
    "    # *** until you rearch a node labelled search_label *** #\n",
    "    #                                                       #\n",
    "    #########################################################\n",
    "    \n",
    "    return depth"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "87a24cf9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "depth 0 node labels: [0]\n",
      "\n",
      "71 can be generated with 0 coins.\n"
     ]
    }
   ],
   "source": [
    "amount = 71\n",
    "\n",
    "# recall, from above, the coins types are 1, 8, 27, 64, and 125\n",
    "\n",
    "depth = bfs_depth(cubic_cashier_graph, 0, amount, True)\n",
    "print(\"\\n\", amount, \" can be generated with \", depth, \" coins.\", sep=\"\")\n",
    "\n",
    "# remark: the output should be 5, since 71 = 27 + 27 + 8 + 8 + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "2e1f5054",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# the following should terminate rather than going into an infinite loop;\n",
    "# it should be determined that a node labelled 24 cannot be reached if we begin at the node labelled 240\n",
    "\n",
    "bfs_depth(cubic_cashier_graph, 240, 24, False)"
   ]
  }
 ],
 "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.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}