Last active
November 8, 2017 02:04
-
-
Save fagonzalezo/e761254c20f43d1526b2 to your computer and use it in GitHub Desktop.
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
| { | |
| "cells": [ | |
| { | |
| "cell_type": "code", | |
| "execution_count": 1, | |
| "metadata": { | |
| "collapsed": false | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "#If you don't have graphviz, you can remove this cell and eliminate all calls to the functions in it.\n", | |
| "\n", | |
| "from graphviz import Graph, Digraph\n", | |
| "from IPython.display import display\n", | |
| "\n", | |
| "# This function allows to drwaw a graph. It requires graphviz to be installed\n", | |
| "def display_graph(G, color = {}):\n", | |
| " dot = Graph(graph_attr = {'size':'3.5'})\n", | |
| " for node in G:\n", | |
| " if not node in color or color[node] == 'white':\n", | |
| " dot.node(node)\n", | |
| " else:\n", | |
| " if color[node] == 'black':\n", | |
| " dot.node(node, style = 'filled', color = color[node], fontcolor = 'white')\n", | |
| " else:\n", | |
| " dot.node(node, style = 'filled', color = color[node])\n", | |
| " for n1 in G:\n", | |
| " for n2 in G[n1]:\n", | |
| " if n1 < n2:\n", | |
| " dot.edge(n1, n2)\n", | |
| " display(dot)\n", | |
| "\n", | |
| "# This function allows to draw a search tree. It requires graphviz to be installed\n", | |
| "def display_parent(prnt):\n", | |
| " dot = Digraph(graph_attr = {'size':'2.5'})\n", | |
| " for n1 in prnt:\n", | |
| " if prnt[n1] <> None:\n", | |
| " for n2 in prnt[n1]:\n", | |
| " dot.edge(n2, n1)\n", | |
| " display(dot)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "Búsqueda en grafos\n", | |
| "==================\n", | |
| "\n", | |
| "El objetivo de los algoritmos de búsqueda es recorrer un grafo de manera que se visiten todos sus vértices, o por lo menos aquellos que sean alcanzables desde un nodo de inicio. Hay dos tipos principales de búsqueda: búsqueda en profundidad y búsqueda en amplitud. \n", | |
| "\n", | |
| "Búsqueda en profundidad\n", | |
| "-----------------------\n", | |
| "\n", | |
| "El objetivo de la búsqueda en profundidad es avanzar en un camino de búsqueda tanto como sea posible. Este se logra a través de un proceso recursivo y una estrategia de marcado de nodos, que le permite al algoritmo saber que nodos se han visitado ya. Las marcas corresponden a colores con el siguiente significado:\n", | |
| "\n", | |
| "* Blanco: el nodo no ha sido visitado aun.\n", | |
| "* Gris: el nodo ya se visitó, pero no se han terminado de procesar sus descendientes.\n", | |
| "* Negro: el nodo ya se terminó de procesar.\n", | |
| "\n", | |
| "La siguiente función implementa el algoritmo de búsqeda en profundidad (DFS por sus siglas en Inglés). La función recibe el grafo (G), el nodo desde el que comienza (node) y un arreglo con la información de color para cada nodo." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 2, | |
| "metadata": { | |
| "collapsed": false | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "def DFS_Visit(G, node, color):\n", | |
| " color[node] = 'gray'\n", | |
| " total_marked = 1\n", | |
| "# print \"node=\", node, \">>> \"\n", | |
| "# display_graph(G, color)\n", | |
| " for neighbor in G[node]:\n", | |
| " if color[neighbor] == 'white':\n", | |
| " total_marked += DFS_Visit(G, neighbor, color)\n", | |
| " color[node] = 'black'\n", | |
| "# print \"node=\", node, \"<<< \"\n", | |
| "# display_graph(G, color)\n", | |
| " return total_marked" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "A continuación vamos a probar el algoritmo sobre el siguiente grafo:\n", | |
| "" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 3, | |
| "metadata": { | |
| "collapsed": false | |
| }, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "{'s': {'r': 1, 'w': 1}, 'r': {'s': 1, 'v': 1}, 'u': {'y': 1, 't': 1}, 't': {'x': 1, 'u': 1, 'w': 1}, 'w': {'x': 1, 's': 1, 't': 1}, 'v': {'r': 1}, 'y': {'x': 1, 'u': 1}, 'x': {'y': 1, 't': 1, 'w': 1}}\n" | |
| ] | |
| }, | |
| { | |
| "data": { | |
| "image/svg+xml": [ | |
| "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n", | |
| "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n", | |
| " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n", | |
| "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\n", | |
| " -->\n", | |
| "<!-- Title: %3 Pages: 1 -->\n", | |
| "<svg width=\"178pt\" height=\"252pt\"\n", | |
| " viewBox=\"0.00 0.00 178.37 252.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n", | |
| "<g id=\"graph0\" class=\"graph\" transform=\"scale(0.759036 0.759036) rotate(0) translate(4 328)\">\n", | |
| "<title>%3</title>\n", | |
| "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-328 231,-328 231,4 -4,4\"/>\n", | |
| "<!-- s -->\n", | |
| "<g id=\"node1\" class=\"node\"><title>s</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"128\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"128\" y=\"-229.8\" font-family=\"Times,serif\" font-size=\"14.00\">s</text>\n", | |
| "</g>\n", | |
| "<!-- w -->\n", | |
| "<g id=\"node5\" class=\"node\"><title>w</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"120\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"120\" y=\"-157.8\" font-family=\"Times,serif\" font-size=\"14.00\">w</text>\n", | |
| "</g>\n", | |
| "<!-- s--w -->\n", | |
| "<g id=\"edge1\" class=\"edge\"><title>s--w</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M126.022,-215.697C124.782,-204.846 123.19,-190.917 121.955,-180.104\"/>\n", | |
| "</g>\n", | |
| "<!-- r -->\n", | |
| "<g id=\"node2\" class=\"node\"><title>r</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"164\" cy=\"-306\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"164\" y=\"-301.8\" font-family=\"Times,serif\" font-size=\"14.00\">r</text>\n", | |
| "</g>\n", | |
| "<!-- r--s -->\n", | |
| "<g id=\"edge2\" class=\"edge\"><title>r--s</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M155.65,-288.765C149.835,-277.456 142.11,-262.437 136.304,-251.147\"/>\n", | |
| "</g>\n", | |
| "<!-- v -->\n", | |
| "<g id=\"node6\" class=\"node\"><title>v</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"200\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"200\" y=\"-229.8\" font-family=\"Times,serif\" font-size=\"14.00\">v</text>\n", | |
| "</g>\n", | |
| "<!-- r--v -->\n", | |
| "<g id=\"edge3\" class=\"edge\"><title>r--v</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M172.35,-288.765C178.165,-277.456 185.89,-262.437 191.696,-251.147\"/>\n", | |
| "</g>\n", | |
| "<!-- u -->\n", | |
| "<g id=\"node3\" class=\"node\"><title>u</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"27\" y=\"-85.8\" font-family=\"Times,serif\" font-size=\"14.00\">u</text>\n", | |
| "</g>\n", | |
| "<!-- y -->\n", | |
| "<g id=\"node7\" class=\"node\"><title>y</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"63\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"63\" y=\"-13.8\" font-family=\"Times,serif\" font-size=\"14.00\">y</text>\n", | |
| "</g>\n", | |
| "<!-- u--y -->\n", | |
| "<g id=\"edge4\" class=\"edge\"><title>u--y</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M35.3496,-72.7646C41.1655,-61.456 48.8897,-46.4367 54.6957,-35.1473\"/>\n", | |
| "</g>\n", | |
| "<!-- t -->\n", | |
| "<g id=\"node4\" class=\"node\"><title>t</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"56\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"56\" y=\"-229.8\" font-family=\"Times,serif\" font-size=\"14.00\">t</text>\n", | |
| "</g>\n", | |
| "<!-- t--u -->\n", | |
| "<g id=\"edge6\" class=\"edge\"><title>t--u</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M52.5019,-215.871C46.928,-188.578 36.0922,-135.52 30.5105,-108.189\"/>\n", | |
| "</g>\n", | |
| "<!-- t--w -->\n", | |
| "<g id=\"edge7\" class=\"edge\"><title>t--w</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M69.5728,-218.155C80.4338,-206.276 95.591,-189.697 106.447,-177.824\"/>\n", | |
| "</g>\n", | |
| "<!-- x -->\n", | |
| "<g id=\"node8\" class=\"node\"><title>x</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"99\" y=\"-85.8\" font-family=\"Times,serif\" font-size=\"14.00\">x</text>\n", | |
| "</g>\n", | |
| "<!-- t--x -->\n", | |
| "<g id=\"edge5\" class=\"edge\"><title>t--x</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M61.1015,-216.153C69.3773,-188.824 85.6337,-135.14 93.9051,-107.825\"/>\n", | |
| "</g>\n", | |
| "<!-- w--x -->\n", | |
| "<g id=\"edge8\" class=\"edge\"><title>w--x</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M114.916,-144.055C111.615,-133.049 107.329,-118.764 104.037,-107.789\"/>\n", | |
| "</g>\n", | |
| "<!-- x--y -->\n", | |
| "<g id=\"edge9\" class=\"edge\"><title>x--y</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M90.6504,-72.7646C84.8345,-61.456 77.1103,-46.4367 71.3043,-35.1473\"/>\n", | |
| "</g>\n", | |
| "</g>\n", | |
| "</svg>\n" | |
| ], | |
| "text/plain": [ | |
| "<graphviz.dot.Graph at 0x103e7c710>" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "output_type": "display_data" | |
| } | |
| ], | |
| "source": [ | |
| "# Graph construction\n", | |
| "\n", | |
| "def make_link(G, node1, node2):\n", | |
| " if node1 not in G:\n", | |
| " G[node1] = {}\n", | |
| " (G[node1])[node2] = 1\n", | |
| " if node2 not in G:\n", | |
| " G[node2] = {}\n", | |
| " (G[node2])[node1] = 1\n", | |
| " return G\n", | |
| "\n", | |
| "edges1 = [('v', 'r'), ('r', 's'), ('w', 't'), ('s','w'),\n", | |
| " ('w', 'x'), ('t', 'x'), ('t', 'u'), ('x', 'y'),\n", | |
| " ('u', 'y')]\n", | |
| "\n", | |
| "G1 = {'y':{}}\n", | |
| "for v1, v2 in edges1:\n", | |
| " make_link(G1, v1, v2)\n", | |
| "\n", | |
| "print G1\n", | |
| "display_graph(G1, {})" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 4, | |
| "metadata": { | |
| "collapsed": false | |
| }, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "Number of visited nodes: 8\n", | |
| "{'s': 'black', 'r': 'black', 'u': 'black', 't': 'black', 'w': 'black', 'v': 'black', 'y': 'black', 'x': 'black'}\n" | |
| ] | |
| }, | |
| { | |
| "data": { | |
| "image/svg+xml": [ | |
| "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n", | |
| "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n", | |
| " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n", | |
| "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\n", | |
| " -->\n", | |
| "<!-- Title: %3 Pages: 1 -->\n", | |
| "<svg width=\"178pt\" height=\"252pt\"\n", | |
| " viewBox=\"0.00 0.00 178.37 252.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n", | |
| "<g id=\"graph0\" class=\"graph\" transform=\"scale(0.759036 0.759036) rotate(0) translate(4 328)\">\n", | |
| "<title>%3</title>\n", | |
| "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-328 231,-328 231,4 -4,4\"/>\n", | |
| "<!-- s -->\n", | |
| "<g id=\"node1\" class=\"node\"><title>s</title>\n", | |
| "<ellipse fill=\"black\" stroke=\"black\" cx=\"128\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"128\" y=\"-229.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"white\">s</text>\n", | |
| "</g>\n", | |
| "<!-- w -->\n", | |
| "<g id=\"node5\" class=\"node\"><title>w</title>\n", | |
| "<ellipse fill=\"black\" stroke=\"black\" cx=\"120\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"120\" y=\"-157.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"white\">w</text>\n", | |
| "</g>\n", | |
| "<!-- s--w -->\n", | |
| "<g id=\"edge1\" class=\"edge\"><title>s--w</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M126.022,-215.697C124.782,-204.846 123.19,-190.917 121.955,-180.104\"/>\n", | |
| "</g>\n", | |
| "<!-- r -->\n", | |
| "<g id=\"node2\" class=\"node\"><title>r</title>\n", | |
| "<ellipse fill=\"black\" stroke=\"black\" cx=\"164\" cy=\"-306\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"164\" y=\"-301.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"white\">r</text>\n", | |
| "</g>\n", | |
| "<!-- r--s -->\n", | |
| "<g id=\"edge2\" class=\"edge\"><title>r--s</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M155.65,-288.765C149.835,-277.456 142.11,-262.437 136.304,-251.147\"/>\n", | |
| "</g>\n", | |
| "<!-- v -->\n", | |
| "<g id=\"node6\" class=\"node\"><title>v</title>\n", | |
| "<ellipse fill=\"black\" stroke=\"black\" cx=\"200\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"200\" y=\"-229.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"white\">v</text>\n", | |
| "</g>\n", | |
| "<!-- r--v -->\n", | |
| "<g id=\"edge3\" class=\"edge\"><title>r--v</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M172.35,-288.765C178.165,-277.456 185.89,-262.437 191.696,-251.147\"/>\n", | |
| "</g>\n", | |
| "<!-- u -->\n", | |
| "<g id=\"node3\" class=\"node\"><title>u</title>\n", | |
| "<ellipse fill=\"black\" stroke=\"black\" cx=\"27\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"27\" y=\"-85.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"white\">u</text>\n", | |
| "</g>\n", | |
| "<!-- y -->\n", | |
| "<g id=\"node7\" class=\"node\"><title>y</title>\n", | |
| "<ellipse fill=\"black\" stroke=\"black\" cx=\"63\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"63\" y=\"-13.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"white\">y</text>\n", | |
| "</g>\n", | |
| "<!-- u--y -->\n", | |
| "<g id=\"edge4\" class=\"edge\"><title>u--y</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M35.3496,-72.7646C41.1655,-61.456 48.8897,-46.4367 54.6957,-35.1473\"/>\n", | |
| "</g>\n", | |
| "<!-- t -->\n", | |
| "<g id=\"node4\" class=\"node\"><title>t</title>\n", | |
| "<ellipse fill=\"black\" stroke=\"black\" cx=\"56\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"56\" y=\"-229.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"white\">t</text>\n", | |
| "</g>\n", | |
| "<!-- t--u -->\n", | |
| "<g id=\"edge6\" class=\"edge\"><title>t--u</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M52.5019,-215.871C46.928,-188.578 36.0922,-135.52 30.5105,-108.189\"/>\n", | |
| "</g>\n", | |
| "<!-- t--w -->\n", | |
| "<g id=\"edge7\" class=\"edge\"><title>t--w</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M69.5728,-218.155C80.4338,-206.276 95.591,-189.697 106.447,-177.824\"/>\n", | |
| "</g>\n", | |
| "<!-- x -->\n", | |
| "<g id=\"node8\" class=\"node\"><title>x</title>\n", | |
| "<ellipse fill=\"black\" stroke=\"black\" cx=\"99\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"99\" y=\"-85.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"white\">x</text>\n", | |
| "</g>\n", | |
| "<!-- t--x -->\n", | |
| "<g id=\"edge5\" class=\"edge\"><title>t--x</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M61.1015,-216.153C69.3773,-188.824 85.6337,-135.14 93.9051,-107.825\"/>\n", | |
| "</g>\n", | |
| "<!-- w--x -->\n", | |
| "<g id=\"edge8\" class=\"edge\"><title>w--x</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M114.916,-144.055C111.615,-133.049 107.329,-118.764 104.037,-107.789\"/>\n", | |
| "</g>\n", | |
| "<!-- x--y -->\n", | |
| "<g id=\"edge9\" class=\"edge\"><title>x--y</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M90.6504,-72.7646C84.8345,-61.456 77.1103,-46.4367 71.3043,-35.1473\"/>\n", | |
| "</g>\n", | |
| "</g>\n", | |
| "</svg>\n" | |
| ], | |
| "text/plain": [ | |
| "<graphviz.dot.Graph at 0x103e55790>" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "output_type": "display_data" | |
| } | |
| ], | |
| "source": [ | |
| "# Initialization of 'color' array\n", | |
| "color = {}\n", | |
| "for v in G1:\n", | |
| " color[v] = 'white'\n", | |
| " \n", | |
| "# Run DFS starting from node 's'\n", | |
| "num_nodes = DFS_Visit(G1, 's', color)\n", | |
| "\n", | |
| "print \"Number of visited nodes:\", num_nodes\n", | |
| "\n", | |
| "print color\n", | |
| "display_graph(G1, color)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "Como se puede ver, la función visitó los 8 nodos del grafo y por lo tanto su color final es negro. \n", | |
| "\n", | |
| "### Componentes conexas\n", | |
| "\n", | |
| "Una componente conexa de un grafo no dirigido es un subgrafo (maximal) en el cual todos los vértices están conectados. La siguiente función calcula el número de componentes conexas.\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 5, | |
| "metadata": { | |
| "collapsed": false, | |
| "scrolled": true | |
| }, | |
| "outputs": [ | |
| { | |
| "data": { | |
| "image/svg+xml": [ | |
| "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n", | |
| "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n", | |
| " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n", | |
| "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\n", | |
| " -->\n", | |
| "<!-- Title: %3 Pages: 1 -->\n", | |
| "<svg width=\"252pt\" height=\"155pt\"\n", | |
| " viewBox=\"0.00 0.00 252.00 155.33\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n", | |
| "<g id=\"graph0\" class=\"graph\" transform=\"scale(0.82623 0.82623) rotate(0) translate(4 184)\">\n", | |
| "<title>%3</title>\n", | |
| "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-184 301,-184 301,4 -4,4\"/>\n", | |
| "<!-- s -->\n", | |
| "<g id=\"node1\" class=\"node\"><title>s</title>\n", | |
| "<ellipse fill=\"black\" stroke=\"black\" cx=\"27\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"27\" y=\"-85.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"white\">s</text>\n", | |
| "</g>\n", | |
| "<!-- r -->\n", | |
| "<g id=\"node2\" class=\"node\"><title>r</title>\n", | |
| "<ellipse fill=\"black\" stroke=\"black\" cx=\"63\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"63\" y=\"-157.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"white\">r</text>\n", | |
| "</g>\n", | |
| "<!-- r--s -->\n", | |
| "<g id=\"edge1\" class=\"edge\"><title>r--s</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M54.6504,-144.765C48.8345,-133.456 41.1103,-118.437 35.3043,-107.147\"/>\n", | |
| "</g>\n", | |
| "<!-- v -->\n", | |
| "<g id=\"node6\" class=\"node\"><title>v</title>\n", | |
| "<ellipse fill=\"black\" stroke=\"black\" cx=\"99\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"99\" y=\"-85.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"white\">v</text>\n", | |
| "</g>\n", | |
| "<!-- r--v -->\n", | |
| "<g id=\"edge2\" class=\"edge\"><title>r--v</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M71.3496,-144.765C77.1655,-133.456 84.8897,-118.437 90.6957,-107.147\"/>\n", | |
| "</g>\n", | |
| "<!-- u -->\n", | |
| "<g id=\"node3\" class=\"node\"><title>u</title>\n", | |
| "<ellipse fill=\"black\" stroke=\"black\" cx=\"171\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"171\" y=\"-157.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"white\">u</text>\n", | |
| "</g>\n", | |
| "<!-- y -->\n", | |
| "<g id=\"node7\" class=\"node\"><title>y</title>\n", | |
| "<ellipse fill=\"black\" stroke=\"black\" cx=\"171\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"171\" y=\"-85.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"white\">y</text>\n", | |
| "</g>\n", | |
| "<!-- u--y -->\n", | |
| "<g id=\"edge3\" class=\"edge\"><title>u--y</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M171,-143.697C171,-132.846 171,-118.917 171,-108.104\"/>\n", | |
| "</g>\n", | |
| "<!-- t -->\n", | |
| "<g id=\"node4\" class=\"node\"><title>t</title>\n", | |
| "<ellipse fill=\"black\" stroke=\"black\" cx=\"243\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"243\" y=\"-157.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"white\">t</text>\n", | |
| "</g>\n", | |
| "<!-- w -->\n", | |
| "<g id=\"node5\" class=\"node\"><title>w</title>\n", | |
| "<ellipse fill=\"black\" stroke=\"black\" cx=\"243\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"243\" y=\"-85.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"white\">w</text>\n", | |
| "</g>\n", | |
| "<!-- t--w -->\n", | |
| "<g id=\"edge5\" class=\"edge\"><title>t--w</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M243,-143.697C243,-132.846 243,-118.917 243,-108.104\"/>\n", | |
| "</g>\n", | |
| "<!-- x -->\n", | |
| "<g id=\"node8\" class=\"node\"><title>x</title>\n", | |
| "<ellipse fill=\"black\" stroke=\"black\" cx=\"270\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"270\" y=\"-13.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"white\">x</text>\n", | |
| "</g>\n", | |
| "<!-- t--x -->\n", | |
| "<g id=\"edge4\" class=\"edge\"><title>t--x</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M256.75,-146.069C264.961,-136.1 274.619,-122.247 279,-108 286.486,-83.6555 280.687,-53.9768 275.552,-35.7893\"/>\n", | |
| "</g>\n", | |
| "<!-- w--x -->\n", | |
| "<g id=\"edge6\" class=\"edge\"><title>w--x</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M249.399,-72.411C253.64,-61.4141 259.189,-47.0274 263.46,-35.9562\"/>\n", | |
| "</g>\n", | |
| "</g>\n", | |
| "</svg>\n" | |
| ], | |
| "text/plain": [ | |
| "<graphviz.dot.Graph at 0x103e7c610>" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "output_type": "display_data" | |
| }, | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "v = s\n" | |
| ] | |
| }, | |
| { | |
| "data": { | |
| "image/svg+xml": [ | |
| "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n", | |
| "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n", | |
| " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n", | |
| "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\n", | |
| " -->\n", | |
| "<!-- Title: %3 Pages: 1 -->\n", | |
| "<svg width=\"178pt\" height=\"252pt\"\n", | |
| " viewBox=\"0.00 0.00 178.37 252.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n", | |
| "<g id=\"graph0\" class=\"graph\" transform=\"scale(0.759036 0.759036) rotate(0) translate(4 328)\">\n", | |
| "<title>%3</title>\n", | |
| "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-328 231,-328 231,4 -4,4\"/>\n", | |
| "<!-- s -->\n", | |
| "<g id=\"node1\" class=\"node\"><title>s</title>\n", | |
| "<ellipse fill=\"black\" stroke=\"black\" cx=\"128\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"128\" y=\"-229.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"white\">s</text>\n", | |
| "</g>\n", | |
| "<!-- w -->\n", | |
| "<g id=\"node5\" class=\"node\"><title>w</title>\n", | |
| "<ellipse fill=\"black\" stroke=\"black\" cx=\"120\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"120\" y=\"-157.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"white\">w</text>\n", | |
| "</g>\n", | |
| "<!-- s--w -->\n", | |
| "<g id=\"edge1\" class=\"edge\"><title>s--w</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M126.022,-215.697C124.782,-204.846 123.19,-190.917 121.955,-180.104\"/>\n", | |
| "</g>\n", | |
| "<!-- r -->\n", | |
| "<g id=\"node2\" class=\"node\"><title>r</title>\n", | |
| "<ellipse fill=\"black\" stroke=\"black\" cx=\"164\" cy=\"-306\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"164\" y=\"-301.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"white\">r</text>\n", | |
| "</g>\n", | |
| "<!-- r--s -->\n", | |
| "<g id=\"edge2\" class=\"edge\"><title>r--s</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M155.65,-288.765C149.835,-277.456 142.11,-262.437 136.304,-251.147\"/>\n", | |
| "</g>\n", | |
| "<!-- v -->\n", | |
| "<g id=\"node6\" class=\"node\"><title>v</title>\n", | |
| "<ellipse fill=\"black\" stroke=\"black\" cx=\"200\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"200\" y=\"-229.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"white\">v</text>\n", | |
| "</g>\n", | |
| "<!-- r--v -->\n", | |
| "<g id=\"edge3\" class=\"edge\"><title>r--v</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M172.35,-288.765C178.165,-277.456 185.89,-262.437 191.696,-251.147\"/>\n", | |
| "</g>\n", | |
| "<!-- u -->\n", | |
| "<g id=\"node3\" class=\"node\"><title>u</title>\n", | |
| "<ellipse fill=\"black\" stroke=\"black\" cx=\"27\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"27\" y=\"-85.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"white\">u</text>\n", | |
| "</g>\n", | |
| "<!-- y -->\n", | |
| "<g id=\"node7\" class=\"node\"><title>y</title>\n", | |
| "<ellipse fill=\"black\" stroke=\"black\" cx=\"63\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"63\" y=\"-13.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"white\">y</text>\n", | |
| "</g>\n", | |
| "<!-- u--y -->\n", | |
| "<g id=\"edge4\" class=\"edge\"><title>u--y</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M35.3496,-72.7646C41.1655,-61.456 48.8897,-46.4367 54.6957,-35.1473\"/>\n", | |
| "</g>\n", | |
| "<!-- t -->\n", | |
| "<g id=\"node4\" class=\"node\"><title>t</title>\n", | |
| "<ellipse fill=\"black\" stroke=\"black\" cx=\"56\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"56\" y=\"-229.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"white\">t</text>\n", | |
| "</g>\n", | |
| "<!-- t--u -->\n", | |
| "<g id=\"edge6\" class=\"edge\"><title>t--u</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M52.5019,-215.871C46.928,-188.578 36.0922,-135.52 30.5105,-108.189\"/>\n", | |
| "</g>\n", | |
| "<!-- t--w -->\n", | |
| "<g id=\"edge7\" class=\"edge\"><title>t--w</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M69.5728,-218.155C80.4338,-206.276 95.591,-189.697 106.447,-177.824\"/>\n", | |
| "</g>\n", | |
| "<!-- x -->\n", | |
| "<g id=\"node8\" class=\"node\"><title>x</title>\n", | |
| "<ellipse fill=\"black\" stroke=\"black\" cx=\"99\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"99\" y=\"-85.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"white\">x</text>\n", | |
| "</g>\n", | |
| "<!-- t--x -->\n", | |
| "<g id=\"edge5\" class=\"edge\"><title>t--x</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M61.1015,-216.153C69.3773,-188.824 85.6337,-135.14 93.9051,-107.825\"/>\n", | |
| "</g>\n", | |
| "<!-- w--x -->\n", | |
| "<g id=\"edge8\" class=\"edge\"><title>w--x</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M114.916,-144.055C111.615,-133.049 107.329,-118.764 104.037,-107.789\"/>\n", | |
| "</g>\n", | |
| "<!-- x--y -->\n", | |
| "<g id=\"edge9\" class=\"edge\"><title>x--y</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M90.6504,-72.7646C84.8345,-61.456 77.1103,-46.4367 71.3043,-35.1473\"/>\n", | |
| "</g>\n", | |
| "</g>\n", | |
| "</svg>\n" | |
| ], | |
| "text/plain": [ | |
| "<graphviz.dot.Graph at 0x103e55650>" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "output_type": "display_data" | |
| }, | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "v = r\n", | |
| "v = u\n", | |
| "v = t\n", | |
| "v = w\n", | |
| "v = v\n", | |
| "v = y\n", | |
| "v = x\n", | |
| "1\n", | |
| "v = s\n" | |
| ] | |
| }, | |
| { | |
| "data": { | |
| "image/svg+xml": [ | |
| "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n", | |
| "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n", | |
| " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n", | |
| "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\n", | |
| " -->\n", | |
| "<!-- Title: %3 Pages: 1 -->\n", | |
| "<svg width=\"252pt\" height=\"155pt\"\n", | |
| " viewBox=\"0.00 0.00 252.00 155.33\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n", | |
| "<g id=\"graph0\" class=\"graph\" transform=\"scale(0.82623 0.82623) rotate(0) translate(4 184)\">\n", | |
| "<title>%3</title>\n", | |
| "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-184 301,-184 301,4 -4,4\"/>\n", | |
| "<!-- s -->\n", | |
| "<g id=\"node1\" class=\"node\"><title>s</title>\n", | |
| "<ellipse fill=\"black\" stroke=\"black\" cx=\"27\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"27\" y=\"-85.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"white\">s</text>\n", | |
| "</g>\n", | |
| "<!-- r -->\n", | |
| "<g id=\"node2\" class=\"node\"><title>r</title>\n", | |
| "<ellipse fill=\"black\" stroke=\"black\" cx=\"63\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"63\" y=\"-157.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"white\">r</text>\n", | |
| "</g>\n", | |
| "<!-- r--s -->\n", | |
| "<g id=\"edge1\" class=\"edge\"><title>r--s</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M54.6504,-144.765C48.8345,-133.456 41.1103,-118.437 35.3043,-107.147\"/>\n", | |
| "</g>\n", | |
| "<!-- v -->\n", | |
| "<g id=\"node6\" class=\"node\"><title>v</title>\n", | |
| "<ellipse fill=\"black\" stroke=\"black\" cx=\"99\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"99\" y=\"-85.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"white\">v</text>\n", | |
| "</g>\n", | |
| "<!-- r--v -->\n", | |
| "<g id=\"edge2\" class=\"edge\"><title>r--v</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M71.3496,-144.765C77.1655,-133.456 84.8897,-118.437 90.6957,-107.147\"/>\n", | |
| "</g>\n", | |
| "<!-- u -->\n", | |
| "<g id=\"node3\" class=\"node\"><title>u</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"171\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"171\" y=\"-157.8\" font-family=\"Times,serif\" font-size=\"14.00\">u</text>\n", | |
| "</g>\n", | |
| "<!-- y -->\n", | |
| "<g id=\"node7\" class=\"node\"><title>y</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"171\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"171\" y=\"-85.8\" font-family=\"Times,serif\" font-size=\"14.00\">y</text>\n", | |
| "</g>\n", | |
| "<!-- u--y -->\n", | |
| "<g id=\"edge3\" class=\"edge\"><title>u--y</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M171,-143.697C171,-132.846 171,-118.917 171,-108.104\"/>\n", | |
| "</g>\n", | |
| "<!-- t -->\n", | |
| "<g id=\"node4\" class=\"node\"><title>t</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"243\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"243\" y=\"-157.8\" font-family=\"Times,serif\" font-size=\"14.00\">t</text>\n", | |
| "</g>\n", | |
| "<!-- w -->\n", | |
| "<g id=\"node5\" class=\"node\"><title>w</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"243\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"243\" y=\"-85.8\" font-family=\"Times,serif\" font-size=\"14.00\">w</text>\n", | |
| "</g>\n", | |
| "<!-- t--w -->\n", | |
| "<g id=\"edge5\" class=\"edge\"><title>t--w</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M243,-143.697C243,-132.846 243,-118.917 243,-108.104\"/>\n", | |
| "</g>\n", | |
| "<!-- x -->\n", | |
| "<g id=\"node8\" class=\"node\"><title>x</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"270\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"270\" y=\"-13.8\" font-family=\"Times,serif\" font-size=\"14.00\">x</text>\n", | |
| "</g>\n", | |
| "<!-- t--x -->\n", | |
| "<g id=\"edge4\" class=\"edge\"><title>t--x</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M256.75,-146.069C264.961,-136.1 274.619,-122.247 279,-108 286.486,-83.6555 280.687,-53.9768 275.552,-35.7893\"/>\n", | |
| "</g>\n", | |
| "<!-- w--x -->\n", | |
| "<g id=\"edge6\" class=\"edge\"><title>w--x</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M249.399,-72.411C253.64,-61.4141 259.189,-47.0274 263.46,-35.9562\"/>\n", | |
| "</g>\n", | |
| "</g>\n", | |
| "</svg>\n" | |
| ], | |
| "text/plain": [ | |
| "<graphviz.dot.Graph at 0x103e556d0>" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "output_type": "display_data" | |
| }, | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "v = r\n", | |
| "v = u\n" | |
| ] | |
| }, | |
| { | |
| "data": { | |
| "image/svg+xml": [ | |
| "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n", | |
| "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n", | |
| " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n", | |
| "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\n", | |
| " -->\n", | |
| "<!-- Title: %3 Pages: 1 -->\n", | |
| "<svg width=\"252pt\" height=\"155pt\"\n", | |
| " viewBox=\"0.00 0.00 252.00 155.33\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n", | |
| "<g id=\"graph0\" class=\"graph\" transform=\"scale(0.82623 0.82623) rotate(0) translate(4 184)\">\n", | |
| "<title>%3</title>\n", | |
| "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-184 301,-184 301,4 -4,4\"/>\n", | |
| "<!-- s -->\n", | |
| "<g id=\"node1\" class=\"node\"><title>s</title>\n", | |
| "<ellipse fill=\"black\" stroke=\"black\" cx=\"27\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"27\" y=\"-85.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"white\">s</text>\n", | |
| "</g>\n", | |
| "<!-- r -->\n", | |
| "<g id=\"node2\" class=\"node\"><title>r</title>\n", | |
| "<ellipse fill=\"black\" stroke=\"black\" cx=\"63\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"63\" y=\"-157.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"white\">r</text>\n", | |
| "</g>\n", | |
| "<!-- r--s -->\n", | |
| "<g id=\"edge1\" class=\"edge\"><title>r--s</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M54.6504,-144.765C48.8345,-133.456 41.1103,-118.437 35.3043,-107.147\"/>\n", | |
| "</g>\n", | |
| "<!-- v -->\n", | |
| "<g id=\"node6\" class=\"node\"><title>v</title>\n", | |
| "<ellipse fill=\"black\" stroke=\"black\" cx=\"99\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"99\" y=\"-85.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"white\">v</text>\n", | |
| "</g>\n", | |
| "<!-- r--v -->\n", | |
| "<g id=\"edge2\" class=\"edge\"><title>r--v</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M71.3496,-144.765C77.1655,-133.456 84.8897,-118.437 90.6957,-107.147\"/>\n", | |
| "</g>\n", | |
| "<!-- u -->\n", | |
| "<g id=\"node3\" class=\"node\"><title>u</title>\n", | |
| "<ellipse fill=\"black\" stroke=\"black\" cx=\"171\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"171\" y=\"-157.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"white\">u</text>\n", | |
| "</g>\n", | |
| "<!-- y -->\n", | |
| "<g id=\"node7\" class=\"node\"><title>y</title>\n", | |
| "<ellipse fill=\"black\" stroke=\"black\" cx=\"171\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"171\" y=\"-85.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"white\">y</text>\n", | |
| "</g>\n", | |
| "<!-- u--y -->\n", | |
| "<g id=\"edge3\" class=\"edge\"><title>u--y</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M171,-143.697C171,-132.846 171,-118.917 171,-108.104\"/>\n", | |
| "</g>\n", | |
| "<!-- t -->\n", | |
| "<g id=\"node4\" class=\"node\"><title>t</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"243\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"243\" y=\"-157.8\" font-family=\"Times,serif\" font-size=\"14.00\">t</text>\n", | |
| "</g>\n", | |
| "<!-- w -->\n", | |
| "<g id=\"node5\" class=\"node\"><title>w</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"243\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"243\" y=\"-85.8\" font-family=\"Times,serif\" font-size=\"14.00\">w</text>\n", | |
| "</g>\n", | |
| "<!-- t--w -->\n", | |
| "<g id=\"edge5\" class=\"edge\"><title>t--w</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M243,-143.697C243,-132.846 243,-118.917 243,-108.104\"/>\n", | |
| "</g>\n", | |
| "<!-- x -->\n", | |
| "<g id=\"node8\" class=\"node\"><title>x</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"270\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"270\" y=\"-13.8\" font-family=\"Times,serif\" font-size=\"14.00\">x</text>\n", | |
| "</g>\n", | |
| "<!-- t--x -->\n", | |
| "<g id=\"edge4\" class=\"edge\"><title>t--x</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M256.75,-146.069C264.961,-136.1 274.619,-122.247 279,-108 286.486,-83.6555 280.687,-53.9768 275.552,-35.7893\"/>\n", | |
| "</g>\n", | |
| "<!-- w--x -->\n", | |
| "<g id=\"edge6\" class=\"edge\"><title>w--x</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M249.399,-72.411C253.64,-61.4141 259.189,-47.0274 263.46,-35.9562\"/>\n", | |
| "</g>\n", | |
| "</g>\n", | |
| "</svg>\n" | |
| ], | |
| "text/plain": [ | |
| "<graphviz.dot.Graph at 0x103e556d0>" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "output_type": "display_data" | |
| }, | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "v = t\n" | |
| ] | |
| }, | |
| { | |
| "data": { | |
| "image/svg+xml": [ | |
| "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n", | |
| "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n", | |
| " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n", | |
| "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\n", | |
| " -->\n", | |
| "<!-- Title: %3 Pages: 1 -->\n", | |
| "<svg width=\"252pt\" height=\"155pt\"\n", | |
| " viewBox=\"0.00 0.00 252.00 155.33\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n", | |
| "<g id=\"graph0\" class=\"graph\" transform=\"scale(0.82623 0.82623) rotate(0) translate(4 184)\">\n", | |
| "<title>%3</title>\n", | |
| "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-184 301,-184 301,4 -4,4\"/>\n", | |
| "<!-- s -->\n", | |
| "<g id=\"node1\" class=\"node\"><title>s</title>\n", | |
| "<ellipse fill=\"black\" stroke=\"black\" cx=\"27\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"27\" y=\"-85.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"white\">s</text>\n", | |
| "</g>\n", | |
| "<!-- r -->\n", | |
| "<g id=\"node2\" class=\"node\"><title>r</title>\n", | |
| "<ellipse fill=\"black\" stroke=\"black\" cx=\"63\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"63\" y=\"-157.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"white\">r</text>\n", | |
| "</g>\n", | |
| "<!-- r--s -->\n", | |
| "<g id=\"edge1\" class=\"edge\"><title>r--s</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M54.6504,-144.765C48.8345,-133.456 41.1103,-118.437 35.3043,-107.147\"/>\n", | |
| "</g>\n", | |
| "<!-- v -->\n", | |
| "<g id=\"node6\" class=\"node\"><title>v</title>\n", | |
| "<ellipse fill=\"black\" stroke=\"black\" cx=\"99\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"99\" y=\"-85.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"white\">v</text>\n", | |
| "</g>\n", | |
| "<!-- r--v -->\n", | |
| "<g id=\"edge2\" class=\"edge\"><title>r--v</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M71.3496,-144.765C77.1655,-133.456 84.8897,-118.437 90.6957,-107.147\"/>\n", | |
| "</g>\n", | |
| "<!-- u -->\n", | |
| "<g id=\"node3\" class=\"node\"><title>u</title>\n", | |
| "<ellipse fill=\"black\" stroke=\"black\" cx=\"171\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"171\" y=\"-157.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"white\">u</text>\n", | |
| "</g>\n", | |
| "<!-- y -->\n", | |
| "<g id=\"node7\" class=\"node\"><title>y</title>\n", | |
| "<ellipse fill=\"black\" stroke=\"black\" cx=\"171\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"171\" y=\"-85.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"white\">y</text>\n", | |
| "</g>\n", | |
| "<!-- u--y -->\n", | |
| "<g id=\"edge3\" class=\"edge\"><title>u--y</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M171,-143.697C171,-132.846 171,-118.917 171,-108.104\"/>\n", | |
| "</g>\n", | |
| "<!-- t -->\n", | |
| "<g id=\"node4\" class=\"node\"><title>t</title>\n", | |
| "<ellipse fill=\"black\" stroke=\"black\" cx=\"243\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"243\" y=\"-157.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"white\">t</text>\n", | |
| "</g>\n", | |
| "<!-- w -->\n", | |
| "<g id=\"node5\" class=\"node\"><title>w</title>\n", | |
| "<ellipse fill=\"black\" stroke=\"black\" cx=\"243\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"243\" y=\"-85.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"white\">w</text>\n", | |
| "</g>\n", | |
| "<!-- t--w -->\n", | |
| "<g id=\"edge5\" class=\"edge\"><title>t--w</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M243,-143.697C243,-132.846 243,-118.917 243,-108.104\"/>\n", | |
| "</g>\n", | |
| "<!-- x -->\n", | |
| "<g id=\"node8\" class=\"node\"><title>x</title>\n", | |
| "<ellipse fill=\"black\" stroke=\"black\" cx=\"270\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"270\" y=\"-13.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"white\">x</text>\n", | |
| "</g>\n", | |
| "<!-- t--x -->\n", | |
| "<g id=\"edge4\" class=\"edge\"><title>t--x</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M256.75,-146.069C264.961,-136.1 274.619,-122.247 279,-108 286.486,-83.6555 280.687,-53.9768 275.552,-35.7893\"/>\n", | |
| "</g>\n", | |
| "<!-- w--x -->\n", | |
| "<g id=\"edge6\" class=\"edge\"><title>w--x</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M249.399,-72.411C253.64,-61.4141 259.189,-47.0274 263.46,-35.9562\"/>\n", | |
| "</g>\n", | |
| "</g>\n", | |
| "</svg>\n" | |
| ], | |
| "text/plain": [ | |
| "<graphviz.dot.Graph at 0x103e556d0>" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "output_type": "display_data" | |
| }, | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "v = w\n", | |
| "v = v\n", | |
| "v = y\n", | |
| "v = x\n", | |
| "3\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "def connected_components(G):\n", | |
| " color = {}\n", | |
| " for v in G:\n", | |
| " color[v] = 'white'\n", | |
| " count = 0\n", | |
| " for v in G:\n", | |
| " print 'v = ', v \n", | |
| " if color[v] == 'white':\n", | |
| " count += 1\n", | |
| " DFS_Visit(G, v, color)\n", | |
| " display_graph(G, color)\n", | |
| " return count\n", | |
| "\n", | |
| "edges3 = [('v', 'r'), ('r', 's'), ('w', 't'), \n", | |
| " ('w', 'x'), ('t', 'x'),\n", | |
| " ('u', 'y')]\n", | |
| "G3 = {}\n", | |
| "for v1, v2 in edges3:\n", | |
| " make_link(G3, v1, v2)\n", | |
| "display_graph(G3, color) \n", | |
| "\n", | |
| "print connected_components(G1)\n", | |
| "print connected_components(G3)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "### Conectividad\n", | |
| "\n", | |
| "Podemos usar DFS para determinar si hay un camino que conecte dos nodos:" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 6, | |
| "metadata": { | |
| "collapsed": false | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "def connected(G, v1, v2):\n", | |
| " color = {}\n", | |
| " for v in G1:\n", | |
| " color[v] = 'white'\n", | |
| " DFS_Visit(G, v1, color)\n", | |
| " return color[v2] == 'black'\n", | |
| " " | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "Vamos a probarla sobre el grafo inicial, pero al cual se le ha removido el arco que conecta los nodos 's' y 'w'." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 7, | |
| "metadata": { | |
| "collapsed": false | |
| }, | |
| "outputs": [ | |
| { | |
| "data": { | |
| "image/svg+xml": [ | |
| "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n", | |
| "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n", | |
| " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n", | |
| "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\n", | |
| " -->\n", | |
| "<!-- Title: %3 Pages: 1 -->\n", | |
| "<svg width=\"252pt\" height=\"251pt\"\n", | |
| " viewBox=\"0.00 0.00 252.00 251.03\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n", | |
| "<g id=\"graph0\" class=\"graph\" transform=\"scale(0.965517 0.965517) rotate(0) translate(4 256)\">\n", | |
| "<title>%3</title>\n", | |
| "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-256 257,-256 257,4 -4,4\"/>\n", | |
| "<!-- s -->\n", | |
| "<g id=\"node1\" class=\"node\"><title>s</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"27\" y=\"-157.8\" font-family=\"Times,serif\" font-size=\"14.00\">s</text>\n", | |
| "</g>\n", | |
| "<!-- r -->\n", | |
| "<g id=\"node2\" class=\"node\"><title>r</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"63\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"63\" y=\"-229.8\" font-family=\"Times,serif\" font-size=\"14.00\">r</text>\n", | |
| "</g>\n", | |
| "<!-- r--s -->\n", | |
| "<g id=\"edge1\" class=\"edge\"><title>r--s</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M54.6504,-216.765C48.8345,-205.456 41.1103,-190.437 35.3043,-179.147\"/>\n", | |
| "</g>\n", | |
| "<!-- v -->\n", | |
| "<g id=\"node6\" class=\"node\"><title>v</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"99\" y=\"-157.8\" font-family=\"Times,serif\" font-size=\"14.00\">v</text>\n", | |
| "</g>\n", | |
| "<!-- r--v -->\n", | |
| "<g id=\"edge2\" class=\"edge\"><title>r--v</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M71.3496,-216.765C77.1655,-205.456 84.8897,-190.437 90.6957,-179.147\"/>\n", | |
| "</g>\n", | |
| "<!-- u -->\n", | |
| "<g id=\"node3\" class=\"node\"><title>u</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"154\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"154\" y=\"-85.8\" font-family=\"Times,serif\" font-size=\"14.00\">u</text>\n", | |
| "</g>\n", | |
| "<!-- y -->\n", | |
| "<g id=\"node7\" class=\"node\"><title>y</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"190\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"190\" y=\"-13.8\" font-family=\"Times,serif\" font-size=\"14.00\">y</text>\n", | |
| "</g>\n", | |
| "<!-- u--y -->\n", | |
| "<g id=\"edge3\" class=\"edge\"><title>u--y</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M162.35,-72.7646C168.165,-61.456 175.89,-46.4367 181.696,-35.1473\"/>\n", | |
| "</g>\n", | |
| "<!-- t -->\n", | |
| "<g id=\"node4\" class=\"node\"><title>t</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"209\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"209\" y=\"-229.8\" font-family=\"Times,serif\" font-size=\"14.00\">t</text>\n", | |
| "</g>\n", | |
| "<!-- t--u -->\n", | |
| "<g id=\"edge5\" class=\"edge\"><title>t--u</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M196.252,-217.702C188.441,-207.587 178.852,-193.708 173,-180 162.826,-156.17 157.89,-126.346 155.656,-107.988\"/>\n", | |
| "</g>\n", | |
| "<!-- w -->\n", | |
| "<g id=\"node5\" class=\"node\"><title>w</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"209\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"209\" y=\"-157.8\" font-family=\"Times,serif\" font-size=\"14.00\">w</text>\n", | |
| "</g>\n", | |
| "<!-- t--w -->\n", | |
| "<g id=\"edge6\" class=\"edge\"><title>t--w</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M209,-215.697C209,-204.846 209,-190.917 209,-180.104\"/>\n", | |
| "</g>\n", | |
| "<!-- x -->\n", | |
| "<g id=\"node8\" class=\"node\"><title>x</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"226\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"226\" y=\"-85.8\" font-family=\"Times,serif\" font-size=\"14.00\">x</text>\n", | |
| "</g>\n", | |
| "<!-- t--x -->\n", | |
| "<g id=\"edge4\" class=\"edge\"><title>t--x</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M222.75,-218.069C230.961,-208.1 240.619,-194.247 245,-180 252.662,-155.082 242.554,-125.313 234.4,-107.297\"/>\n", | |
| "</g>\n", | |
| "<!-- w--x -->\n", | |
| "<g id=\"edge7\" class=\"edge\"><title>w--x</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M213.115,-144.055C215.749,-133.211 219.156,-119.183 221.805,-108.275\"/>\n", | |
| "</g>\n", | |
| "<!-- x--y -->\n", | |
| "<g id=\"edge8\" class=\"edge\"><title>x--y</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M217.65,-72.7646C211.835,-61.456 204.11,-46.4367 198.304,-35.1473\"/>\n", | |
| "</g>\n", | |
| "</g>\n", | |
| "</svg>\n" | |
| ], | |
| "text/plain": [ | |
| "<graphviz.dot.Graph at 0x103e7c750>" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "output_type": "display_data" | |
| }, | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "True\n", | |
| "False\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "edges2 = [('v', 'r'), ('r', 's'), ('w', 't'), \n", | |
| " ('w', 'x'), ('t', 'x'), ('t', 'u'), ('x', 'y'),\n", | |
| " ('u', 'y')]\n", | |
| "\n", | |
| "G2 = {}\n", | |
| "for v1, v2 in edges2:\n", | |
| " make_link(G2, v1, v2)\n", | |
| "\n", | |
| "display_graph(G2)\n", | |
| "\n", | |
| "print connected(G2, 'v', 's')\n", | |
| "print connected(G2, 'v', 'y')" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "### Camino entre dos nodos\n", | |
| "\n", | |
| "Para poder calcular el camino entre dos vértices encontrado por DFS, necesitamos llevar un registro del orden en que se visitan los vértices, en particular a través de que vértice se llegó a otro vértice. Esto se llevará a cabo con una arreglo adicional, `parent`, el cual indicará para cada vértice el nodo a través del cual fue alcanzado, es decir su padre.\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 8, | |
| "metadata": { | |
| "collapsed": false | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "def DFS_Visit_p(G, node, color, parent):\n", | |
| " color[node] = 'gray'\n", | |
| " total_marked = 1\n", | |
| " for neighbor in G[node]:\n", | |
| " if color[neighbor] == 'white':\n", | |
| " parent[neighbor] = node\n", | |
| " total_marked += DFS_Visit_p(G, neighbor, color, parent)\n", | |
| " color[node] = 'black'\n", | |
| " return total_marked" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 9, | |
| "metadata": { | |
| "collapsed": false | |
| }, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "{'s': None, 'r': 's', 'u': 'y', 't': 'u', 'w': 's', 'v': 'r', 'y': 'x', 'x': 'w'}\n" | |
| ] | |
| }, | |
| { | |
| "data": { | |
| "image/svg+xml": [ | |
| "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n", | |
| "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n", | |
| " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n", | |
| "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\n", | |
| " -->\n", | |
| "<!-- Title: %3 Pages: 1 -->\n", | |
| "<svg width=\"60pt\" height=\"180pt\"\n", | |
| " viewBox=\"0.00 0.00 59.70 180.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n", | |
| "<g id=\"graph0\" class=\"graph\" transform=\"scale(0.445545 0.445545) rotate(0) translate(4 400)\">\n", | |
| "<title>%3</title>\n", | |
| "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-400 130,-400 130,4 -4,4\"/>\n", | |
| "<!-- s -->\n", | |
| "<g id=\"node1\" class=\"node\"><title>s</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"63\" cy=\"-378\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"63\" y=\"-373.8\" font-family=\"Times,serif\" font-size=\"14.00\">s</text>\n", | |
| "</g>\n", | |
| "<!-- r -->\n", | |
| "<g id=\"node2\" class=\"node\"><title>r</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-306\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"27\" y=\"-301.8\" font-family=\"Times,serif\" font-size=\"14.00\">r</text>\n", | |
| "</g>\n", | |
| "<!-- s->r -->\n", | |
| "<g id=\"edge1\" class=\"edge\"><title>s->r</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M54.6504,-360.765C50.2885,-352.283 44.8531,-341.714 39.9587,-332.197\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"42.9904,-330.439 35.3043,-323.147 36.7654,-333.641 42.9904,-330.439\"/>\n", | |
| "</g>\n", | |
| "<!-- w -->\n", | |
| "<g id=\"node6\" class=\"node\"><title>w</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-306\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"99\" y=\"-301.8\" font-family=\"Times,serif\" font-size=\"14.00\">w</text>\n", | |
| "</g>\n", | |
| "<!-- s->w -->\n", | |
| "<g id=\"edge4\" class=\"edge\"><title>s->w</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M71.3496,-360.765C75.7115,-352.283 81.1469,-341.714 86.0413,-332.197\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"89.2346,-333.641 90.6957,-323.147 83.0096,-330.439 89.2346,-333.641\"/>\n", | |
| "</g>\n", | |
| "<!-- v -->\n", | |
| "<g id=\"node7\" class=\"node\"><title>v</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"27\" y=\"-229.8\" font-family=\"Times,serif\" font-size=\"14.00\">v</text>\n", | |
| "</g>\n", | |
| "<!-- r->v -->\n", | |
| "<g id=\"edge5\" class=\"edge\"><title>r->v</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M27,-287.697C27,-279.983 27,-270.712 27,-262.112\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"30.5001,-262.104 27,-252.104 23.5001,-262.104 30.5001,-262.104\"/>\n", | |
| "</g>\n", | |
| "<!-- y -->\n", | |
| "<g id=\"node3\" class=\"node\"><title>y</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"99\" y=\"-157.8\" font-family=\"Times,serif\" font-size=\"14.00\">y</text>\n", | |
| "</g>\n", | |
| "<!-- u -->\n", | |
| "<g id=\"node4\" class=\"node\"><title>u</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"99\" y=\"-85.8\" font-family=\"Times,serif\" font-size=\"14.00\">u</text>\n", | |
| "</g>\n", | |
| "<!-- y->u -->\n", | |
| "<g id=\"edge2\" class=\"edge\"><title>y->u</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M99,-143.697C99,-135.983 99,-126.712 99,-118.112\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"102.5,-118.104 99,-108.104 95.5001,-118.104 102.5,-118.104\"/>\n", | |
| "</g>\n", | |
| "<!-- t -->\n", | |
| "<g id=\"node5\" class=\"node\"><title>t</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"99\" y=\"-13.8\" font-family=\"Times,serif\" font-size=\"14.00\">t</text>\n", | |
| "</g>\n", | |
| "<!-- u->t -->\n", | |
| "<g id=\"edge3\" class=\"edge\"><title>u->t</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M99,-71.6966C99,-63.9827 99,-54.7125 99,-46.1124\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"102.5,-46.1043 99,-36.1043 95.5001,-46.1044 102.5,-46.1043\"/>\n", | |
| "</g>\n", | |
| "<!-- x -->\n", | |
| "<g id=\"node8\" class=\"node\"><title>x</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"99\" y=\"-229.8\" font-family=\"Times,serif\" font-size=\"14.00\">x</text>\n", | |
| "</g>\n", | |
| "<!-- w->x -->\n", | |
| "<g id=\"edge7\" class=\"edge\"><title>w->x</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M99,-287.697C99,-279.983 99,-270.712 99,-262.112\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"102.5,-262.104 99,-252.104 95.5001,-262.104 102.5,-262.104\"/>\n", | |
| "</g>\n", | |
| "<!-- x->y -->\n", | |
| "<g id=\"edge6\" class=\"edge\"><title>x->y</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M99,-215.697C99,-207.983 99,-198.712 99,-190.112\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"102.5,-190.104 99,-180.104 95.5001,-190.104 102.5,-190.104\"/>\n", | |
| "</g>\n", | |
| "</g>\n", | |
| "</svg>\n" | |
| ], | |
| "text/plain": [ | |
| "<graphviz.dot.Digraph at 0x103e55a50>" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "output_type": "display_data" | |
| } | |
| ], | |
| "source": [ | |
| "color = {}\n", | |
| "parent = {}\n", | |
| "for v in G1:\n", | |
| " color[v] = 'white'\n", | |
| " parent[v] = None\n", | |
| "\n", | |
| "DFS_Visit_p(G1, 's', color, parent)\n", | |
| "print parent\n", | |
| "display_parent(parent)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "Para calcular el camino entre dos vértices `v1` y `v2`, invocamos DFS con `v1` como vértice de arranque, y después usamos el arreglo `parent` para calcular el camino en caso de que este exista." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 10, | |
| "metadata": { | |
| "collapsed": false | |
| }, | |
| "outputs": [ | |
| { | |
| "data": { | |
| "image/svg+xml": [ | |
| "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n", | |
| "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n", | |
| " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n", | |
| "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\n", | |
| " -->\n", | |
| "<!-- Title: %3 Pages: 1 -->\n", | |
| "<svg width=\"60pt\" height=\"180pt\"\n", | |
| " viewBox=\"0.00 0.00 59.70 180.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n", | |
| "<g id=\"graph0\" class=\"graph\" transform=\"scale(0.445545 0.445545) rotate(0) translate(4 400)\">\n", | |
| "<title>%3</title>\n", | |
| "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-400 130,-400 130,4 -4,4\"/>\n", | |
| "<!-- w -->\n", | |
| "<g id=\"node1\" class=\"node\"><title>w</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"27\" y=\"-229.8\" font-family=\"Times,serif\" font-size=\"14.00\">w</text>\n", | |
| "</g>\n", | |
| "<!-- s -->\n", | |
| "<g id=\"node2\" class=\"node\"><title>s</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"27\" y=\"-157.8\" font-family=\"Times,serif\" font-size=\"14.00\">s</text>\n", | |
| "</g>\n", | |
| "<!-- w->s -->\n", | |
| "<g id=\"edge1\" class=\"edge\"><title>w->s</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M27,-215.697C27,-207.983 27,-198.712 27,-190.112\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"30.5001,-190.104 27,-180.104 23.5001,-190.104 30.5001,-190.104\"/>\n", | |
| "</g>\n", | |
| "<!-- r -->\n", | |
| "<g id=\"node3\" class=\"node\"><title>r</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"27\" y=\"-85.8\" font-family=\"Times,serif\" font-size=\"14.00\">r</text>\n", | |
| "</g>\n", | |
| "<!-- s->r -->\n", | |
| "<g id=\"edge2\" class=\"edge\"><title>s->r</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M27,-143.697C27,-135.983 27,-126.712 27,-118.112\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"30.5001,-118.104 27,-108.104 23.5001,-118.104 30.5001,-118.104\"/>\n", | |
| "</g>\n", | |
| "<!-- v -->\n", | |
| "<g id=\"node7\" class=\"node\"><title>v</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"27\" y=\"-13.8\" font-family=\"Times,serif\" font-size=\"14.00\">v</text>\n", | |
| "</g>\n", | |
| "<!-- r->v -->\n", | |
| "<g id=\"edge5\" class=\"edge\"><title>r->v</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M27,-71.6966C27,-63.9827 27,-54.7125 27,-46.1124\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"30.5001,-46.1043 27,-36.1043 23.5001,-46.1044 30.5001,-46.1043\"/>\n", | |
| "</g>\n", | |
| "<!-- y -->\n", | |
| "<g id=\"node4\" class=\"node\"><title>y</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"99\" y=\"-229.8\" font-family=\"Times,serif\" font-size=\"14.00\">y</text>\n", | |
| "</g>\n", | |
| "<!-- u -->\n", | |
| "<g id=\"node5\" class=\"node\"><title>u</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"99\" y=\"-157.8\" font-family=\"Times,serif\" font-size=\"14.00\">u</text>\n", | |
| "</g>\n", | |
| "<!-- y->u -->\n", | |
| "<g id=\"edge3\" class=\"edge\"><title>y->u</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M99,-215.697C99,-207.983 99,-198.712 99,-190.112\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"102.5,-190.104 99,-180.104 95.5001,-190.104 102.5,-190.104\"/>\n", | |
| "</g>\n", | |
| "<!-- x -->\n", | |
| "<g id=\"node6\" class=\"node\"><title>x</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"63\" cy=\"-306\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"63\" y=\"-301.8\" font-family=\"Times,serif\" font-size=\"14.00\">x</text>\n", | |
| "</g>\n", | |
| "<!-- x->w -->\n", | |
| "<g id=\"edge4\" class=\"edge\"><title>x->w</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M54.6504,-288.765C50.2885,-280.283 44.8531,-269.714 39.9587,-260.197\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"42.9904,-258.439 35.3043,-251.147 36.7654,-261.641 42.9904,-258.439\"/>\n", | |
| "</g>\n", | |
| "<!-- x->y -->\n", | |
| "<g id=\"edge6\" class=\"edge\"><title>x->y</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M71.3496,-288.765C75.7115,-280.283 81.1469,-269.714 86.0413,-260.197\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"89.2346,-261.641 90.6957,-251.147 83.0096,-258.439 89.2346,-261.641\"/>\n", | |
| "</g>\n", | |
| "<!-- t -->\n", | |
| "<g id=\"node8\" class=\"node\"><title>t</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"63\" cy=\"-378\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"63\" y=\"-373.8\" font-family=\"Times,serif\" font-size=\"14.00\">t</text>\n", | |
| "</g>\n", | |
| "<!-- t->x -->\n", | |
| "<g id=\"edge7\" class=\"edge\"><title>t->x</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M63,-359.697C63,-351.983 63,-342.712 63,-334.112\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"66.5001,-334.104 63,-324.104 59.5001,-334.104 66.5001,-334.104\"/>\n", | |
| "</g>\n", | |
| "</g>\n", | |
| "</svg>\n" | |
| ], | |
| "text/plain": [ | |
| "<graphviz.dot.Digraph at 0x103e7c490>" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "output_type": "display_data" | |
| }, | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "node = s\n", | |
| "node = w\n", | |
| "node = x\n", | |
| "node = t\n", | |
| "node = None\n", | |
| "['t', 'x', 'w', 's', 'r']\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "def path(G, v1, v2):\n", | |
| " color = {}\n", | |
| " parent = {}\n", | |
| " for v in G:\n", | |
| " color[v] = 'white'\n", | |
| " parent[v] = None\n", | |
| " DFS_Visit_p(G, v1, color, parent)\n", | |
| " display_parent(parent)\n", | |
| " node = v2\n", | |
| " pathlist = [node]\n", | |
| " while node <> None:\n", | |
| " node = parent[node]\n", | |
| " print 'node = ', node\n", | |
| " if node <> None:\n", | |
| " pathlist = [node] + pathlist\n", | |
| " if color[v2] == 'black':\n", | |
| " return pathlist # los vértices en pathlist están en orden inverso, [::-1] los invierte\n", | |
| " else:\n", | |
| " return []\n", | |
| "\n", | |
| "print path(G1, 't', 'r')" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "### Versión iterativa\n", | |
| "La versión de DFS anterior es recursiva, sin embargo es posible formular el mismo algoritmo de una manera iterativa:" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 11, | |
| "metadata": { | |
| "collapsed": false | |
| }, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "1\n" | |
| ] | |
| }, | |
| { | |
| "data": { | |
| "text/plain": [ | |
| "[2, 3, 4]" | |
| ] | |
| }, | |
| "execution_count": 11, | |
| "metadata": {}, | |
| "output_type": "execute_result" | |
| } | |
| ], | |
| "source": [ | |
| "lista = [1,2,3,4]\n", | |
| "print lista.pop(0)\n", | |
| "lista" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 12, | |
| "metadata": { | |
| "collapsed": false | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "def DFS_iterative(G, node):\n", | |
| " color = {}\n", | |
| " parent = {}\n", | |
| " for v in G:\n", | |
| " color[v] = 'white'\n", | |
| " color[node] = 'gray'\n", | |
| " parent[node] = None\n", | |
| " nodelist = [node]\n", | |
| " total_marked = 1\n", | |
| " while nodelist <> []:\n", | |
| " u = nodelist.pop()\n", | |
| " print 'Sale:', u \n", | |
| " for neighbor in G[u]:\n", | |
| " if color[neighbor] == 'white':\n", | |
| " color[neighbor] = 'gray'\n", | |
| "# print color\n", | |
| " parent[neighbor] = u\n", | |
| " display_parent(parent)\n", | |
| " nodelist.append(neighbor)\n", | |
| " print 'Pila:', nodelist\n", | |
| " total_marked += 1\n", | |
| " color[u] = 'black'\n", | |
| " return total_marked, parent" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "Probemos el algoritmo en el Grafo 1 definido anteriormente:" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 13, | |
| "metadata": { | |
| "collapsed": false | |
| }, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "Sale: s\n" | |
| ] | |
| }, | |
| { | |
| "data": { | |
| "image/svg+xml": [ | |
| "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n", | |
| "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n", | |
| " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n", | |
| "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\n", | |
| " -->\n", | |
| "<!-- Title: %3 Pages: 1 -->\n", | |
| "<svg width=\"62pt\" height=\"116pt\"\n", | |
| " viewBox=\"0.00 0.00 62.00 116.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n", | |
| "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 112)\">\n", | |
| "<title>%3</title>\n", | |
| "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-112 58,-112 58,4 -4,4\"/>\n", | |
| "<!-- s -->\n", | |
| "<g id=\"node1\" class=\"node\"><title>s</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"27\" y=\"-85.8\" font-family=\"Times,serif\" font-size=\"14.00\">s</text>\n", | |
| "</g>\n", | |
| "<!-- r -->\n", | |
| "<g id=\"node2\" class=\"node\"><title>r</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"27\" y=\"-13.8\" font-family=\"Times,serif\" font-size=\"14.00\">r</text>\n", | |
| "</g>\n", | |
| "<!-- s->r -->\n", | |
| "<g id=\"edge1\" class=\"edge\"><title>s->r</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M27,-71.6966C27,-63.9827 27,-54.7125 27,-46.1124\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"30.5001,-46.1043 27,-36.1043 23.5001,-46.1044 30.5001,-46.1043\"/>\n", | |
| "</g>\n", | |
| "</g>\n", | |
| "</svg>\n" | |
| ], | |
| "text/plain": [ | |
| "<graphviz.dot.Digraph at 0x103e55910>" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "output_type": "display_data" | |
| }, | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "Pila: ['r']\n" | |
| ] | |
| }, | |
| { | |
| "data": { | |
| "image/svg+xml": [ | |
| "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n", | |
| "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n", | |
| " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n", | |
| "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\n", | |
| " -->\n", | |
| "<!-- Title: %3 Pages: 1 -->\n", | |
| "<svg width=\"134pt\" height=\"116pt\"\n", | |
| " viewBox=\"0.00 0.00 134.00 116.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n", | |
| "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 112)\">\n", | |
| "<title>%3</title>\n", | |
| "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-112 130,-112 130,4 -4,4\"/>\n", | |
| "<!-- s -->\n", | |
| "<g id=\"node1\" class=\"node\"><title>s</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"63\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"63\" y=\"-85.8\" font-family=\"Times,serif\" font-size=\"14.00\">s</text>\n", | |
| "</g>\n", | |
| "<!-- r -->\n", | |
| "<g id=\"node2\" class=\"node\"><title>r</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"27\" y=\"-13.8\" font-family=\"Times,serif\" font-size=\"14.00\">r</text>\n", | |
| "</g>\n", | |
| "<!-- s->r -->\n", | |
| "<g id=\"edge1\" class=\"edge\"><title>s->r</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M54.6504,-72.7646C50.2885,-64.2831 44.8531,-53.7144 39.9587,-44.1974\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"42.9904,-42.4395 35.3043,-35.1473 36.7654,-45.6409 42.9904,-42.4395\"/>\n", | |
| "</g>\n", | |
| "<!-- w -->\n", | |
| "<g id=\"node3\" class=\"node\"><title>w</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"99\" y=\"-13.8\" font-family=\"Times,serif\" font-size=\"14.00\">w</text>\n", | |
| "</g>\n", | |
| "<!-- s->w -->\n", | |
| "<g id=\"edge2\" class=\"edge\"><title>s->w</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M71.3496,-72.7646C75.7115,-64.2831 81.1469,-53.7144 86.0413,-44.1974\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"89.2346,-45.6409 90.6957,-35.1473 83.0096,-42.4395 89.2346,-45.6409\"/>\n", | |
| "</g>\n", | |
| "</g>\n", | |
| "</svg>\n" | |
| ], | |
| "text/plain": [ | |
| "<graphviz.dot.Digraph at 0x103e55910>" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "output_type": "display_data" | |
| }, | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "Pila: ['r', 'w']\n", | |
| "Sale: w\n" | |
| ] | |
| }, | |
| { | |
| "data": { | |
| "image/svg+xml": [ | |
| "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n", | |
| "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n", | |
| " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n", | |
| "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\n", | |
| " -->\n", | |
| "<!-- Title: %3 Pages: 1 -->\n", | |
| "<svg width=\"128pt\" height=\"180pt\"\n", | |
| " viewBox=\"0.00 0.00 128.30 180.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n", | |
| "<g id=\"graph0\" class=\"graph\" transform=\"scale(0.957447 0.957447) rotate(0) translate(4 184)\">\n", | |
| "<title>%3</title>\n", | |
| "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-184 130,-184 130,4 -4,4\"/>\n", | |
| "<!-- w -->\n", | |
| "<g id=\"node1\" class=\"node\"><title>w</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"27\" y=\"-85.8\" font-family=\"Times,serif\" font-size=\"14.00\">w</text>\n", | |
| "</g>\n", | |
| "<!-- x -->\n", | |
| "<g id=\"node2\" class=\"node\"><title>x</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"27\" y=\"-13.8\" font-family=\"Times,serif\" font-size=\"14.00\">x</text>\n", | |
| "</g>\n", | |
| "<!-- w->x -->\n", | |
| "<g id=\"edge1\" class=\"edge\"><title>w->x</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M27,-71.6966C27,-63.9827 27,-54.7125 27,-46.1124\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"30.5001,-46.1043 27,-36.1043 23.5001,-46.1044 30.5001,-46.1043\"/>\n", | |
| "</g>\n", | |
| "<!-- s -->\n", | |
| "<g id=\"node3\" class=\"node\"><title>s</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"63\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"63\" y=\"-157.8\" font-family=\"Times,serif\" font-size=\"14.00\">s</text>\n", | |
| "</g>\n", | |
| "<!-- s->w -->\n", | |
| "<g id=\"edge3\" class=\"edge\"><title>s->w</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M54.6504,-144.765C50.2885,-136.283 44.8531,-125.714 39.9587,-116.197\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"42.9904,-114.439 35.3043,-107.147 36.7654,-117.641 42.9904,-114.439\"/>\n", | |
| "</g>\n", | |
| "<!-- r -->\n", | |
| "<g id=\"node4\" class=\"node\"><title>r</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"99\" y=\"-85.8\" font-family=\"Times,serif\" font-size=\"14.00\">r</text>\n", | |
| "</g>\n", | |
| "<!-- s->r -->\n", | |
| "<g id=\"edge2\" class=\"edge\"><title>s->r</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M71.3496,-144.765C75.7115,-136.283 81.1469,-125.714 86.0413,-116.197\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"89.2346,-117.641 90.6957,-107.147 83.0096,-114.439 89.2346,-117.641\"/>\n", | |
| "</g>\n", | |
| "</g>\n", | |
| "</svg>\n" | |
| ], | |
| "text/plain": [ | |
| "<graphviz.dot.Digraph at 0x103e36310>" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "output_type": "display_data" | |
| }, | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "Pila: ['r', 'x']\n" | |
| ] | |
| }, | |
| { | |
| "data": { | |
| "image/svg+xml": [ | |
| "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n", | |
| "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n", | |
| " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n", | |
| "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\n", | |
| " -->\n", | |
| "<!-- Title: %3 Pages: 1 -->\n", | |
| "<svg width=\"163pt\" height=\"180pt\"\n", | |
| " viewBox=\"0.00 0.00 162.77 180.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n", | |
| "<g id=\"graph0\" class=\"graph\" transform=\"scale(0.957447 0.957447) rotate(0) translate(4 184)\">\n", | |
| "<title>%3</title>\n", | |
| "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-184 166,-184 166,4 -4,4\"/>\n", | |
| "<!-- w -->\n", | |
| "<g id=\"node1\" class=\"node\"><title>w</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"63\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"63\" y=\"-85.8\" font-family=\"Times,serif\" font-size=\"14.00\">w</text>\n", | |
| "</g>\n", | |
| "<!-- x -->\n", | |
| "<g id=\"node2\" class=\"node\"><title>x</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"27\" y=\"-13.8\" font-family=\"Times,serif\" font-size=\"14.00\">x</text>\n", | |
| "</g>\n", | |
| "<!-- w->x -->\n", | |
| "<g id=\"edge1\" class=\"edge\"><title>w->x</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M54.6504,-72.7646C50.2885,-64.2831 44.8531,-53.7144 39.9587,-44.1974\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"42.9904,-42.4395 35.3043,-35.1473 36.7654,-45.6409 42.9904,-42.4395\"/>\n", | |
| "</g>\n", | |
| "<!-- t -->\n", | |
| "<g id=\"node5\" class=\"node\"><title>t</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"99\" y=\"-13.8\" font-family=\"Times,serif\" font-size=\"14.00\">t</text>\n", | |
| "</g>\n", | |
| "<!-- w->t -->\n", | |
| "<g id=\"edge3\" class=\"edge\"><title>w->t</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M71.3496,-72.7646C75.7115,-64.2831 81.1469,-53.7144 86.0413,-44.1974\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"89.2346,-45.6409 90.6957,-35.1473 83.0096,-42.4395 89.2346,-45.6409\"/>\n", | |
| "</g>\n", | |
| "<!-- s -->\n", | |
| "<g id=\"node3\" class=\"node\"><title>s</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"99\" y=\"-157.8\" font-family=\"Times,serif\" font-size=\"14.00\">s</text>\n", | |
| "</g>\n", | |
| "<!-- s->w -->\n", | |
| "<g id=\"edge4\" class=\"edge\"><title>s->w</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M90.6504,-144.765C86.2885,-136.283 80.8531,-125.714 75.9587,-116.197\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"78.9904,-114.439 71.3043,-107.147 72.7654,-117.641 78.9904,-114.439\"/>\n", | |
| "</g>\n", | |
| "<!-- r -->\n", | |
| "<g id=\"node4\" class=\"node\"><title>r</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"135\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"135\" y=\"-85.8\" font-family=\"Times,serif\" font-size=\"14.00\">r</text>\n", | |
| "</g>\n", | |
| "<!-- s->r -->\n", | |
| "<g id=\"edge2\" class=\"edge\"><title>s->r</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M107.35,-144.765C111.712,-136.283 117.147,-125.714 122.041,-116.197\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"125.235,-117.641 126.696,-107.147 119.01,-114.439 125.235,-117.641\"/>\n", | |
| "</g>\n", | |
| "</g>\n", | |
| "</svg>\n" | |
| ], | |
| "text/plain": [ | |
| "<graphviz.dot.Digraph at 0x103e36310>" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "output_type": "display_data" | |
| }, | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "Pila: ['r', 'x', 't']\n", | |
| "Sale: t\n" | |
| ] | |
| }, | |
| { | |
| "data": { | |
| "image/svg+xml": [ | |
| "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n", | |
| "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n", | |
| " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n", | |
| "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\n", | |
| " -->\n", | |
| "<!-- Title: %3 Pages: 1 -->\n", | |
| "<svg width=\"118pt\" height=\"180pt\"\n", | |
| " viewBox=\"0.00 0.00 117.69 180.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n", | |
| "<g id=\"graph0\" class=\"graph\" transform=\"scale(0.692308 0.692308) rotate(0) translate(4 256)\">\n", | |
| "<title>%3</title>\n", | |
| "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-256 166,-256 166,4 -4,4\"/>\n", | |
| "<!-- s -->\n", | |
| "<g id=\"node1\" class=\"node\"><title>s</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"63\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"63\" y=\"-229.8\" font-family=\"Times,serif\" font-size=\"14.00\">s</text>\n", | |
| "</g>\n", | |
| "<!-- r -->\n", | |
| "<g id=\"node2\" class=\"node\"><title>r</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"27\" y=\"-157.8\" font-family=\"Times,serif\" font-size=\"14.00\">r</text>\n", | |
| "</g>\n", | |
| "<!-- s->r -->\n", | |
| "<g id=\"edge1\" class=\"edge\"><title>s->r</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M54.6504,-216.765C50.2885,-208.283 44.8531,-197.714 39.9587,-188.197\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"42.9904,-186.439 35.3043,-179.147 36.7654,-189.641 42.9904,-186.439\"/>\n", | |
| "</g>\n", | |
| "<!-- w -->\n", | |
| "<g id=\"node5\" class=\"node\"><title>w</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"99\" y=\"-157.8\" font-family=\"Times,serif\" font-size=\"14.00\">w</text>\n", | |
| "</g>\n", | |
| "<!-- s->w -->\n", | |
| "<g id=\"edge4\" class=\"edge\"><title>s->w</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M71.3496,-216.765C75.7115,-208.283 81.1469,-197.714 86.0413,-188.197\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"89.2346,-189.641 90.6957,-179.147 83.0096,-186.439 89.2346,-189.641\"/>\n", | |
| "</g>\n", | |
| "<!-- t -->\n", | |
| "<g id=\"node3\" class=\"node\"><title>t</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"63\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"63\" y=\"-85.8\" font-family=\"Times,serif\" font-size=\"14.00\">t</text>\n", | |
| "</g>\n", | |
| "<!-- u -->\n", | |
| "<g id=\"node4\" class=\"node\"><title>u</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"63\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"63\" y=\"-13.8\" font-family=\"Times,serif\" font-size=\"14.00\">u</text>\n", | |
| "</g>\n", | |
| "<!-- t->u -->\n", | |
| "<g id=\"edge2\" class=\"edge\"><title>t->u</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M63,-71.6966C63,-63.9827 63,-54.7125 63,-46.1124\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"66.5001,-46.1043 63,-36.1043 59.5001,-46.1044 66.5001,-46.1043\"/>\n", | |
| "</g>\n", | |
| "<!-- w->t -->\n", | |
| "<g id=\"edge3\" class=\"edge\"><title>w->t</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M90.6504,-144.765C86.2885,-136.283 80.8531,-125.714 75.9587,-116.197\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"78.9904,-114.439 71.3043,-107.147 72.7654,-117.641 78.9904,-114.439\"/>\n", | |
| "</g>\n", | |
| "<!-- x -->\n", | |
| "<g id=\"node6\" class=\"node\"><title>x</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"135\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"135\" y=\"-85.8\" font-family=\"Times,serif\" font-size=\"14.00\">x</text>\n", | |
| "</g>\n", | |
| "<!-- w->x -->\n", | |
| "<g id=\"edge5\" class=\"edge\"><title>w->x</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M107.35,-144.765C111.712,-136.283 117.147,-125.714 122.041,-116.197\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"125.235,-117.641 126.696,-107.147 119.01,-114.439 125.235,-117.641\"/>\n", | |
| "</g>\n", | |
| "</g>\n", | |
| "</svg>\n" | |
| ], | |
| "text/plain": [ | |
| "<graphviz.dot.Digraph at 0x103e36310>" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "output_type": "display_data" | |
| }, | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "Pila: ['r', 'x', 'u']\n", | |
| "Sale: u\n" | |
| ] | |
| }, | |
| { | |
| "data": { | |
| "image/svg+xml": [ | |
| "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n", | |
| "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n", | |
| " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n", | |
| "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\n", | |
| " -->\n", | |
| "<!-- Title: %3 Pages: 1 -->\n", | |
| "<svg width=\"92pt\" height=\"180pt\"\n", | |
| " viewBox=\"0.00 0.00 92.17 180.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n", | |
| "<g id=\"graph0\" class=\"graph\" transform=\"scale(0.542169 0.542169) rotate(0) translate(4 328)\">\n", | |
| "<title>%3</title>\n", | |
| "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-328 166,-328 166,4 -4,4\"/>\n", | |
| "<!-- s -->\n", | |
| "<g id=\"node1\" class=\"node\"><title>s</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"63\" cy=\"-306\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"63\" y=\"-301.8\" font-family=\"Times,serif\" font-size=\"14.00\">s</text>\n", | |
| "</g>\n", | |
| "<!-- r -->\n", | |
| "<g id=\"node2\" class=\"node\"><title>r</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"27\" y=\"-229.8\" font-family=\"Times,serif\" font-size=\"14.00\">r</text>\n", | |
| "</g>\n", | |
| "<!-- s->r -->\n", | |
| "<g id=\"edge1\" class=\"edge\"><title>s->r</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M54.6504,-288.765C50.2885,-280.283 44.8531,-269.714 39.9587,-260.197\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"42.9904,-258.439 35.3043,-251.147 36.7654,-261.641 42.9904,-258.439\"/>\n", | |
| "</g>\n", | |
| "<!-- w -->\n", | |
| "<g id=\"node5\" class=\"node\"><title>w</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"99\" y=\"-229.8\" font-family=\"Times,serif\" font-size=\"14.00\">w</text>\n", | |
| "</g>\n", | |
| "<!-- s->w -->\n", | |
| "<g id=\"edge4\" class=\"edge\"><title>s->w</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M71.3496,-288.765C75.7115,-280.283 81.1469,-269.714 86.0413,-260.197\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"89.2346,-261.641 90.6957,-251.147 83.0096,-258.439 89.2346,-261.641\"/>\n", | |
| "</g>\n", | |
| "<!-- t -->\n", | |
| "<g id=\"node3\" class=\"node\"><title>t</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"63\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"63\" y=\"-157.8\" font-family=\"Times,serif\" font-size=\"14.00\">t</text>\n", | |
| "</g>\n", | |
| "<!-- u -->\n", | |
| "<g id=\"node4\" class=\"node\"><title>u</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"63\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"63\" y=\"-85.8\" font-family=\"Times,serif\" font-size=\"14.00\">u</text>\n", | |
| "</g>\n", | |
| "<!-- t->u -->\n", | |
| "<g id=\"edge2\" class=\"edge\"><title>t->u</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M63,-143.697C63,-135.983 63,-126.712 63,-118.112\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"66.5001,-118.104 63,-108.104 59.5001,-118.104 66.5001,-118.104\"/>\n", | |
| "</g>\n", | |
| "<!-- y -->\n", | |
| "<g id=\"node6\" class=\"node\"><title>y</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"63\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"63\" y=\"-13.8\" font-family=\"Times,serif\" font-size=\"14.00\">y</text>\n", | |
| "</g>\n", | |
| "<!-- u->y -->\n", | |
| "<g id=\"edge5\" class=\"edge\"><title>u->y</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M63,-71.6966C63,-63.9827 63,-54.7125 63,-46.1124\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"66.5001,-46.1043 63,-36.1043 59.5001,-46.1044 66.5001,-46.1043\"/>\n", | |
| "</g>\n", | |
| "<!-- w->t -->\n", | |
| "<g id=\"edge3\" class=\"edge\"><title>w->t</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M90.6504,-216.765C86.2885,-208.283 80.8531,-197.714 75.9587,-188.197\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"78.9904,-186.439 71.3043,-179.147 72.7654,-189.641 78.9904,-186.439\"/>\n", | |
| "</g>\n", | |
| "<!-- x -->\n", | |
| "<g id=\"node7\" class=\"node\"><title>x</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"135\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"135\" y=\"-157.8\" font-family=\"Times,serif\" font-size=\"14.00\">x</text>\n", | |
| "</g>\n", | |
| "<!-- w->x -->\n", | |
| "<g id=\"edge6\" class=\"edge\"><title>w->x</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M107.35,-216.765C111.712,-208.283 117.147,-197.714 122.041,-188.197\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"125.235,-189.641 126.696,-179.147 119.01,-186.439 125.235,-189.641\"/>\n", | |
| "</g>\n", | |
| "</g>\n", | |
| "</svg>\n" | |
| ], | |
| "text/plain": [ | |
| "<graphviz.dot.Digraph at 0x103e36310>" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "output_type": "display_data" | |
| }, | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "Pila: ['r', 'x', 'y']\n", | |
| "Sale: y\n", | |
| "Sale: x\n", | |
| "Sale: r\n" | |
| ] | |
| }, | |
| { | |
| "data": { | |
| "image/svg+xml": [ | |
| "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n", | |
| "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n", | |
| " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n", | |
| "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\n", | |
| " -->\n", | |
| "<!-- Title: %3 Pages: 1 -->\n", | |
| "<svg width=\"112pt\" height=\"180pt\"\n", | |
| " viewBox=\"0.00 0.00 111.69 180.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n", | |
| "<g id=\"graph0\" class=\"graph\" transform=\"scale(0.542169 0.542169) rotate(0) translate(4 328)\">\n", | |
| "<title>%3</title>\n", | |
| "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-328 202,-328 202,4 -4,4\"/>\n", | |
| "<!-- s -->\n", | |
| "<g id=\"node1\" class=\"node\"><title>s</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"63\" cy=\"-306\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"63\" y=\"-301.8\" font-family=\"Times,serif\" font-size=\"14.00\">s</text>\n", | |
| "</g>\n", | |
| "<!-- r -->\n", | |
| "<g id=\"node2\" class=\"node\"><title>r</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"27\" y=\"-229.8\" font-family=\"Times,serif\" font-size=\"14.00\">r</text>\n", | |
| "</g>\n", | |
| "<!-- s->r -->\n", | |
| "<g id=\"edge1\" class=\"edge\"><title>s->r</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M54.6504,-288.765C50.2885,-280.283 44.8531,-269.714 39.9587,-260.197\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"42.9904,-258.439 35.3043,-251.147 36.7654,-261.641 42.9904,-258.439\"/>\n", | |
| "</g>\n", | |
| "<!-- w -->\n", | |
| "<g id=\"node5\" class=\"node\"><title>w</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"99\" y=\"-229.8\" font-family=\"Times,serif\" font-size=\"14.00\">w</text>\n", | |
| "</g>\n", | |
| "<!-- s->w -->\n", | |
| "<g id=\"edge4\" class=\"edge\"><title>s->w</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M71.3496,-288.765C75.7115,-280.283 81.1469,-269.714 86.0413,-260.197\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"89.2346,-261.641 90.6957,-251.147 83.0096,-258.439 89.2346,-261.641\"/>\n", | |
| "</g>\n", | |
| "<!-- v -->\n", | |
| "<g id=\"node6\" class=\"node\"><title>v</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"27\" y=\"-157.8\" font-family=\"Times,serif\" font-size=\"14.00\">v</text>\n", | |
| "</g>\n", | |
| "<!-- r->v -->\n", | |
| "<g id=\"edge5\" class=\"edge\"><title>r->v</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M27,-215.697C27,-207.983 27,-198.712 27,-190.112\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"30.5001,-190.104 27,-180.104 23.5001,-190.104 30.5001,-190.104\"/>\n", | |
| "</g>\n", | |
| "<!-- t -->\n", | |
| "<g id=\"node3\" class=\"node\"><title>t</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"99\" y=\"-157.8\" font-family=\"Times,serif\" font-size=\"14.00\">t</text>\n", | |
| "</g>\n", | |
| "<!-- u -->\n", | |
| "<g id=\"node4\" class=\"node\"><title>u</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"99\" y=\"-85.8\" font-family=\"Times,serif\" font-size=\"14.00\">u</text>\n", | |
| "</g>\n", | |
| "<!-- t->u -->\n", | |
| "<g id=\"edge2\" class=\"edge\"><title>t->u</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M99,-143.697C99,-135.983 99,-126.712 99,-118.112\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"102.5,-118.104 99,-108.104 95.5001,-118.104 102.5,-118.104\"/>\n", | |
| "</g>\n", | |
| "<!-- y -->\n", | |
| "<g id=\"node7\" class=\"node\"><title>y</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"99\" y=\"-13.8\" font-family=\"Times,serif\" font-size=\"14.00\">y</text>\n", | |
| "</g>\n", | |
| "<!-- u->y -->\n", | |
| "<g id=\"edge6\" class=\"edge\"><title>u->y</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M99,-71.6966C99,-63.9827 99,-54.7125 99,-46.1124\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"102.5,-46.1043 99,-36.1043 95.5001,-46.1044 102.5,-46.1043\"/>\n", | |
| "</g>\n", | |
| "<!-- w->t -->\n", | |
| "<g id=\"edge3\" class=\"edge\"><title>w->t</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M99,-215.697C99,-207.983 99,-198.712 99,-190.112\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"102.5,-190.104 99,-180.104 95.5001,-190.104 102.5,-190.104\"/>\n", | |
| "</g>\n", | |
| "<!-- x -->\n", | |
| "<g id=\"node8\" class=\"node\"><title>x</title>\n", | |
| "<ellipse fill=\"none\" stroke=\"black\" cx=\"171\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n", | |
| "<text text-anchor=\"middle\" x=\"171\" y=\"-157.8\" font-family=\"Times,serif\" font-size=\"14.00\">x</text>\n", | |
| "</g>\n", | |
| "<!-- w->x -->\n", | |
| "<g id=\"edge7\" class=\"edge\"><title>w->x</title>\n", | |
| "<path fill=\"none\" stroke=\"black\" d=\"M113.57,-218.834C123.75,-208.938 137.524,-195.546 149.031,-184.359\"/>\n", | |
| "<polygon fill=\"black\" stroke=\"black\" points=\"151.474,-186.865 156.204,-177.385 146.595,-181.846 151.474,-186.865\"/>\n", | |
| "</g>\n", | |
| "</g>\n", | |
| "</svg>\n" | |
| ], | |
| "text/plain": [ | |
| "<graphviz.dot.Digraph at 0x103e36310>" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "output_type": "display_data" | |
| }, | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "Pila: ['v']\n", | |
| "Sale: v\n", | |
| "(8, {'s': None, 'r': 's', 'u': 't', 't': 'w', 'w': 's', 'v': 'r', 'y': 'u', 'x': 'w'})\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "print DFS_iterative(G1, 's')" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "Búsqueda en amplitud\n", | |
| "--------------------\n", | |
| "\n", | |
| "En la búsqueda en amplitud se procesan los nodos por niveles, es decir, el primer nodo que se visita es el nodo de arranque 's', segundo los nodos que están a una distancia 1 de 's', después los nodos que están a una distancia 2 de 's' y así sucesivamente. Esto se logra con un cambio simple en el código de la búsqueda en profundidad iterativa:\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 21, | |
| "metadata": { | |
| "collapsed": false | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "def BFS_iterative(G, node):\n", | |
| " color = {}\n", | |
| " depth = {}\n", | |
| " parent = {}\n", | |
| " for v in G:\n", | |
| " color[v] = 'white'\n", | |
| " depth[v] = float('Inf')\n", | |
| " color[node] = 'gray'\n", | |
| " depth[node] = 0\n", | |
| " parent[node] = None\n", | |
| " nodelist = [node]\n", | |
| " total_marked = 1\n", | |
| " while nodelist <> []:\n", | |
| " u = nodelist.pop(0)\n", | |
| " print 'Sale:', u \n", | |
| " for neighbor in G[u]:\n", | |
| " if color[neighbor] == 'white':\n", | |
| " color[neighbor] = 'gray'\n", | |
| " depth[neighbor] = depth[u] + 1\n", | |
| " parent[neighbor] = u\n", | |
| " nodelist.append(neighbor)\n", | |
| " print 'Pila:', nodelist\n", | |
| " total_marked += 1\n", | |
| " color[u] = 'black'\n", | |
| " return total_marked, parent, depth" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 22, | |
| "metadata": { | |
| "collapsed": false | |
| }, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "Sale: s\n", | |
| "Pila: ['r']\n", | |
| "Pila: ['r', 'w']\n", | |
| "Sale: r\n", | |
| "Pila: ['w', 'v']\n", | |
| "Sale: w\n", | |
| "Pila: ['v', 'x']\n", | |
| "Pila: ['v', 'x', 't']\n", | |
| "Sale: v\n", | |
| "Sale: x\n", | |
| "Pila: ['t', 'y']\n", | |
| "Sale: t\n", | |
| "Pila: ['y', 'u']\n", | |
| "Sale: y\n", | |
| "Sale: u\n", | |
| "(8, {'s': None, 'r': 's', 'u': 't', 't': 'w', 'w': 's', 'v': 'r', 'y': 'x', 'x': 'w'}, {'s': 0, 'r': 1, 'u': 3, 't': 2, 'w': 1, 'v': 2, 'y': 3, 'x': 2})\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "print BFS_iterative(G1, 's')\n", | |
| "\n", | |
| "\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 23, | |
| "metadata": { | |
| "collapsed": false | |
| }, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "{'s': None, 'r': 's', 'u': 'y', 't': 'u', 'w': 's', 'v': 'r', 'y': 'x', 'x': 'w'}\n", | |
| "{'s': 1, 'r': 2, 'u': 9, 't': 10, 'w': 6, 'v': 3, 'y': 8, 'x': 7}\n", | |
| "{'s': 16, 'r': 5, 'u': 12, 't': 11, 'w': 15, 'v': 4, 'y': 13, 'x': 14}\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "time = 0\n", | |
| "\n", | |
| "def DFS_Visit_df(G, node, color, parent, d, f):\n", | |
| " global time\n", | |
| " time = time + 1\n", | |
| " d[node] = time\n", | |
| " color[node] = 'gray'\n", | |
| " total_marked = 1\n", | |
| " for neighbor in G[node]:\n", | |
| " if color[neighbor] == 'white':\n", | |
| " parent[neighbor] = node\n", | |
| " total_marked += \\\n", | |
| " DFS_Visit_df(G, neighbor, color, parent, d, f)\n", | |
| " color[node] = 'black'\n", | |
| " time = time + 1\n", | |
| " f[node] = time\n", | |
| " return total_marked\n", | |
| "\n", | |
| "color = {}\n", | |
| "d = {}\n", | |
| "f = {}\n", | |
| "parent = {}\n", | |
| "\n", | |
| "for v in G1:\n", | |
| " color[v] = 'white'\n", | |
| " d[v] = float('Inf')\n", | |
| " f[v] = float('Inf')\n", | |
| " parent[v] = None\n", | |
| "\n", | |
| "DFS_Visit_df(G1, 's', color, parent, d, f)\n", | |
| "\n", | |
| "print parent\n", | |
| "print d\n", | |
| "print f" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "metadata": { | |
| "collapsed": false | |
| }, | |
| "outputs": [], | |
| "source": [] | |
| } | |
| ], | |
| "metadata": { | |
| "kernelspec": { | |
| "display_name": "Python 2", | |
| "language": "python", | |
| "name": "python2" | |
| }, | |
| "language_info": { | |
| "codemirror_mode": { | |
| "name": "ipython", | |
| "version": 2 | |
| }, | |
| "file_extension": ".py", | |
| "mimetype": "text/x-python", | |
| "name": "python", | |
| "nbconvert_exporter": "python", | |
| "pygments_lexer": "ipython2", | |
| "version": "2.7.11" | |
| } | |
| }, | |
| "nbformat": 4, | |
| "nbformat_minor": 0 | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment