cugraph/traversal/SSSP.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Single Source Shortest Path (SSSP)\n",
    "\n",
    "In this notebook, we will use cuGraph to compute the shortest path from a starting vertex to everyother vertex in our training dataset.\n",
    "\n",
    "Notebook Credits\n",
    "* Original Authors: Bradley Rees and James Wyles\n",
    "* available since rerlease 0.6\n",
    "* Last Edit: 10/28/2019\n",
    "\n",
    "\n",
    "RAPIDS Versions: 0.10.0   \n",
    "\n",
    "Test Hardware\n",
    "\n",
    "* GV100 32G, CUDA 10.0\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "## Introduction\n",
    "\n",
    "Single source shortest path computes the shortest paths from the given starting vertex to all other reachable vertices. \n",
    "\n",
    "To compute SSSP for a graph in cuGraph we use:\n",
    "**cugraph.sssp(G, source)**\n",
    "\n",
    "Input\n",
    "* __G__: cugraph.Graph object\n",
    "* __source__: int, Index of the source vertex\n",
    "\n",
    "Returns \n",
    "* __df__:  a cudf.DataFrame object with two columns:\n",
    "    * df['vertex']: The vertex identifier for the vertex\n",
    "    * df['distance']: The computed distance from the source vertex to this vertex\n",
    "    * df['predecessor']: The predecessor vertex along this paths.  Allows paths to be recreated\n",
    "\n",
    "\n",
    "## cuGraph Notice \n",
    "The current version of cuGraph has some limitations:\n",
    "\n",
    "* Vertex IDs need to be 32-bit integers.\n",
    "* Vertex IDs are expected to be contiguous integers starting from 0.\n",
    "\n",
    "cuGraph provides the renumber function to mitigate this problem. Input vertex IDs for the renumber function can be either 32-bit or 64-bit integers, can be non-contiguous, and can start from an arbitrary number. The renumber function maps the provided input vertex IDs to 32-bit contiguous integers starting from 0. cuGraph still requires the renumbered vertex IDs to be representable in 32-bit integers. These limitations are being addressed and will be fixed soon."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Test Data\n",
    "We will be using the Zachary Karate club dataset \n",
    "*W. W. Zachary, An information flow model for conflict and fission in small groups, Journal of\n",
    "Anthropological Research 33, 452-473 (1977).*\n",
    "\n",
    "\n",
    "![Karate Club](../img/zachary_black_lines.png)\n",
    "\n",
    "This is a small graph which allows for easy visual inspection to validate results.  \n",
    "__Note__: The Karate dataset starts with vertex ID 1 which the cuGraph analytics assume a zero-based starting ID.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Import needed libraries\n",
    "import cudf\n",
    "import cugraph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Read the data and adjust the vertex IDs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test file  - using the clasic Karate club dataset.  \n",
    "datafile='../data/karate-data.csv'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "gdf = cudf.read_csv(datafile, names=[\"src\", \"dst\"], delimiter='\\t', dtype=[\"int32\", \"int32\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "source": [
    "Since the data starts with vertex ID of 1, the code will add a disconnected vertex (ID 0) that \n",
    "is unreachable (no path from vertices in data to vertex 0).  In earlier version of cuGraph, we shifted the data\n",
    "so that it started to avoid that case.  Starting with release 0.8, a new feature to filter unreachable vertices from the results has been added"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "gdf.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Create a Graph and call SSSP"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# create a Graph \n",
    "G = cugraph.Graph()\n",
    "G.add_edge_list(gdf[\"src\"], gdf[\"dst\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Call cugraph.sssp to get the distances from vertex 1:\n",
    "df = cugraph.sssp(G, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Print the paths\n",
    "# Not using the filterred dataframe to ensure that vertex IDs match row IDs\n",
    "for i in range(len(ldf)) :\n",
    "    v = ldf['vertex'][i]   \n",
    "    d = int(df['distance'][v])\n",
    "   \n",
    "    path = [None] *  ( int(longest_distance) + 1)\n",
    "    path[d] = v\n",
    "    \n",
    "    while d > 0 :\n",
    "        v = df['predecessor'][v]\n",
    "        d = int(df['distance'][v])\n",
    "        path[d] = v\n",
    "        \n",
    "    print( \"(\" + str(i) + \") path: \" + str(path))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are a number of vertices with the same distance of 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "___\n",
    "Copyright (c) 2019, NVIDIA CORPORATION.\n",
    "\n",
    "Licensed under the Apache License, Version 2.0 (the \"License\");  you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0\n",
    "\n",
    "Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an \"AS IS\" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.\n",
    "___"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "cugraph_dev",
   "language": "python",
   "name": "cugraph_dev"
  },
  "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}