TSP_DFS.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "TSP-DFS.ipynb",
      "provenance": [],
      "authorship_tag": "ABX9TyOTRZqPyfoG1YsQiigKrs6A",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/sergionl/TP_complejidad/blob/main/TSP_DFS.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "BmXPNsw3AcFj",
        "outputId": "556e11cb-463c-4b6d-8ccc-8ddbdc9c2801"
      },
      "source": [
        "!git clone https://github.com/lmcanavals/algorithmic_complexity.git"
      ],
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Cloning into 'algorithmic_complexity'...\n",
            "remote: Enumerating objects: 260, done.\u001b[K\n",
            "remote: Counting objects: 100% (260/260), done.\u001b[K\n",
            "remote: Compressing objects: 100% (255/255), done.\u001b[K\n",
            "remote: Total 260 (delta 144), reused 0 (delta 0), pack-reused 0\u001b[K\n",
            "Receiving objects: 100% (260/260), 270.98 KiB | 3.34 MiB/s, done.\n",
            "Resolving deltas: 100% (144/144), done.\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "nV7penC4Apbd"
      },
      "source": [
        "from algorithmic_complexity.aclib import graphstuff as gs\n"
      ],
      "execution_count": 2,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "C1vkhMLgAqcv"
      },
      "source": [
        "import pandas as pd\n",
        "import numpy as np\n",
        "import networkx as nx\n",
        "import math\n",
        "import pdb\n",
        "import random"
      ],
      "execution_count": 82,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "XJCvYPWcjbfC"
      },
      "source": [
        "**DATASET CODE**"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "D6tMlfH6AsTf"
      },
      "source": [
        "url=\"https://raw.githubusercontent.com/lmcanavals/algorithmic_complexity/main/data/poblaciones.csv\"\n",
        "poblacionesDF = pd.read_csv(url)"
      ],
      "execution_count": 4,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 221
        },
        "id": "l_qMEJlFA1E9",
        "outputId": "42741a9b-2f8b-4b47-ab03-52a5545eb212"
      },
      "source": [
        "print(len(poblacionesDF))\n",
        "poblacionesDF.head()"
      ],
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "3757\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/html": [
              "<div>\n",
              "<style scoped>\n",
              "    .dataframe tbody tr th:only-of-type {\n",
              "        vertical-align: middle;\n",
              "    }\n",
              "\n",
              "    .dataframe tbody tr th {\n",
              "        vertical-align: top;\n",
              "    }\n",
              "\n",
              "    .dataframe thead th {\n",
              "        text-align: right;\n",
              "    }\n",
              "</style>\n",
              "<table border=\"1\" class=\"dataframe\">\n",
              "  <thead>\n",
              "    <tr style=\"text-align: right;\">\n",
              "      <th></th>\n",
              "      <th>DEPARTAMENTO</th>\n",
              "      <th>PROVINCIA</th>\n",
              "      <th>DISTRITO</th>\n",
              "      <th>CENTRO POBLADO</th>\n",
              "      <th>LATITUD</th>\n",
              "      <th>LONGITUD</th>\n",
              "      <th>NMI1</th>\n",
              "      <th>NMI2</th>\n",
              "    </tr>\n",
              "  </thead>\n",
              "  <tbody>\n",
              "    <tr>\n",
              "      <th>0</th>\n",
              "      <td>AMAZONAS</td>\n",
              "      <td>BAGUA</td>\n",
              "      <td>ARAMANGO</td>\n",
              "      <td>EL MUYO (C.P.L.)</td>\n",
              "      <td>-5.422545</td>\n",
              "      <td>-78.45299</td>\n",
              "      <td>311</td>\n",
              "      <td>1206</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>1</th>\n",
              "      <td>AMAZONAS</td>\n",
              "      <td>BAGUA</td>\n",
              "      <td>ARAMANGO</td>\n",
              "      <td>RESERVA UJUCANO</td>\n",
              "      <td>-5.427565</td>\n",
              "      <td>-78.444372</td>\n",
              "      <td>44</td>\n",
              "      <td>129</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>2</th>\n",
              "      <td>AMAZONAS</td>\n",
              "      <td>BAGUA</td>\n",
              "      <td>ARAMANGO</td>\n",
              "      <td>TUTUMBEROS</td>\n",
              "      <td>-5.327317</td>\n",
              "      <td>-78.44472</td>\n",
              "      <td>49</td>\n",
              "      <td>179</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>3</th>\n",
              "      <td>AMAZONAS</td>\n",
              "      <td>BAGUA</td>\n",
              "      <td>BAGUA</td>\n",
              "      <td>ALENYA BAJO</td>\n",
              "      <td>-5.682439</td>\n",
              "      <td>-78.495229</td>\n",
              "      <td>3</td>\n",
              "      <td>8</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>4</th>\n",
              "      <td>AMAZONAS</td>\n",
              "      <td>BONGARA</td>\n",
              "      <td>CUISPES</td>\n",
              "      <td>MITOPAMPA</td>\n",
              "      <td>-5.93856</td>\n",
              "      <td>-77.965302</td>\n",
              "      <td>1</td>\n",
              "      <td>4</td>\n",
              "    </tr>\n",
              "  </tbody>\n",
              "</table>\n",
              "</div>"
            ],
            "text/plain": [
              "  DEPARTAMENTO PROVINCIA  DISTRITO  ...    LONGITUD NMI1  NMI2\n",
              "0     AMAZONAS     BAGUA  ARAMANGO  ...   -78.45299  311  1206\n",
              "1     AMAZONAS     BAGUA  ARAMANGO  ...  -78.444372   44   129\n",
              "2     AMAZONAS     BAGUA  ARAMANGO  ...   -78.44472   49   179\n",
              "3     AMAZONAS     BAGUA     BAGUA  ...  -78.495229    3     8\n",
              "4     AMAZONAS   BONGARA   CUISPES  ...  -77.965302    1     4\n",
              "\n",
              "[5 rows x 8 columns]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 5
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "NMSJRCCnA1sG",
        "outputId": "7f45db99-48cd-4497-ed59-10dc72c583a6"
      },
      "source": [
        "nomprovincias = poblacionesDF['PROVINCIA'].unique()\n",
        "print(len(nomprovincias))\n",
        "nomprovincias"
      ],
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "157\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array(['BAGUA', 'BONGARA', 'CHACHAPOYAS', 'UTCUBAMBA', 'ANTONIO RAYMONDI',\n",
              "       'BOLOGNESI', 'CARHUAZ', 'CASMA', 'HUARAZ', 'HUARI', 'HUAYLAS',\n",
              "       'OCROS', 'POMABAMBA', 'RECUAY', 'SANTA', 'SIHUAS', 'YUNGAY',\n",
              "       'ABANCAY', 'ANDAHUAYLAS', 'ANTABAMBA', 'AYMARAES', 'CHINCHEROS',\n",
              "       'GRAU', 'AREQUIPA', 'CAMANA', 'CARAVELI', 'CASTILLA', 'CAYLLOMA',\n",
              "       'CONDESUYOS', 'CANGALLO', 'HUAMANGA', 'HUANCA SANCOS', 'HUANTA',\n",
              "       'LUCANAS', 'PARINACOCHAS', 'VICTOR FAJARDO', 'CAJABAMBA',\n",
              "       'CAJAMARCA', 'CELENDIN', 'CHOTA', 'CONTUMAZA', 'CUTERVO', 'JAEN',\n",
              "       'SAN IGNACIO', 'SAN MARCOS', 'SAN MIGUEL', 'SAN MIMGUEL',\n",
              "       'SANTA CRUZ', 'ACOMAYO', 'CALCA', 'CANAS', 'CANCHIS',\n",
              "       'CHUMBIVILCAS', 'LA CONVENCION', 'PARURO', 'QUISPICANCHI',\n",
              "       'PROVINCIA', 'CASTROVIRREYNA', 'CHURCAMPA', 'HUANCAVELICA',\n",
              "       'HUAYTARA', 'TAYACAJA', 'AMBO', 'DOS DE MAYO', 'DOSDEMAYO',\n",
              "       'HUAMALIES', 'HUANUCO SANTA', 'HUANUCO', 'LAURICOCHA',\n",
              "       'LEONCIO PRADO', 'MARAÑON', 'PUERTO INCA', 'CHINCHA', 'ICA',\n",
              "       'NASCA', 'PALPA', 'PISCO', 'CHANCHAMAYO', 'CHUPACA', 'CONCEPCION',\n",
              "       'HUANCAYO', 'JAUJA', 'JUNIN', 'SATIPO', 'TARMA', 'ASCOPE',\n",
              "       'BOLIVAR', 'CHEPEN', 'GRAN CHIMU', 'JULCAN', 'OTUZCO', 'PACASMAYO',\n",
              "       'PATAZ', 'SANCHEZ CARRION', 'SANTIAGO DE CHUCO', 'TRUJILLO',\n",
              "       'VIRU', 'CHICLAYO', 'FERREÑAFE', 'LAMBAYEQUE', 'BARRANCA',\n",
              "       'CAJATAMBO', 'CAÑETE', 'HUARAL', 'HUAROCHIRI', 'HUAURA', 'LIMA',\n",
              "       'OYON', 'YAUYOS', 'ALTO AMAZONAS', 'LORETO',\n",
              "       'MARISCAL RAMON CASTILLA', 'MAYNAS', 'PUTUMAYO   10', 'REQUENA',\n",
              "       'UCAYALI', 'MANU', 'TAMBOPATA', 'GENERAL SANCHEZ CERRO',\n",
              "       'MARISCAL NIETO', 'DANIEL ALCIDES CARRION', 'OXAPAMPA', 'PASCO',\n",
              "       'AYABACA', 'HUANCABAMBA', 'MORROPON', 'PAITA', 'PIURA', 'SECHURA',\n",
              "       'SULLANA', 'TALARA', 'AZANGARO', 'CARABAYA', 'CHUCUITO',\n",
              "       'EL COLLAO', 'LAMPA', 'MELGAR', 'PUNO', 'SANDIA', 'BELLAVISTA',\n",
              "       'HUALLAGA', 'LAMAS', 'MARISCAL CACERES', 'MOYOBAMBA', 'PICOTA',\n",
              "       'RIOJA', 'SAN MARTIN', 'TOCACHE', 'CANDARAVE', 'JORGE BASADRE',\n",
              "       'TACNA', 'TARATA', 'CONTRALMIRANTE VILLAR', 'TUMBES', 'ZARUMILLA',\n",
              "       'CORONEL PORTILLO', 'PADRE ABAD'], dtype=object)"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 6
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "oBJPZRMEA2Aa",
        "outputId": "bae473c4-16d2-4278-dbaf-497a8662f7b8"
      },
      "source": [
        "provincias = dict()\n",
        "for nom in nomprovincias:\n",
        "  provincias[nom] = poblacionesDF[poblacionesDF['PROVINCIA'] == nom]\n",
        "  print(nom, len(provincias[nom]))"
      ],
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "BAGUA 4\n",
            "BONGARA 8\n",
            "CHACHAPOYAS 1\n",
            "UTCUBAMBA 12\n",
            "ANTONIO RAYMONDI 2\n",
            "BOLOGNESI 5\n",
            "CARHUAZ 20\n",
            "CASMA 14\n",
            "HUARAZ 38\n",
            "HUARI 20\n",
            "HUAYLAS 5\n",
            "OCROS 2\n",
            "POMABAMBA 21\n",
            "RECUAY 28\n",
            "SANTA 22\n",
            "SIHUAS 6\n",
            "YUNGAY 7\n",
            "ABANCAY 41\n",
            "ANDAHUAYLAS 8\n",
            "ANTABAMBA 2\n",
            "AYMARAES 23\n",
            "CHINCHEROS 12\n",
            "GRAU 1\n",
            "AREQUIPA 24\n",
            "CAMANA 16\n",
            "CARAVELI 16\n",
            "CASTILLA 1\n",
            "CAYLLOMA 20\n",
            "CONDESUYOS 3\n",
            "CANGALLO 20\n",
            "HUAMANGA 3\n",
            "HUANCA SANCOS 38\n",
            "HUANTA 7\n",
            "LUCANAS 92\n",
            "PARINACOCHAS 1\n",
            "VICTOR FAJARDO 29\n",
            "CAJABAMBA 10\n",
            "CAJAMARCA 13\n",
            "CELENDIN 16\n",
            "CHOTA 6\n",
            "CONTUMAZA 16\n",
            "CUTERVO 6\n",
            "JAEN 11\n",
            "SAN IGNACIO 2\n",
            "SAN MARCOS 2\n",
            "SAN MIGUEL 13\n",
            "SAN MIMGUEL 1\n",
            "SANTA CRUZ 1\n",
            "ACOMAYO 14\n",
            "CALCA 3\n",
            "CANAS 4\n",
            "CANCHIS 12\n",
            "CHUMBIVILCAS 3\n",
            "LA CONVENCION 13\n",
            "PARURO 14\n",
            "QUISPICANCHI 22\n",
            "PROVINCIA 1\n",
            "CASTROVIRREYNA 49\n",
            "CHURCAMPA 1\n",
            "HUANCAVELICA 6\n",
            "HUAYTARA 32\n",
            "TAYACAJA 1\n",
            "AMBO 37\n",
            "DOS DE MAYO 7\n",
            "DOSDEMAYO 1\n",
            "HUAMALIES 6\n",
            "HUANUCO SANTA 1\n",
            "HUANUCO 27\n",
            "LAURICOCHA 11\n",
            "LEONCIO PRADO 28\n",
            "MARAÑON 12\n",
            "PUERTO INCA 9\n",
            "CHINCHA 1\n",
            "ICA 60\n",
            "NASCA 6\n",
            "PALPA 30\n",
            "PISCO 14\n",
            "CHANCHAMAYO 14\n",
            "CHUPACA 13\n",
            "CONCEPCION 1\n",
            "HUANCAYO 13\n",
            "JAUJA 1\n",
            "JUNIN 2\n",
            "SATIPO 6\n",
            "TARMA 35\n",
            "ASCOPE 67\n",
            "BOLIVAR 15\n",
            "CHEPEN 82\n",
            "GRAN CHIMU 21\n",
            "JULCAN 1\n",
            "OTUZCO 2\n",
            "PACASMAYO 52\n",
            "PATAZ 8\n",
            "SANCHEZ CARRION 6\n",
            "SANTIAGO DE CHUCO 22\n",
            "TRUJILLO 68\n",
            "VIRU 1\n",
            "CHICLAYO 250\n",
            "FERREÑAFE 127\n",
            "LAMBAYEQUE 440\n",
            "BARRANCA 15\n",
            "CAJATAMBO 3\n",
            "CAÑETE 48\n",
            "HUARAL 27\n",
            "HUAROCHIRI 6\n",
            "HUAURA 23\n",
            "LIMA 2\n",
            "OYON 26\n",
            "YAUYOS 22\n",
            "ALTO AMAZONAS 7\n",
            "LORETO 23\n",
            "MARISCAL RAMON CASTILLA 23\n",
            "MAYNAS 70\n",
            "PUTUMAYO   10 3\n",
            "REQUENA 79\n",
            "UCAYALI 19\n",
            "MANU 4\n",
            "TAMBOPATA 1\n",
            "GENERAL SANCHEZ CERRO 25\n",
            "MARISCAL NIETO 24\n",
            "DANIEL ALCIDES CARRION 6\n",
            "OXAPAMPA 4\n",
            "PASCO 33\n",
            "AYABACA 13\n",
            "HUANCABAMBA 46\n",
            "MORROPON 102\n",
            "PAITA 20\n",
            "PIURA 185\n",
            "SECHURA 76\n",
            "SULLANA 56\n",
            "TALARA 6\n",
            "AZANGARO 4\n",
            "CARABAYA 36\n",
            "CHUCUITO 12\n",
            "EL COLLAO 4\n",
            "LAMPA 4\n",
            "MELGAR 7\n",
            "PUNO 5\n",
            "SANDIA 11\n",
            "BELLAVISTA 7\n",
            "HUALLAGA 3\n",
            "LAMAS 7\n",
            "MARISCAL CACERES 8\n",
            "MOYOBAMBA 9\n",
            "PICOTA 10\n",
            "RIOJA 9\n",
            "SAN MARTIN 6\n",
            "TOCACHE 9\n",
            "CANDARAVE 1\n",
            "JORGE BASADRE 7\n",
            "TACNA 11\n",
            "TARATA 14\n",
            "CONTRALMIRANTE VILLAR 15\n",
            "TUMBES 33\n",
            "ZARUMILLA 24\n",
            "CORONEL PORTILLO 159\n",
            "PADRE ABAD 4\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qFFVFiHXA2R0",
        "cellView": "form"
      },
      "source": [
        "#@title Provincia \n",
        "#@markdown Ingrese la provincia\n",
        "\n",
        "no_type_checking = ''\n",
        "nom_distrito = 'PASCO' #@param {type:\"string\"}"
      ],
      "execution_count": 92,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "FDombWg1A2h2",
        "outputId": "2cd63a12-4e0c-4978-eeb9-63211a062717"
      },
      "source": [
        "nomdistritos = provincias[nom_distrito]['DISTRITO'].unique()\n",
        "print(len(nomdistritos))\n",
        "nomdistritos"
      ],
      "execution_count": 93,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "6\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array(['HUACHON', 'HUARIACA', 'NINACACA', 'PAUCARTAMBO', 'TICLACAYAN',\n",
              "       'YANACANCHA'], dtype=object)"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 93
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "v1vYPDvFBFKF",
        "outputId": "2da6dd1c-c807-4c10-963a-f19333e2eea5"
      },
      "source": [
        "distritos = dict()\n",
        "for nom in nomdistritos:\n",
        "  distritos[nom] = provincias['PASCO'][provincias['PASCO']['DISTRITO'] == nom]\n",
        "  print(nom, len(distritos[nom]))"
      ],
      "execution_count": 94,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "HUACHON 2\n",
            "HUARIACA 5\n",
            "NINACACA 1\n",
            "PAUCARTAMBO 11\n",
            "TICLACAYAN 5\n",
            "YANACANCHA 9\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "GrQl8c4iBI9S"
      },
      "source": [
        "distrito = distritos['YANACANCHA']"
      ],
      "execution_count": 95,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "w_P6ujubBFp2"
      },
      "source": [
        "def dist(cp1, cp2):\n",
        "  x1, y1 = float(cp1['LATITUD']), float(cp1['LONGITUD'])\n",
        "  x2, y2 = float(cp2['LATITUD']), float(cp2['LONGITUD'])\n",
        "\n",
        "  return math.sqrt((x1 - x2)**2 + (y1 - y2)**2)"
      ],
      "execution_count": 96,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "rqRIzQHyBF5r",
        "outputId": "9d4f67b7-0651-40b9-f2b8-2a1cd1ceab9a"
      },
      "source": [
        "G = nx.Graph()\n",
        "col = 'CENTRO POBLADO'\n",
        "for i, cp1 in distrito.iterrows():\n",
        "  print(cp1[col])\n",
        "  for j, cp2 in distrito.iterrows():\n",
        "    if cp1[col] != cp2[col]:\n",
        "      G.add_edge(cp1[col], cp2[col], weight=dist(cp1, cp2))"
      ],
      "execution_count": 97,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "HUALANGAYOC\n",
            "LA QUINUA\n",
            "MACAPATA\n",
            "MUYOMUYO\n",
            "NUNUNYAYOC\n",
            "PARIAMARCA\n",
            "QUICHAS\n",
            "SAN MIGUEL\n",
            "SANTA ROSA DE PITIC BAJA\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 628
        },
        "id": "_zT_ubZsBGM8",
        "outputId": "7baf1f41-3e85-4b9c-f01b-7702dfb53ef3"
      },
      "source": [
        "gs.nx2gv(G, weighted=True, params={'size':'15'})"
      ],
      "execution_count": 98,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<graphviz.dot.Graph at 0x7f74dcbc6a10>"
            ],
            "image/svg+xml": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n -->\n<!-- Title: G Pages: 1 -->\n<svg width=\"1080pt\" height=\"440pt\"\n viewBox=\"0.00 0.00 1080.00 439.85\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(.5944 .5944) rotate(0) translate(4 736)\">\n<title>G</title>\n<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-736 1813,-736 1813,4 -4,4\"/>\n<!-- HUALANGAYOC -->\n<g id=\"node1\" class=\"node\">\n<title>HUALANGAYOC</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"643\" cy=\"-714\" rx=\"83.3857\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"643\" y=\"-710.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">HUALANGAYOC</text>\n</g>\n<!-- LA QUINUA -->\n<g id=\"node2\" class=\"node\">\n<title>LA QUINUA</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"562\" cy=\"-627\" rx=\"62.2891\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"562\" y=\"-623.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">LA QUINUA</text>\n</g>\n<!-- HUALANGAYOC&#45;&#45;LA QUINUA -->\n<g id=\"edge1\" class=\"edge\">\n<title>HUALANGAYOC&#45;&#45;LA QUINUA</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M589.4283,-699.9591C579.0225,-694.7546 569.3799,-687.6581 563,-678 556.7521,-668.5418 556.5021,-655.7918 557.8141,-645.4063\"/>\n<text text-anchor=\"middle\" x=\"636.5\" y=\"-666.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0.039023187363412745</text>\n</g>\n<!-- MACAPATA -->\n<g id=\"node3\" class=\"node\">\n<title>MACAPATA</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"1471\" cy=\"-540\" rx=\"61.99\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"1471\" y=\"-536.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">MACAPATA</text>\n</g>\n<!-- HUALANGAYOC&#45;&#45;MACAPATA -->\n<g id=\"edge2\" class=\"edge\">\n<title>HUALANGAYOC&#45;&#45;MACAPATA</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M723.7156,-709.5807C828.6435,-703.4223 1006.0315,-691.4858 1070,-678 1209.941,-648.4977 1368.3907,-584.3124 1436.6881,-555.0646\"/>\n<text text-anchor=\"middle\" x=\"1365.5\" y=\"-623.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0.03343449562951626</text>\n</g>\n<!-- MUYOMUYO -->\n<g id=\"node4\" class=\"node\">\n<title>MUYOMUYO</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"794\" cy=\"-453\" rx=\"68.4888\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"794\" y=\"-449.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">MUYOMUYO</text>\n</g>\n<!-- HUALANGAYOC&#45;&#45;MUYOMUYO -->\n<g id=\"edge3\" class=\"edge\">\n<title>HUALANGAYOC&#45;&#45;MUYOMUYO</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M682.3158,-698.0843C692.2039,-692.7612 702.2079,-686.0785 710,-678 751.2589,-635.2244 755.5391,-615.8865 769,-558 772.6239,-542.4158 777.3342,-535.658 769,-522 759.8885,-507.0683 743.1115,-518.9317 734,-504 730.5274,-498.3092 730.7153,-494.8013 734,-489 738.9677,-480.226 747.0213,-473.3572 755.6375,-468.0804\"/>\n<text text-anchor=\"middle\" x=\"838.5\" y=\"-579.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0.007243888044414451</text>\n</g>\n<!-- NUNUNYAYOC -->\n<g id=\"node5\" class=\"node\">\n<title>NUNUNYAYOC</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"1151\" cy=\"-366\" rx=\"76.8869\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"1151\" y=\"-362.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">NUNUNYAYOC</text>\n</g>\n<!-- HUALANGAYOC&#45;&#45;NUNUNYAYOC -->\n<g id=\"edge4\" class=\"edge\">\n<title>HUALANGAYOC&#45;&#45;NUNUNYAYOC</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M724.9844,-710.9211C883.9597,-704.0799 1221.5344,-684.9634 1255,-645 1265.2724,-632.7331 1256.5766,-624.9221 1255,-609 1252.3203,-581.9376 1246.32,-511.4689 1231,-489 1222.6659,-476.7768 1212.8618,-482.0277 1203,-471 1179.6765,-444.9192 1164.2203,-406.4858 1156.5883,-384.0719\"/>\n<text text-anchor=\"middle\" x=\"1322.5\" y=\"-536.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0.001365438024960333</text>\n</g>\n<!-- PARIAMARCA -->\n<g id=\"node6\" class=\"node\">\n<title>PARIAMARCA</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"956\" cy=\"-279\" rx=\"72.5877\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"956\" y=\"-275.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">PARIAMARCA</text>\n</g>\n<!-- HUALANGAYOC&#45;&#45;PARIAMARCA -->\n<g id=\"edge5\" class=\"edge\">\n<title>HUALANGAYOC&#45;&#45;PARIAMARCA</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M709.6943,-703.1654C812.5706,-684.9401 1002.2867,-644.7999 1042,-591 1045.9593,-585.6364 1046.1112,-581.2481 1042,-576 1021.3928,-549.6944 770.6072,-530.3056 750,-504 745.8888,-498.7519 745.6466,-494.049 750,-489 785.5042,-447.8235 827.2668,-503.3026 871,-471 898.3433,-450.8035 878.7141,-424.7196 904,-402 921.8798,-385.9348 941.0236,-403.556 955,-384 973.2318,-358.4897 967.416,-319.8602 961.6365,-297.2562\"/>\n<text text-anchor=\"middle\" x=\"823.5\" y=\"-492.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0.010020307430412725</text>\n</g>\n<!-- QUICHAS -->\n<g id=\"node7\" class=\"node\">\n<title>QUICHAS</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"573\" cy=\"-192\" rx=\"52.7911\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"573\" y=\"-188.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">QUICHAS</text>\n</g>\n<!-- HUALANGAYOC&#45;&#45;QUICHAS -->\n<g id=\"edge6\" class=\"edge\">\n<title>HUALANGAYOC&#45;&#45;QUICHAS</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M559.957,-712.3018C450.0447,-709.1797 267.6574,-700.6206 247,-678 216.6499,-644.7657 -75.7499,-853.269 363,-435 377.1103,-421.5483 385.5874,-425.7666 403,-417 429.836,-403.4891 442.269,-406.6584 462,-384 500.5369,-339.7454 483.4553,-313.3348 510,-261 517.8639,-245.4958 519.6096,-241.1332 531,-228 537.0407,-221.0351 544.4571,-214.2313 551.368,-208.4473\"/>\n<text text-anchor=\"middle\" x=\"436.5\" y=\"-449.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0.009641835354332457</text>\n</g>\n<!-- SAN MIGUEL -->\n<g id=\"node8\" class=\"node\">\n<title>SAN MIGUEL</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"708\" cy=\"-105\" rx=\"68.7879\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"708\" y=\"-101.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">SAN MIGUEL</text>\n</g>\n<!-- HUALANGAYOC&#45;&#45;SAN MIGUEL -->\n<g id=\"edge7\" class=\"edge\">\n<title>HUALANGAYOC&#45;&#45;SAN MIGUEL</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M586.7025,-700.7216C461.2433,-667.8517 174.1215,-572.7465 232,-402 253.8259,-337.6117 377.1066,-207.9674 436,-174 477.6404,-149.9835 492.4085,-152.83 539,-141 580.6518,-130.4242 591.9971,-132.0814 634,-123 641.7539,-121.3235 649.9382,-119.4441 657.925,-117.549\"/>\n<text text-anchor=\"middle\" x=\"301.5\" y=\"-405.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0.03778526174317589</text>\n</g>\n<!-- SANTA ROSA DE PITIC BAJA -->\n<g id=\"node9\" class=\"node\">\n<title>SANTA ROSA DE PITIC BAJA</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"550\" cy=\"-18\" rx=\"135.6761\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"550\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">SANTA ROSA DE PITIC BAJA</text>\n</g>\n<!-- HUALANGAYOC&#45;&#45;SANTA ROSA DE PITIC BAJA -->\n<g id=\"edge8\" class=\"edge\">\n<title>HUALANGAYOC&#45;&#45;SANTA ROSA DE PITIC BAJA</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M560.5906,-711.3744C436.3491,-706.8858 207.0829,-696.393 127,-678 67.7179,-664.3844 0,-687.8256 0,-627 0,-627 0,-627 0,-105 0,-84.4046 46.7681,-69.3865 113,-54 169.8178,-40.8005 315.2134,-30.5033 422.7744,-24.3638\"/>\n<text text-anchor=\"middle\" x=\"69.5\" y=\"-362.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0.03783556101077597</text>\n</g>\n<!-- LA QUINUA&#45;&#45;MACAPATA -->\n<g id=\"edge9\" class=\"edge\">\n<title>LA QUINUA&#45;&#45;MACAPATA</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M620.931,-620.9012C720.9834,-610.68 930.5077,-589.8522 1108,-576 1235.4187,-566.0557 1268.5834,-576.7953 1395,-558 1404.7908,-556.5443 1415.1776,-554.4552 1425.0245,-552.2122\"/>\n<text text-anchor=\"middle\" x=\"1181.5\" y=\"-579.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0.009172378208517101</text>\n</g>\n<!-- LA QUINUA&#45;&#45;MUYOMUYO -->\n<g id=\"edge10\" class=\"edge\">\n<title>LA QUINUA&#45;&#45;MUYOMUYO</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M570.5305,-608.8973C583.3451,-582.3252 607.5931,-534.5489 622,-522 655.9658,-492.4147 704.2219,-474.5523 740.9801,-464.4391\"/>\n<text text-anchor=\"middle\" x=\"695.5\" y=\"-536.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0.038827837977408186</text>\n</g>\n<!-- LA QUINUA&#45;&#45;NUNUNYAYOC -->\n<g id=\"edge11\" class=\"edge\">\n<title>LA QUINUA&#45;&#45;NUNUNYAYOC</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M607.8635,-614.7514C647.5373,-604.2312 706.4694,-588.7848 758,-576 893.183,-542.461 949.4379,-584.641 1063,-504 1106.3241,-473.2354 1133.3098,-413.7813 1144.7095,-383.9667\"/>\n<text text-anchor=\"middle\" x=\"1153.5\" y=\"-492.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0.039447077521662016</text>\n</g>\n<!-- LA QUINUA&#45;&#45;PARIAMARCA -->\n<g id=\"edge12\" class=\"edge\">\n<title>LA QUINUA&#45;&#45;PARIAMARCA</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M557.2337,-608.8855C548.5137,-571.2016 534.7006,-483.8209 579,-435 608.1708,-402.8518 634.9224,-433.6802 675,-417 748.7535,-386.304 750.5161,-348.5843 823,-315 837.3793,-308.3376 872.5028,-298.9279 903.0449,-291.3995\"/>\n<text text-anchor=\"middle\" x=\"648\" y=\"-449.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0.03611105981551622</text>\n</g>\n<!-- LA QUINUA&#45;&#45;QUICHAS -->\n<g id=\"edge13\" class=\"edge\">\n<title>LA QUINUA&#45;&#45;QUICHAS</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M549.1349,-609.3158C538.1108,-592.3939 524,-565.7121 524,-540 524,-540 524,-540 524,-279 524,-252.1307 541.963,-225.9049 556.137,-209.3934\"/>\n<text text-anchor=\"middle\" x=\"597.5\" y=\"-405.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0.034987446391527295</text>\n</g>\n<!-- LA QUINUA&#45;&#45;SAN MIGUEL -->\n<g id=\"edge14\" class=\"edge\">\n<title>LA QUINUA&#45;&#45;SAN MIGUEL</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M519.8681,-613.5815C463.4259,-593.0595 365.5623,-547.9374 324,-471 316.3953,-456.9227 314.7588,-448.0614 324,-435 337.8831,-415.3776 361.1169,-436.6224 375,-417 378.8505,-411.5577 379.0146,-407.3223 375,-402 357.4638,-378.7517 329.5362,-407.2483 312,-384 302.3649,-371.2264 305.3859,-362.5689 312,-348 375.6035,-207.8989 564.2819,-141.6678 656.3317,-117.0071\"/>\n<text text-anchor=\"middle\" x=\"385\" y=\"-362.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0.011091395088097415</text>\n</g>\n<!-- LA QUINUA&#45;&#45;SANTA ROSA DE PITIC BAJA -->\n<g id=\"edge15\" class=\"edge\">\n<title>LA QUINUA&#45;&#45;SANTA ROSA DE PITIC BAJA</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M510.3873,-616.6934C467.6372,-606.503 406.5699,-588.0126 360,-558 280.6084,-506.835 266.8968,-484.6646 201,-417 173.0495,-388.2997 177.45,-368.4484 143,-348 108.2965,-327.4012 82.7194,-358.352 54,-330 37.4984,-313.7096 43,-302.1879 43,-279 43,-279 43,-279 43,-105 43,-65.8164 281.2771,-39.4694 431.131,-26.7741\"/>\n<text text-anchor=\"middle\" x=\"127.5\" y=\"-318.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0.006830328615823036</text>\n</g>\n<!-- MACAPATA&#45;&#45;MUYOMUYO -->\n<g id=\"edge16\" class=\"edge\">\n<title>MACAPATA&#45;&#45;MUYOMUYO</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M1425.455,-527.696C1415.4869,-525.4296 1404.9422,-523.3542 1395,-522 1291.2153,-507.8634 1023.8125,-535.7582 924,-504 912.3705,-500.2997 911.9826,-494.3218 901,-489 882.1274,-479.8549 860.3384,-472.0654 841.368,-466.096\"/>\n<text text-anchor=\"middle\" x=\"993.5\" y=\"-492.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0.03478315373855731</text>\n</g>\n<!-- MACAPATA&#45;&#45;NUNUNYAYOC -->\n<g id=\"edge17\" class=\"edge\">\n<title>MACAPATA&#45;&#45;NUNUNYAYOC</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M1424.0412,-528.1765C1359.4784,-511.6412 1249.4828,-482.3612 1234,-471 1204.2851,-449.1953 1211.5614,-430.3422 1188,-402 1182.7289,-395.6594 1176.4679,-389.2267 1170.6092,-383.587\"/>\n<text text-anchor=\"middle\" x=\"1306.5\" y=\"-449.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0.034111079915479035</text>\n</g>\n<!-- MACAPATA&#45;&#45;PARIAMARCA -->\n<g id=\"edge18\" class=\"edge\">\n<title>MACAPATA&#45;&#45;PARIAMARCA</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M1441.5445,-524.0045C1432.9599,-518.4295 1424.0133,-511.6333 1417,-504 1393.3134,-478.2197 1407.6278,-455.1526 1379,-435 1337.7739,-405.9787 1306.8284,-447.9116 1267,-417 1240.583,-396.4972 1261.5612,-370.6929 1237,-348 1203.862,-317.3826 1184.727,-326.1132 1141,-315 1094.2621,-303.1216 1081.2936,-306.426 1034,-297 1025.686,-295.3429 1016.9055,-293.4536 1008.3528,-291.5367\"/>\n<text text-anchor=\"middle\" x=\"1340.5\" y=\"-405.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0.032754640358276514</text>\n</g>\n<!-- MACAPATA&#45;&#45;QUICHAS -->\n<g id=\"edge19\" class=\"edge\">\n<title>MACAPATA&#45;&#45;QUICHAS</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M1463.8199,-521.9907C1449.0608,-485.058 1416.4835,-404.0175 1414,-402 1380.3062,-374.629 1352.6989,-410.0851 1318,-384 1269.0662,-347.2136 1306.4051,-295.743 1256,-261 1230.0114,-243.0867 779.198,-207.561 624.5627,-195.8466\"/>\n<text text-anchor=\"middle\" x=\"1387.5\" y=\"-362.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0.03150176034764204</text>\n</g>\n<!-- MACAPATA&#45;&#45;SAN MIGUEL -->\n<g id=\"edge20\" class=\"edge\">\n<title>MACAPATA&#45;&#45;SAN MIGUEL</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M1474.8491,-521.6691C1484.8289,-468.6318 1505.7069,-313.3791 1429,-228 1342.8627,-132.1243 939.9694,-110.9591 776.8384,-106.3048\"/>\n<text text-anchor=\"middle\" x=\"1550.5\" y=\"-318.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0.005323541020791335</text>\n</g>\n<!-- MACAPATA&#45;&#45;SANTA ROSA DE PITIC BAJA -->\n<g id=\"edge21\" class=\"edge\">\n<title>MACAPATA&#45;&#45;SANTA ROSA DE PITIC BAJA</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M1517.431,-527.8616C1571.9395,-512.2156 1655,-483.3884 1655,-453 1655,-453 1655,-453 1655,-105 1655,-56.7562 976.7625,-30.7057 683.0141,-21.6854\"/>\n<text text-anchor=\"middle\" x=\"1732\" y=\"-275.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0.0045002805468097404</text>\n</g>\n<!-- MUYOMUYO&#45;&#45;NUNUNYAYOC -->\n<g id=\"edge22\" class=\"edge\">\n<title>MUYOMUYO&#45;&#45;NUNUNYAYOC</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M828.0722,-437.2805C853.9032,-425.9462 890.5463,-411.0992 924,-402 975.5946,-387.9666 1035.3711,-378.7609 1080.6278,-373.1739\"/>\n<text text-anchor=\"middle\" x=\"997.5\" y=\"-405.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0.006022292669737662</text>\n</g>\n<!-- MUYOMUYO&#45;&#45;PARIAMARCA -->\n<g id=\"edge23\" class=\"edge\">\n<title>MUYOMUYO&#45;&#45;PARIAMARCA</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M791.4843,-434.7383C789.3912,-412.1285 789.2739,-373.493 808,-348 830.0699,-317.9549 868.5175,-300.5702 900.694,-290.767\"/>\n<text text-anchor=\"middle\" x=\"881.5\" y=\"-362.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0.003769803841049788</text>\n</g>\n<!-- MUYOMUYO&#45;&#45;QUICHAS -->\n<g id=\"edge24\" class=\"edge\">\n<title>MUYOMUYO&#45;&#45;QUICHAS</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M759.9913,-437.2989C698.4976,-408.5679 574.1202,-348.7607 563,-330 540.5856,-292.1851 555.3268,-237.9155 565.5565,-210.0397\"/>\n<text text-anchor=\"middle\" x=\"636.5\" y=\"-318.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0.004279599630806023</text>\n</g>\n<!-- MUYOMUYO&#45;&#45;SAN MIGUEL -->\n<g id=\"edge25\" class=\"edge\">\n<title>MUYOMUYO&#45;&#45;SAN MIGUEL</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M784.6677,-434.8949C770.5828,-406.4439 744.5277,-349.1252 735,-297 732.1231,-281.2608 731.6785,-276.6514 735,-261 736.8174,-252.4362 741.1826,-251.5638 743,-243 752.4108,-198.6542 760.053,-183.0037 743,-141 740.18,-134.054 735.3048,-127.7122 730.0735,-122.3524\"/>\n<text text-anchor=\"middle\" x=\"804.5\" y=\"-275.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0.03964532775750961</text>\n</g>\n<!-- MUYOMUYO&#45;&#45;SANTA ROSA DE PITIC BAJA -->\n<g id=\"edge26\" class=\"edge\">\n<title>MUYOMUYO&#45;&#45;SANTA ROSA DE PITIC BAJA</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M746.7616,-439.8508C738.2452,-437.9107 729.4031,-436.173 721,-435 693.1962,-431.119 236.6312,-436.0386 216,-417 184.9257,-388.3245 205,-364.7836 205,-322.5 205,-322.5 205,-322.5 205,-105 205,-57.668 328.6346,-35.8276 427.8804,-25.9205\"/>\n<text text-anchor=\"middle\" x=\"274.5\" y=\"-231.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0.03891382408605139</text>\n</g>\n<!-- NUNUNYAYOC&#45;&#45;PARIAMARCA -->\n<g id=\"edge27\" class=\"edge\">\n<title>NUNUNYAYOC&#45;&#45;PARIAMARCA</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M1085.6672,-356.4445C1048.2257,-350.0024 1005.6459,-340.7359 990,-330 978.2424,-321.9322 969.4779,-308.337 963.7947,-297.2114\"/>\n<text text-anchor=\"middle\" x=\"1063.5\" y=\"-318.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0.009038236221738423</text>\n</g>\n<!-- NUNUNYAYOC&#45;&#45;QUICHAS -->\n<g id=\"edge28\" class=\"edge\">\n<title>NUNUNYAYOC&#45;&#45;QUICHAS</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M1149.5487,-347.8987C1147.9037,-337.3636 1144.4092,-324.3582 1137,-315 1133.1111,-310.0881 1043.8981,-263.1124 1038,-261 962.3186,-233.8947 727.7527,-207.6458 623.6523,-196.9865\"/>\n<text text-anchor=\"middle\" x=\"1180.5\" y=\"-275.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0.008796690855088996</text>\n</g>\n<!-- NUNUNYAYOC&#45;&#45;SAN MIGUEL -->\n<g id=\"edge29\" class=\"edge\">\n<title>NUNUNYAYOC&#45;&#45;SAN MIGUEL</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M1186.9326,-350.0573C1234.5631,-326.5021 1309.4608,-279.5873 1281,-228 1245.9758,-164.5162 1211.7657,-163.9818 1143,-141 1076.9681,-118.9318 881.6166,-109.9964 776.6095,-106.7105\"/>\n<text text-anchor=\"middle\" x=\"1355.5\" y=\"-231.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0.03855841288228038</text>\n</g>\n<!-- NUNUNYAYOC&#45;&#45;SANTA ROSA DE PITIC BAJA -->\n<g id=\"edge30\" class=\"edge\">\n<title>NUNUNYAYOC&#45;&#45;SANTA ROSA DE PITIC BAJA</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M1213.6949,-355.4634C1312.9163,-336.9894 1495,-294.9838 1495,-235.5 1495,-235.5 1495,-235.5 1495,-105 1495,-64.5575 938.9366,-34.9679 679.911,-23.3784\"/>\n<text text-anchor=\"middle\" x=\"1561\" y=\"-188.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0.0384784124672551</text>\n</g>\n<!-- PARIAMARCA&#45;&#45;QUICHAS -->\n<g id=\"edge31\" class=\"edge\">\n<title>PARIAMARCA&#45;&#45;QUICHAS</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M901.2155,-267.0027C890.2469,-264.8243 878.7818,-262.7056 868,-261 797.3193,-249.8186 777.5658,-259.7746 708,-243 671.4658,-234.1904 631.3966,-218.1951 604.4779,-206.4594\"/>\n<text text-anchor=\"middle\" x=\"784.5\" y=\"-231.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0.0013031116605985622</text>\n</g>\n<!-- PARIAMARCA&#45;&#45;SAN MIGUEL -->\n<g id=\"edge32\" class=\"edge\">\n<title>PARIAMARCA&#45;&#45;SAN MIGUEL</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M934.6891,-261.7604C900.8878,-234.7282 832.5022,-181.2964 771,-141 760.5684,-134.1652 748.7832,-127.2328 738.2515,-121.3005\"/>\n<text text-anchor=\"middle\" x=\"937.5\" y=\"-188.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0.03779097270513538</text>\n</g>\n<!-- PARIAMARCA&#45;&#45;SANTA ROSA DE PITIC BAJA -->\n<g id=\"edge33\" class=\"edge\">\n<title>PARIAMARCA&#45;&#45;SANTA ROSA DE PITIC BAJA</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M976.5063,-261.5915C998.7637,-240.503 1028.8865,-204.0653 1011,-174 953.855,-77.9453 895.9821,-89.4942 790,-54 750.8472,-40.8875 706.4999,-32.5386 666.6728,-27.2278\"/>\n<text text-anchor=\"middle\" x=\"1069.5\" y=\"-144.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0.03671365577002771</text>\n</g>\n<!-- QUICHAS&#45;&#45;SAN MIGUEL -->\n<g id=\"edge34\" class=\"edge\">\n<title>QUICHAS&#45;&#45;SAN MIGUEL</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M582.899,-173.8453C589.5963,-163.0244 599.3348,-149.7381 611,-141 624.8015,-130.6617 641.8924,-123.0146 657.865,-117.4942\"/>\n<text text-anchor=\"middle\" x=\"677\" y=\"-144.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0.0365215651636203</text>\n</g>\n<!-- QUICHAS&#45;&#45;SANTA ROSA DE PITIC BAJA -->\n<g id=\"edge35\" class=\"edge\">\n<title>QUICHAS&#45;&#45;SANTA ROSA DE PITIC BAJA</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M546.889,-176.3089C529.4508,-164.1919 507.9535,-145.6824 498,-123 484.3491,-91.892 510.6371,-56.6872 530.5654,-35.9688\"/>\n<text text-anchor=\"middle\" x=\"564\" y=\"-101.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0.0354854598392121</text>\n</g>\n<!-- SAN MIGUEL&#45;&#45;SANTA ROSA DE PITIC BAJA -->\n<g id=\"edge36\" class=\"edge\">\n<title>SAN MIGUEL&#45;&#45;SANTA ROSA DE PITIC BAJA</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M678.2814,-88.636C650.838,-73.5247 610.1841,-51.1393 582.0287,-35.636\"/>\n<text text-anchor=\"middle\" x=\"712.5\" y=\"-57.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0.004261505133168619</text>\n</g>\n</g>\n</svg>\n"
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 98
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "IRlg66TGjPxt"
      },
      "source": [
        "**Implementacion con DFS**"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "XloGlZI3Oyek",
        "outputId": "45985855-8b13-4901-e968-2c8af6e11354"
      },
      "source": [
        "def _dfs(G,u,r,t,h): \n",
        "  if not G.nodes[u]['visited']:\n",
        "    G.nodes[u]['visited']=True\n",
        "    #pdb.set_trace()\n",
        "    m=list(G.neighbors(u)) # shuffle para encontrar diferentes rutas\n",
        "    random.shuffle(m)\n",
        "    for v in m:\n",
        "      if not G.nodes[v]['visited']:\n",
        "        t+=G.edges[u,v]['weight']\n",
        "        h+=[v]\n",
        "        _dfs(G,v,r,t,h)\n",
        "    if u!=r:\n",
        "      t+=G.edges[u,r]['weight']\n",
        "      save.append(t)\n",
        "      save.append(h)\n",
        "\n",
        "\n",
        "def dfs(G,s):\n",
        "  temp=0 #para almacenar la distancia \n",
        "  ruta=[s] #para almacenar la ruta que seguira\n",
        "  for p in G.nodes:\n",
        "    G.nodes[p]['visited']=False\n",
        "  _dfs(G,s,s,temp,ruta)\n",
        "  return save[0],save[1]\n",
        "print('Posibles caminos:')\n",
        "caminos=[]\n",
        "for k in G.nodes: #se aplica el dfs a cada nodo\n",
        "  save=[]\n",
        "  caminos.append(dfs(G,k))\n",
        "print(caminos)\n",
        "print('Menor camino:', min(caminos))"
      ],
      "execution_count": 99,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Posibles caminos:\n",
            "[(0.17457799789893652, ['HUALANGAYOC', 'MUYOMUYO', 'LA QUINUA', 'NUNUNYAYOC', 'PARIAMARCA', 'QUICHAS', 'SAN MIGUEL', 'SANTA ROSA DE PITIC BAJA', 'MACAPATA']), (0.17692168879658401, ['LA QUINUA', 'MACAPATA', 'NUNUNYAYOC', 'HUALANGAYOC', 'PARIAMARCA', 'MUYOMUYO', 'SAN MIGUEL', 'QUICHAS', 'SANTA ROSA DE PITIC BAJA']), (0.17619348567383006, ['MACAPATA', 'MUYOMUYO', 'QUICHAS', 'LA QUINUA', 'SANTA ROSA DE PITIC BAJA', 'SAN MIGUEL', 'NUNUNYAYOC', 'PARIAMARCA', 'HUALANGAYOC']), (0.1733943124657027, ['MUYOMUYO', 'SAN MIGUEL', 'LA QUINUA', 'SANTA ROSA DE PITIC BAJA', 'HUALANGAYOC', 'NUNUNYAYOC', 'PARIAMARCA', 'QUICHAS', 'MACAPATA']), (0.12093466790897814, ['NUNUNYAYOC', 'MUYOMUYO', 'PARIAMARCA', 'LA QUINUA', 'MACAPATA', 'SAN MIGUEL', 'SANTA ROSA DE PITIC BAJA', 'HUALANGAYOC', 'QUICHAS']), (0.24106973729073247, ['PARIAMARCA', 'NUNUNYAYOC', 'SANTA ROSA DE PITIC BAJA', 'SAN MIGUEL', 'MUYOMUYO', 'LA QUINUA', 'QUICHAS', 'HUALANGAYOC', 'MACAPATA']), (0.16939881284324798, ['QUICHAS', 'PARIAMARCA', 'MACAPATA', 'SAN MIGUEL', 'MUYOMUYO', 'HUALANGAYOC', 'NUNUNYAYOC', 'LA QUINUA', 'SANTA ROSA DE PITIC BAJA']), (0.243276464213683, ['SAN MIGUEL', 'QUICHAS', 'NUNUNYAYOC', 'LA QUINUA', 'MUYOMUYO', 'HUALANGAYOC', 'MACAPATA', 'SANTA ROSA DE PITIC BAJA', 'PARIAMARCA']), (0.30243002990958223, ['SANTA ROSA DE PITIC BAJA', 'QUICHAS', 'LA QUINUA', 'HUALANGAYOC', 'MACAPATA', 'NUNUNYAYOC', 'PARIAMARCA', 'SAN MIGUEL', 'MUYOMUYO'])]\n",
            "Menor camino: (0.12093466790897814, ['NUNUNYAYOC', 'MUYOMUYO', 'PARIAMARCA', 'LA QUINUA', 'MACAPATA', 'SAN MIGUEL', 'SANTA ROSA DE PITIC BAJA', 'HUALANGAYOC', 'QUICHAS'])\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}