docs/source/Introduction/own-algorithms.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Implementing your own algorithms\n",
    "\n",
    "In the previous tutorial we looked at the algorithms within the standard Raphtory library and the different ways we can apply them to a graph. While we have also written some simple custom functions, here we're going to go over how to write a new multi-step algorithm. This example algorithm will calculate the _degrees of separation_ from one a character to every other, defaulting to `Gandalf`. \n",
    "\n",
    "As background: [Six degrees of separation](https://en.wikipedia.org/wiki/Six_degrees_of_separation) is \"the idea that all people on average are six, or fewer, social connections away from each other.\"\n",
    "\n",
    "## How analysis works in Raphtory\n",
    "\n",
    "Raphtory’s analysis engine is based on __vertex centric computation__  where algorithms are executed in [bulk synchronous parallel](https://en.wikipedia.org/wiki/Bulk_synchronous_parallel) `supersteps`. Within each superstep all vertices complete a function, within which they may execute any of the follow `GAS` operations:\n",
    "\n",
    "* __Gather__: Receive information sent from other nodes in the graph (normally neighbouring nodes).\n",
    "* __Apply__:  Calculate some new state and store these values.\n",
    "* __Scatter__: Send this state to neighbours to be used in the next step.\n",
    "\n",
    "While Raphtory does have APIs for global aggregation and histograms, individual vertices have limited knowledge of the graph and must converge to their final state over several supersteps. Each vertex knows:\n",
    "\n",
    "* Its own update history, property set and property history e.g. values and update times.\n",
    "* The history/properties of the edges attached to it - both incoming and outgoing. \n",
    "* Its own algorithmic state - this is a map of temporary values that can be set and modified during analysis.\n",
    "\n",
    "Writing algorithms in this manner allows them to be run on both your laptop and a cluster without requiring any change. Let's see how it looks to implement the proposed __Degree Separation__ algorithm in this format.\n",
    "\n",
    "To begin first import pyraphtory, create a local context and ingest the Lord of The Rings data into a graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-02-02T22:48:08.581013Z",
     "iopub.status.busy": "2023-02-02T22:48:08.580139Z",
     "iopub.status.idle": "2023-02-02T22:48:27.619513Z",
     "shell.execute_reply": "2023-02-02T22:48:27.618628Z"
    }
   },
   "outputs": [],
   "source": [
    "import pyraphtory\n",
    "from pyraphtory.api.algorithm import PyAlgorithm\n",
    "from pyraphtory.api.graph import TemporalGraph\n",
    "from pyraphtory.api.table import Table\n",
    "from pyraphtory.api.vertex import Vertex\n",
    "import csv\n",
    "\n",
    "structure_file = \"/tmp/lotr.csv\"\n",
    "ctx = pyraphtory.local()\n",
    "\n",
    "graph = ctx.new_graph()\n",
    "with open(structure_file, 'r') as csvfile:\n",
    "    datareader = csv.reader(csvfile)\n",
    "    for row in datareader:\n",
    "        source_node = row[0]\n",
    "        destination_node = row[1]\n",
    "        timestamp = int(row[2])\n",
    "        graph.add_vertex(timestamp, source_node, vertex_type=\"Character\")\n",
    "        graph.add_vertex(timestamp, destination_node, vertex_type=\"Character\")  \n",
    "        graph.add_edge(timestamp, source_node, destination_node, edge_type=\"Character_Co-occurence\")"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Algorithm Structure\n",
    "Now that we have the graph set up we can create a new algorithm. \n",
    "\n",
    "Algorithms are classes which extend `PyAlgorithm`. This class has two functions to implement, `__call__()` and `tabularise()`: \n",
    "\n",
    "* \\_\\_call\\_\\_ is where we will be doing the majority of our computation. This takes a `TemporalGraph` and applies a set of operations to it (the functions we will define) and returns a new `TemporalGraph`. \n",
    "* tabularise is where we will choose what data on our vertices to return. This takes a `TemporalGraph` and returns a `Table` which can either be turned into a dataframe or output to a `Sink`.\n",
    "\n",
    "In this tutorial we will implement both as we want to compute a new property and output the results, but in many instances we may only need one or the other. For instance, we chained multiple algorithms together in the last tutorial by only applying the \\_\\_call\\_\\_ functions of each algorithm. No tabularise was then required as we finished off with our own call to `select` (returning a `Table`).    \n",
    "\n",
    "### \\_\\_call\\_\\_()\n",
    "There are many functions which may be called on the `TemporalGraph` to build algorithms as complex as you like; these can be found in the PythonDocs on the left. The main two of these are `step()` and `iterate()`.\n",
    "\n",
    "* step takes a function which will execute on all vertices once. This is normally to set up an algorithm or called in succession when you have a known number of steps to complete an algorithm.\n",
    "* iterate takes a function which will be applied on vertices until some convergence state is met. This is normally used for the bulk of an algorithm when the number of required steps is unknown. \n",
    "    * This function also requires the user to set a maximum number of steps (to bound the computation) and to decide if all vertices need to execute every superstep or if only messaged vertices are required to, minimising wasted cycles. \n",
    "\n",
    "### tabularise()\n",
    "As tabularise receives a TemporalGraph we can continue calling the same functions here, however, be aware that these won't be applied if you use this algorithm in a chain or run your own `select`. Once you have called select, as we have seen before, we can apply several `Table` steps, such as `filter`, before returning our data in the desired format.\n",
    "\n",
    "## Degree Separation from 10,000ft\n",
    "For our algorithm we want to take these building blocks and set it up such that we start at Gandalf who will tell all of his neighbours they are 1 hop away.\n",
    "These nodes should then message all their neighbours telling them they are 2 hops away, and so on until no more nodes can be reached. Importantly, nodes should only update their state once, as we want the lowest number of hops. \n",
    "\n",
    "Lets take a look at an example implementation of this algorithm, we can then go through what is happening step by step. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-02-02T22:48:27.624226Z",
     "iopub.status.busy": "2023-02-02T22:48:27.623841Z",
     "iopub.status.idle": "2023-02-02T22:48:29.823161Z",
     "shell.execute_reply": "2023-02-02T22:48:29.821178Z"
    }
   },
   "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>timestamp</th>\n",
       "      <th>name</th>\n",
       "      <th>separation</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>32674</td>\n",
       "      <td>Hirgon</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>32674</td>\n",
       "      <td>Hador</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>32674</td>\n",
       "      <td>Horn</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>32674</td>\n",
       "      <td>Galadriel</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>32674</td>\n",
       "      <td>Isildur</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>...</th>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>134</th>\n",
       "      <td>32674</td>\n",
       "      <td>Faramir</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>135</th>\n",
       "      <td>32674</td>\n",
       "      <td>Bain</td>\n",
       "      <td>-1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>136</th>\n",
       "      <td>32674</td>\n",
       "      <td>Walda</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>137</th>\n",
       "      <td>32674</td>\n",
       "      <td>Thranduil</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>138</th>\n",
       "      <td>32674</td>\n",
       "      <td>Boromir</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "<p>139 rows × 3 columns</p>\n",
       "</div>"
      ],
      "text/plain": [
       "     timestamp       name  separation\n",
       "0        32674     Hirgon           1\n",
       "1        32674      Hador           3\n",
       "2        32674       Horn           2\n",
       "3        32674  Galadriel           1\n",
       "4        32674    Isildur           1\n",
       "..         ...        ...         ...\n",
       "134      32674    Faramir           1\n",
       "135      32674       Bain          -1\n",
       "136      32674      Walda           2\n",
       "137      32674  Thranduil           2\n",
       "138      32674    Boromir           1\n",
       "\n",
       "[139 rows x 3 columns]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "state_name = 'separation' #name the state we are going to be creating on each vertex\n",
    "\n",
    "class DegreeSeparation(PyAlgorithm): #our new class extends PyAlgorithm\n",
    "\n",
    "    #create our __call__ function which takes the TemporalGraph and a name (defaulting to Gandalf)\n",
    "    def __call__(self, graph: TemporalGraph,name = \"Gandalf\") -> TemporalGraph:\n",
    "\n",
    "        #create a setup step function\n",
    "        def step(v: Vertex):\n",
    "            #find our starting node - the one with the correct name\n",
    "            if v.get_property_or_else(\"name\",\"\") == name: \n",
    "                #Set the `separation` of this node to 0 and send this value to all its neighbours\n",
    "                v[state_name] = 0\n",
    "                v.message_all_neighbours(0)\n",
    "            else:\n",
    "                #if this isn't the starting node, set its separation to -1, which we can imagine means 'unreached'\n",
    "                v[state_name] = -1    \n",
    "\n",
    "        #create our iteration function\n",
    "        def iterate(v: Vertex):  \n",
    "            #if the node hasn't been reached before (current state is still -1)\n",
    "            if v[state_name] == -1:\n",
    "                #take the minimum value of the messages received and add 1\n",
    "                sep_state   = min(v.message_queue()) + 1\n",
    "                #set its state to the new separation value\n",
    "                v[state_name] = sep_state\n",
    "                #and tell its neighbours\n",
    "                v.message_all_neighbours(sep_state)\n",
    "            #if the node has been reached before we can ignore the messages and vote to halt\n",
    "            else:\n",
    "                v.vote_to_halt()\n",
    "\n",
    "        #finally we apply these two functions to the graph\n",
    "        #for iterate we set the maximum supersteps to 6 and \n",
    "        # execute_messaged_only to True as nodes which receive no new information don't need to do anything.\n",
    "        return graph.step(step).iterate(iterate, iterations=6,execute_messaged_only=True)\n",
    "\n",
    "    #define our tabularise function which calls select on the graph and returns the vertex name and its separation value\n",
    "    def tabularise(self, graph: TemporalGraph) -> Table:\n",
    "        return graph.select(\"name\", \"separation\")\n",
    "\n",
    "#execute our new algorithm on the graph and return a dataframe\n",
    "graph \\\n",
    ".execute(DegreeSeparation()) \\\n",
    ".to_df() \n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Digging in the steps\n",
    "As you can see from the output we now have a separation value for all vertices in the graph. Most of these scores are quite low with Gandalf being a central character, but we still have a couple with `-1` who were unreachable. Lets dig into how we calculated these scores.\n",
    "\n",
    "### Step\n",
    "To begin we have one setup `step` in which we:\n",
    "\n",
    "* First check if a vertex is our __starting point__, where in the default case we are looking for Gandalf. \n",
    "* Once this node is found we:\n",
    "    * Create a new state on the vertex representing the __separation score__ and set it to `0` - i.e. no separation\n",
    "    * Message all of the node's neighbours to tell them they are directly connected. \n",
    "* If a node is not the __starting point__ their state is initialised to `-1`. We can read this as currently `unreachable`. \n",
    "\n",
    "### Iterate\n",
    "Next we implemented the bulk of the algorithm inside of a singular `iterate` function. Within this we:\n",
    "\n",
    "* Check if the vertex has been reached before (its state is still `-1`). \n",
    "* If it hasn't we take the minimum value it has been messaged by its neighbours and increment this by one. \n",
    "* This is its separation from the starting node which it can then tell to its neighbours. \n",
    "* If it has already been contacted it ignores all messages and `votes to halt` meaning the node is happy with its current state and it thinks the algorithm has converged. \n",
    "\n",
    "This function is then set to execute only on vertices that have been sent a message (`execute_messaged_only=True`) and runs up to \n",
    "6 times (`iterations = 6`) for our six degrees of separation).\n",
    "\n",
    "### The Return of The King\n",
    "Following the definition of `__call__()` we implemented a `tabularise()` which goes through all vertices and extracts the node name and the final degree of separation. \n",
    "\n",
    "You could additionally add a filter here to ignore any nodes with a score of `-1`. This would exclude nodes that are not at all connected to Gandalf or whose shortest path to Gandalf is longer than 6 hops"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## What is next?\n",
    "You should now be equipped with all the tools you need to do some very cool graph analysis with Raphtory. Your next stop should be the Python docs on the left where you can dig into the variety of functionality available on the `Graph`, `Vertex` and `Table`. We also have several example projects with some interesting algorithms which will be a good inspiration!\n",
    "\n",
    "If you have any issues or just want to tell us about your awesome new project, come and join us on [Slack](https://join.slack.com/t/raphtory/shared_invite/zt-xbebws9j-VgPIFRleJFJBwmpf81tvxA) where there are always many members of the Raphtory team hanging out."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "base",
   "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.10.4"
  },
  "vscode": {
   "interpreter": {
    "hash": "a9a34730827747ae273d5a5e0748f342e2039a3997e32d9a086d01739bd0f055"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}