cugraph/traversal/BFS.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Breadth First Search (BFS) \n",
    "In this notebook, we will use cuGraph to compute the Breadth First Search path from a starting vertex to every other vertex in our training dataset.\n",
    "\n",
    "Notebook Credits\n",
    "* Original Authors: Bradley Rees and James Wyles\n",
    "* Feature available since 0.6\n",
    "* Last Edit: 10/28/2019\n",
    "\n",
    "RAPIDS Versions: 0.10.0    \n",
    "\n",
    "Test Hardware\n",
    "\n",
    "* GV100 32G, CUDA 10.0\n",
    "\n",
    "\n",
    "\n",
    "## Introduction\n",
    "\n",
    "As the name implies, BFS traverses the given graph in a breadth first manner. Starting at a specified vertex, the algorithms iteratively searches neighboring vertices.  \n",
    "\n",
    "\n",
    "@see https://en.wikipedia.org/wiki/Breadth-first_search\n",
    "\n",
    "\n",
    "To compute BFS in cuGraph use: __bfs(G, start_id)__\n",
    "\n",
    "* __G__: A cugraph.Graph object\n",
    "* __start_id__ : the starting vertex ID\n",
    "\n",
    "Returns:\n",
    "\n",
    "* __df__: cudf.DataFrame with three names columns:\n",
    "    * df[\"vertex\"]:   The vertex id.\n",
    "    * df[\"distance\"]: The distance to the starting vertex\n",
    "    * df[\"predecessor\"]: The vertex ID of the vertex that was used to reach this vertex\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",
    "Our test data is small so that results can be visually verified"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# First step is to import the needed libraries\n",
    "import cugraph\n",
    "import cudf\n",
    "from collections import OrderedDict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# define a print path function that take the dataframe and a vertex ID\n",
    "\n",
    "def print_path(df, id):\n",
    "    \n",
    "    # Use the BFS predecessors and distance to trace the path \n",
    "    # from vertex id back to the starting vertex ( vertex 1 in this example)\n",
    "    dist = df['distance'][id]\n",
    "    lastVert = id\n",
    "    for i in range(dist):\n",
    "        nextVert = df['predecessor'][lastVert]\n",
    "        d = df['distance'][lastVert]\n",
    "        print(\"Vertex: \" + str(lastVert) + \" was reached from vertex \" + str(nextVert) + \n",
    "        \" and distance to start is \" + str(d) )\n",
    "        lastVert = nextVert"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Read the data using cuDF"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Read the data file\n",
    "datafile='../data/karate-data.csv'\n",
    "\n",
    "gdf = cudf.read_csv(datafile, names=[\"src\", \"dst\"], delimiter='\\t', dtype=[\"int32\", \"int32\"] )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Look at the first few data records - the output should be two colums src and dst\n",
    "gdf.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you can see in the output, the starting vertex ID is 1.  For the BFS algorithm that is okay.   \n",
    "cuGraph will add an isolated vertex with an ID of zero.  It will not be reachable from the test dataset  "
   ]
  },
  {
   "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 BFS on the graph starting from vertex 1\n",
    "df = cugraph.bfs(G,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Let's take a looks at the structure of the returned dataframe\n",
    "df.dtypes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print_path(df, 22)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print_path(df, 30)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Picking a starting vertex\n",
    "Since we can see in the graph illustraion above that vertex 17 is at the edge of the graph, let's run BFS with that as the startring vertex"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Call BFS on the graph starting from vertex 17\n",
    "df2 = cugraph.bfs(G,17)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Print the max distance\n",
    "df2[\"distance\"].max()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that max returned an unexpected value.  That is becouse the isoluated vertex, 0, is unreachable.\n",
    "Whenever a graph contains disjointed components, the distance to the unconnected vertices will always be max_int"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "df2[\"distance\"][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# drop all large distances \n",
    "exp=\"distance < 100\"\n",
    "df3 = df2.query(exp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Print the max distance\n",
    "df3[\"distance\"].max()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Print path to vertex 30\n",
    "print_path(df2, 30)"
   ]
  },
  {
   "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
}