Last active
January 20, 2023 07:13
-
-
Save sanchezcarlosjr/74f5ad860dd51ddf8b5f137b0d93aa26 to your computer and use it in GitHub Desktop.
Graph Algorithms.ipynb
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| { | |
| "nbformat": 4, | |
| "nbformat_minor": 0, | |
| "metadata": { | |
| "colab": { | |
| "name": "Graph Algorithms.ipynb", | |
| "provenance": [], | |
| "collapsed_sections": [ | |
| "QO_2XP9jJHXS" | |
| ], | |
| "authorship_tag": "ABX9TyOGDTFiYvz7ETessSClXIVm", | |
| "include_colab_link": true | |
| }, | |
| "kernelspec": { | |
| "name": "python3", | |
| "display_name": "Python 3" | |
| }, | |
| "language_info": { | |
| "name": "python" | |
| } | |
| }, | |
| "cells": [ | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "view-in-github", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "<a href=\"https://colab.research.google.com/gist/sanchezcarlosjr/74f5ad860dd51ddf8b5f137b0d93aa26/introduction-to-algorithms-graph.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "# 3 Algoritmos para Grafos\n", | |
| "## UABC\n", | |
| "\n", | |
| "### Ilustración\n", | |
| "Por [Carlos Eduardo Sanchez Torres](https://twitter.com/CharllierJr)\n", | |
| "\n", | |
| "[Análisis de algoritmos](https://sanchezcarlosjr.notion.site/An-lisis-de-Algoritmos-38fac5ca34e740719b43673db9f8b9188)" | |
| ], | |
| "metadata": { | |
| "id": "eQDLIDnFiRDU" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "! pip install treelib" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "qWb2JzCnGr8p", | |
| "outputId": "796cd925-ee92-4db6-b3ff-9fc356da6db4" | |
| }, | |
| "execution_count": 3, | |
| "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", | |
| " Preparing metadata (setup.py) ... \u001b[?25l\u001b[?25hdone\n", | |
| "Requirement already satisfied: future in /usr/local/lib/python3.8/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=afda2a1ad18ce49822272d72b905525475cdc913e93e4cf30eb52d0a5a3a8424\n", | |
| " Stored in directory: /root/.cache/pip/wheels/71/df/8b/6b005e3bb9b275c24dfc392cda334f43f132e85a6f17cfad3a\n", | |
| "Successfully built treelib\n", | |
| "Installing collected packages: treelib\n", | |
| "Successfully installed treelib-1.6.1\n" | |
| ] | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "! pip install networkx[default]" | |
| ], | |
| "metadata": { | |
| "id": "riXKItQgvOM7", | |
| "outputId": "fcb2dd4b-a2e1-46f7-b657-064b138f192a", | |
| "colab": { | |
| "base_uri": "https://localhost:8080/", | |
| "height": 764 | |
| } | |
| }, | |
| "execution_count": 2, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "name": "stdout", | |
| "text": [ | |
| "Looking in indexes: https://pypi.org/simple, https://us-python.pkg.dev/colab-wheels/public/simple/\n", | |
| "Requirement already satisfied: networkx[default] in /usr/local/lib/python3.8/dist-packages (3.0)\n", | |
| "Collecting matplotlib>=3.4\n", | |
| " Downloading matplotlib-3.6.3-cp38-cp38-manylinux_2_12_x86_64.manylinux2010_x86_64.whl (9.4 MB)\n", | |
| "\u001b[2K \u001b[90m━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\u001b[0m \u001b[32m9.4/9.4 MB\u001b[0m \u001b[31m50.0 MB/s\u001b[0m eta \u001b[36m0:00:00\u001b[0m\n", | |
| "\u001b[?25hRequirement already satisfied: numpy>=1.20 in /usr/local/lib/python3.8/dist-packages (from networkx[default]) (1.21.6)\n", | |
| "Collecting scipy>=1.8\n", | |
| " Downloading scipy-1.10.0-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (34.5 MB)\n", | |
| "\u001b[2K \u001b[90m━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\u001b[0m \u001b[32m34.5/34.5 MB\u001b[0m \u001b[31m28.6 MB/s\u001b[0m eta \u001b[36m0:00:00\u001b[0m\n", | |
| "\u001b[?25hRequirement already satisfied: pandas>=1.3 in /usr/local/lib/python3.8/dist-packages (from networkx[default]) (1.3.5)\n", | |
| "Requirement already satisfied: pyparsing>=2.2.1 in /usr/local/lib/python3.8/dist-packages (from matplotlib>=3.4->networkx[default]) (3.0.9)\n", | |
| "Collecting fonttools>=4.22.0\n", | |
| " Downloading fonttools-4.38.0-py3-none-any.whl (965 kB)\n", | |
| "\u001b[2K \u001b[90m━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\u001b[0m \u001b[32m965.4/965.4 KB\u001b[0m \u001b[31m27.7 MB/s\u001b[0m eta \u001b[36m0:00:00\u001b[0m\n", | |
| "\u001b[?25hRequirement already satisfied: packaging>=20.0 in /usr/local/lib/python3.8/dist-packages (from matplotlib>=3.4->networkx[default]) (21.3)\n", | |
| "Requirement already satisfied: pillow>=6.2.0 in /usr/local/lib/python3.8/dist-packages (from matplotlib>=3.4->networkx[default]) (7.1.2)\n", | |
| "Collecting contourpy>=1.0.1\n", | |
| " Downloading contourpy-1.0.7-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (300 kB)\n", | |
| "\u001b[2K \u001b[90m━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\u001b[0m \u001b[32m300.0/300.0 KB\u001b[0m \u001b[31m16.1 MB/s\u001b[0m eta \u001b[36m0:00:00\u001b[0m\n", | |
| "\u001b[?25hRequirement already satisfied: python-dateutil>=2.7 in /usr/local/lib/python3.8/dist-packages (from matplotlib>=3.4->networkx[default]) (2.8.2)\n", | |
| "Requirement already satisfied: kiwisolver>=1.0.1 in /usr/local/lib/python3.8/dist-packages (from matplotlib>=3.4->networkx[default]) (1.4.4)\n", | |
| "Requirement already satisfied: cycler>=0.10 in /usr/local/lib/python3.8/dist-packages (from matplotlib>=3.4->networkx[default]) (0.11.0)\n", | |
| "Requirement already satisfied: pytz>=2017.3 in /usr/local/lib/python3.8/dist-packages (from pandas>=1.3->networkx[default]) (2022.7)\n", | |
| "Requirement already satisfied: six>=1.5 in /usr/local/lib/python3.8/dist-packages (from python-dateutil>=2.7->matplotlib>=3.4->networkx[default]) (1.15.0)\n", | |
| "Installing collected packages: scipy, fonttools, contourpy, matplotlib\n", | |
| " Attempting uninstall: scipy\n", | |
| " Found existing installation: scipy 1.7.3\n", | |
| " Uninstalling scipy-1.7.3:\n", | |
| " Successfully uninstalled scipy-1.7.3\n", | |
| " Attempting uninstall: matplotlib\n", | |
| " Found existing installation: matplotlib 3.1.3\n", | |
| " Uninstalling matplotlib-3.1.3:\n", | |
| " Successfully uninstalled matplotlib-3.1.3\n", | |
| "Successfully installed contourpy-1.0.7 fonttools-4.38.0 matplotlib-3.6.3 scipy-1.10.0\n" | |
| ] | |
| }, | |
| { | |
| "output_type": "display_data", | |
| "data": { | |
| "application/vnd.colab-display-data+json": { | |
| "pip_warning": { | |
| "packages": [ | |
| "matplotlib", | |
| "mpl_toolkits" | |
| ] | |
| } | |
| } | |
| }, | |
| "metadata": {} | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "# Representación lista de adyacencia (lista ligada)" | |
| ], | |
| "metadata": { | |
| "id": "EmhVCvR5k34B" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "import uuid\n", | |
| "\n", | |
| "class Node:\n", | |
| " def __init__(self, id=None, value=None, children=[]):\n", | |
| " self.id = str(uuid.uuid4()) if id == None else id\n", | |
| " self.value = self.id if value == None else value\n", | |
| " self.children = children\n", | |
| " def __repr__(self):\n", | |
| " if isinstance(self.value, list) and len(self.value) == 1:\n", | |
| " return str(self.value[0])\n", | |
| " return str(self.value)\n", | |
| " def __str__(self):\n", | |
| " return str(self.value)\n", | |
| " def __len__(self):\n", | |
| " return len(self.children)\n", | |
| " def __eq__(self, another):\n", | |
| " return another != None and self.id == another.id\n", | |
| " def __hash__(self):\n", | |
| " return hash(self.id)\n", | |
| " def traverse_reverse_order(self):\n", | |
| " pass\n", | |
| " # Recursive BFS\n", | |
| " def traverse_level_order(self, root=True):\n", | |
| " if root == True:\n", | |
| " yield self\n", | |
| " for child in self.children:\n", | |
| " yield child\n", | |
| " for child in self.children:\n", | |
| " yield from child.traverse_level_order(False)\n", | |
| " def traverse_inorder(self):\n", | |
| " for child in self.children[0:len(self.children)//2]:\n", | |
| " yield from child.traverse_inorder()\n", | |
| " yield self\n", | |
| " for child in self.children[len(self.children)//2:len(self.children)]:\n", | |
| " yield from child.traverse_inorder()\n", | |
| " def __add__(self, node):\n", | |
| " return Node(value=self.value.__add__(node.value))\n", | |
| " # Backtracking, DFS, Euler tour\n", | |
| " def traverse_preorder(self):\n", | |
| " yield self\n", | |
| " for child in self.children:\n", | |
| " yield from child.traverse_preorder()\n", | |
| " # It's bottom-up approach.\n", | |
| " def traverse_postorder(self):\n", | |
| " for child in self.children:\n", | |
| " yield from child.traverse_postorder()\n", | |
| " yield self\n", | |
| " def append(self, node):\n", | |
| " if not isinstance(node, Node):\n", | |
| " return\n", | |
| " self.children.append(node)\n", | |
| " def invert(self):\n", | |
| " self.children = self.children[::-1]\n", | |
| " for child in self.children:\n", | |
| " child.invert()" | |
| ], | |
| "metadata": { | |
| "id": "pY6EVCajk3Q-" | |
| }, | |
| "execution_count": 2, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "from treelib import Tree\n", | |
| "def to_tree_lib(tree, node, parent=None):\n", | |
| " uuid = tree.create_node(node.__repr__(), parent=parent)\n", | |
| " for child in node.children:\n", | |
| " to_tree_lib(tree, child, uuid)\n", | |
| " return tree" | |
| ], | |
| "metadata": { | |
| "id": "cUkwhgQ4Gul3" | |
| }, | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "# Tree\n", | |
| "b = Node(value=5, children=[])\n", | |
| "a = Node(value=4, children=[])\n", | |
| "b.append(a)\n", | |
| "b.append(Node(value=0, children=[]))\n", | |
| "a.append(Node(value=2, children=[]))\n", | |
| "a.children[0].append(Node(value=1, children=[]))\n", | |
| "a.children[0].append(Node(value=3, children=[]))\n", | |
| "a.append(Node(value=7, children=[]))\n", | |
| "a.children[1].append(Node(value=6, children=[]))\n", | |
| "a.children[1].append(Node(value=9, children=[]))" | |
| ], | |
| "metadata": { | |
| "id": "fKwQt182lASJ" | |
| }, | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "b.children" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "VKruEA86xn6C", | |
| "outputId": "e5de691f-1542-4784-f4ce-c68a2473ddd2" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "[4, 0]" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "execution_count": 7 | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "to_tree_lib(Tree(), b).show()" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "pXrjbCMyJ7M0", | |
| "outputId": "d60f6d80-1253-4615-f67b-ff8a46f1bbec" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "name": "stdout", | |
| "text": [ | |
| "5\n", | |
| "├── 0\n", | |
| "└── 4\n", | |
| " ├── 2\n", | |
| " │ ├── 1\n", | |
| " │ └── 3\n", | |
| " └── 7\n", | |
| " ├── 6\n", | |
| " └── 9\n", | |
| "\n" | |
| ] | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "[node.value for node in a.traverse_level_order()]" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "m0Y9X-A_JMyd", | |
| "outputId": "da10bafa-107f-418d-b7ab-b469fcb53f39" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "[4, 2, 7, 1, 3, 6, 9]" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "execution_count": 9 | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "[node.value for node in a.traverse_preorder()]" | |
| ], | |
| "metadata": { | |
| "id": "Qn4CWrdHlDfs", | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "outputId": "9e68e16c-240f-414f-ebfa-a41d6d4cbd39" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "[4, 2, 1, 3, 7, 6, 9]" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "execution_count": 10 | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "preorder=[node.value for node in a.traverse_preorder()]\n", | |
| "preorder.reverse()\n", | |
| "preorder # Topological sort" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "jYiq3wh2CwjF", | |
| "outputId": "594204f2-e48a-4e84-e6f4-55bd5cc2f568" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "[9, 6, 7, 3, 1, 2, 4]" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "execution_count": 96 | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "[node.value for node in a.traverse_postorder()] # Another Topological sort" | |
| ], | |
| "metadata": { | |
| "id": "Dw6kPNZ8lErL", | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "outputId": "cad0dc50-40a3-45e4-d574-fa807ba74f01" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "[1, 3, 2, 6, 9, 7, 4]" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "execution_count": 97 | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "[node.value for node in a.traverse_inorder()]" | |
| ], | |
| "metadata": { | |
| "id": "cx7oncmElHbH", | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "outputId": "5ff93bfd-db47-494b-b340-45992f686f3f" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "[1, 2, 3, 4, 6, 7, 9]" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "execution_count": 12 | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "# Representación lista de adyacencia (hash map)." | |
| ], | |
| "metadata": { | |
| "id": "F2mUIITkj-jN" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "import sys\n", | |
| "def my_hash(x):\n", | |
| " hash = 0\n", | |
| " for symbol in x:\n", | |
| " hash = ((hash<<5)-hash)+ord(symbol)\n", | |
| " hash = hash & hash\n", | |
| " return hash\n", | |
| "\n", | |
| "class ImmutableKeyNode(Node):\n", | |
| " def __eq__(self, other):\n", | |
| " return isinstance(other, Node) and self.__hash__() == other.__hash__()\n", | |
| " def __hash__(self):\n", | |
| " MAX = sys.maxsize\n", | |
| " MASK = 2 * MAX + 1\n", | |
| " n = len(self)\n", | |
| " h = 1927868237 * (n + 1)\n", | |
| " h &= MASK\n", | |
| " for x in self.id:\n", | |
| " hx = my_hash(x)\n", | |
| " h ^= (hx ^ (hx << 16) ^ 89869747) * 3644798167\n", | |
| " h &= MASK\n", | |
| " h = h * 69069 + 907133923\n", | |
| " h &= MASK\n", | |
| " if h > MAX:\n", | |
| " h -= MASK + 1\n", | |
| " if h == -1:\n", | |
| " h = 590923713\n", | |
| " return h" | |
| ], | |
| "metadata": { | |
| "id": "H-0PqqdZjNv0" | |
| }, | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "{\"abc\", \"cba\", \"bca\"}" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "dxcZhqFljuwU", | |
| "outputId": "a8550189-ce1d-4367-d919-8f2010127402" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "{'abc', 'bca', 'cba'}" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "execution_count": 14 | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "{ImmutableKeyNode(id=\"abc\"), ImmutableKeyNode(id=\"cba\"), ImmutableKeyNode(id=\"bca\")}" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "aFdJrDI9js9B", | |
| "outputId": "6b130892-a30c-4c20-f3bb-103a0940e2e3" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "{abc}" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "execution_count": 15 | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "{Node(\"abc\"), Node(\"cba\"), Node(\"bca\")}" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "Po7hy835jxkp", | |
| "outputId": "d8e7b498-7787-4c01-9744-ce018f856afd" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "{abc, bca, cba}" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "execution_count": 16 | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "graph={\n", | |
| " Node(\"u\"): {Node(\"v\"), Node(\"x\")},\n", | |
| " Node(\"v\"): {Node(\"y\")},\n", | |
| " Node(\"w\"): {Node(\"y\"), Node(\"z\")},\n", | |
| " Node(\"x\"): {Node(\"v\")},\n", | |
| " Node(\"y\"): {Node(\"x\")},\n", | |
| " Node(\"z\"): {Node(\"z\")},\n", | |
| " Node(\"u\"): {Node(\"u\")}\n", | |
| "}\n", | |
| "graph[Node(\"u\")]" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "jUknXAFzK24c", | |
| "outputId": "de95a4fa-83f8-4d1b-f9d1-4870bc8274f6" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "{u}" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "execution_count": 17 | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "class Graph:\n", | |
| " def __init__(self, graph):\n", | |
| " self.graph = graph\n", | |
| " vertices = {vertex: vertex for vertex in self.graph}\n", | |
| " for vertex in vertices:\n", | |
| " for neighbor in self.graph[vertex]:\n", | |
| " self.graph[vertex].remove(neighbor)\n", | |
| " self.graph[vertex].add(vertices[neighbor])\n", | |
| " def setEdge(self, pivot, v):\n", | |
| " v.predecessor = pivot\n", | |
| " def isAGoal(self, v):\n", | |
| " return False\n", | |
| " def finish(self, v):\n", | |
| " pass\n", | |
| " def topological_sort(self):\n", | |
| " dfs = DepthFirstSearcher(self)\n", | |
| " dfs.explore()\n", | |
| " return dfs.topological_sort # topological sort is the inverse of dfs\n", | |
| " def explore(self):\n", | |
| " dfs = DepthFirstSearcher(self)\n", | |
| " return dfs.explore()\n", | |
| " def __repr__(self):\n", | |
| " return self.graph.__repr__()\n", | |
| " def __getitem__(self, i):\n", | |
| " return self.graph[i]\n", | |
| " def __contains__(self, node):\n", | |
| " return node in self.graph\n", | |
| " def len_vertices(self):\n", | |
| " return len(self.graph)\n", | |
| " def exploreNeighbor(self, vertex):\n", | |
| " if len(self.graph[vertex]) == 0:\n", | |
| " return None\n", | |
| " return self.graph[vertex].pop()\n", | |
| " def vertices(self):\n", | |
| " return self.graph\n", | |
| " \n", | |
| "g = Graph({\n", | |
| " Node(\"u\"): {Node(\"v\"), Node(\"x\")},\n", | |
| " Node(\"v\"): {Node(\"y\")},\n", | |
| " Node(\"w\"): {Node(\"y\"), Node(\"z\")},\n", | |
| " Node(\"x\"): {Node(\"v\")},\n", | |
| " Node(\"y\"): {Node(\"x\")},\n", | |
| " Node(\"z\"): {Node(\"z\")},\n", | |
| "})\n", | |
| "g.exploreNeighbor(Node(\"u\"))" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "7x4ES9DMjt5F", | |
| "outputId": "5a55a497-40a5-432d-f485-3e3964a5bccc" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "x" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "execution_count": 81 | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "class DepthFirstSearcher:\n", | |
| " def __init__(self, graph, branch_and_bound=True):\n", | |
| " self.graph = graph\n", | |
| " self.records = set()\n", | |
| " self.branch_and_bound = branch_and_bound\n", | |
| " self.topological_sort = [None]*graph.len_vertices()\n", | |
| " self.topological_sort_stack_index = graph.len_vertices()-1 \n", | |
| "\n", | |
| " def register_topological_sort(self, value):\n", | |
| " self.topological_sort[self.topological_sort_stack_index] = value\n", | |
| " self.topological_sort_stack_index -= 1\n", | |
| " def explore(self):\n", | |
| " found = False\n", | |
| " for vertex in self.graph.vertices():\n", | |
| " if vertex not in self.records:\n", | |
| " found, v = self.visit(vertex)\n", | |
| " if found:\n", | |
| " return found, v\n", | |
| " return False, None\n", | |
| " def visit(self, vertex):\n", | |
| " stack = []\n", | |
| " v = vertex\n", | |
| " while True:\n", | |
| " pivot = v\n", | |
| " while v != None:\n", | |
| " while v != None and v not in self.records:\n", | |
| " stack.append(v)\n", | |
| " self.records.add(v)\n", | |
| " if len(stack) >= 2:\n", | |
| " self.graph.setEdge(stack[-2], stack[-1])\n", | |
| " if self.graph.isAGoal(v):\n", | |
| " return True, v\n", | |
| " pivot = v\n", | |
| " v = self.graph.exploreNeighbor(v)\n", | |
| " v = self.graph.exploreNeighbor(pivot)\n", | |
| " self.register_topological_sort(stack.pop())\n", | |
| " self.graph.finish(v)\n", | |
| " if len(stack) == 0:\n", | |
| " return False, None\n", | |
| " v=self.graph.exploreNeighbor(stack[-1])" | |
| ], | |
| "metadata": { | |
| "id": "MrM7nQisdUmG" | |
| }, | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "g=Graph({\n", | |
| " Node(\"0\"): {Node(\"2\")},\n", | |
| " Node(\"2\"): {Node(\"6\")},\n", | |
| " Node(\"1\"): {Node(\"6\")},\n", | |
| " Node(\"6\"): {Node(\"7\")},\n", | |
| " Node(\"3\"): {Node(\"7\")},\n", | |
| " Node(\"4\"): {Node(\"6\"), Node(\"7\")},\n", | |
| " Node(\"5\"): {Node(\"7\")},\n", | |
| " Node(\"7\"): set()\n", | |
| "})\n", | |
| "g.topological_sort()" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "DClQw5XF8N7t", | |
| "outputId": "8aa0da5f-645c-4f51-adcc-8587a5bbd7f9" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "[5, 4, 3, 1, 0, 2, 6, 7]" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "execution_count": 89 | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "g=Graph({\n", | |
| " Node(\"m\"): set(),\n", | |
| " Node(\"u\"): {Node(\"m\"), Node(\"v\"), Node(\"x\")},\n", | |
| " Node(\"v\"): {Node(\"y\"), Node(\"A\")},\n", | |
| " Node(\"w\"): {Node(\"y\"), Node(\"z\")},\n", | |
| " Node(\"x\"): {Node(\"v\")},\n", | |
| " Node(\"y\"): {Node(\"x\"), Node(\"B\")},\n", | |
| " Node(\"z\"): {Node(\"z\")},\n", | |
| " Node(\"A\"): set(),\n", | |
| " Node(\"B\"): set(),\n", | |
| "})" | |
| ], | |
| "metadata": { | |
| "id": "cQFZvdgbdZpA" | |
| }, | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "# Networkx" | |
| ], | |
| "metadata": { | |
| "id": "OyQEz5Uy24fs" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "import networkx as nx" | |
| ], | |
| "metadata": { | |
| "id": "MFaxXay84LcE" | |
| }, | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "G = nx.Graph()\n", | |
| "G.add_edge('A', 'B')\n", | |
| "G.add_edge('B', 'C')\n", | |
| "G.adj" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "gS8OLvIb23-c", | |
| "outputId": "b15c77a5-05ad-4ddc-f276-4c02fba2e1c9" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "AdjacencyView({'A': {'B': {}}, 'B': {'A': {}, 'C': {}}, 'C': {'B': {}}})" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "execution_count": 25 | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "nx.draw(G)" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/", | |
| "height": 319 | |
| }, | |
| "id": "vWNcabv-3lPk", | |
| "outputId": "387a1f7c-bd40-49c4-b044-1a56219bb38d" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "display_data", | |
| "data": { | |
| "text/plain": [ | |
| "<Figure size 432x288 with 1 Axes>" | |
| ], | |
| "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAEuCAYAAADx63eqAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjYuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8o6BhiAAAACXBIWXMAAAsTAAALEwEAmpwYAAAN70lEQVR4nO3dz2vV+X7H8fdJTq7HyxiEqfcqOGDvhJp7Fw5oy1haGO2it7hWGKjtuBpKuvAPcKML4f4Dzma4OFAXVULpLOqipajQHy5qBgdGo0grNUXvRMEbwzUhMd8unGjU5CQ55/s95/v9fh6Ppcn58tnIi2fOOd9vI8uyLAAgEQP9PgAA9JLhAyAphg+ApBg+AJJi+ABIiuEDICmGD4CkGD4AkmL4AEiK4QMgKYYPgKQYPgCSYvgASIrhAyAphg+ApBg+AJJi+ABIiuEDICmGD4CkGD4AkmL4AEiK4QMgKc1+HwCA6nk8Ox/jN6Zi8tFMzMwtxnCrGaM7h+PYgd3x/ntb+n28thpZlmX9PgQA1XDzwdM4d/VeXLs7HRER84tLr37Wag5EFhGH9u6IsU9G4qMPtvfnkOswfABsyIXr9+Ps5cmYW3wR7Zaj0YhoNQfj1JHROH5wT8/Ot1H+1AnAul6O3u14vrC07u9mWcTzhRdx9vLtiIjSjZ8PtwDQ1s0HT+Ps5ckNjd5KzxeW4uzlyfh26mkxB+uQ4QOgrXNX78Xc4ouOXju3+CK+uHov5xN1x/ABsKbHs/Nx7e502/f02smyiCt3puPJ7Hy+B+uC4QNgTeM3prq+RiMixie6v05eDB8Aa5p8NPPGVxY6Mbe4FJMPn+V0ou4ZPgDWNDO3mNN1FnK5Th4MHwBrGm7l86234dZQLtfJg+EDYE2jO4djS7O7qWg1B2J017acTtQ9wwfAmo4e2B3d3uAri4ij+3fnc6AcGD4AVpVlWfzrP/1jPP/v/4pOv8/QaEQc3rujVDeuNnwAvOP777+PY8eOxZkzZ+JXf/1nsfVHnb3X12oOxtihkZxP1x3DB8ArWZbFxYsXY9++fTEyMhITExPxl3/xp3HqyGhsHdrcZGwdGohTR0Zj3+7txRy2Q25SDUBEvKy8sbGxuHXrVnz99dfx8ccfv/rZ8o2m6/B0BsUHkLjVKm/l6C07fnBPXPz8YPzyFz+NLc2BaL31ac9WcyC2NAfil7/4aVz8/GApRy/C8/gAkray8s6fP7/q4K3myex8jE9MxeTDZzEztxDDraEY3bUtju73BHYASijLsrh06VKcPHkyTpw4EadPn45Wq9XvY/WE9/gAEtPuvbwUeI8PIBEbfS+v7hQfQAJSr7yVFB9Ajam8dyk+gJpSeatTfAA1o/LaU3wANaLy1qf4AGpA5W2c4gOoOJW3OYoPoKJUXmcUH0AFqbzOKT6AClF53VN8ABWh8vKh+ABKTuXlS/EBlJjKy5/iAyghlVccxQdQMiqvWIoPoCRUXm8oPoASUHm9o/gA+kjl9Z7iA+gTldcfig+gx1Refyk+gB5Sef2n+AB6QOWVh+IDKJjKKxfFB1AQlVdOig+gACqvvBQfQI5UXvkpPoCcqLxqUHwAXVJ51aL4ALqg8qpH8QF0QOVVl+ID2CSVV22KD2CDVF49KD6ADVB59aH4ANpQefWj+ADWoPLqSfEBvEXl1ZviA1hB5dWf4gMIlZcSxQckT+WlRfEByVJ5aVJ8QJJUXroUH5AUlYfiA5Kh8ohQfEACVB4rKT6g1lQeb1N8QC2pPNai+IDaWa687777TuXxDsUH1MbKyvvwww/jm2++MXq8Q/EBtaDy2CjFB1SaymOzFB9QWSqPTig+oHJUHt1QfEClqDy6pfiASlB55EXxAaWn8siT4gNKS+VRBMUHlJLKoyiKDygVlUfRFB9QGiqPXlB8QN+pPHpJ8QF9pfLoNcUH9IXKo18UH9BzKo9+UnxAz6g8ykDxAT2h8igLxQcUSuVRNooPKIzKo4wUH5A7lUeZKT4gVyqPslN8QC5UHlWh+ICuqTyqRPEBHVN5VJHiAzqi8qgqxQdsisqj6hQfsGEqjzpQfMC6VB51oviAtlQedaP4gFWpPOpK8QHvUHnUmeIDXlF5pEDxARGh8kiH4oPEqTxSo/ggYSqPFCk+SJDKI2WKDxKj8kid4oNEqDx4SfFBAlQevKb4oMZUHrxL8UFNqTxYneKDmlF50J7igxpRebA+xQc1oPJg4xQfVJzKg81RfFBRKg86o/igglQedE7xQYWoPOie4oOKUHmQD8MHPfR4dj7Gb0zF5KOZmJlbjOFWM0Z3DsexA7vj/fe2rPqaLMvi0qVLcfLkyfjss8/iwoUL0Wq1enxyqI9GlmVZvw8BdXfzwdM4d/VeXLs7HRER84tLr37Wag5EFhGH9u6IsU9G4qMPtr/62crK++qrr1Qe5MB7fFCwC9fvx6dfXo9/uf2bmF9cemP0IiLmfvi3f771m/j0y+tx4fp97+VBgRQfFOjC9ftx9vLteL6wtP4v/6DVHIif/N+/xfR//oPKgwIYPijIzQdP49Mvr8fzhRebfu1g9iL+/vOD8Uc/+0kBJ4O0+VMnFOTc1Xsxt7j50YuIWBoYjF//x//mfCIgwvBBIR7Pzse1u9PR6d9Tsiziyp3peDI7n+/BAMMHRRi/MdX1NRoRMT7R/XWANxk+KMDko5l3Pr25WXOLSzH58FlOJwKWGT4owMzcYk7XWcjlOsBrhg8KMNzK56ZIw62hXK4DvGb4oACjO4djS7O7/16t5kCM7tqW04mAZYYPCnD0wO6ur5FFxNH93V8HeJPhgwIs/e63sfXp/0QsdfYBl0Yj4vDeHWveuBronOGDHK28x+Yf/vhJtLZ09l5fqzkYY4dGcj4dEOGxRJCb1Z6X18m9OrcODcSpI6Oxb/f24g4LCVN80KV2T1I4fnBPnDry89g6NBiNRvvrNBoRW4cG49SRn8fxg3uKPzgkyk2qoQsbfV7et1NP44ur9+LKneloxMsvpy9bfh7f4b07YuzQiNKDghk+6MDbT0U/c+bMhp6K/mR2PsYnpmLy4bOYmVuI4dZQjO7aFkf3r/0EdiBfhg82yVPRodq8xwcb5KnoUA8+1QkbsNonNoFqUnzQhsqD+lF8sAaVB/Wk+OAtKg/qTfHBCioP6k/xQag8SIniI3kqD9Ki+EiWyoM0KT6SpPIgXYqPpKg8QPGRDJUHRCg+EqDygJUUH7Wm8oC3KT5qSeUBa1F81I7KA9pRfNSGygM2QvFRCyoP2CjFR6WpPGCzFB+VpfKATig+KkflAd1QfFSKygO6pfioBJUH5EXxUXoqD8iT4qO0VB5QBMVHKak8oCiKj1JReUDRFB+lofKAXlB89J3KA3pJ8dFXKg/oNcVHX6g8oF8UHz2n8oB+Unz0jMoDykDx0RMqDygLxUehVB5QNoqPwqg8oIwUH7lTeUCZKT5ypfKAslN85ELlAVWh+OiaygOqRPHRMZUHVJHioyMqD6gqxcemqDyg6hQfG6bygDpQfKxL5QF1ovhoS+UBdaP4WJXKA+pK8fEOlQfUmeLjlZWVNzIyovKAWlJ8RMTryrt165bKA2pN8SXu7cqbmJgwekCtKb6EqTwgRYovQSoPSJniS4zKA1Kn+BKh8gBeUnwJUHkArym+GlN5AO9SfDWl8gBWp/hqRuUBtKf4akTlAaxP8dWAygPYOMVXcSoPYHMUX0WpPIDOKL4KUnkAnVN8FaLyALqn+CpC5QHkQ/GVnMoDyJfiKzGVB5A/xVdCKg+gOIqvZFQeQLEUX0moPIDeUHwloPIAekfx9ZHKA+g9xdcnKg+gPxRfj6k8gP5SfD2k8gD6T/H1gMoDKA/FVzCVB1Auiq8gKg+gnBRfAVQeQHkpvhypPIDyU3w5UXkA1aD4uqTyAKpF8XVB5QFUj+LrgMoDqC7Ft0kqD6DaFN8GqTyAelB8G6DyAOpD8bWh8gDqR/GtQeUB1JPie4vKA6g3xbeCygOoP8UXKg8gJckXn8oDSEuyxafyANKUZPGpPIB0JVV8Kg+AZIpP5QEQkUDxqTwAVqpM8T2enY/xG1Mx+WgmZuYWY7jVjNGdw3HswO54/70tq75G5QHwtkaWZVm/D9HOzQdP49zVe3Ht7nRERMwvLr36Was5EFlEHNq7I8Y+GYmPPtgeES8r79KlS3Hy5Mk4ceJEnD59OlqtVh9OD0DZlHr4Lly/H2cvT8bc4otod8pGI6LVHIxTR0bjz3/241eVd/78eZUHwBtKO3wvR+92PF9YWv+XfzDUyOJ3//538Vd//PsqD4BVlXL4bj54Gp9+eT2eL7zY9Gt/NBgx/jd/Evt2b8//YABUXik/1Xnu6r2YW9z86EVELCxFfHH1Xs4nAqAuSjd8j2fn49rd6bbv6bWTZRFX7kzHk9n5fA8GQC2UbvjGb0x1fY1GRIxPdH8dAOqndMM3+Wjmja8sdGJucSkmHz7L6UQA1Enphm9mbjGn6yzkch0A6qV0wzfcyudmMsOtoVyuA0C9lG74RncOx5Zmd8dqNQdidNe2nE4EQJ2UbviOHtjd9TWyiDi6v/vrAFA/pRu+33tvS3zyBzui0ejs9Y1GxOG9O9a8cTUAaSvd8EVE/O2hkWg1Bzt6bas5GGOHRnI+EQB1Ucrh++iD7XHqyGhsHdrc8bYODcSpI6NuVwbAmkr7PL7jB/dERGz66QzLrwOA1ZTyJtUrfTv1NL64ei+u3JmORrz8cvqy5efxHd67I8YOjSg9ANZV+uFb9mR2PsYnpmLy4bOYmVuI4dZQjO7aFkf3r/0EdgB4W2WGDwDyUMoPtwBAUQwfAEkxfAAkxfABkBTDB0BSDB8ASTF8ACTF8AGQFMMHQFIMHwBJMXwAJMXwAZAUwwdAUgwfAEkxfAAkxfABkBTDB0BSDB8ASTF8ACTF8AGQFMMHQFL+H/GjytFktmrWAAAAAElFTkSuQmCC\n" | |
| }, | |
| "metadata": {} | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "d = {0: {1: 1}}\n", | |
| "G = nx.Graph(d)\n", | |
| "nx.draw(G)" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/", | |
| "height": 319 | |
| }, | |
| "id": "8cDEQaqY3u9b", | |
| "outputId": "6e09e6be-d22a-4714-d99a-45828dd2b61a" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "display_data", | |
| "data": { | |
| "text/plain": [ | |
| "<Figure size 432x288 with 1 Axes>" | |
| ], | |
| "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAEuCAYAAADx63eqAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjYuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8o6BhiAAAACXBIWXMAAAsTAAALEwEAmpwYAAAL50lEQVR4nO3dQYiU5x3H8f+su7iCTi2JoKAQisTNIRUUipSC5rIHTz2YEmiu24O5WnqQXko99JAeCvGy11wKngVtqXrzopAEmlWkBLKgQQUZBXdx3elh47JRd3Z25p13nvd5Pp+j7jw8tx/fmd13Wt1utxsAUIiJcV8AAOpk+AAoiuEDoCiGD4CiGD4AimL4ACiK4QOgKIYPgKIYPgCKYvgAKIrhA6Aohg+Aohg+AIpi+AAoiuEDoCiGD4CiGD4AimL4ACiK4QOgKIYPgKIYPgCKYvgAKMrkuC/Qr0fPluPSrcVYeNCJztJKtKcnY2Z/Oz4+fjDe2b1z3NcDoCFa3W63O+5L9PLV90/ii+v34sbdhxERsbyyuv5/05MT0Y2IU0f2xdmTh+Poob3juSQAjZH08H1587u4cHkhllZeRq9btloR05M74vzpmfj0xHu13Q+A5kn2rc610fs2nr9Y3fJnu92I5y9exoXL30ZEGD8ANpXkL7d89f2TuHB5oa/R2+j5i9W4cHkhvl58MpqLAdB4SQ7fF9fvxdLKy4Feu7TyMi5ev1fxjQDIRXLD9+jZcty4+7DnZ3q9dLsR1+48jMfPlqu9GABZSG74Lt1aHPqMVkRcuj38OQDkJ7nhW3jQ+cmfLAxiaWU1Fu4/rehGAOQkueHrLK1UdM6LSs4BIC/JDV97upq/sGhPT1VyDgB5SW74Zva3Y+fkcNeanpyImQN7KroRADlJbvjOHD849BndiDhzbPhzAMhPcsP37u6dcfL9fdFqDXhAdzV+84ufe3A1AG+V3PBFRHx26nBMT+4Y6LUTsRr//scf4+rVqxXfCoAcJDl8Rw/tjfOnZ2LX1Paut2tqIv7y26Mx/7c/x9zcXMzNzUWn0xnRLQFooiSHL2LtQdPnT38Qu6Z2bPm2Z6sVsWtqR5w//UF8euK9mJ2djW+++SZarVZ8+OGH6g+AdUl/LVFExNeLT+Li9Xtx7c7DaMXaH6e/8ur7+D46si/Onjocvzy4943XX716Nebm5mJ2djY+//zzaLfbtd0dgPQkP3yvPH62HJduL8bC/afRWXoR7empmDmwJ84c2/ob2DudTpw7dy6uXLkS8/PzMTs7W9OtAUhNY4avCuoPgGQ/4xsFn/0BUFTxbaT+AMpUVPFtpP4AylRs8W2k/gDKUWzxbaT+AMqh+F6j/gDypvheo/4A8qb4elB/APlRfD2oP4D8KL4+qT+APCi+Pqk/gDwovgGoP4DmUnwDUH8AzaX4hqT+AJpF8Q1J/QE0i+KrkPoDSJ/iq5D6A0if4hsR9QeQJsU3IuoPIE2KrwbqDyAdiq8G6g8gHYqvZuoPYLwUX83UH8B4Kb4xUn8A9VN8Y6T+AOqn+BKh/gDqofgSof4A6qH4EqT+AEZH8SVI/QGMjuJLnPoDqJbiS5z6A6iW4msQ9QcwPMXXIOoPYHiKr6HUH8BgFF9DqT+AwSi+DKg/gP4pvgyoP4D+Kb7MqD+A3hRfZtQfQG+KL2PqD+BNii9j6g/gTYqvEOoPYI3iK4T6A1ij+Aqk/oCSKb4CqT+gZIqvcOoPKI3iK5z6A0qj+Fin/oASKD7WqT+gBIqPt1J/QK4UH2+l/oBcKT62pP6AnCg+tqT+gJwoPrZF/QFNp/jYFvUHNJ3iY2DqD2gixcfA1B/QRIqPSqg/oCkUH5VQf0BTKD4qp/6AlCk+Kqf+gJQpPkZK/QGpUXyMlPoDUqP4qI36A1Kg+KiN+gNSoPgYC/UHjIviYyzUHzAuio+xU39AnRQfY6f+gDopPpKi/oBRU3wkRf0Bo6b4SJb6A0ZB8ZEs9QeMguKjEdQfUBXFRyOoP6Aqio/GUX/AMBQfjaP+gGEoPhpN/QHbpfhoNPUHbJfiIxvqD+iH4iMb6g/oh+IjS+oP2IziI0vqD9iM4iN76g/YSPGRPfUHbKT4KIr6AxQfRVF/gOKjWOoPyqT4KJb6gzIpPgj1ByVRfBDqD0qi+OA16g/ypvjgNeoP8qb4oAf1B/lRfNCD+oP8KD7ok/qDPCg+6JP6gzwoPhiA+oPmUnwwAPUHzaX4YEjqD5pF8cGQ1B80i+KDCqk/SJ/igwqpP0if4oMRUX+QJsUHI6L+IE2KD2qg/iAdig9qoP4gHYoPaqb+YLwUH9RM/cF4KT4YI/UH9VN8MEbqD+qn+CAR6g/qofggEeoP6qH4IEHqD0ZH8UGC1B+MjuKDxKk/qJbig8SpP6iW4oMGUX8wPMUHDaL+YHiKDxpK/cFgFB80lPqDwSg+yID6g/4pPsiA+oP+KT7IjPqD3hQfZEb9QW+KDzKm/uBNig8ypv7gTYoPCqH+YI3ig0KoP1ij+KBA6o+SKT4okPqjZIoPCqf+KI3ig8KpP0qj+IB16o8SKD5gnfqjBIoPeCv1R64UH/BW6o9cKT5gS+qPnCg+YEvqj5woPmBb1B9Np/iAbVF/NJ3iAwam/mgixQcMTP3RRIoPqIT6oykUH1AJ9UdTKD6gcuqPlCk+oHLqj5QpPmCk1B+pUXzASKk/UqP4gNqoP1Kg+IDaqD9SoPiAsVB/jIviA8ZC/TEuig8YO/VHnRQfMHbqjzopPiAp6o9RU3xAUtQfo6b4gGSpP0ZB8QHJUn+MguIDGkH9URXFBzSC+qMqig9oHPXHMBQf0Djqj2EoPqDR1B/bpfiARlN/bJfiA7Kh/uiH4gOyof7oh+IDsqT+2IziA7Kk/tiM4gOyp/7YSPEB2VN/bKT4gKKoPxQfUBT1h+IDiqX+yqT4gGKpvzIpPoBQfyVRfACh/kqi+ABeo/7ypvgAXqP+8qb4AHpQf/lRfAA9qL/8KD6APqm/PCg+gD6pvzwoPoABqL/mUnwAA1B/zaX4AIak/ppF8QEMSf01i+IDqJD6S5/iA6iQ+kuf4gMYEfWXJsUHMCLqL02KD6AG6i8dig+gBuovHYoPoGbqb7wUH0DN1N94KT6AMVJ/9VN8AGOk/uqn+AASof7qofgAEqH+6qH4ABKk/kZH8QEkSP2NjuIDSJz6q5biA0ic+quW4gNoEPU3PMUH0CDqb3iKD6Ch1N9gFB9AQ6m/wSg+gAyov/4pPoAMqL/+KT6AzKi/3hQfQGbUX2+KDyBj6u9Nig8gY+rvTYoPoBDqb43iAyiE+luj+AAKVHL9KT6AApVcf4oPoHCl1Z/hAyA6nU6cO3curly5EvPz8zE7O9vz5x89W45LtxZj4UEnOksr0Z6ejJn97fj4+MF4Z/fOmm49GMMHwLqt6u+r75/EF9fvxY27DyMiYnlldf3/picnohsRp47si7MnD8fRQ3trvHn/fMYHwLpen/19efO7+GT+Zvzr2x9ieWX1J6MXEbH0479d/e8P8cn8zfjy5nc1374/ig+At9pYf7/6/bn4+3/+F89frG79wh/tmpqI86c/iE9PvDe6Sw7A8AGwqU6nE3N/+mvc3H0iWpPb/+xu19SO+OcfTsQvD+6t/nID8lYnAJtqt9vxs1//LiYGGL2IiKWVl3Hx+r2KbzUcwwfAph49W44bdx/GoG8NdrsR1+48jMfPliu91zAMHwCbunRrcegzWhFx6fbw51TF8AGwqYUHnTd+e3O7llZWY+H+04puNDzDB8CmOksrFZ3zopJzqmD4ANhUe3qyonOmKjmnCoYPgE3N7G/HzsnhpmJ6ciJmDuyp6EbDM3wAbOrM8YNDn9GNiDPHhj+nKoYPgE29u3tnnHx/X7Rag72+1Yr46Mi+pB5cbfgA6OmzU4djenLHQK+dntwRZ08drvhGwzF8APR09NDeOH96JnZNbW8y1p7VOZPU48oiIqr5dR0AsvbqQdMXLi/E0srL6PWU51ZrrfTOn55J7gHVER5SDcA2fL34JC5evxfX7jyMVqz9cforr76P76Mj++LsqcPJld4rhg+AbXv8bDku3V6MhftPo7P0ItrTUzFzYE+cOeYb2AEgKX65BYCiGD4AimL4ACiK4QOgKIYPgKIYPgCKYvgAKIrhA6Aohg+Aohg+AIpi+AAoiuEDoCiGD4CiGD4AimL4ACiK4QOgKIYPgKIYPgCKYvgAKIrhA6Aohg+AovwfREByWztU5iYAAAAASUVORK5CYII=\n" | |
| }, | |
| "metadata": {} | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "from google.colab import output\n", | |
| "import time\n", | |
| "def debug(graph):\n", | |
| " output.clear()\n", | |
| " nx.draw(G, with_labels=True, font_weight='bold')\n", | |
| " time.sleep(3)" | |
| ], | |
| "metadata": { | |
| "id": "Ki3KTkax6Fb1" | |
| }, | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "G = nx.DiGraph({\n", | |
| " \"0\": {\"2\"},\n", | |
| " \"2\": {\"6\"},\n", | |
| " \"1\": {\"6\"},\n", | |
| " \"4\": {\"6\", \"7\"},\n", | |
| " \"6\": {\"7\"},\n", | |
| " \"5\": {\"7\"},\n", | |
| " \"3\": {\"7\"}\n", | |
| "})" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "nwbgMPF_313-", | |
| "outputId": "368a4640-ad49-4eac-db23-4233d55bab53" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "name": "stdout", | |
| "text": [ | |
| "u\n", | |
| "v\n", | |
| "w\n", | |
| "x\n", | |
| "y\n", | |
| "z\n" | |
| ] | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "# Aplicaciones" | |
| ], | |
| "metadata": { | |
| "id": "jT5qa5lXJBLU" | |
| } | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "## Bottom-Up Parser" | |
| ], | |
| "metadata": { | |
| "id": "QO_2XP9jJHXS" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "# Grammar\n", | |
| "production_rules = [\n", | |
| " (['S'], ['S', '+', 'S']),\n", | |
| " (['S'], ['E']),\n", | |
| " (['E'], ['id'])\n", | |
| "]\n", | |
| "HEAD = 0\n", | |
| "BODY = 1\n", | |
| "start_symbol = ['S']\n", | |
| "nonterminals = {'S', 'E'}\n", | |
| "symbols = {'+', 'id'}\n", | |
| "w = ['(', 'id', ')'] # We suppose a previous lexical processing" | |
| ], | |
| "metadata": { | |
| "id": "xU0bZfamM319" | |
| }, | |
| "execution_count": 1, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "assert 'id' in production_rules[2][BODY]" | |
| ], | |
| "metadata": { | |
| "id": "HJWplA7mTRuP" | |
| }, | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "U = 0\n", | |
| "X = 1\n", | |
| "V = 2\n", | |
| "\n", | |
| "def determine_uXvs(w):\n", | |
| " ws = []\n", | |
| " for i in range(0, len(w)):\n", | |
| " for j in range(i, len(w)):\n", | |
| " u=w[0:i]\n", | |
| " x=w[i:j+1]\n", | |
| " v=w[j+1:len(w)]\n", | |
| " ws.append(([u,x,v], (i,j+1)))\n", | |
| " return ws" | |
| ], | |
| "metadata": { | |
| "id": "LSmEeUQcTFBf" | |
| }, | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "def find_the_body_X_that_matches_uXv_and_substitute_by_head_Y_uYv(uXvs):\n", | |
| " possible_ws = []\n", | |
| " for uxv in uXvs:\n", | |
| " for index,rule in enumerate(production_rules):\n", | |
| " if uxv[0][X] == rule[BODY]:\n", | |
| " Y = rule[HEAD]\n", | |
| " possible_ws.append((uxv[0][U]+Y+uxv[0][V], uxv[1]))\n", | |
| " return possible_ws" | |
| ], | |
| "metadata": { | |
| "id": "j7t2G1xENzJU" | |
| }, | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "def build_tree(match, root):\n", | |
| " value=match[0][match[1][0]:match[1][1]]\n", | |
| " parent=Node(value=value,children=root.children[match[1][0]:match[1][1]])\n", | |
| " root.children[match[1][0]:match[1][1]] = [parent]\n", | |
| " root.w = match[0]\n", | |
| " return root" | |
| ], | |
| "metadata": { | |
| "id": "nZrgxyfQK7GX" | |
| }, | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "class RNode(Node):\n", | |
| " def __eq__(self, another):\n", | |
| " if self.value != another.value:\n", | |
| " return False\n", | |
| " if len(self.children) != len(another.children):\n", | |
| " return False\n", | |
| " if len(self.children) == 0:\n", | |
| " return True\n", | |
| " for index, child in enumerate(self.children):\n", | |
| " if child != another.children[index]:\n", | |
| " return False\n", | |
| " return True\n", | |
| " def __hash__(self):\n", | |
| " return hash(self.id)" | |
| ], | |
| "metadata": { | |
| "id": "SfIj9h5fu1vq" | |
| }, | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "import copy\n", | |
| "\n", | |
| "def parse(w):\n", | |
| " derivations = []\n", | |
| " stack = []\n", | |
| " original_w = w\n", | |
| " is_original_w = True\n", | |
| " current_root = None\n", | |
| " while True:\n", | |
| " uXvs = determine_uXvs(w)\n", | |
| " matches = find_the_body_X_that_matches_uXv_and_substitute_by_head_Y_uYv(uXvs)\n", | |
| " for match in matches:\n", | |
| " if match[0] == start_symbol:\n", | |
| " derivations.append(build_tree(match, current_root))\n", | |
| " root = Node(children=[Node(value=string) for string in w]) if is_original_w and w == original_w else copy.deepcopy(current_root)\n", | |
| " root = build_tree(match, root)\n", | |
| " stack.append(root)\n", | |
| " is_original_w = False\n", | |
| " if len(stack) == 0:\n", | |
| " return derivations\n", | |
| " current_root = stack.pop()\n", | |
| " w = current_root.w" | |
| ], | |
| "metadata": { | |
| "id": "9pNBfAg6Vyrq" | |
| }, | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "derivations=parse(['id', '+', 'id', '+', 'id'])\n", | |
| "for i in derivations:\n", | |
| " to_tree_lib(Tree(), i).show()" | |
| ], | |
| "metadata": { | |
| "id": "_vAYba7yWjaF" | |
| }, | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [], | |
| "metadata": { | |
| "id": "OrPOCLVNt7xQ" | |
| }, | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "# Top-Down" | |
| ], | |
| "metadata": { | |
| "id": "ElOh6iwWir8f" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "! python -m pip uninstall matplotlib\n", | |
| "! pip install matplotlib==3.1.3" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/", | |
| "height": 572 | |
| }, | |
| "id": "EF-I27C84H4R", | |
| "outputId": "08f1a318-14fb-4b7e-ca0d-e3ab1fc9cf0f" | |
| }, | |
| "execution_count": 5, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "name": "stdout", | |
| "text": [ | |
| "Found existing installation: matplotlib 3.6.3\n", | |
| "Uninstalling matplotlib-3.6.3:\n", | |
| " Would remove:\n", | |
| " /usr/local/lib/python3.8/dist-packages/matplotlib-3.6.3-py3.8-nspkg.pth\n", | |
| " /usr/local/lib/python3.8/dist-packages/matplotlib-3.6.3.dist-info/*\n", | |
| " /usr/local/lib/python3.8/dist-packages/matplotlib/*\n", | |
| " /usr/local/lib/python3.8/dist-packages/mpl_toolkits/axes_grid1/*\n", | |
| " /usr/local/lib/python3.8/dist-packages/mpl_toolkits/axisartist/*\n", | |
| " /usr/local/lib/python3.8/dist-packages/mpl_toolkits/mplot3d/*\n", | |
| " /usr/local/lib/python3.8/dist-packages/mpl_toolkits/tests/*\n", | |
| " /usr/local/lib/python3.8/dist-packages/pylab.py\n", | |
| "Proceed (Y/n)? y\n", | |
| " Successfully uninstalled matplotlib-3.6.3\n", | |
| "Looking in indexes: https://pypi.org/simple, https://us-python.pkg.dev/colab-wheels/public/simple/\n", | |
| "Collecting matplotlib==3.1.3\n", | |
| " Using cached matplotlib-3.1.3-cp38-cp38-manylinux1_x86_64.whl (13.1 MB)\n", | |
| "Requirement already satisfied: numpy>=1.11 in /usr/local/lib/python3.8/dist-packages (from matplotlib==3.1.3) (1.21.6)\n", | |
| "Requirement already satisfied: pyparsing!=2.0.4,!=2.1.2,!=2.1.6,>=2.0.1 in /usr/local/lib/python3.8/dist-packages (from matplotlib==3.1.3) (3.0.9)\n", | |
| "Requirement already satisfied: kiwisolver>=1.0.1 in /usr/local/lib/python3.8/dist-packages (from matplotlib==3.1.3) (1.4.4)\n", | |
| "Requirement already satisfied: cycler>=0.10 in /usr/local/lib/python3.8/dist-packages (from matplotlib==3.1.3) (0.11.0)\n", | |
| "Requirement already satisfied: python-dateutil>=2.1 in /usr/local/lib/python3.8/dist-packages (from matplotlib==3.1.3) (2.8.2)\n", | |
| "Requirement already satisfied: six>=1.5 in /usr/local/lib/python3.8/dist-packages (from python-dateutil>=2.1->matplotlib==3.1.3) (1.15.0)\n", | |
| "Installing collected packages: matplotlib\n", | |
| "Successfully installed matplotlib-3.1.3\n" | |
| ] | |
| }, | |
| { | |
| "output_type": "display_data", | |
| "data": { | |
| "application/vnd.colab-display-data+json": { | |
| "pip_warning": { | |
| "packages": [ | |
| "matplotlib", | |
| "mpl_toolkits" | |
| ] | |
| } | |
| } | |
| }, | |
| "metadata": {} | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "import networkx as nx\n", | |
| "d = {\"S\": {\"S+S\", \"1\"}, \"S+S\": {\"S\"}}\n", | |
| "G = nx.DiGraph(d)\n", | |
| "nx.draw(G, with_labels=True, font_weight='bold')" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/", | |
| "height": 319 | |
| }, | |
| "id": "hLoDBlqDjJbW", | |
| "outputId": "b3b82947-8d20-4fbf-cf9b-2d1ebff50115" | |
| }, | |
| "execution_count": 37, | |
| "outputs": [ | |
| { | |
| "output_type": "display_data", | |
| "data": { | |
| "text/plain": [ | |
| "<Figure size 432x288 with 1 Axes>" | |
| ], | |
| "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAEuCAYAAADx63eqAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAATAUlEQVR4nO3df3DUdX7H8ddmd8kmJDEKQTgIRowhcQ6UxOtxFSqgEGTa6TiHHT3pdKYttMdNndHGsymDMnLItepM/UPmKrad8bxOsdhWx6FHAAkdr2AVlKgQ0gh4SY8f4UeyWcwu+6t/5MgRkmw2ye53v9/v5/n485vdr+/9g3n7/O7udz3JZDIpAAAMkZfrAQAAsBKLDwBgFBYfAMAoLD4AgFFYfAAAo7D4AABGYfEBAIzC4gMAGIXFBwAwCosPAGAUFh8AwCgsPgCAUVh8AACjsPgAAEZh8QEAjMLiAwAYhcUHADAKiw8AYBQWHwDAKCw+AIBRWHwAAKOw+AAARvHleoB0XQhFtPNwp1rPBhUMx1QS8Kl6eokeqZulKUX5uR4PAOAQnmQymcz1EKkc7ejWq83tOtDWJUmKxBIDfwv48pSUtGRumdbfX6m7y0tzNCUAwClsvfjePHRaW3a1KhyLK9WUHo8U8Hm1YVW11iyssGw+AIDz2PZSZ//SO66+aGLUxyaTUl80ri27jksSyw8AMCJbFt/Rjm49uv2Q+qLxgWPBj95RqGWPohd+KSUTuum+x1S6+PEhzy3we7Vj3ULNn8VlTwDAULb8VOerze0Kx+KDjl092668QJG8xVNTPjcci2tbc3s2xwMAOJjtFt+FUEQH2rqGvKc39ff+UtMf/7Em3Ton5fOTSWn/iS5dDEWyOCUAwKlst/h2Hu6c8Dk8knYemfh5AADuY7vF13o2OOgrC+MRjiXUeqY3QxMBANzEdosvGI5l6DzRjJwHAOAutlt8JYHMfMOiJODPyHkAAO5iu+/xVU8vUb7v7JDLnb1HdyvScUxXz30pSfr6fw8p1nNehVULVVj1nUGPDfjyVD2j2LKZAQDOYbviW103a9jjkY5juvL5PsWD/bcui54/pSuf79PVcyeHPDYpaXXt8OcBAJjNll9gX/fTj7Xn+LmUtykbiUdS7TSvfrKmTlOnTpXH48n4fAAA57Jd8UnSD5ZUKuDzju/J8aje+9u/0MyZM5Wfn6/y8nI9//zzmR0QAOBYtlx8d5eXasOqahX4xzZegT9PP1xRqbzuTkWjUUWjUZ0/f16zZnHZEwDQz5aLT+q/0fSGVTUq8Hs12tVKj6f/Hp0bVtXo+w9+U5s2bVJhYaE8Ho88Ho9mzpxpzdAAANuz5Xt812vp7Na25nbtP9Elj/q/nH7Ntd/jWzq3TOuXVA7cmPrq1auqqKhQMBjUa6+9psbGRtXX1+ull15SSUlJbl4IAMAWbL/4rrkYimjnkU61nulVMBxVScCv6hnFWl07/C+wHzx4UD09PVq5cqV6enrU0NCgpqYmbd++XStWrMjBKwAA2IFjFl8mNDU1ae3atdQfABjMtu/xZcOKFSvU0tKiZDKpefPmqampKdcjAQAsZlTxXY/6AwAzGVV816P+AMBMxhbf9ag/ADCHscV3PeoPAMxB8d2A+gMAd6P4bkD9AYC7UXwpUH8A4D4UXwrUHwC4D8WXJuoPANyB4ksT9QcA7kDxjQP1BwDORfGNA/UHAM5F8U0Q9QcAzkLxTRD1BwDOQvFlEPUHAPZH8WUQ9QcA9kfxZQn1BwD2RPFlCfUHAPZE8VmA+gMA+6D4LED9AYB9UHwWo/4AILcoPovdWH979uzJ9UgAYBSKL4eu1d/KlSv14osvUn8AYAGKL4eu1V8ikaD+AMAiFJ9NUH8AYA2KzyaoPwCwBsVnQ9QfAGQPxWdD1B8AZA/FZ3PUHwBkFsVnc9QfAGQWxecg1B8ATBzF5yDUHwBMHMXnUNQfAIwPxedQ1B8AjA/F5wLUHwCkj+JzAeoPANJH8bkM9QcAqVF8LkP9AUBqFJ+LUX8AMBTF52LUHwAMRfEZgvoDgH4UnyGoPwDoR/EZiPoDYDKKz0DUHwCTUXyGo/4AmIbiMxz1B8A0FB8GUH8ATEDxYQD1B8AEFB+GRf0BcCuKD8Oi/gC4FcWHUe3evVtr167VQw89RP0BcDyKD6Oqr6/XZ599Rv0BcAWKD2NC/QFwOooPY0L9AXA6ig/jRv0BcCKKD+NG/QFwIooPGUH9AXAKig8ZQf0BcAqKDxlH/QGwM4oPGUf9AbAzig9ZRf0BsBuKD1lF/QGwG4oPlqH+ANgBxQfLUH8A7IDiQ05QfwByheJDTlB/AHKF4kPOUX8ArETxIeeoPwBWovhgK9QfgGyj+GAr1B+AbKP4YFvUH4BsoPhgW9QfgGyg+OAI1B+ATKH44AjUH4BMofjgONQfgImg+OA41B+AiaD44GjUH4CxovjgaNQfgLGi+OAa1B+AdFB8cA3qD0A6KD64EvUHYCQUH1yJ+gMwEooPrkf9AbgexQfXo/4AXI/ig1GoPwAUH4xC/QGg+GAs6g8wE8UHY1F/gJkoPkDUH2ASig8Q9QeYhOIDbkD9Ae5G8QE3oP4Ad6P4gBSoP8B9KD4gBeoPcB+KD0gT9Qe4A8UHpIn6A9yB4gPGgfoDnIviA8aB+gOci+IDJoj6A5yF4gMmiPoDnIXiAzKI+gPsj+IDMoj6A+yP4gOyZKz1dyEU0c7DnWo9G1QwHFNJwKfq6SV6pG6WphTlWzQ14H4sPiCLenp61NDQoKamJr3++utavnz5kMcc7ejWq83tOtDWJUmKxBIDfwv48pSUtGRumdbfX6m7y0utGh1wLRYfYIGR6u/NQ6e1ZVerwrG4Uv1L9HikgM+rDauqtWZhhTVDAy7Fe3yABYZ7769/6R1XXzT10pOkZFLqi8a1ZddxvXnotCUzA25F8QEW2717t57c/HdKLH1C4esua0a7z+ry+/+gSOcxJSJfy1tYIv/U23TLiu/Lf/OMgccV+L3asW6h5s/isicwHhQfYLH6+not+rPNisQTg453vf0j9bUd1KSy21Q0/0FNmjZHkV+1Kh66NOhx4Vhc25rbrRwZcBVfrgcATHMhFNGBtq5Blzfjfb2Kdp1WXv5kTXt0izwejyQpGYsqmYwPen4yKe0/0aWLoQif9gTGgeIDLLbzcOeQY3mTCuSZVKBE5IrO/NMTurRvu75uO6hkIq48f2DI4z2Sdh4Zeh4Ao2PxARZrPRsc9JUFSfJ4fZry0BPy5E9W9Pwp9X70jrr+bYv+7+//VJEzbUPOEY4l1Hqm16qRAVfhUidgsWA4NuzxyTWLVXjntxX+5WcKdx5T6NPdSlzpVs8v/kXTVj87zHmi2R4VcCWKD7BYSWDo/28m4zGFO76QxzdJBXPqdPPv/KFu+s4jkqTE1b4RzuPP6pyAW1F8gMWqp5co33d20OXOZDyqcz97Rv4p5fLfOkd5/nx93XZIklRQsWDIOQK+PFXPKLZsZsBNKD7AYqvrZg055vFNUvG3fl/y+hX+8mOFPt+vvPzJuum3H1XJwu8OeXxS0uraoecBMDqKD7DY1KJ83V9Vpj3Hzw18pcGT59UtD6xN6/keSUvnlvFVBmCcuHMLkANHO7r16PZD6ovGR3/wDZLRiC7+60Ytvmu2amtrdccdd+iee+5RbW1tFiYF3IfFB+TIb+7VmRj9wb9W4M/T92oK9Oz3lg4c8/v9uv3223XixIlsjAm4Du/xATmyZmGFNqyqUYHfq1/fqGVEHk//PTo3rKrRxseW6Omnn5bf3/+pzlgsphdeeMGCiQF3oPiAHGvp7Na25nbtP9EljzToxtXXfo9v6dwyrV9SOXBj6lAopNmzZysUCqmwsFChUEibN29WY2Njbl4E4CAsPsAmLoYi2nmkU61nehUMR1US8Kt6RrFW1w7/C+xvvPGGnnvuOX3xxRd65ZVXtHHjRt15553as2ePZs3iE5/ASFh8gIPF43F5vV5JUkdHh5YvX6729nbqD0iBxQe4zNatW6k/IAU+3AK4TGNjo06dOqVkMqmKigpt3bo11yMBtkLxAS5G/QFDUXyAi1F/wFAUH2AI6g/oR/EBhqD+gH4UH2Ag6g8mo/gAA1F/MBnFBxiO+oNpKD7AcNQfTEPxARhA/cEEFB+AAdQfTEDxARgW9Qe3ovgADIv6g1tRfABGRf3BTSg+AKOi/uAmFB+AMaH+4HQUH4Axof7gdBQfgHGj/uBEFB+AcaP+4EQUH4CMoP7gFBQfgIy4Vn+SqD/YGsUHIOOoP9gZxQcg4xobG3X69GlJ1B/sh+IDkFXUH+yG4gOQVdQf7IbiA2AZ6g92QPEBsAz1Bzug+ADkBPWHXKH4AOQE9YdcofgA5Bz1BytRfAByjvqDlSg+ALZC/SHbKD4AtkL9IdsoPgC2Rf0hGyg+ALZF/SEbKD4AjkD9IVMoPgCOQP0hUyg+AI5D/WEiKD4AjkP9YSIoPgCORv1hrCg+AI5G/WGsKD4ArkH9IR0UHwDXoP6QDooPgCtRfxgJxQfAlag/jITiA+B61+qvsrJSe/fupf4MR/EBcL3GxkadOnVKEvUHig+AYag/UHwAjEL9geIDYCzqz0wUHwBjUX9movgAQNSfSSg+ABD1ZxKKDwBuQP25G8UHADeg/tyN4gOAFKg/96H4ACAF6s99KD4ASBP15w4UHwCkifpzB4oPAMaB+nMuig8AxoH6cy6KDwAmiPpzFooPACaI+nMWig8AMoj6sz+KDwAyiPqzP4oPALKE+rMnig8AsoT6syeKDwAsQP3ZB8UHABag/uyD4gMAi1F/uUXxAYDFqL/covgAIIeoP+tRfACQQ9Sf9Sg+ALAJ6s8aFB8A2AT1Zw2KDwBsiPrLHooPAGyI+sseig8AbI76yyyKDwBsjvrLLIoPAByE+ps4ig8AHIT6mziKDwAcivobH4oPAByK+hsfig8AXID6Sx/FBwAuQP2lj+IDAJeh/lKj+ADAZai/1Cg+AHAx6m8oig8AXIz6G4riAwBDUH/9KD4AMAT114/iAwADmVx/FB8AGMjk+mPxAYChysvL1draqs2bN2vjxo2qrq5WZ2enmpubVVVVpStXruR6xKzgUicAQB0dHVq+fLna29sVCAQUiUTU0NAwYgleCEW083CnWs8GFQzHVBLwqXp6iR6pm6UpRfkWTz82LD4AwIB7771Xhw8fliTl5+erra1Ns2fPHvj70Y5uvdrcrgNtXZKkSCwx8LeAL09JSUvmlmn9/ZW6u7zU0tnTxeIDAEiSPvnkE9XW1g46VlNTo2PHjkmS3jx0Wlt2tSociyvV5vB4pIDPqw2rqrVmYUUWJx4f76ZNmzbleggAQO4VFRWpqqpK8+fPV1lZmS5fvqyvvvpKXV1dunTLXdqy67j6oonRTyQplkjq4MmLKi3wa/4se5UfxQcAGOTkyZNqaGjQBx98oGAwqPyCQsWmzFHpg38u/80z0j5P3+lP1fvBPyuvu0NKJjR9+nTV1dVpx44dWZx+dL6c/tcBALbz8MMPq6WlRcuWLVNVVZV2HfpcHcePqDh0acji69z2xyqa94BKFz8+6His94K63t6sZDymO761TMvmV6itrU3vvvuulS9lWCw+AMCAS5cuqaWlRaWlpdq7d68uXrmq9//mfZU/GFEyGU/7PFd/1aZkNKKCym/Lu/xJbX1mmaYU5evSpUtZnD49LD4AwIDi4mIVFRWpu7tbCxYs0NSqWoU0U97ye5Q3KZD2ebxFN0uS+r78SJ0/+2v9UcciPfMnf6D77rsvW6Onjff4AACDvPXWW1q3bp16enoGjuVNLtW01c8qf0aVLu19beB4qGWP/FNnK/8bcyVJBXPqVDCnTpJ0+f1/VPCj/5CSv/lATG1trfbt26fS0tx94IXFBwAYIhwO68CBA/rhqzv0+b5/V+LrbhVU/pamrX5WX/34d0d83k33PTbo/b54X1Dh00c1padNJ3/xnqLRqF5++WU99dRTVryMYXGpEwAwIBqN6sMPP9SiRYtUX1+v/+yepo6vfbq8b7sSV/skSbf91XsDjx/xwy0955VMxOW/eYYm1yzWQ/c8qlM3JfTOO++ot7fX0td0IxYfAGBAJBLR4sWLVVNTowULFuirnph6/vvnkqSCigVpn+dq12l1vf0j5X9jrgJTy/XB/0zSp//1c3k8Hj3wwAPZGj8tLD4AwIBAIKAnn3xS+/fv165du9TX1ydv4S0qXrBKJQu/m/Z5/FNna/I3lynS+YWCx07peL5P8+bNU0NDgxYtWpTFVzA63uMDAKS07qcfa8/xcylvUzYSj0eqv+tW/WTNvZkfbJz4WSIAQEo/WFKpgM87rucGfF6tX1KZ4YkmhsUHAEjp7vJSbVhVrQL/2FZGgT9PG1ZV2+5enbzHBwAY1bVfWXDDrzPwHh8AIG0tnd3a1tyu/Se65JEUHub3+JbOLdP6JZW2K71rWHwAgDG7GIpo55FOtZ7pVTAcVUnAr+oZxVpdyy+wAwBgK3y4BQBgFBYfAMAoLD4AgFFYfAAAo7D4AABGYfEBAIzC4gMAGIXFBwAwCosPAGAUFh8AwCgsPgCAUVh8AACjsPgAAEZh8QEAjMLiAwAYhcUHADAKiw8AYBQWHwDAKCw+AIBRWHwAAKOw+AAARvl/FaUYxjPBSeMAAAAASUVORK5CYII=\n" | |
| }, | |
| "metadata": {} | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "def combinations(x,y):\n", | |
| " n=max(len(x),1)\n", | |
| " m=len(y)\n", | |
| " c=[[]]*n*m\n", | |
| " k = 0\n", | |
| " for i in range(n):\n", | |
| " for j in range(m):\n", | |
| " c[k] = x[i]+y[j]\n", | |
| " k += 1\n", | |
| " return c" | |
| ], | |
| "metadata": { | |
| "id": "aw-33ANEQIO-" | |
| }, | |
| "execution_count": 185, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "class Terminal:\n", | |
| " def __init__(self, value):\n", | |
| " self.value = value\n", | |
| " def __repr__(self):\n", | |
| " return self.value\n", | |
| " def apply(self):\n", | |
| " return ([[self]], 0, 0)\n", | |
| "\n", | |
| "class Nonterminal:\n", | |
| " def __init__(self, value, terminals, nonterminals):\n", | |
| " self.value = value\n", | |
| " self.terminals = terminals\n", | |
| " self.nonterminals = nonterminals\n", | |
| " def __repr__(self):\n", | |
| " return \"Nonterminal\"\n", | |
| " def apply(self):\n", | |
| " return (self.value, self.terminals, self.nonterminals)\n", | |
| "\n", | |
| "class Derivation:\n", | |
| " def __init__(self, value):\n", | |
| " self.value = value\n", | |
| " def __repr__(self):\n", | |
| " return self.value.__repr__()\n", | |
| " def derive(self):\n", | |
| " derivations = [[]]\n", | |
| " terminals = 0\n", | |
| " nonterminals = 0\n", | |
| " for symbol in self.value:\n", | |
| " possibilities,t,n=symbol.apply()\n", | |
| " derivations=combinations(derivations,possibilities)\n", | |
| " terminals += t\n", | |
| " nonterminals += n\n", | |
| " derivations.sort(key=lambda derivation: len(derivation))\n", | |
| " for i in range(0, len(derivations)):\n", | |
| " derivations[i] = Derivation(derivations[i])\n", | |
| " return (derivations, terminals, nonterminals)\n", | |
| " def isterminal(self):\n", | |
| " return False\n", | |
| "\n", | |
| "def language(S):\n", | |
| " stack = [Derivation([S])]\n", | |
| " terminals = 0\n", | |
| " i = 0\n", | |
| " while i < 10 and terminals != len(stack):\n", | |
| " derivation=stack.pop()\n", | |
| " derivations,t,_=derivation.derive()\n", | |
| " nonterminals = stack[terminals:]\n", | |
| " stack = stack[:terminals]\n", | |
| " stack.extend(derivations)\n", | |
| " stack.extend(nonterminals)\n", | |
| " terminals += t\n", | |
| " i += 1\n", | |
| " return stack[:terminals]" | |
| ], | |
| "metadata": { | |
| "id": "8Rf74PP0KoF9" | |
| }, | |
| "execution_count": 378, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "b=Nonterminal([], 2, 2)\n", | |
| "b.value=[[Terminal('1')], [Terminal('2')], [Terminal('('), b, Terminal(')')], [b, Terminal('+'), b]]\n", | |
| "\n", | |
| "language(b)" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "49UrWJk8PpRv", | |
| "outputId": "654c3dc2-e2d6-4ce5-fa45-e4b8be03e3de" | |
| }, | |
| "execution_count": 379, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "[[1],\n", | |
| " [2],\n", | |
| " [1, +, 1],\n", | |
| " [1, +, 2],\n", | |
| " [2, +, 1],\n", | |
| " [2, +, 2],\n", | |
| " [(, 1, )],\n", | |
| " [(, 2, )],\n", | |
| " [1, +, 1, +, 1, +, 1],\n", | |
| " [1, +, 1, +, 1, +, 2],\n", | |
| " [1, +, 1, +, 2, +, 1],\n", | |
| " [1, +, 1, +, 2, +, 2],\n", | |
| " [1, +, 2, +, 1, +, 1],\n", | |
| " [1, +, 2, +, 1, +, 2],\n", | |
| " [1, +, 2, +, 2, +, 1],\n", | |
| " [1, +, 2, +, 2, +, 2],\n", | |
| " [1, +, 1, +, (, 1, )],\n", | |
| " [1, +, 1, +, (, 2, )],\n", | |
| " [1, +, 2, +, (, 1, )],\n", | |
| " [1, +, 2, +, (, 2, )],\n", | |
| " [2, +, 1, +, (, 1, )],\n", | |
| " [2, +, 1, +, (, 2, )],\n", | |
| " [(, 1, ), +, 1, +, 1],\n", | |
| " [(, 1, ), +, 1, +, 2],\n", | |
| " [(, 1, ), +, 2, +, 1],\n", | |
| " [(, 1, ), +, 2, +, 2],\n", | |
| " [(, 2, ), +, 1, +, 1],\n", | |
| " [(, 2, ), +, 1, +, 2],\n", | |
| " [(, 1, ), +, (, 1, )],\n", | |
| " [(, 1, ), +, (, 2, )],\n", | |
| " [(, 2, ), +, (, 1, )],\n", | |
| " [(, 2, ), +, (, 2, )],\n", | |
| " [1, +, 1, +, 2],\n", | |
| " [1, +, 2, +, 2],\n", | |
| " [2, +, 1, +, 2],\n", | |
| " [2, +, 2, +, 2],\n", | |
| " [1, +, 1, +, 1],\n", | |
| " [1, +, 2, +, 1],\n", | |
| " [2, +, 1, +, 1],\n", | |
| " [2, +, 2, +, 1],\n", | |
| " [(, 1, ), +, 2],\n", | |
| " [(, 2, ), +, 2]]" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "execution_count": 379 | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "Derivation([b, Terminal('+'), b]).derive()[0]" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "DtQXSARYeyaS", | |
| "outputId": "f5615814-496b-402d-f6ae-6440d2ace8b8" | |
| }, | |
| "execution_count": 370, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "[[1, +, 1],\n", | |
| " [1, +, 2],\n", | |
| " [2, +, 1],\n", | |
| " [2, +, 2],\n", | |
| " [1, +, (, Nonterminal, )],\n", | |
| " [1, +, Nonterminal, +, Nonterminal],\n", | |
| " [2, +, (, Nonterminal, )],\n", | |
| " [2, +, Nonterminal, +, Nonterminal],\n", | |
| " [(, Nonterminal, ), +, 1],\n", | |
| " [(, Nonterminal, ), +, 2],\n", | |
| " [Nonterminal, +, Nonterminal, +, 1],\n", | |
| " [Nonterminal, +, Nonterminal, +, 2],\n", | |
| " [(, Nonterminal, ), +, (, Nonterminal, )],\n", | |
| " [(, Nonterminal, ), +, Nonterminal, +, Nonterminal],\n", | |
| " [Nonterminal, +, Nonterminal, +, (, Nonterminal, )],\n", | |
| " [Nonterminal, +, Nonterminal, +, Nonterminal, +, Nonterminal]]" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "execution_count": 370 | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "combinations([[]], Terminal('x').apply())" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "AxrqiJLeWAjO", | |
| "outputId": "dab3871e-e830-453c-9192-d97937cc9f38" | |
| }, | |
| "execution_count": 184, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "[[x]]" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "execution_count": 184 | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "['X']+['(']" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "0XRXDwWIW_yE", | |
| "outputId": "1fa8c3cb-665e-4963-dd09-2c6a2233935b" | |
| }, | |
| "execution_count": 154, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "['X', '(']" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "execution_count": 154 | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "from itertools import combinations\n", | |
| "list(combinations([1, 2, 3], 2))" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "4FbtnOT9XGSC", | |
| "outputId": "72449fa7-ba44-4595-8e73-ddd35eea5e12" | |
| }, | |
| "execution_count": 122, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "[(1, 2), (1, 3), (2, 3)]" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "execution_count": 122 | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [], | |
| "metadata": { | |
| "id": "R5b1UllnYAsQ" | |
| }, | |
| "execution_count": null, | |
| "outputs": [] | |
| } | |
| ] | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment