Traveling_tourist/Part 2 - Exploring Pathfinding Graph Algorithms.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "view-in-github"
   },
   "source": [
    "<a href=\"https://colab.research.google.com/github/tomasonjo/blogs/blob/master/Traveling_tourist/Part%202%20-%20Exploring%20Pathfinding%20Graph%20Algorithms.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "dCh1ugYd37IZ"
   },
   "source": [
    "* Updated to GDS 2.0 version\n",
    "* Link to original blog post: https://towardsdatascience.com/part-2-exploring-pathfinding-graph-algorithms-e194ffb7f569"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "Htf1Vgwi3xj7",
    "outputId": "7e9740b9-48ee-472e-9a01-831699a34e9b"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Collecting neo4j\n",
      "  Downloading neo4j-4.4.2.tar.gz (89 kB)\n",
      "\u001b[K     |████████████████████████████████| 89 kB 3.7 MB/s \n",
      "\u001b[?25hRequirement already satisfied: pytz in /usr/local/lib/python3.7/dist-packages (from neo4j) (2018.9)\n",
      "Building wheels for collected packages: neo4j\n",
      "  Building wheel for neo4j (setup.py) ... \u001b[?25l\u001b[?25hdone\n",
      "  Created wheel for neo4j: filename=neo4j-4.4.2-py3-none-any.whl size=115365 sha256=b8565e9c966a064f53e98497c6b624870c5778fb0f3deee8e6ba91866ff013c2\n",
      "  Stored in directory: /root/.cache/pip/wheels/10/d6/28/95029d7f69690dbc3b93e4933197357987de34fbd44b50a0e4\n",
      "Successfully built neo4j\n",
      "Installing collected packages: neo4j\n",
      "Successfully installed neo4j-4.4.2\n"
     ]
    }
   ],
   "source": [
    "!pip install neo4j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "id": "6A8XqDDk3vi4"
   },
   "outputs": [],
   "source": [
    "# Define Neo4j connections\n",
    "import pandas as pd\n",
    "from neo4j import GraphDatabase\n",
    "host = 'bolt://3.231.25.240:7687'\n",
    "user = 'neo4j'\n",
    "password = 'hatchets-visitor-axes'\n",
    "driver = GraphDatabase.driver(host,auth=(user, password))\n",
    "\n",
    "def run_query(query, parameters = {}):\n",
    "    with driver.session() as session:\n",
    "        result = session.run(query,parameters)\n",
    "        return pd.DataFrame([r.values() for r in result], columns=result.keys())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "lhZqESev3vi8"
   },
   "source": [
    "In the first part of the series, we constructed a knowledge graph of monuments located in Spain from WikiData API. Now we'll put on our graph data science goggles and explore various pathfinding algorithms available in the Neo4j Graph Data Science library. To top it off, we'll look at a brute force solution for a Santa Claus problem. Now, you might wonder what a Santa Claus problem is. It is a variation of the traveling salesman problem, except we don't require the solution to end in the same city as it started. This is because of the Santa Claus' ability to bend the time-space continuum and instantly fly back to the North Pole once he's finished with delivering goodies.\n",
    "## Agenda\n",
    "* Infer spatial network of monuments\n",
    "* Load the in-memory projected graph with cypher projection\n",
    "* Weakly connected component algorithm\n",
    "* Shortest path algorithm\n",
    "* Yen's k-shortest path algorithm\n",
    "* Single source shortest paths algorithm\n",
    "* Minimum spanning tree algorithm\n",
    "* Random walk algorithm\n",
    "* Traveling salesman problem\n",
    "* Conclusion\n",
    "\n",
    "### Infer spatial network of monuments\n",
    "Currently, we have no direct relationships between the monuments in our graph. We do, however, have their GPS locations, which allows us to identify which monuments are nearby. This way, we can infer a spatial network of monuments.\n",
    "The process is very similar to inferring a similarity network. We usually don't want to end up with a complete graph, where each node is connected to all the other ones. It would defeat the purpose of demonstrating pathfinding algorithms as the shortest path between any two nodes would always be a straight line, which would be represented as a direct relationship between the two nodes. In our case, we will connect each monument to the five closest monuments that are less than 100 kilometers away. These two numbers are entirely arbitrary. You can pick any other depending on your scenario."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 49
    },
    "id": "jnoyCh6E3vi-",
    "outputId": "fedf5535-06b4-48a2-bf10-8f970e7625ab"
   },
   "outputs": [
    {
     "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",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "Empty DataFrame\n",
       "Columns: []\n",
       "Index: []"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "infer_spatial_network = \"\"\"\n",
    "\n",
    "MATCH (m1:Monument),(m2:Monument) \n",
    "WHERE id(m1) > id(m2) \n",
    "WITH m1,m2, point.distance(m1.location_point,m2.location_point) as distance \n",
    "ORDER BY distance ASC\n",
    "WHERE distance < 100000\n",
    "WITH m1,collect({node:m2,distance:distance})[..5] as nearest \n",
    "UNWIND nearest as near \n",
    "WITH m1, near, near.node as nearest_node \n",
    "MERGE (m1)-[m:NEAR]-(nearest_node) SET m.distance = near.distance\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "run_query(infer_spatial_network)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "mhqj72T93vi_"
   },
   "source": [
    "### Load the in-memory projected graph with cypher projection\n",
    "Let's just quickly refresh how does the GDS library work.\n",
    "\n",
    "The graph analytics pipeline consists of three parts. In the first part, the graph loader reads the stored graph from Neo4j and loads it as an in-memory projected graph. We can use either native projection or cypher projection to load the projected graph. In the second step, we execute the graph algorithms in sequence. We can use the results of one graph algorithm as an input to another. Last but not least, we store or stream the results back to Neo4j.\n",
    "Here, we will use the cypher projection to load the in-memory graph. I suggest you take a look at the official documentation for more details regarding how it works. In the node statement, we will describe all monuments in our graph and add their architecture style as a node label. Adding a custom node label will allow us to filter nodes by architectural style at algorithm execution time. In the relationship statement, we will describe all the links between monuments and include the distance property, that we will use as a relationship weight."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 81
    },
    "id": "TOuM269w3vjA",
    "outputId": "8589750e-131b-4297-a381-0b65f7518ba5"
   },
   "outputs": [
    {
     "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>nodeQuery</th>\n",
       "      <th>relationshipQuery</th>\n",
       "      <th>graphName</th>\n",
       "      <th>nodeCount</th>\n",
       "      <th>relationshipCount</th>\n",
       "      <th>projectMillis</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>MATCH (m:Monument)-[:ARCHITECTURE]-&gt;(a) \\n   R...</td>\n",
       "      <td>MATCH (m1:Monument)-[r:NEAR]-(m2:Monument) \\n ...</td>\n",
       "      <td>monuments</td>\n",
       "      <td>1198</td>\n",
       "      <td>11334</td>\n",
       "      <td>688</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                                           nodeQuery  \\\n",
       "0  MATCH (m:Monument)-[:ARCHITECTURE]->(a) \\n   R...   \n",
       "\n",
       "                                   relationshipQuery  graphName  nodeCount  \\\n",
       "0  MATCH (m1:Monument)-[r:NEAR]-(m2:Monument) \\n ...  monuments       1198   \n",
       "\n",
       "   relationshipCount  projectMillis  \n",
       "0              11334            688  "
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "load_projected_graph = \"\"\"\n",
    "\n",
    "CALL gds.graph.project.cypher('monuments',\n",
    "  'MATCH (m:Monument)-[:ARCHITECTURE]->(a) \n",
    "   RETURN id(m) as id, collect(a.name) as labels',\n",
    "  'MATCH (m1:Monument)-[r:NEAR]-(m2:Monument) \n",
    "   RETURN id(m1) as source, id(m2) as target, r.distance as distance')\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "run_query(load_projected_graph)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "4mX3E-1E3vjB"
   },
   "source": [
    "### Weakly connected component algorithm\n",
    "Even though the weakly connected component algorithm is not a pathfinding algorithm, it is part of almost every graph analysis. It is used to find disconnected components or islands within our graph. We'll begin by running the stats mode of the algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 81
    },
    "id": "SEyNocDL3vjC",
    "outputId": "e0ebd1c8-5671-4ffb-8f9c-b47d9e1a075e"
   },
   "outputs": [
    {
     "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>componentCount</th>\n",
       "      <th>componentDistribution</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>6</td>\n",
       "      <td>{'p99': 1173, 'min': 1, 'max': 1173, 'mean': 1...</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   componentCount                              componentDistribution\n",
       "0               6  {'p99': 1173, 'min': 1, 'max': 1173, 'mean': 1..."
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "wcc_stats_query = \"\"\"\n",
    "CALL gds.wcc.stats('monuments') \n",
    "YIELD componentCount, componentDistribution\n",
    "\"\"\"\n",
    "\n",
    "run_query(wcc_stats_query)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "enPdFeYt3vjC"
   },
   "source": [
    "There are six separate components within our monuments network. The results are typical for a real-world dataset. We have a single super component that contains 98% of all nodes and a couple of tiny islands floating around. Let's examine the smaller components."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 206
    },
    "id": "-Dit2ypp3vjD",
    "outputId": "35d08278-8160-4aed-86e8-8decea7e34af"
   },
   "outputs": [
    {
     "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>componentId</th>\n",
       "      <th>component_size</th>\n",
       "      <th>monuments</th>\n",
       "      <th>state</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>59</td>\n",
       "      <td>14</td>\n",
       "      <td>[Canarias Cabrera Pinto High School, Basilica ...</td>\n",
       "      <td>[Canarias]</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>189</td>\n",
       "      <td>6</td>\n",
       "      <td>[Arab Baths of Palma de Mallorca, Can Maneu, C...</td>\n",
       "      <td>[Illes Balears]</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>740</td>\n",
       "      <td>3</td>\n",
       "      <td>[Church of Nuestra Señora de la Concepción, Va...</td>\n",
       "      <td>[Canarias]</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>[Fortín de Reina Regente, Melilla]</td>\n",
       "      <td>[]</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>742</td>\n",
       "      <td>1</td>\n",
       "      <td>[Iglesia de Nuestra Señora (Antigua (Fuerteven...</td>\n",
       "      <td>[Canarias]</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   componentId  component_size  \\\n",
       "0           59              14   \n",
       "1          189               6   \n",
       "2          740               3   \n",
       "3            0               1   \n",
       "4          742               1   \n",
       "\n",
       "                                           monuments            state  \n",
       "0  [Canarias Cabrera Pinto High School, Basilica ...       [Canarias]  \n",
       "1  [Arab Baths of Palma de Mallorca, Can Maneu, C...  [Illes Balears]  \n",
       "2  [Church of Nuestra Señora de la Concepción, Va...       [Canarias]  \n",
       "3                 [Fortín de Reina Regente, Melilla]               []  \n",
       "4  [Iglesia de Nuestra Señora (Antigua (Fuerteven...       [Canarias]  "
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "examine_wcc_components_query = \"\"\"\n",
    "\n",
    "CALL gds.wcc.stream('monuments')\n",
    "YIELD nodeId, componentId \n",
    "WITH componentId, gds.util.asNode(nodeId) as node\n",
    "OPTIONAL MATCH (node)-[:IS_IN*2..2]->(state)\n",
    "RETURN componentId, \n",
    "       count(*) as component_size,\n",
    "       collect(node.name) as monuments, \n",
    "       collect(distinct state.id) as state\n",
    "ORDER BY component_size DESC \n",
    "SKIP 1\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "run_query(examine_wcc_components_query)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "kDi1xZsU3vjD"
   },
   "source": [
    "hree of the five smaller components are located in the Canaries archipelago, and one is located in the Balearic Islands, specifically on Majorca. With the Neomap application, developed by Estelle Scifo, we can visualize the Canaries archipelago components on a map."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "KZlgofAl3vjE"
   },
   "source": [
    "### Shortest Path algorithm\n",
    "The first pathfinding graph algorithm we will use is the Shortest Path algorithm. It finds the shortest weighted path between two nodes. We define the start node and the end node and specify which relationship weight property should the algorithm take into consideration when calculating the shortest path."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 269
    },
    "id": "lm5yNRdP3vjE",
    "outputId": "29f23994-4813-4981-9b23-3412c3de534f"
   },
   "outputs": [
    {
     "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>i</th>\n",
       "      <th>monument</th>\n",
       "      <th>cost</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>0</td>\n",
       "      <td>Iglesia de Santo Domingo</td>\n",
       "      <td>0.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1</td>\n",
       "      <td>Iglesia de San Isidoro</td>\n",
       "      <td>363.694539</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>2</td>\n",
       "      <td>Iglesia de San Emeterio</td>\n",
       "      <td>39815.236290</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>3</td>\n",
       "      <td>Church of Santiago de Gobiendes</td>\n",
       "      <td>50922.273639</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>4</td>\n",
       "      <td>Iglesia de Santa María del Conceyu</td>\n",
       "      <td>90441.740216</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>5</td>\n",
       "      <td>Gothic church of San Vicente, Potes</td>\n",
       "      <td>121910.069518</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>6</td>\n",
       "      <td>Colegiata de Santa María de Piasca</td>\n",
       "      <td>127242.580124</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   i                             monument           cost\n",
       "0  0             Iglesia de Santo Domingo       0.000000\n",
       "1  1               Iglesia de San Isidoro     363.694539\n",
       "2  2              Iglesia de San Emeterio   39815.236290\n",
       "3  3      Church of Santiago de Gobiendes   50922.273639\n",
       "4  4   Iglesia de Santa María del Conceyu   90441.740216\n",
       "5  5  Gothic church of San Vicente, Potes  121910.069518\n",
       "6  6   Colegiata de Santa María de Piasca  127242.580124"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "shortest_path_query = \"\"\"\n",
    "\n",
    "MATCH (s:Monument{name:'Iglesia de Santo Domingo'}),  \n",
    "      (e:Monument{name:'Colegiata de Santa María de Piasca'})\n",
    "CALL gds.shortestPath.dijkstra.stream('monuments',{\n",
    "  sourceNode:s,\n",
    "  targetNode:e,\n",
    "  relationshipWeightProperty:'distance'})\n",
    "YIELD nodeIds, costs\n",
    "UNWIND range(0, size(nodeIds) - 1) AS i\n",
    "RETURN i, gds.util.asNode(nodeIds[i]).name AS monument, costs[i] AS cost\n",
    "\"\"\"\n",
    "\n",
    "run_query(shortest_path_query)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "BI07Scow3vjF"
   },
   "source": [
    "What if we wanted to plan a trip for an architectural class and visit only monuments that were influenced by either Gothic or Romanesque architecture along the way? Planning such a trip is very easy with the GDS library, as we can filter which nodes can the algorithm visit with the nodeLabels parameter."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 332
    },
    "id": "B0izlQsZ3vjF",
    "outputId": "e40f8075-e2bd-425f-da3c-f4989911879c"
   },
   "outputs": [
    {
     "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>i</th>\n",
       "      <th>monument</th>\n",
       "      <th>cost</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>0</td>\n",
       "      <td>Iglesia de Santo Domingo</td>\n",
       "      <td>0.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1</td>\n",
       "      <td>Iglesia de San Juan</td>\n",
       "      <td>7133.775358</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>2</td>\n",
       "      <td>Colegiata de San Pedro de Teverga</td>\n",
       "      <td>31750.759896</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>3</td>\n",
       "      <td>Astorga Cathedral</td>\n",
       "      <td>109770.935291</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>4</td>\n",
       "      <td>Church of San Lorenzo, Sahagún</td>\n",
       "      <td>194688.354724</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>5</td>\n",
       "      <td>Hermitage of Santa Cecilia (Vallespinoso de Ag...</td>\n",
       "      <td>265010.752425</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>6</td>\n",
       "      <td>Church of San Cornelio y San Cipriano, Revilla...</td>\n",
       "      <td>279283.385210</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>7</td>\n",
       "      <td>Church of San Salvador, San Salvador de Cantamuda</td>\n",
       "      <td>297916.692629</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>8</td>\n",
       "      <td>Colegiata de Santa María de Piasca</td>\n",
       "      <td>316368.966950</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   i                                           monument           cost\n",
       "0  0                           Iglesia de Santo Domingo       0.000000\n",
       "1  1                                Iglesia de San Juan    7133.775358\n",
       "2  2                  Colegiata de San Pedro de Teverga   31750.759896\n",
       "3  3                                  Astorga Cathedral  109770.935291\n",
       "4  4                     Church of San Lorenzo, Sahagún  194688.354724\n",
       "5  5  Hermitage of Santa Cecilia (Vallespinoso de Ag...  265010.752425\n",
       "6  6  Church of San Cornelio y San Cipriano, Revilla...  279283.385210\n",
       "7  7  Church of San Salvador, San Salvador de Cantamuda  297916.692629\n",
       "8  8                 Colegiata de Santa María de Piasca  316368.966950"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "shortest_path_filter_query = \"\"\"\n",
    "\n",
    "MATCH (s:Monument{name:'Iglesia de Santo Domingo'}),  \n",
    "      (t:Monument{name:'Colegiata de Santa María de Piasca'})\n",
    "CALL gds.shortestPath.dijkstra.stream('monuments',{\n",
    "  sourceNode:s,\n",
    "  targetNode:t,\n",
    "  relationshipWeightProperty:'distance',\n",
    "  nodeLabels:['Gothic architecture','Romanesque architecture']}) \n",
    "YIELD nodeIds, costs\n",
    "UNWIND range(0, size(nodeIds) - 1) AS i\n",
    "RETURN i, gds.util.asNode(nodeIds[i]).name AS monument, costs[i] AS cost\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "run_query(shortest_path_filter_query)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "EIKmp1Af3vjF"
   },
   "source": [
    "The route is a bit different this time as the algorithm can only visit monuments that were influenced by Gothic or Romanesque architecture style.\n",
    "\n",
    "### Yen's k-shortest path algorithm\n",
    "We have learned how to calculate the shortest weighted path between a pair of nodes. What if we were more cautious tourists and wanted to find the top three shortest paths? Having a backup plan if something unexpected might happen along the way is always a good idea. In this scenario, we could use the Yen's k-shortest path algorithm. The syntax is almost identical to the Shortest Path algorithm, except for the added k parameter, which defines how many shortest paths we would like to find."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 143
    },
    "id": "Nl757C0D3vjG",
    "outputId": "36d43244-16b2-410d-9338-b3591292e57f"
   },
   "outputs": [
    {
     "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>index</th>\n",
       "      <th>monuments</th>\n",
       "      <th>total_cost</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>0</td>\n",
       "      <td>[Iglesia de Santo Domingo, Iglesia de San Isid...</td>\n",
       "      <td>430695.594326</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1</td>\n",
       "      <td>[Iglesia de Santo Domingo, Church of San Tirso...</td>\n",
       "      <td>432845.257110</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>2</td>\n",
       "      <td>[Iglesia de Santo Domingo, Palacio de los Cond...</td>\n",
       "      <td>433141.177100</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   index                                          monuments     total_cost\n",
       "0      0  [Iglesia de Santo Domingo, Iglesia de San Isid...  430695.594326\n",
       "1      1  [Iglesia de Santo Domingo, Church of San Tirso...  432845.257110\n",
       "2      2  [Iglesia de Santo Domingo, Palacio de los Cond...  433141.177100"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "yens_shortest_path_query = \"\"\"\n",
    "\n",
    "MATCH (s:Monument{name:'Iglesia de Santo Domingo'}),\n",
    "      (t:Monument{name:'Colegiata de Santa María de Piasca'})\n",
    "CALL gds.shortestPath.yens.stream('monuments',{\n",
    "  sourceNode:s,\n",
    "  targetNode:t,\n",
    "  k:3,\n",
    "  relationshipWeightProperty:'distance'}) \n",
    "YIELD index,nodeIds,costs\n",
    "RETURN index,[nodeId in nodeIds | gds.util.asNode(nodeId).name] as monuments,apoc.coll.sum(costs) as total_cost\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "run_query(yens_shortest_path_query)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "DIzMHY803vjG"
   },
   "source": [
    "The three paths are almost the same length, just a couple hundred meters of difference. If you look closely, only the second stop is different among the three variants. Such a small difference can be attributed to the nature of our spatial network and the example pair of nodes.\n",
    "### Single source shortest path algorithm\n",
    "With the Single Source Shortest Path algorithm, we define the start node and search for the shortest weighted path to all the other nodes in the network. We'll inspect one of the Canaries components to limit the number of shortest paths to a reasonable number.\n",
    "We'll examine the Tenerife - Gran Canaria component and choose the Cathedral of La Laguna as the starting node. The algorithm tries to find the shortest paths to all the other nodes in the network, and if no such way exists, it returns Infinity value as a result. We will filter out the unreachable nodes with the gds.util.isFinite procedure."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 551
    },
    "id": "AhbikQAE3vjG",
    "outputId": "ffd939d1-cc6a-4c58-e724-15fd8ee439af"
   },
   "outputs": [
    {
     "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>index</th>\n",
       "      <th>monuments</th>\n",
       "      <th>totalCost</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>0</td>\n",
       "      <td>Cathedral of La Laguna</td>\n",
       "      <td>0.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1</td>\n",
       "      <td>Canarias Cabrera Pinto High School</td>\n",
       "      <td>235.611277</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>2</td>\n",
       "      <td>Iglesia de la Concepción</td>\n",
       "      <td>420.110622</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>3</td>\n",
       "      <td>Iglesia de San Francisco de Asís</td>\n",
       "      <td>6953.377218</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>4</td>\n",
       "      <td>Iglesia de la Concepción</td>\n",
       "      <td>7141.925011</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>5</td>\n",
       "      <td>Basilica of Candelaria</td>\n",
       "      <td>16192.932014</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>6</td>\n",
       "      <td>Immaculate Conception Church</td>\n",
       "      <td>23252.693912</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>7</td>\n",
       "      <td>Shrine of Our Lady of Mount Carmel</td>\n",
       "      <td>28826.040899</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>8</td>\n",
       "      <td>Church of San Juan Bautista, Arico</td>\n",
       "      <td>40479.026879</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>9</td>\n",
       "      <td>Church of Santiago de los Caballeros, Galdar</td>\n",
       "      <td>75266.654817</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>10</th>\n",
       "      <td>10</td>\n",
       "      <td>Mother church of Santa María de Guía</td>\n",
       "      <td>79964.177287</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11</th>\n",
       "      <td>11</td>\n",
       "      <td>Basílica de Nuestra Señora del Pino</td>\n",
       "      <td>89360.846045</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>12</th>\n",
       "      <td>12</td>\n",
       "      <td>Parroquia de San Francisco de Asís</td>\n",
       "      <td>98058.579461</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>13</th>\n",
       "      <td>13</td>\n",
       "      <td>Cathedral of Santa Ana</td>\n",
       "      <td>98388.990460</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "    index                                     monuments     totalCost\n",
       "0       0                        Cathedral of La Laguna      0.000000\n",
       "1       1            Canarias Cabrera Pinto High School    235.611277\n",
       "2       2                      Iglesia de la Concepción    420.110622\n",
       "3       3              Iglesia de San Francisco de Asís   6953.377218\n",
       "4       4                      Iglesia de la Concepción   7141.925011\n",
       "5       5                        Basilica of Candelaria  16192.932014\n",
       "6       6                  Immaculate Conception Church  23252.693912\n",
       "7       7            Shrine of Our Lady of Mount Carmel  28826.040899\n",
       "8       8            Church of San Juan Bautista, Arico  40479.026879\n",
       "9       9  Church of Santiago de los Caballeros, Galdar  75266.654817\n",
       "10     10          Mother church of Santa María de Guía  79964.177287\n",
       "11     11           Basílica de Nuestra Señora del Pino  89360.846045\n",
       "12     12            Parroquia de San Francisco de Asís  98058.579461\n",
       "13     13                        Cathedral of Santa Ana  98388.990460"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sssp_query = \"\"\"\n",
    "\n",
    "MATCH (start:Monument{name:'Cathedral of La Laguna'})\n",
    "CALL gds.allShortestPaths.dijkstra.stream('monuments',\n",
    " {sourceNode:start, relationshipWeightProperty:'distance'})\n",
    "YIELD index,nodeIds,costs\n",
    "RETURN index,gds.util.asNode(nodeIds[-1]).name as monuments,costs[-1] as totalCost\n",
    "ORDER BY totalCost ASC\n",
    "\"\"\"\n",
    "\n",
    "run_query(sssp_query)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "fXBvQJff3vjH"
   },
   "source": [
    "The closest monument to the Cathedral of La Laguna is the Iglesia de la Concepción, which is just 420 meters away. It seems that there are two Iglesia de la Concepción on Tenerife Island as we can observe that it shows up twice in our results. The farthest reachable monument in our network from the Cathedral of La Laguna is Basilica of San Juan Bautista.\n",
    "If we wanted to find the cost of the shortest path to all the reachable neoclassical monuments from the Cathedral of La Laguna, we could effortlessly achieve this with the nodeLabels parameter."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 238
    },
    "id": "5CS0IgiX3vjH",
    "outputId": "c46c84fb-65d4-478f-82f2-71c328c7ed42"
   },
   "outputs": [
    {
     "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>index</th>\n",
       "      <th>monuments</th>\n",
       "      <th>totalCost</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>0</td>\n",
       "      <td>Cathedral of La Laguna</td>\n",
       "      <td>0.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1</td>\n",
       "      <td>Basilica of Candelaria</td>\n",
       "      <td>16192.932014</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>2</td>\n",
       "      <td>Basílica de Nuestra Señora del Pino</td>\n",
       "      <td>103134.802997</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>3</td>\n",
       "      <td>Mother church of Santa María de Guía</td>\n",
       "      <td>113601.351155</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>4</td>\n",
       "      <td>Cathedral of Santa Ana</td>\n",
       "      <td>113927.864686</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>5</td>\n",
       "      <td>Church of Santiago de los Caballeros, Galdar</td>\n",
       "      <td>117417.110559</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   index                                     monuments      totalCost\n",
       "0      0                        Cathedral of La Laguna       0.000000\n",
       "1      1                        Basilica of Candelaria   16192.932014\n",
       "2      2           Basílica de Nuestra Señora del Pino  103134.802997\n",
       "3      3          Mother church of Santa María de Guía  113601.351155\n",
       "4      4                        Cathedral of Santa Ana  113927.864686\n",
       "5      5  Church of Santiago de los Caballeros, Galdar  117417.110559"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sssp_filter_query = \"\"\"\n",
    "\n",
    "MATCH (start:Monument{name:'Cathedral of La Laguna'})\n",
    "CALL gds.allShortestPaths.dijkstra.stream('monuments',\n",
    " {sourceNode:start, relationshipWeightProperty:'distance',   \n",
    "  nodeLabels:['Neoclassical architecture']})\n",
    "YIELD index,nodeIds,costs\n",
    "RETURN index,gds.util.asNode(nodeIds[-1]).name as monuments,costs[-1] as totalCost\n",
    "ORDER BY totalCost ASC\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "run_query(sssp_filter_query)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "n_IzOVlU3vjH"
   },
   "source": [
    "It seems there are only four neoclassical monuments on Tenerife and Gran Canaria islands.\n",
    "### Minimum weight spanning tree algorithm\n",
    "The Minimum Weight Spanning Tree algorithm starts from a given node and calculates a spanning tree connecting all reachable nodes with the minimum possible sum of relationship weights. For example, if we wanted to connect all the monuments in Tenerife and Gran Canaria with an optical or electric cable, we would use the Minimum Weight Spanning Tree algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 81
    },
    "id": "oUhwiLsD3vjI",
    "outputId": "59016571-40dc-4ede-f1c0-d24f7a4a6eb5"
   },
   "outputs": [],
   "source": [
    "# Not working anymore\n",
    "mwst_query = \"\"\"\n",
    "\n",
    "MATCH (start:Monument{name:'Cathedral of La Laguna'})\n",
    "CALL gds.beta.spanningTree.write('monuments',{\n",
    " sourceNode:id(start),\n",
    " relationshipWeightProperty:'distance',\n",
    " writeProperty:'cost',\n",
    " writeRelationshipType:'SPANNING_TREE'})\n",
    "YIELD effectiveNodeCount\n",
    "RETURN effectiveNodeCount\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "run_query(mwst_query)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "vK7wY7AX3vjI"
   },
   "source": [
    "Currently, only the write mode of the algorithm is available. We can visualize our potential cable route with Neomap.\n",
    "### Random walk algorithm\n",
    "We can imagine the Random Walk algorithm trying to mimic a drunk crowd traversing the network. They might go left, or right, take two steps forward, one step back, we never really know. It depends on how drunk the crowd is. We can use this algorithm to provide random trip recommendations. Imagine we have just visited the University of Barcelona historical building and are not sure which monuments we should take a look at next."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 143
    },
    "id": "Jy3k81eJ3vjI",
    "outputId": "9854a518-5a54-49d3-ef0c-66809f3160bb"
   },
   "outputs": [
    {
     "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>result</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>[University of Barcelona historical building, ...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>[University of Barcelona historical building, ...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>[University of Barcelona historical building, ...</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                                              result\n",
       "0  [University of Barcelona historical building, ...\n",
       "1  [University of Barcelona historical building, ...\n",
       "2  [University of Barcelona historical building, ..."
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "random_walk_1 = \"\"\"\n",
    "\n",
    "MATCH (m:Monument{name:\"University of Barcelona historical building\"})\n",
    "CALL gds.randomWalk.stream('monuments',\n",
    "  {sourceNodes:[id(m)], walksPerNode:3, walkLength:5})\n",
    "YIELD nodeIds\n",
    "RETURN [nodeId in nodeIds | gds.util.asNode(nodeId).name] as result\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "run_query(random_walk_1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "b6CaoJKK3vjJ"
   },
   "source": [
    "Remember, we mentioned that the Random Walk algorithm tries to mimic a drunk person traversing the network. Well, an intoxicated person might visit the same monument twice and not care. For example, in the first and third suggestions, a single monument shows up twice. Luckily, we have some options to influence how the algorithm should traverse the network in the node2vec mode with the following two parameters:\n",
    ">return: This parameter controls the likelihood of immediately revisiting a node in a walk. Setting it to a high value (> max(inOut, 1)) ensures that we are less likely to sample an already visited node in the following two steps.\n",
    "\n",
    ">inOut: This parameter allows the search to differentiate between \"inward\" and \"outward\" nodes. If inOut > 1, the random walk is biased towards nodes close to node t. In contrast, if inOut < 1, the walk is more inclined to visit nodes that are further away from the node t.\n",
    "\n",
    "The definition of the two parameters is summarized from the original Node2vec paper.\n",
    "We want to recommend monuments close to our starting point, so we choose the inOut parameter to be greater than 1. And we definitely would like to avoid revisiting an already visited node during the walk, so we choose the return parameter to be greater than the inOut parameter."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 143
    },
    "id": "TOsalrhA3vjJ",
    "outputId": "f76c5e04-8724-4636-b35d-c4576d003eb2"
   },
   "outputs": [
    {
     "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>result</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>[University of Barcelona historical building, ...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>[University of Barcelona historical building, ...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>[University of Barcelona historical building, ...</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                                              result\n",
       "0  [University of Barcelona historical building, ...\n",
       "1  [University of Barcelona historical building, ...\n",
       "2  [University of Barcelona historical building, ..."
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "random_walk_2 = \"\"\"\n",
    "\n",
    "MATCH (m:Monument{name:\"University of Barcelona historical building\"})\n",
    "CALL gds.randomWalk.stream('monuments',\n",
    "  {sourceNodes:[id(m)], walksPerNode:3, walkLength:5, \n",
    "   inOutFactor:5, returnFactor:10})\n",
    "YIELD nodeIds\n",
    "RETURN [nodeId in nodeIds | gds.util.asNode(nodeId).name] as result\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "run_query(random_walk_2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "562skOZA3vjJ"
   },
   "source": [
    "Unfortunately, the return parameter ensures that we are less likely to sample an already visited node in the following two steps. This means that we can't be sure that duplicates won't show up later during our walk.  In our example, Casa Batlló appears twice in the first suggestion. We can circumnavigate this problem by creating longer walk suggestions and filtering out duplicates before showing the results to the user. In the following query, we calculate nine steps long walks, filter out duplicates, and return only the first five results."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 143
    },
    "id": "unhYMkC73vjJ",
    "outputId": "842a69ed-29d6-4744-d5b1-0784dd17230d"
   },
   "outputs": [
    {
     "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>result</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>[University of Barcelona historical building, ...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>[University of Barcelona historical building, ...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>[University of Barcelona historical building, ...</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                                              result\n",
       "0  [University of Barcelona historical building, ...\n",
       "1  [University of Barcelona historical building, ...\n",
       "2  [University of Barcelona historical building, ..."
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "random_walk_3 = \"\"\"\n",
    "\n",
    "MATCH (m:Monument{name:\"University of Barcelona historical building\"})\n",
    "CALL gds.randomWalk.stream('monuments',\n",
    "  {sourceNodes:[id(m)], walksPerNode:3, walkLength:5, \n",
    "   inOutFactor:5, returnFactor:10})\n",
    "YIELD nodeIds\n",
    "RETURN apoc.coll.toSet([nodeId in nodeIds | gds.util.asNode(nodeId).name])[..5] as result\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "run_query(random_walk_3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "fVCMpZ5f3vjK"
   },
   "source": [
    "This way, we make sure the results never contain duplicates. Now we can visualize the results with our trip recommendation application.\n",
    "\n",
    "### Traveling salesman problem\n",
    "To top it off, we will solve the Santa Claus variation of the traveling salesman problem. As mentioned, the only difference is that we omit the requirement to end up in the same location as we started. I found the inspiration for this problem in the Gaming the Christmas Market post written by David Barton. I give all the credits to David Barton for conjuring up the solution. My contribution is to update it to work with Neo4j 4.0 and the GDS library.\n",
    "Say we want to find the optimal route between this monuments:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "id": "PNtNQ9t23vjK"
   },
   "outputs": [],
   "source": [
    "\n",
    "selection = run_query(\"\"\"MATCH (m:Monument) RETURN m.name AS s LIMIT 6\"\"\")['s'].to_list() "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "fSxQp3zA3vjK"
   },
   "source": [
    "We split the solution into two steps. First, we calculate the shortest path between all pairs of selected monuments with the gds.alpha.shortestPath algorithm and store the results as the SHORTEST_ROUTE_TO relationship between the given pair of nodes. We save the total cost and all the intermediate nodes along the shortest path as the properties of the SHORTEST_ROUTE_TO relationship."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 49
    },
    "id": "Ui2qFSMr3vjK",
    "outputId": "51382a2b-7a21-4b68-a6cd-d39ed789de19"
   },
   "outputs": [
    {
     "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",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "Empty DataFrame\n",
       "Columns: []\n",
       "Index: []"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "traveling_salesman_part1 = \"\"\"\n",
    "\n",
    "WITH $selection as selection\n",
    "MATCH (c:Monument)\n",
    "WHERE c.name in selection\n",
    "WITH collect(c) as monuments\n",
    "UNWIND monuments as c1\n",
    "WITH c1,\n",
    "    [c in monuments where c.name > c1.name | c] as c2s,\n",
    "    monuments\n",
    "UNWIND c2s as c2\n",
    "CALL gds.shortestPath.dijkstra.stream('monuments',{sourceNode:c1,targetNode:c2,relationshipWeightProperty:'distance'})\n",
    "YIELD nodeIds, costs\n",
    "WITH c1,\n",
    "     c2,\n",
    "     costs[-1] as totalCost,\n",
    "     nodeIds as shortestHopNodeIds\n",
    "MERGE (c1) -[r:SHORTEST_ROUTE_TO]- (c2)\n",
    "SET r.cost = totalCost,\n",
    "    r.shortestHopNodeIds = shortestHopNodeIds\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "run_query(traveling_salesman_part1, {'selection': selection})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "W9Is_M3H3vjK"
   },
   "source": [
    "In the second step, we will use the apoc.path.expandConfig procedure. It enables us to perform variable-length path traversals with fine-grained control over the traversals. Check out the documentation for more details.\n",
    "We allow the procedure to traverse only SHORTEST_ROUTE_TO relationships with the relationshipFilter parameter and visit only the selected monuments with the whitelistNodes parameter. We ensure that all selected nodes must be visited exactly once by defining the number of hops or levels traversed (minLevel and maxLevel) and with the uniqueness parameter. I know it is a lot to comprehend, and if you need some help, I would suggest asking questions on the Neo4j community site. We then select the path with the minimum sum of relationship weights as the solution. Because we calculate all the possible routes between the chosen monuments, this is a brute-force solution of the traveling salesman problem."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 49
    },
    "id": "rFqGKD6r3vjL",
    "outputId": "d779be58-c26f-45a4-b096-e5134b288eee"
   },
   "outputs": [
    {
     "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>path</th>\n",
       "      <th>total_distance</th>\n",
       "      <th>optional_stops</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "Empty DataFrame\n",
       "Columns: [path, total_distance, optional_stops]\n",
       "Index: []"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "traveling_salesman_part2 = \"\"\"\n",
    "\n",
    "WITH $selection as selection\n",
    "MATCH (c:Monument) \n",
    "WHERE c.name in selection\n",
    "WITH collect(c) as monuments\n",
    "UNWIND monuments as c1\n",
    "WITH c1,\n",
    "    [c in monuments where c.name > c1.name | c] as c2s,\n",
    "    monuments,\n",
    "    (size(monuments) - 1) as level\n",
    "UNWIND c2s as c2\n",
    "CALL apoc.path.expandConfig(c1, {\n",
    "  relationshipFilter: 'SHORTEST_ROUTE_TO',\n",
    "  minLevel: level,\n",
    "  maxLevel: level,\n",
    "  whitelistNodes: monuments,\n",
    "  terminatorNodes: [c2],\n",
    "  uniqueness: 'NODE_PATH'}) \n",
    "YIELD path\n",
    "WITH path,\n",
    "    reduce(cost = 0, x in relationships(path) | cost + x.cost) as totalCost\n",
    "ORDER BY totalCost LIMIT 1\n",
    "WITH path,\n",
    "     totalCost,\n",
    "     apoc.coll.flatten([r in relationships(path) | r.shortestHopNodeIds]) as intermediate_stops,\n",
    "     [n in nodes(path) | id(n)] as node_ids\n",
    "RETURN  [n in nodes(path) | n.name] as path,\n",
    "        round(totalCost, 2) as total_distance,\n",
    "        [optional in intermediate_stops where not optional in node_ids | gds.util.asNode(optional).name] as optional_stops\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "run_query(traveling_salesman_part2, {'selection': selection})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "i5ggf5vK3vjL"
   },
   "source": [
    "In the path column of the results, we have an ordered array of selected monuments to visit. Our travel would start with Castell de Sant Jaume and continue to Castell de Vilaüt and so on. We could dub this the Spanish castle-visiting trip as we selected six castles, and we have an option to see four more along the way. The total air distance of the path is 126 kilometers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "8L9HUt3N3vjL"
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "colab": {
   "include_colab_link": true,
   "name": "Part 2 - Exploring Pathfinding Graph Algorithms.ipynb",
   "provenance": []
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}