comp7015_Lab1_Solving problems_using_Search.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "comp7015 Lab1 Solving problems using Search",
      "provenance": [],
      "collapsed_sections": [],
      "toc_visible": true,
      "authorship_tag": "ABX9TyMw+QUJZHu8LcY2rjkoDwWQ",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    },
    "gpuClass": "standard"
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/hkbu-kennycheng/comp7015/blob/main/comp7015_Lab1_Solving%C2%A0problems_using_Search.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Lab1: Solving problems using Search\n",
        "\n",
        "---"
      ],
      "metadata": {
        "id": "QBmfNrus59Cu"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from IPython import display"
      ],
      "metadata": {
        "id": "9eBdGN4QbQIu"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Queue\n",
        "\n",
        "**Producer**\n",
        "\n",
        "**Consumer**"
      ],
      "metadata": {
        "id": "WfZ9w0h3yRSm"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## First in first out (FIFO) queue\n",
        "\n",
        "FIFO queue is a simple queue concept, just like you lineup in front of the casher. The one goes lineup in the queue first would goes out first."
      ],
      "metadata": {
        "id": "v3aCW_GsydpN"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "display.IFrame(src='https://cslinux0.comp.hkbu.edu.hk/~kennycheng/fifo.html', width=400, height=200)"
      ],
      "metadata": {
        "id": "5jcZf872yP0u",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 221
        },
        "outputId": "f42c6968-d13c-49b5-f538-9cd6ef7536df"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<IPython.lib.display.IFrame at 0x7fbe962bfdd0>"
            ],
            "text/html": [
              "\n",
              "        <iframe\n",
              "            width=\"400\"\n",
              "            height=\"200\"\n",
              "            src=\"https://cslinux0.comp.hkbu.edu.hk/~kennycheng/fifo.html\"\n",
              "            frameborder=\"0\"\n",
              "            allowfullscreen\n",
              "        ></iframe>\n",
              "        "
            ]
          },
          "metadata": {},
          "execution_count": 3
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### FIFO queue in Python\n",
        "\n"
      ],
      "metadata": {
        "id": "2olgqiDdLigr"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from queue import Queue\n",
        "\n",
        "fifo = Queue()\n",
        "fifo.put('Peter')\n",
        "fifo.put('John')\n",
        "fifo.put('Mary')\n",
        "fifo.put('Amy')\n",
        "\n",
        "# we would check how many items in the queue with `.qsize()`.\n",
        "print(f'We have {fifo.qsize()} persons in queue.')"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ewSV1pamLpe_",
        "outputId": "f0047ee0-9167-47fc-ea3a-74cd3ff9452f"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "We have 4 persons in queue.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "`.empty()` would return `false` if there are items in the queue, otherwise."
      ],
      "metadata": {
        "id": "NffCoXSz9K6N"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "while not fifo.empty():\n",
        "  print(f'{fifo.get()} gone')"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "cd6tBv_DNC7r",
        "outputId": "fffb7688-d71d-4cc6-d324-122a70ca57b9"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Peter gone\n",
            "John gone\n",
            "Mary gone\n",
            "Amy gone\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Last in first out (LIFO) queue\n",
        "\n",
        "Basically LIFO is similar to a **stack**. The last item put on stack will be taken out first."
      ],
      "metadata": {
        "id": "MB4Bczpbyigh"
      }
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "qLHVl4G55O5h",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 321
        },
        "outputId": "ac677623-2228-40a6-e323-bc64191eef19"
      },
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<IPython.lib.display.IFrame at 0x7fbe99d77650>"
            ],
            "text/html": [
              "\n",
              "        <iframe\n",
              "            width=\"400\"\n",
              "            height=\"300\"\n",
              "            src=\"https://cslinux0.comp.hkbu.edu.hk/~kennycheng/lifo.html\"\n",
              "            frameborder=\"0\"\n",
              "            allowfullscreen\n",
              "        ></iframe>\n",
              "        "
            ]
          },
          "metadata": {},
          "execution_count": 6
        }
      ],
      "source": [
        "display.IFrame(src='https://cslinux0.comp.hkbu.edu.hk/~kennycheng/lifo.html', width=400, height=300)"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### LIFO queue in Python"
      ],
      "metadata": {
        "id": "Km04i33OMy9y"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from queue import LifoQueue\n",
        "\n",
        "lifo = LifoQueue()\n",
        "lifo.put('Peter')\n",
        "lifo.put('John')\n",
        "lifo.put('Mary')\n",
        "lifo.put('Amy')\n",
        "\n",
        "print(f'We have {lifo.qsize()} persons in queue.')"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "J248To6fM1nT",
        "outputId": "267f7a15-7081-47df-abff-57c17e4c5f73"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "We have 4 persons in queue.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "while not lifo.empty():\n",
        "  print(f'{lifo.get()} gone')"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "y6pPM8VDNlNP",
        "outputId": "25d4c1b5-a874-4aac-8a74-97bb3a682ddb"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Amy gone\n",
            "Mary gone\n",
            "John gone\n",
            "Peter gone\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Tree data structure\n",
        "\n",
        "We could construct a tree easily using `treelib` module. It support visualizing the tree in text format natively. However, it would need `graphviz` module for output the tree in image format."
      ],
      "metadata": {
        "id": "0M_qvpDSQTE6"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "!pip install treelib graphviz"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "XZ7I9SXBL4k2",
        "outputId": "9bdd8a72-01ee-4145-f307-07fb3cc443f5"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Looking in indexes: https://pypi.org/simple, https://us-python.pkg.dev/colab-wheels/public/simple/\n",
            "Collecting treelib\n",
            "  Downloading treelib-1.6.1.tar.gz (24 kB)\n",
            "Requirement already satisfied: graphviz in /usr/local/lib/python3.7/dist-packages (0.10.1)\n",
            "Requirement already satisfied: future in /usr/local/lib/python3.7/dist-packages (from treelib) (0.16.0)\n",
            "Building wheels for collected packages: treelib\n",
            "  Building wheel for treelib (setup.py) ... \u001b[?25l\u001b[?25hdone\n",
            "  Created wheel for treelib: filename=treelib-1.6.1-py3-none-any.whl size=18385 sha256=16e1f839fe0b31e33d46b6b58bba0e055ad05c6deadabd809e634bef15388b82\n",
            "  Stored in directory: /root/.cache/pip/wheels/89/be/94/2c6d949ce599d1443426d83ba4dc93cd35c0f4638260930a53\n",
            "Successfully built treelib\n",
            "Installing collected packages: treelib\n",
            "Successfully installed treelib-1.6.1\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Tree Basics\n",
        "\n",
        "Tree structure is an abstract hierarchical structure to represent hierarchical data. It consists of a **root node** with one or more child nodes. **Node** is the basic unit in a tree. For node in the depthest level, we call it **leaf node**.\n",
        "\n",
        "To construct a tree with `treelib`, we first import `Tree` and `Node` class from `treelib`.\n",
        "\n",
        "`Tree()` is for creating a treee and `.create_node(...)` is for creating a node."
      ],
      "metadata": {
        "id": "0VC-5BtybVfa"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Tree and Node\n",
        "\n",
        "Let's take a look to this 5 nodes tree as an example."
      ],
      "metadata": {
        "id": "5qyXYF-niAyB"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from treelib import Node, Tree\n",
        "tree = Tree()\n",
        "tree.create_node(\"Root Node\", 0) # 0 is the ID of node\n",
        "tree.create_node(\"Node 1\", 1, parent=0) # parent argument specify parent node of this node\n",
        "tree.create_node(\"Leaf Node 2\", 2, parent=0)\n",
        "tree.create_node(\"Leaf Node 3\", 3, parent=0)\n",
        "tree.create_node(\"Leaf Node 4\", 4, parent=1)\n",
        "tree.show() # print the tree in ascii format\n",
        "\n",
        "# output the tree in dot foramt for graphviz to render it as image\n",
        "tree.to_graphviz('tree.dot')\n",
        "\n",
        "from graphviz import Source\n",
        "Source.from_file('tree.dot')"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 676
        },
        "id": "1Q1_H78gQpA3",
        "outputId": "5701b2b9-c653-4b79-ed2f-46cf2382838f"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Root Node\n",
            "├── Leaf Node 2\n",
            "├── Leaf Node 3\n",
            "└── Node 1\n",
            "    └── Leaf Node 4\n",
            "\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<graphviz.files.Source at 0x7fbe9627be10>"
            ],
            "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.40.1 (20161225.0304)\n -->\n<!-- Title: tree Pages: 1 -->\n<svg width=\"372pt\" height=\"415pt\"\n viewBox=\"0.00 0.00 371.69 415.37\" 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 411.3702)\">\n<title>tree</title>\n<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-411.3702 367.6897,-411.3702 367.6897,4 -4,4\"/>\n<!-- 0 -->\n<g id=\"node1\" class=\"node\">\n<title>0</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"191.8449\" cy=\"-355.3749\" rx=\"51.9908\" ry=\"51.9908\"/>\n<text text-anchor=\"middle\" x=\"191.8449\" y=\"-351.6749\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">Root Node</text>\n</g>\n<!-- 2 -->\n<g id=\"node2\" class=\"node\">\n<title>2</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"57.8449\" cy=\"-209.5346\" rx=\"57.6901\" ry=\"57.6901\"/>\n<text text-anchor=\"middle\" x=\"57.8449\" y=\"-205.8346\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">Leaf Node 2</text>\n</g>\n<!-- 0&#45;&gt;2 -->\n<g id=\"edge2\" class=\"edge\">\n<title>0&#45;&gt;2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M156.6379,-317.057C140.6254,-299.6296 121.4588,-278.7694 104.2871,-260.0804\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"106.4081,-257.2158 97.0649,-252.2201 101.2535,-261.9519 106.4081,-257.2158\"/>\n</g>\n<!-- 3 -->\n<g id=\"node3\" class=\"node\">\n<title>3</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"191.8449\" cy=\"-209.5346\" rx=\"57.6901\" ry=\"57.6901\"/>\n<text text-anchor=\"middle\" x=\"191.8449\" y=\"-205.8346\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">Leaf Node 3</text>\n</g>\n<!-- 0&#45;&gt;3 -->\n<g id=\"edge3\" class=\"edge\">\n<title>0&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M191.8449,-303.1351C191.8449,-295.0001 191.8449,-286.4908 191.8449,-278.0601\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"195.345,-277.8459 191.8449,-267.8459 188.345,-277.8459 195.345,-277.8459\"/>\n</g>\n<!-- 1 -->\n<g id=\"node4\" class=\"node\">\n<title>1</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"305.8449\" cy=\"-209.5346\" rx=\"38.1938\" ry=\"38.1938\"/>\n<text text-anchor=\"middle\" x=\"305.8449\" y=\"-205.8346\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">Node 1</text>\n</g>\n<!-- 0&#45;&gt;1 -->\n<g id=\"edge1\" class=\"edge\">\n<title>0&#45;&gt;1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M223.9036,-314.3621C240.1104,-293.6287 259.6681,-268.6085 275.6113,-248.2124\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"278.5761,-250.1028 281.9771,-240.0686 273.061,-245.7918 278.5761,-250.1028\"/>\n</g>\n<!-- 4 -->\n<g id=\"node5\" class=\"node\">\n<title>4</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"305.8449\" cy=\"-57.8449\" rx=\"57.6901\" ry=\"57.6901\"/>\n<text text-anchor=\"middle\" x=\"305.8449\" y=\"-54.1449\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">Leaf Node 4</text>\n</g>\n<!-- 1&#45;&gt;4 -->\n<g id=\"edge4\" class=\"edge\">\n<title>1&#45;&gt;4</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M305.8449,-170.8644C305.8449,-157.1835 305.8449,-141.3587 305.8449,-125.963\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"309.345,-125.9346 305.8449,-115.9346 302.345,-125.9347 309.345,-125.9346\"/>\n</g>\n</g>\n</svg>\n"
          },
          "metadata": {},
          "execution_count": 10
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Root node\n",
        "\n",
        "`.root` would return the ID of root node"
      ],
      "metadata": {
        "id": "MtmZLLixiyjj"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "tree.root"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "SMzhO726i1yP",
        "outputId": "59d4cd11-557f-4fc9-9cfc-0b4a408c75c0"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "0"
            ]
          },
          "metadata": {},
          "execution_count": 11
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "tree.get_node(0).is_root()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "DEiAdH0ekC-_",
        "outputId": "cac113e4-d1a1-4d49-c740-9b0abff27afa"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "True"
            ]
          },
          "metadata": {},
          "execution_count": 12
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Leaf node\n",
        "\n",
        "`.leaves()` lists leaf nodes in the tree."
      ],
      "metadata": {
        "id": "9WqBqnZVkG9S"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "tree.leaves()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "wPj__STukZa5",
        "outputId": "5a2694ce-17e6-41e0-bcdb-d77d5e893753"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[Node(tag=Leaf Node 2, identifier=2, data=None),\n",
              " Node(tag=Leaf Node 3, identifier=3, data=None),\n",
              " Node(tag=Leaf Node 4, identifier=4, data=None)]"
            ]
          },
          "metadata": {},
          "execution_count": 13
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "`is_leaf()` of a **node** checks whether it is a leaf node in the tree."
      ],
      "metadata": {
        "id": "SnqXvtOrkjEa"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "tree.get_node(4).is_leaf()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "yADtLiIXkJYp",
        "outputId": "15125215-6951-4cb3-aeff-de6b8d39e650"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "True"
            ]
          },
          "metadata": {},
          "execution_count": 14
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "tree.get_node(1).is_leaf()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "NzmUEDMakPSI",
        "outputId": "112d8869-62e7-4933-f9b8-f76de4708c24"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "False"
            ]
          },
          "metadata": {},
          "execution_count": 15
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Size of a tree\n",
        "\n",
        "Size of a tree tells how many nodes in the tree."
      ],
      "metadata": {
        "id": "0e9yJyBzh3aA"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "tree.size()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "mr0E2IW9h4D-",
        "outputId": "94af6d85-8e52-4a6e-dbd3-66357c664c10"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "5"
            ]
          },
          "metadata": {},
          "execution_count": 16
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Depth of a tree\n",
        "\n",
        "Depth of a tree tells how many levels in the tree. (without root level)\n"
      ],
      "metadata": {
        "id": "RmkgSAbqiOBM"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "tree.depth()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "x9fvaFAqiQE8",
        "outputId": "be392385-d840-41a7-efa0-5dea26a6db84"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "2"
            ]
          },
          "metadata": {},
          "execution_count": 17
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "We could use `.subtree(id)` to obtain a sub tree."
      ],
      "metadata": {
        "id": "D3Zqkfikhc1P"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "tree.subtree(1).show()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "I9G0HyuWhVn5",
        "outputId": "c82aaceb-2dcd-42a6-8fb6-15051c1f43d7"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Node 1\n",
            "└── Leaf Node 4\n",
            "\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Level of a node"
      ],
      "metadata": {
        "id": "hCLCqTjShVFU"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "tree.level(4)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "pw7VLbIN6TFU",
        "outputId": "294b3ad4-c45f-4cb3-a1fc-276e8b989a6d"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "2"
            ]
          },
          "metadata": {},
          "execution_count": 19
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Traveling"
      ],
      "metadata": {
        "id": "_xcqsgkJVOCD"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### children"
      ],
      "metadata": {
        "id": "6zA2Qo17jQ2F"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "tree.children(tree.root)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "FapgUY-cdX01",
        "outputId": "b9808315-bf43-40db-ac0c-79ac51e8d150"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[Node(tag=Node 1, identifier=1, data=None),\n",
              " Node(tag=Leaf Node 2, identifier=2, data=None),\n",
              " Node(tag=Leaf Node 3, identifier=3, data=None)]"
            ]
          },
          "metadata": {},
          "execution_count": 20
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### parent"
      ],
      "metadata": {
        "id": "KMBMiAf94WYp"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "tree.parent(4)"
      ],
      "metadata": {
        "id": "j2cGJP9Z4YUt",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "4c68aab5-bfae-47f2-a2ae-87a760c38ac5"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "Node(tag=Node 1, identifier=1, data=None)"
            ]
          },
          "metadata": {},
          "execution_count": 21
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### siblings"
      ],
      "metadata": {
        "id": "uzzM7N11jk01"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "tree.siblings(1)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "049e8ae8-21a6-4ede-869a-91390992e35b",
        "id": "RXrL90Nljk05"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[Node(tag=Leaf Node 2, identifier=2, data=None),\n",
              " Node(tag=Leaf Node 3, identifier=3, data=None)]"
            ]
          },
          "metadata": {},
          "execution_count": 22
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "tree.siblings(2)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "F87xKWeFjuyb",
        "outputId": "a1658766-1d5e-4d0e-9cf9-75ed7e871166"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[Node(tag=Node 1, identifier=1, data=None),\n",
              " Node(tag=Leaf Node 3, identifier=3, data=None)]"
            ]
          },
          "metadata": {},
          "execution_count": 23
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Save data in Node\n",
        "\n",
        "The following code save a dictionary with key-value pair `\"isRoot\":True` in root node."
      ],
      "metadata": {
        "id": "CFPhJS9wjxS6"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "tree.get_node(0).data = {\"isRoot\":True}"
      ],
      "metadata": {
        "id": "w6UTeQAPjxmv"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Breadth-First Search (BFS)\n",
        "\n",
        "BFS search travels the tree by **going flat first**.\n",
        "\n",
        "Here is an example tree indicating the traveling sequence."
      ],
      "metadata": {
        "id": "ZYWbB7IU5_Vm"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from treelib import Node, Tree\n",
        "tree = Tree()\n",
        "tree.create_node(\"0\", 0)\n",
        "tree.create_node(\"1\", 1, parent=0)\n",
        "tree.create_node(\"2\", 2, parent=0)\n",
        "tree.create_node(\"3\", 3, parent=0)\n",
        "tree.create_node(\"4\", 4, parent=1)\n",
        "tree.create_node(\"5\", 5, parent=1)\n",
        "tree.create_node(\"6\", 6, parent=3)\n",
        "tree.create_node(\"7\", 7, parent=3)\n",
        "tree.create_node(\"8\", 8, parent=4)\n",
        "tree.create_node(\"9\", 9, parent=4)\n",
        "tree.create_node(\"10\", 10, parent=6)\n",
        "tree.create_node(\"11\", 11, parent=6)\n",
        "tree.show()\n",
        "tree.to_graphviz('bfs.dot')"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "qvUlg9RML9LI",
        "outputId": "83cb38b4-3f05-46bd-9f5c-0cb28c3d1ebc"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "0\n",
            "├── 1\n",
            "│   ├── 4\n",
            "│   │   ├── 8\n",
            "│   │   └── 9\n",
            "│   └── 5\n",
            "├── 2\n",
            "└── 3\n",
            "    ├── 6\n",
            "    │   ├── 10\n",
            "    │   └── 11\n",
            "    └── 7\n",
            "\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "from graphviz import Source\n",
        "Source.from_file('bfs.dot')"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 376
        },
        "id": "nGRKLSsbWQPR",
        "outputId": "218f7fff-696c-4564-980d-7a70ece8b6ea"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<graphviz.files.Source at 0x7fbe959c04d0>"
            ],
            "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.40.1 (20161225.0304)\n -->\n<!-- Title: tree Pages: 1 -->\n<svg width=\"253pt\" height=\"266pt\"\n viewBox=\"0.00 0.00 253.00 265.60\" 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 261.5963)\">\n<title>tree</title>\n<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-261.5963 249,-261.5963 249,4 -4,4\"/>\n<!-- 0 -->\n<g id=\"node1\" class=\"node\">\n<title>0</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"133\" cy=\"-239.5963\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"133\" y=\"-235.8963\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- 1 -->\n<g id=\"node2\" class=\"node\">\n<title>1</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"79\" cy=\"-167.5963\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"79\" y=\"-163.8963\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- 0&#45;&gt;1 -->\n<g id=\"edge1\" class=\"edge\">\n<title>0&#45;&gt;1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M122.0723,-225.026C114.6066,-215.0717 104.5632,-201.6805 96.0526,-190.3332\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"98.7115,-188.0449 89.9115,-182.1449 93.1115,-192.2449 98.7115,-188.0449\"/>\n</g>\n<!-- 2 -->\n<g id=\"node3\" class=\"node\">\n<title>2</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"133\" cy=\"-167.5963\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"133\" y=\"-163.8963\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n</g>\n<!-- 0&#45;&gt;2 -->\n<g id=\"edge2\" class=\"edge\">\n<title>0&#45;&gt;2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M133,-221.4277C133,-213.7273 133,-204.5707 133,-196.0129\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"136.5001,-196.0095 133,-186.0096 129.5001,-196.0096 136.5001,-196.0095\"/>\n</g>\n<!-- 3 -->\n<g id=\"node4\" class=\"node\">\n<title>3</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"187\" cy=\"-167.5963\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"187\" y=\"-163.8963\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">3</text>\n</g>\n<!-- 0&#45;&gt;3 -->\n<g id=\"edge3\" class=\"edge\">\n<title>0&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M143.9277,-225.026C151.3934,-215.0717 161.4368,-201.6805 169.9474,-190.3332\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"172.8885,-192.2449 176.0885,-182.1449 167.2885,-188.0449 172.8885,-192.2449\"/>\n</g>\n<!-- 4 -->\n<g id=\"node5\" class=\"node\">\n<title>4</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"52\" cy=\"-95.5963\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"52\" y=\"-91.8963\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">4</text>\n</g>\n<!-- 1&#45;&gt;4 -->\n<g id=\"edge4\" class=\"edge\">\n<title>1&#45;&gt;4</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M72.6014,-150.5333C69.407,-142.0149 65.471,-131.5191 61.8982,-121.9915\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"65.1411,-120.6712 58.3527,-112.5368 58.5868,-123.1291 65.1411,-120.6712\"/>\n</g>\n<!-- 5 -->\n<g id=\"node6\" class=\"node\">\n<title>5</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"106\" cy=\"-95.5963\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"106\" y=\"-91.8963\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">5</text>\n</g>\n<!-- 1&#45;&gt;5 -->\n<g id=\"edge5\" class=\"edge\">\n<title>1&#45;&gt;5</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M85.3986,-150.5333C88.593,-142.0149 92.529,-131.5191 96.1018,-121.9915\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"99.4132,-123.1291 99.6473,-112.5368 92.8589,-120.6712 99.4132,-123.1291\"/>\n</g>\n<!-- 6 -->\n<g id=\"node7\" class=\"node\">\n<title>6</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"173\" cy=\"-95.5963\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"173\" y=\"-91.8963\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">6</text>\n</g>\n<!-- 3&#45;&gt;6 -->\n<g id=\"edge6\" class=\"edge\">\n<title>3&#45;&gt;6</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M183.5393,-149.7986C181.9912,-141.8369 180.1297,-132.2634 178.4047,-123.392\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"181.8138,-122.5869 176.4694,-113.4389 174.9425,-123.9231 181.8138,-122.5869\"/>\n</g>\n<!-- 7 -->\n<g id=\"node8\" class=\"node\">\n<title>7</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"227\" cy=\"-95.5963\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"227\" y=\"-91.8963\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">7</text>\n</g>\n<!-- 3&#45;&gt;7 -->\n<g id=\"edge7\" class=\"edge\">\n<title>3&#45;&gt;7</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M195.8773,-151.6172C200.9524,-142.482 207.4285,-130.825 213.1577,-120.5125\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"216.3506,-121.9721 218.1475,-111.5308 210.2315,-118.5726 216.3506,-121.9721\"/>\n</g>\n<!-- 8 -->\n<g id=\"node9\" class=\"node\">\n<title>8</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"18\" cy=\"-20.7982\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"18\" y=\"-17.0982\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">8</text>\n</g>\n<!-- 4&#45;&gt;8 -->\n<g id=\"edge8\" class=\"edge\">\n<title>4&#45;&gt;8</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M44.4543,-78.9962C40.1405,-69.506 34.6358,-57.3959 29.766,-46.6827\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"32.8491,-45.0072 25.5246,-37.3519 26.4765,-47.9039 32.8491,-45.0072\"/>\n</g>\n<!-- 9 -->\n<g id=\"node10\" class=\"node\">\n<title>9</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"72\" cy=\"-20.7982\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"72\" y=\"-17.0982\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">9</text>\n</g>\n<!-- 4&#45;&gt;9 -->\n<g id=\"edge9\" class=\"edge\">\n<title>4&#45;&gt;9</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M56.7397,-77.8702C59.1059,-69.0208 62.0215,-58.117 64.668,-48.2192\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"68.0923,-48.9618 67.2943,-38.397 61.3299,-47.1535 68.0923,-48.9618\"/>\n</g>\n<!-- 10 -->\n<g id=\"node11\" class=\"node\">\n<title>10</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"154\" cy=\"-20.7982\" rx=\"20.5982\" ry=\"20.5982\"/>\n<text text-anchor=\"middle\" x=\"154\" y=\"-17.0982\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">10</text>\n</g>\n<!-- 6&#45;&gt;10 -->\n<g id=\"edge10\" class=\"edge\">\n<title>6&#45;&gt;10</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M168.4973,-77.8702C166.4561,-69.8348 163.9848,-60.1057 161.6651,-50.9738\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"164.996,-49.8701 159.1417,-41.0396 158.2115,-51.5935 164.996,-49.8701\"/>\n</g>\n<!-- 11 -->\n<g id=\"node12\" class=\"node\">\n<title>11</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"213\" cy=\"-20.7982\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"213\" y=\"-17.0982\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">11</text>\n</g>\n<!-- 6&#45;&gt;11 -->\n<g id=\"edge11\" class=\"edge\">\n<title>6&#45;&gt;11</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M181.6794,-79.3662C186.6554,-70.0613 193.0254,-58.1497 198.72,-47.5011\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"201.869,-49.0346 203.4984,-38.5658 195.6962,-45.7335 201.869,-49.0346\"/>\n</g>\n</g>\n</svg>\n"
          },
          "metadata": {},
          "execution_count": 26
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## BFS implementation using FIFO"
      ],
      "metadata": {
        "id": "PTxxCj2sJPWv"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "q = Queue()\n",
        "q.put(0) # put the root node ID in queue\n",
        "\n",
        "while not q.empty():           # keep looping when the queue is not empty\n",
        "  nodeId = q.get()             # get a nodeId from queue\n",
        "  for n in tree.children(nodeId): # looping through its childs\n",
        "    q.put(n.identifier)        # put each child into the queue\n",
        "  tree.get_node(nodeId).tag += \" (reached)\" # mark node tag with (reached)\n",
        "  tree.show()                     # print out current tree"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "qFjMXPHxJxZL",
        "outputId": "0c09bdf4-32db-4fcb-cab0-8c9b13b9812c"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "0 (reached)\n",
            "├── 1\n",
            "│   ├── 4\n",
            "│   │   ├── 8\n",
            "│   │   └── 9\n",
            "│   └── 5\n",
            "├── 2\n",
            "└── 3\n",
            "    ├── 6\n",
            "    │   ├── 10\n",
            "    │   └── 11\n",
            "    └── 7\n",
            "\n",
            "0 (reached)\n",
            "├── 1 (reached)\n",
            "│   ├── 4\n",
            "│   │   ├── 8\n",
            "│   │   └── 9\n",
            "│   └── 5\n",
            "├── 2\n",
            "└── 3\n",
            "    ├── 6\n",
            "    │   ├── 10\n",
            "    │   └── 11\n",
            "    └── 7\n",
            "\n",
            "0 (reached)\n",
            "├── 1 (reached)\n",
            "│   ├── 4\n",
            "│   │   ├── 8\n",
            "│   │   └── 9\n",
            "│   └── 5\n",
            "├── 2 (reached)\n",
            "└── 3\n",
            "    ├── 6\n",
            "    │   ├── 10\n",
            "    │   └── 11\n",
            "    └── 7\n",
            "\n",
            "0 (reached)\n",
            "├── 1 (reached)\n",
            "│   ├── 4\n",
            "│   │   ├── 8\n",
            "│   │   └── 9\n",
            "│   └── 5\n",
            "├── 2 (reached)\n",
            "└── 3 (reached)\n",
            "    ├── 6\n",
            "    │   ├── 10\n",
            "    │   └── 11\n",
            "    └── 7\n",
            "\n",
            "0 (reached)\n",
            "├── 1 (reached)\n",
            "│   ├── 4 (reached)\n",
            "│   │   ├── 8\n",
            "│   │   └── 9\n",
            "│   └── 5\n",
            "├── 2 (reached)\n",
            "└── 3 (reached)\n",
            "    ├── 6\n",
            "    │   ├── 10\n",
            "    │   └── 11\n",
            "    └── 7\n",
            "\n",
            "0 (reached)\n",
            "├── 1 (reached)\n",
            "│   ├── 4 (reached)\n",
            "│   │   ├── 8\n",
            "│   │   └── 9\n",
            "│   └── 5 (reached)\n",
            "├── 2 (reached)\n",
            "└── 3 (reached)\n",
            "    ├── 6\n",
            "    │   ├── 10\n",
            "    │   └── 11\n",
            "    └── 7\n",
            "\n",
            "0 (reached)\n",
            "├── 1 (reached)\n",
            "│   ├── 4 (reached)\n",
            "│   │   ├── 8\n",
            "│   │   └── 9\n",
            "│   └── 5 (reached)\n",
            "├── 2 (reached)\n",
            "└── 3 (reached)\n",
            "    ├── 6 (reached)\n",
            "    │   ├── 10\n",
            "    │   └── 11\n",
            "    └── 7\n",
            "\n",
            "0 (reached)\n",
            "├── 1 (reached)\n",
            "│   ├── 4 (reached)\n",
            "│   │   ├── 8\n",
            "│   │   └── 9\n",
            "│   └── 5 (reached)\n",
            "├── 2 (reached)\n",
            "└── 3 (reached)\n",
            "    ├── 6 (reached)\n",
            "    │   ├── 10\n",
            "    │   └── 11\n",
            "    └── 7 (reached)\n",
            "\n",
            "0 (reached)\n",
            "├── 1 (reached)\n",
            "│   ├── 4 (reached)\n",
            "│   │   ├── 8 (reached)\n",
            "│   │   └── 9\n",
            "│   └── 5 (reached)\n",
            "├── 2 (reached)\n",
            "└── 3 (reached)\n",
            "    ├── 6 (reached)\n",
            "    │   ├── 10\n",
            "    │   └── 11\n",
            "    └── 7 (reached)\n",
            "\n",
            "0 (reached)\n",
            "├── 1 (reached)\n",
            "│   ├── 4 (reached)\n",
            "│   │   ├── 8 (reached)\n",
            "│   │   └── 9 (reached)\n",
            "│   └── 5 (reached)\n",
            "├── 2 (reached)\n",
            "└── 3 (reached)\n",
            "    ├── 6 (reached)\n",
            "    │   ├── 10\n",
            "    │   └── 11\n",
            "    └── 7 (reached)\n",
            "\n",
            "0 (reached)\n",
            "├── 1 (reached)\n",
            "│   ├── 4 (reached)\n",
            "│   │   ├── 8 (reached)\n",
            "│   │   └── 9 (reached)\n",
            "│   └── 5 (reached)\n",
            "├── 2 (reached)\n",
            "└── 3 (reached)\n",
            "    ├── 6 (reached)\n",
            "    │   ├── 10 (reached)\n",
            "    │   └── 11\n",
            "    └── 7 (reached)\n",
            "\n",
            "0 (reached)\n",
            "├── 1 (reached)\n",
            "│   ├── 4 (reached)\n",
            "│   │   ├── 8 (reached)\n",
            "│   │   └── 9 (reached)\n",
            "│   └── 5 (reached)\n",
            "├── 2 (reached)\n",
            "└── 3 (reached)\n",
            "    ├── 6 (reached)\n",
            "    │   ├── 10 (reached)\n",
            "    │   └── 11 (reached)\n",
            "    └── 7 (reached)\n",
            "\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Depth First Search (DFS)\n",
        "\n",
        "DFS search travels the tree by **going deep first**.\n",
        "\n",
        "Here is an example tree indicating the traveling sequence."
      ],
      "metadata": {
        "id": "P2pJ-cym6A-g"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from treelib import Node, Tree\n",
        "tree = Tree()\n",
        "tree.create_node(\"0\", 0)\n",
        "tree.create_node(\"1\", 1, parent=0)\n",
        "tree.create_node(\"2\", 2, parent=1)\n",
        "tree.create_node(\"3\", 3, parent=2)\n",
        "tree.create_node(\"4\", 4, parent=2)\n",
        "tree.create_node(\"5\", 5, parent=1)\n",
        "tree.create_node(\"6\", 6, parent=0)\n",
        "tree.create_node(\"7\", 7, parent=0)\n",
        "tree.create_node(\"8\", 8, parent=7)\n",
        "tree.create_node(\"9\", 9, parent=8)\n",
        "tree.create_node(\"10\", 10, parent=8)\n",
        "tree.create_node(\"11\", 11, parent=7)\n",
        "tree.show()\n",
        "tree.to_graphviz('dfs.dot')"
      ],
      "metadata": {
        "id": "4nH4f96T6B7u",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "b67087be-4d96-4d41-a5f8-58277ea7b5bc"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "0\n",
            "├── 1\n",
            "│   ├── 2\n",
            "│   │   ├── 3\n",
            "│   │   └── 4\n",
            "│   └── 5\n",
            "├── 6\n",
            "└── 7\n",
            "    ├── 11\n",
            "    └── 8\n",
            "        ├── 10\n",
            "        └── 9\n",
            "\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "from graphviz import Source\n",
        "Source.from_file('dfs.dot')"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 381
        },
        "id": "HBctnGCzZ-PU",
        "outputId": "94deb47e-77ab-4ef6-d12b-a7c4dce66df8"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<graphviz.files.Source at 0x7fbe95c0e2d0>"
            ],
            "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.40.1 (20161225.0304)\n -->\n<!-- Title: tree Pages: 1 -->\n<svg width=\"240pt\" height=\"270pt\"\n viewBox=\"0.00 0.00 240.00 269.89\" 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 265.8927)\">\n<title>tree</title>\n<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-265.8927 236,-265.8927 236,4 -4,4\"/>\n<!-- 0 -->\n<g id=\"node1\" class=\"node\">\n<title>0</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"108\" cy=\"-243.8927\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"108\" y=\"-240.1927\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- 1 -->\n<g id=\"node2\" class=\"node\">\n<title>1</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"54\" cy=\"-171.8927\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"54\" y=\"-168.1927\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- 0&#45;&gt;1 -->\n<g id=\"edge1\" class=\"edge\">\n<title>0&#45;&gt;1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M97.0723,-229.3225C89.6066,-219.3682 79.5632,-205.977 71.0526,-194.6296\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"73.7115,-192.3413 64.9115,-186.4413 68.1115,-196.5414 73.7115,-192.3413\"/>\n</g>\n<!-- 6 -->\n<g id=\"node3\" class=\"node\">\n<title>6</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"108\" cy=\"-171.8927\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"108\" y=\"-168.1927\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">6</text>\n</g>\n<!-- 0&#45;&gt;6 -->\n<g id=\"edge2\" class=\"edge\">\n<title>0&#45;&gt;6</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M108,-225.7241C108,-218.0237 108,-208.8671 108,-200.3094\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"111.5001,-200.306 108,-190.306 104.5001,-200.306 111.5001,-200.306\"/>\n</g>\n<!-- 7 -->\n<g id=\"node4\" class=\"node\">\n<title>7</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"162\" cy=\"-171.8927\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"162\" y=\"-168.1927\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">7</text>\n</g>\n<!-- 0&#45;&gt;7 -->\n<g id=\"edge3\" class=\"edge\">\n<title>0&#45;&gt;7</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M118.9277,-229.3225C126.3934,-219.3682 136.4368,-205.977 144.9474,-194.6296\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"147.8885,-196.5414 151.0885,-186.4413 142.2885,-192.3413 147.8885,-196.5414\"/>\n</g>\n<!-- 2 -->\n<g id=\"node5\" class=\"node\">\n<title>2</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"19\" cy=\"-97.7445\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"19\" y=\"-94.0445\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n</g>\n<!-- 1&#45;&gt;2 -->\n<g id=\"edge4\" class=\"edge\">\n<title>1&#45;&gt;2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M46.2324,-155.4368C41.7917,-146.0291 36.125,-134.0243 31.112,-123.4041\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"34.1797,-121.7036 26.7459,-114.1544 27.8495,-124.6916 34.1797,-121.7036\"/>\n</g>\n<!-- 5 -->\n<g id=\"node6\" class=\"node\">\n<title>5</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"73\" cy=\"-97.7445\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"73\" y=\"-94.0445\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">5</text>\n</g>\n<!-- 1&#45;&gt;5 -->\n<g id=\"edge5\" class=\"edge\">\n<title>1&#45;&gt;5</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M58.5027,-154.3206C60.7506,-145.5481 63.5204,-134.7391 66.0346,-124.9273\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"69.4377,-125.7463 68.5296,-115.1905 62.6568,-124.0087 69.4377,-125.7463\"/>\n</g>\n<!-- 11 -->\n<g id=\"node7\" class=\"node\">\n<title>11</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"143\" cy=\"-97.7445\" rx=\"20.2975\" ry=\"20.2975\"/>\n<text text-anchor=\"middle\" x=\"143\" y=\"-94.0445\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">11</text>\n</g>\n<!-- 7&#45;&gt;11 -->\n<g id=\"edge7\" class=\"edge\">\n<title>7&#45;&gt;11</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M157.4973,-154.3206C155.4243,-146.2306 152.9074,-136.4087 150.5565,-127.2341\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"153.878,-126.0958 148.0052,-117.2776 147.0971,-127.8334 153.878,-126.0958\"/>\n</g>\n<!-- 8 -->\n<g id=\"node8\" class=\"node\">\n<title>8</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"199\" cy=\"-97.7445\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"199\" y=\"-94.0445\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">8</text>\n</g>\n<!-- 7&#45;&gt;8 -->\n<g id=\"edge6\" class=\"edge\">\n<title>7&#45;&gt;8</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M170.2115,-155.4368C174.9868,-145.8671 181.1031,-133.6101 186.469,-122.8567\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"189.6055,-124.4099 190.9388,-113.8993 183.342,-121.2844 189.6055,-124.4099\"/>\n</g>\n<!-- 3 -->\n<g id=\"node9\" class=\"node\">\n<title>3</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"18\" cy=\"-20.7982\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"18\" y=\"-17.0982\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">3</text>\n</g>\n<!-- 2&#45;&gt;3 -->\n<g id=\"edge8\" class=\"edge\">\n<title>2&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M18.763,-79.5093C18.6447,-70.4057 18.4989,-59.1888 18.3666,-49.0067\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"21.865,-48.8561 18.2353,-38.9025 14.8656,-48.9471 21.865,-48.8561\"/>\n</g>\n<!-- 4 -->\n<g id=\"node10\" class=\"node\">\n<title>4</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"72\" cy=\"-20.7982\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"72\" y=\"-17.0982\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">4</text>\n</g>\n<!-- 2&#45;&gt;4 -->\n<g id=\"edge9\" class=\"edge\">\n<title>2&#45;&gt;4</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M29.2189,-82.9085C36.7226,-72.0145 47.0697,-56.9924 55.7084,-44.4507\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"58.8415,-46.072 61.6316,-35.8512 53.0766,-42.1013 58.8415,-46.072\"/>\n</g>\n<!-- 10 -->\n<g id=\"node11\" class=\"node\">\n<title>10</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"157\" cy=\"-20.7982\" rx=\"20.5982\" ry=\"20.5982\"/>\n<text text-anchor=\"middle\" x=\"157\" y=\"-17.0982\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">10</text>\n</g>\n<!-- 8&#45;&gt;10 -->\n<g id=\"edge11\" class=\"edge\">\n<title>8&#45;&gt;10</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M190.2976,-81.8012C185.004,-72.1031 178.1008,-59.4561 171.9534,-48.1936\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"174.8825,-46.2545 167.0192,-39.1539 168.7382,-49.6083 174.8825,-46.2545\"/>\n</g>\n<!-- 9 -->\n<g id=\"node12\" class=\"node\">\n<title>9</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"214\" cy=\"-20.7982\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"214\" y=\"-17.0982\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">9</text>\n</g>\n<!-- 8&#45;&gt;9 -->\n<g id=\"edge10\" class=\"edge\">\n<title>8&#45;&gt;9</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M202.479,-79.8981C204.2965,-70.5749 206.5612,-58.9574 208.6006,-48.496\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"212.0617,-49.0328 210.5399,-38.5478 205.1911,-47.6933 212.0617,-49.0328\"/>\n</g>\n</g>\n</svg>\n"
          },
          "metadata": {},
          "execution_count": 29
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## DFS implementation using LIFO"
      ],
      "metadata": {
        "id": "i_KEKapwYCZc"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "q = LifoQueue()\n",
        "q.put(0) # put the root node ID in queue\n",
        "\n",
        "while not q.empty():           # keep looping when the queue is not empty\n",
        "  nodeId = q.get()             # get a nodeId from queue\n",
        "  for n in tree.children(nodeId): # looping through its childs\n",
        "    q.put(n.identifier)        # put each child into the queue\n",
        "  tree.get_node(nodeId).tag += \" (reached)\" # mark node tag with (reached)\n",
        "  tree.show()                     # print out current tree"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "IgNK-nVkYC0l",
        "outputId": "e570b5f3-cf8e-4dd8-e822-9d87910db467"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "0 (reached)\n",
            "├── 1\n",
            "│   ├── 2\n",
            "│   │   ├── 3\n",
            "│   │   └── 4\n",
            "│   └── 5\n",
            "├── 6\n",
            "└── 7\n",
            "    ├── 11\n",
            "    └── 8\n",
            "        ├── 10\n",
            "        └── 9\n",
            "\n",
            "0 (reached)\n",
            "├── 1\n",
            "│   ├── 2\n",
            "│   │   ├── 3\n",
            "│   │   └── 4\n",
            "│   └── 5\n",
            "├── 6\n",
            "└── 7 (reached)\n",
            "    ├── 11\n",
            "    └── 8\n",
            "        ├── 10\n",
            "        └── 9\n",
            "\n",
            "0 (reached)\n",
            "├── 1\n",
            "│   ├── 2\n",
            "│   │   ├── 3\n",
            "│   │   └── 4\n",
            "│   └── 5\n",
            "├── 6\n",
            "└── 7 (reached)\n",
            "    ├── 11 (reached)\n",
            "    └── 8\n",
            "        ├── 10\n",
            "        └── 9\n",
            "\n",
            "0 (reached)\n",
            "├── 1\n",
            "│   ├── 2\n",
            "│   │   ├── 3\n",
            "│   │   └── 4\n",
            "│   └── 5\n",
            "├── 6\n",
            "└── 7 (reached)\n",
            "    ├── 11 (reached)\n",
            "    └── 8 (reached)\n",
            "        ├── 10\n",
            "        └── 9\n",
            "\n",
            "0 (reached)\n",
            "├── 1\n",
            "│   ├── 2\n",
            "│   │   ├── 3\n",
            "│   │   └── 4\n",
            "│   └── 5\n",
            "├── 6\n",
            "└── 7 (reached)\n",
            "    ├── 11 (reached)\n",
            "    └── 8 (reached)\n",
            "        ├── 10 (reached)\n",
            "        └── 9\n",
            "\n",
            "0 (reached)\n",
            "├── 1\n",
            "│   ├── 2\n",
            "│   │   ├── 3\n",
            "│   │   └── 4\n",
            "│   └── 5\n",
            "├── 6\n",
            "└── 7 (reached)\n",
            "    ├── 11 (reached)\n",
            "    └── 8 (reached)\n",
            "        ├── 10 (reached)\n",
            "        └── 9 (reached)\n",
            "\n",
            "0 (reached)\n",
            "├── 1\n",
            "│   ├── 2\n",
            "│   │   ├── 3\n",
            "│   │   └── 4\n",
            "│   └── 5\n",
            "├── 6 (reached)\n",
            "└── 7 (reached)\n",
            "    ├── 11 (reached)\n",
            "    └── 8 (reached)\n",
            "        ├── 10 (reached)\n",
            "        └── 9 (reached)\n",
            "\n",
            "0 (reached)\n",
            "├── 1 (reached)\n",
            "│   ├── 2\n",
            "│   │   ├── 3\n",
            "│   │   └── 4\n",
            "│   └── 5\n",
            "├── 6 (reached)\n",
            "└── 7 (reached)\n",
            "    ├── 11 (reached)\n",
            "    └── 8 (reached)\n",
            "        ├── 10 (reached)\n",
            "        └── 9 (reached)\n",
            "\n",
            "0 (reached)\n",
            "├── 1 (reached)\n",
            "│   ├── 2\n",
            "│   │   ├── 3\n",
            "│   │   └── 4\n",
            "│   └── 5 (reached)\n",
            "├── 6 (reached)\n",
            "└── 7 (reached)\n",
            "    ├── 11 (reached)\n",
            "    └── 8 (reached)\n",
            "        ├── 10 (reached)\n",
            "        └── 9 (reached)\n",
            "\n",
            "0 (reached)\n",
            "├── 1 (reached)\n",
            "│   ├── 2 (reached)\n",
            "│   │   ├── 3\n",
            "│   │   └── 4\n",
            "│   └── 5 (reached)\n",
            "├── 6 (reached)\n",
            "└── 7 (reached)\n",
            "    ├── 11 (reached)\n",
            "    └── 8 (reached)\n",
            "        ├── 10 (reached)\n",
            "        └── 9 (reached)\n",
            "\n",
            "0 (reached)\n",
            "├── 1 (reached)\n",
            "│   ├── 2 (reached)\n",
            "│   │   ├── 3\n",
            "│   │   └── 4 (reached)\n",
            "│   └── 5 (reached)\n",
            "├── 6 (reached)\n",
            "└── 7 (reached)\n",
            "    ├── 11 (reached)\n",
            "    └── 8 (reached)\n",
            "        ├── 10 (reached)\n",
            "        └── 9 (reached)\n",
            "\n",
            "0 (reached)\n",
            "├── 1 (reached)\n",
            "│   ├── 2 (reached)\n",
            "│   │   ├── 3 (reached)\n",
            "│   │   └── 4 (reached)\n",
            "│   └── 5 (reached)\n",
            "├── 6 (reached)\n",
            "└── 7 (reached)\n",
            "    ├── 11 (reached)\n",
            "    └── 8 (reached)\n",
            "        ├── 10 (reached)\n",
            "        └── 9 (reached)\n",
            "\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Case study 1: 8-puzzle\n",
        "\n",
        "Given a `3 x 3` board with 8 tiles numbered from 1 to 8 arrange in random order.\n",
        "\n",
        "|   |   |   |\n",
        "|---|---|---|\n",
        "| 7 | 5 | 2 |\n",
        "| 4 |   | 6 |\n",
        "| 8 | 3 | 1 |\n",
        "\n",
        "You will need to rearrange the number in sequence like the following. In each move, you are allowed to swap position with surrounding number.\n",
        "\n",
        "|   |   |   |\n",
        "|---|---|---|\n",
        "| 1 | 2 | 3 |\n",
        "| 4 | 5 | 6 |\n",
        "| 7 | 8 |   |\n",
        "\n"
      ],
      "metadata": {
        "id": "O4UJkVCF6DJZ"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Program the game"
      ],
      "metadata": {
        "id": "wMq07lBzDxiS"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Initialize a game board\n",
        "\n",
        "Let's define a function for initializing a new game board in 3x3."
      ],
      "metadata": {
        "id": "MEkpeb2BZQzF"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "import numpy as np\n",
        "import random\n",
        "\n",
        "def newGameBoard():\n",
        "  board = [str(i) for i in range(1,9)] # create a string list with number 1 to 8\n",
        "  random.shuffle(board)\n",
        "  board.insert(4, '') # insert an empty string at the middle of list\n",
        "   # shuffle the list\n",
        "  return np.reshape(board, (3,3)) # reshape the list to 3x3 2d-array"
      ],
      "metadata": {
        "id": "VbbTkaVN6Efq"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "To use the function, simply invoke it without any argument. It would return a 2D-array with shape `(3, 3)`."
      ],
      "metadata": {
        "id": "QQSIdG3627k8"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "gameBoard = np.array([['1', '2', '3'],\n",
        "             ['4', '5', '6'],\n",
        "['7','','8']])"
      ],
      "metadata": {
        "id": "MmpjVUoovlVP"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "gameBoard = newGameBoard()\n",
        "print(gameBoard)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "zdGsmAiCZvWB",
        "outputId": "02e05fdf-fa26-4944-9077-f20793fb4f99"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[['3' '8' '5']\n",
            " ['2' '' '6']\n",
            " ['4' '7' '1']]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Access the numbers\n",
        "\n",
        "We could access an item with `numpy.ndarray` syntax `gameBoard[y, x]`. It would return the corresponding item in the coordinate. For the coordinate system in `gameBoard`, `[0, 0]` locates the top left item and `[2, 2]` locates the bottom right item."
      ],
      "metadata": {
        "id": "yKl9C2RzaWOW"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "print(gameBoard[0, 0])\n",
        "print(gameBoard[0, 1])\n",
        "print(gameBoard[1, 0])\n",
        "print(gameBoard[1, 1])"
      ],
      "metadata": {
        "id": "vG8E0WN2aZBA",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "bfee1def-de9a-492d-e7a8-2d65f90e4723"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "3\n",
            "8\n",
            "2\n",
            "\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Finding an item in the game board with value\n",
        "\n",
        "Let's define another helper function for getting the coordinate of a particular value.\n"
      ],
      "metadata": {
        "id": "jV17tGX5jcSg"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def getCoord(board, value):\n",
        "  return tuple(np.reshape(np.where(board == value), 2))\n",
        "\n",
        "coord = getCoord(gameBoard, '')\n",
        "print(coord)\n",
        "print(gameBoard[coord])\n",
        "\n",
        "y, x = coord\n",
        "print(y, x)\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "CcZgzKymkDSy",
        "outputId": "fe9e4961-8e8a-4a20-a4f8-761e9282f0f6"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "(1, 1)\n",
            "\n",
            "1 1\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### List possible moves\n",
        "\n",
        "Let's define a function to list possible moves for a particular item.\n",
        "\n"
      ],
      "metadata": {
        "id": "szwkXe1sq0P7"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def listMoves(board):\n",
        "  y, x = getCoord(board, '')\n",
        "  moves = [tuple([y, x] + np.array([-1,0])), # top\n",
        "           tuple([y, x] + np.array([0,1])), # right\n",
        "           tuple([y, x] + np.array([1,0])), # bottom\n",
        "           tuple([y, x] + np.array([0,-1]))] # left\n",
        "  return [(y, x) for y, x in moves if y >= 0 and y < gameBoard.shape[0] and x >= 0 and x < gameBoard.shape[1]]"
      ],
      "metadata": {
        "id": "KwNSkANEq0Yj"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "currentMoves = listMoves(gameBoard)\n",
        "print(currentMoves)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "KMtm-t-fDeOb",
        "outputId": "92a190d2-189d-43fc-92cb-28a08cef7eda"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[(0, 1), (1, 2), (2, 1), (1, 0)]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Swap position"
      ],
      "metadata": {
        "id": "7fPY79Zc-O9C"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def moveTo(board, target):\n",
        "  coord = getCoord(board, '')\n",
        "  board[target], board[coord] = board[coord], board[target]\n",
        "  return board"
      ],
      "metadata": {
        "id": "k0hcilvT-S1h"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "print(gameBoard)\n",
        "\n",
        "moveTo(gameBoard, currentMoves[0])\n",
        "\n",
        "print(gameBoard)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "JZ9326e-qzMp",
        "outputId": "0668a76c-732f-4122-bdbe-6fb43ab2968a"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[['3' '8' '5']\n",
            " ['2' '' '6']\n",
            " ['4' '7' '1']]\n",
            "[['3' '' '5']\n",
            " ['2' '8' '6']\n",
            " ['4' '7' '1']]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Solve the game with BFS"
      ],
      "metadata": {
        "id": "fwtnBoXvD8xM"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Initialization"
      ],
      "metadata": {
        "id": "c0aPqeLaytgl"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "game = newGameBoard() # create a new game\n",
        "tree = Tree() # create a tree\n",
        "\n",
        "fifo = Queue() # create a FIFO queue\n",
        "# put the root node in queue\n",
        "fifo.put(tree.create_node(f\"{game}\", identifier=f\"{game}\", data=game))\n",
        "\n",
        "# define the goal state in string format\n",
        "goalId = f\"{np.array([['1','2','3'],['4','5','6'],['7','8','']])}\"\n",
        "\n",
        "tree.show()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "tKEnH5Reg8Lk",
        "outputId": "cb87d28a-5b2f-4029-f994-8a1b648bdc15"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[['5' '4' '8']\n",
            " ['3' '' '2']\n",
            " ['6' '7' '1']]\n",
            "\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Define goal checking function"
      ],
      "metadata": {
        "id": "rgSzLDnCym2v"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def goalCheck():\n",
        "  while tree.get_node(goalId) == None:\n",
        "    yield"
      ],
      "metadata": {
        "id": "1xXlcf9PnXy3"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Game loop"
      ],
      "metadata": {
        "id": "JvlLoITFy1nn"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from tqdm import tqdm\n",
        "\n",
        "for _ in tqdm(goalCheck(), position=0, leave=True):\n",
        "  if fifo.empty():\n",
        "    break\n",
        "  node = fifo.get()\n",
        "  for move in listMoves(node.data):\n",
        "    board = moveTo(np.copy(node.data), move) # make a copy of the tree for each node\n",
        "    try: # skipping node already in tree, it would throw a duplicated node execption\n",
        "      fifo.put(tree.create_node(f\"{move}\", identifier=f\"{board}\", parent=node.identifier, data=board))\n",
        "    except:\n",
        "      pass"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "wHcUpbpCpFTs",
        "outputId": "9e87f316-784a-4a75-9c96-2406b1d60b21"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stderr",
          "text": [
            "181440it [00:57, 3132.89it/s]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Result checking"
      ],
      "metadata": {
        "id": "uvYDH87i9-Nh"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "print(tree.size())\n",
        "print(len(tree.leaves()))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "t2jLV_S1HkvV",
        "outputId": "8adefed0-b365-4ae0-aa36-14cde3571ecd"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "181440\n",
            "53771\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "if tree.get_node(goalId) == None:\n",
        "  print(\"No solution\")\n",
        "else:\n",
        "  print(\"Solved\")\n",
        "\n",
        "  # print out steps reversed from goal to root\n",
        "  for node in tree.rsearch(goalId): \n",
        "    print(node)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "3sGyHBp7HSmn",
        "outputId": "9ba60a59-c9db-45cf-e0af-2b10a87f5059"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "No solution\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Solve the game with DFS"
      ],
      "metadata": {
        "id": "0qMFqn59-VQ8"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Initialization\n",
        "\n",
        "We only need to re-initialize the tree and queue"
      ],
      "metadata": {
        "id": "UQORGs11-jKj"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "tree = Tree() # create a tree\n",
        "\n",
        "lifo = LifoQueue() # create a FIFO queue\n",
        "# put the root node in queue\n",
        "lifo.put(tree.create_node(f\"{game}\", identifier=f\"{game}\", data=game))\n",
        "\n",
        "tree.show()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "WFi9w7kL-YHK",
        "outputId": "e34f8c7b-3d8a-43e4-8f0e-f630c1abe075"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[['5' '4' '8']\n",
            " ['3' '' '2']\n",
            " ['6' '7' '1']]\n",
            "\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Game loop"
      ],
      "metadata": {
        "id": "Mt9gpv2i_Ddi"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "for _ in tqdm(goalCheck(), position=0, leave=True):\n",
        "  if lifo.empty():\n",
        "    break\n",
        "  node = lifo.get()\n",
        "  for move in listMoves(node.data):\n",
        "    board = moveTo(np.copy(node.data), move) # make a copy of the tree for each node\n",
        "    try: # skipping node already in tree, it would throw a duplicated node execption\n",
        "      lifo.put(tree.create_node(f\"{move}\", identifier=f\"{board}\", parent=node.identifier, data=board))\n",
        "    except:\n",
        "      pass"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "YQWYVFcq_JBk",
        "outputId": "f9007396-c857-4ac2-87f1-e30db53f6760"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stderr",
          "text": [
            "181440it [00:58, 3087.58it/s]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Result checking"
      ],
      "metadata": {
        "id": "6bQLyy54_jIW"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "print(tree.size())\n",
        "print(len(tree.leaves()))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "ec4e5744-a842-4b5d-ff4b-60ce84d573c3",
        "id": "93iP3HR6_jIY"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "181440\n",
            "63146\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "if tree.get_node(goalId) == None:\n",
        "  print(\"No solution\")\n",
        "else:\n",
        "  print(\"Solved\")\n",
        "\n",
        "  # print out steps reversed from goal to root\n",
        "  for node in tree.rsearch(goalId): \n",
        "    print(node)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "CW_2hb2RHzUS",
        "outputId": "9b8810b2-4b9b-463d-fb44-0334ebdfe935"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "No solution\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Case study 2: pathfinding\n",
        "\n",
        "Let's take a look to another case study of applying BFS in path finding. This time we will use an path finding module intead of using our own implementation."
      ],
      "metadata": {
        "id": "Fz_RL6LP6K42"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Let's install [pathfinding](https://github.com/brean/python-pathfinding.git) module and import it."
      ],
      "metadata": {
        "id": "SRjvsmrMOTCu"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "!pip install pathfinding"
      ],
      "metadata": {
        "id": "yku_OUSj6MPm",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "18897677-1b3a-4cdb-9b30-e00c33e0f7ab"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Looking in indexes: https://pypi.org/simple, https://us-python.pkg.dev/colab-wheels/public/simple/\n",
            "Collecting pathfinding\n",
            "  Downloading pathfinding-1.0.1-py3-none-any.whl (19 kB)\n",
            "Installing collected packages: pathfinding\n",
            "Successfully installed pathfinding-1.0.1\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## BFS path finder"
      ],
      "metadata": {
        "id": "RXxWNVttfvDy"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from pathfinding.core.diagonal_movement import DiagonalMovement\n",
        "from pathfinding.core.grid import Grid\n",
        "from pathfinding.finder.breadth_first import BreadthFirstFinder"
      ],
      "metadata": {
        "id": "Uiu8sKAkOqgg"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Map initialization\n",
        "\n",
        "Let's create a 2d-array as map with `Grid`. In this map, `0` indicates an obstacle and `1` is free space allow for travel."
      ],
      "metadata": {
        "id": "LJqBWxVoPBWk"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "grid = Grid(matrix=[\n",
        "  [1, 1, 1],\n",
        "  [1, 0, 1],\n",
        "  [1, 1, 1]\n",
        "])"
      ],
      "metadata": {
        "id": "HiKd8TDAPQE_"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "We are going to travel from the top left to the bottom right point. Let's get the points with `.node` of `grid`."
      ],
      "metadata": {
        "id": "KYx47N2KcR2F"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "start = grid.node(0, 0)\n",
        "end = grid.node(2, 2)"
      ],
      "metadata": {
        "id": "WWOjIi8dcNoj"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Specify finder algorithm\n",
        "\n",
        "We then specify the finder by initializing an instance and then find the path by invoking `.find_path` function with starting point, ending point and the grid."
      ],
      "metadata": {
        "id": "QsJMWQeXcvC1"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "finder = BreadthFirstFinder(diagonal_movement=DiagonalMovement.always)\n",
        "path, runs = finder.find_path(start, end, grid)"
      ],
      "metadata": {
        "id": "4JWmpBCgdFTa"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Check the result\n",
        "\n",
        "After running the algorithm, we could display the path in ascii format by passing in the path, starting point and ending point to `.grid_str` function.\n",
        "\n",
        "- `s` indicates starting point\n",
        "- `e` indicates ending point\n",
        "- `x` indicates the path\n",
        "- `#` indicates obstacle"
      ],
      "metadata": {
        "id": "sgGLR5CwdSWO"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "print('operations:', runs, 'path length:', len(path))\n",
        "print(grid.grid_str(path=path, start=start, end=end))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "CKj6r889dUaL",
        "outputId": "5582b4e6-6485-401e-f203-668668db6001"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "operations: 8 path length: 4\n",
            "+---+\n",
            "|sx |\n",
            "| #x|\n",
            "|  e|\n",
            "+---+\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Detail implemenating of BFS finder\n",
        "\n",
        "Let's take a look to the [BFS implementation](https://github.com/brean/python-pathfinding/blob/main/pathfinding/finder/breadth_first.py) in `pathfinding` library. The main logic of BFS is happened in the `check_neighbors` function.\n",
        "\n",
        "```python\n",
        "  def check_neighbors(self, start, end, grid, open_list):\n",
        "        node = open_list.pop(0) # takes out first item in open_list as node\n",
        "        node.closed = True\n",
        "\n",
        "        if node == end:\n",
        "            return backtrace(end)\n",
        "\n",
        "        neighbors = self.find_neighbors(grid, node)\n",
        "        for neighbor in neighbors: # loop the neighbors of node\n",
        "            if neighbor.closed or neighbor.opened:\n",
        "                continue\n",
        "\n",
        "            open_list.append(neighbor) # append each neighbor to open_list\n",
        "            neighbor.opened = True\n",
        "            neighbor.parent = node\n",
        "```\n",
        "\n",
        "`open_list` is the queue implemented using a simple list. At the beginning of function, it takes out the first item in `open_list` with `.pop(0)`. Then find out its neighbors and add each neighbor into the `open_list` queue."
      ],
      "metadata": {
        "id": "OLmw44eVf68V"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Make a new DFS finder for `pathfinding` library\n",
        "\n",
        "After read through the code of BFS finder in `pathfinding`, we would know how to implement a DFS finder by modifying the code. The main modification is changing the FIFO queue to LIFO queue.\n",
        "\n",
        "\n",
        "Here is an example."
      ],
      "metadata": {
        "id": "CP7D5atKE4oa"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from pathfinding.finder.finder import Finder, TIME_LIMIT, MAX_RUNS\n",
        "from pathfinding.core.util import backtrace\n",
        "from pathfinding.core.diagonal_movement import DiagonalMovement\n",
        "\n",
        "class DepthFirstFinder(Finder):\n",
        "    def __init__(self, heuristic=None, weight=1,\n",
        "                 diagonal_movement=DiagonalMovement.never,\n",
        "                 time_limit=TIME_LIMIT,\n",
        "                 max_runs=MAX_RUNS):\n",
        "        super(DepthFirstFinder, self).__init__(\n",
        "            heuristic=heuristic,\n",
        "            weight=weight,\n",
        "            weighted=False,\n",
        "            diagonal_movement=diagonal_movement,\n",
        "            time_limit=time_limit,\n",
        "            max_runs=max_runs)\n",
        "        if not diagonal_movement:\n",
        "            self.diagonalMovement = DiagonalMovement.never\n",
        "\n",
        "    def check_neighbors(self, start, end, grid, open_list):\n",
        "        node = open_list.pop(-1) # get the last item from list\n",
        "\n",
        "        if node == end:\n",
        "            return backtrace(end)\n",
        "\n",
        "        neighbors = [neighbor for neighbor in self.find_neighbors(grid, node) if not neighbor.closed]\n",
        "        if len(neighbors) > 0:\n",
        "          open_list.append(node)\n",
        "          open_list.append(neighbors[0])\n",
        "          neighbors[0].opened = True\n",
        "          neighbors[0].parent = node\n",
        "        \n",
        "        node.closed = True"
      ],
      "metadata": {
        "id": "ej5dHRmvgIwn"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Reinitialize the map"
      ],
      "metadata": {
        "id": "3ipJjx3VzI09"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "grid = Grid(matrix=[\n",
        "  [1, 1, 1],\n",
        "  [1, 0, 1],\n",
        "  [1, 1, 1]\n",
        "])\n",
        "\n",
        "start = grid.node(0, 0)\n",
        "end = grid.node(2, 2)"
      ],
      "metadata": {
        "id": "ENmaDAgrxbOg"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Try out our DepthFirstFinder"
      ],
      "metadata": {
        "id": "ATxg6Ox-lMdP"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "finder = DepthFirstFinder(diagonal_movement=DiagonalMovement.always)\n",
        "path, runs = finder.find_path(start, end, grid)"
      ],
      "metadata": {
        "id": "K2F__TwLlUOO"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Check the result"
      ],
      "metadata": {
        "id": "ft2TTaF_lfa4"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "print('operations:', runs, 'path length:', len(path))\n",
        "print(grid.grid_str(path=path, start=start, end=end))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "9Qk_BRQYlhaC",
        "outputId": "6b0402f9-6cab-4e22-e207-5a5a0f10b180"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "operations: 5 path length: 5\n",
            "+---+\n",
            "|sxx|\n",
            "| #x|\n",
            "|  e|\n",
            "+---+\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "aC7bwiYgH78J"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}