class02b_storage_python3.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Class Session 2 \n",
    "## Comparing running times for enumerating neighbors of all vertices in a graph (with different graph data structures)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this notebook we will measure the running time for enumerating the neighbor vertices for three different data structures for representing an undirected graph:\n",
    "- adjacency matrix\n",
    "- adjacency list\n",
    "- edge list\n",
    "\n",
    "Let's assume that each vertex is labeled with a unique integer number.  So if there are N vertices, the vertices are labeled 0, 2, 3, 4, ..., N-1.\n",
    "\n",
    "First, we will import all of the Python modules that we will need for this exercise:\n",
    "note how we assign a short name, \"np\" to the numpy module. This will save typing. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import igraph\n",
    "import timeit\n",
    "import itertools"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, define a function that returns the index numbers of the neighbors of a vertex i, when the \n",
    "graph is stored in adjacency matrix format.  So your function will accept as an input a NxN numpy matrix. The function should return a list (of index numbers of the neighbors)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def enumerate_matrix(gmat, i):\n",
    "    return np.nonzero(gmat[i,:])[1].tolist()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Define a function that enumerates the neighbors of a vertex i, when the \n",
    "graph is stored in adjacency list format (a list of lists). The function should return a list (of index numbers of the neighbors)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def enumerate_adj_list(adj_list, i):\n",
    "    return adj_list[i]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Define a function that enumerates the neighbors of a vertex i, when the \n",
    "graph is stored in edge-list format (a numpy array of length-two-lists); use `numpy.where` and `numpy.unique`. The function should return a list (of index numbers of the neighbors)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def enumerate_edge_list(edge_list, i):\n",
    "    inds1 = np.where(edge_list[:,0] == i)[0]\n",
    "    elems1 = edge_list[inds1, 1].tolist()\n",
    "    inds2 = np.where(edge_list[:,1] == i)[0]\n",
    "    elems2 = edge_list[inds2, 0].tolist()\n",
    "    return np.unique(elems1 + elems2).tolist()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this notebook, we are going to create some random networks. We'll use the Barabasi-Albert method, which has two parameters, *n* and *m* (where *n* > *m*). (For more information on the Barabasi-Albert model, see http://barabasi.com/f/622.pdf). In `igraph`, the `igraph.Graph.Barabasi` method will generate a single connected undirected graph with *n* vertices and where the total number *E* of edges is:\n",
    "\n",
    "    E = nm - (m^2 / 2) - m/2\n",
    "    \n",
    "Let's plot a Barabasi-Albert graph generated using *n*=5 and *m*=3:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n",
       "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"200pt\" height=\"200pt\" viewBox=\"0 0 200 200\" version=\"1.1\">\n",
       "<g id=\"surface14\">\n",
       "<rect x=\"0\" y=\"0\" width=\"200\" height=\"200\" style=\"fill:rgb(100%,100%,100%);fill-opacity:1;stroke:none;\"/>\n",
       "<path style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(26.666667%,26.666667%,26.666667%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 39.375 152.074219 L 105.496094 106.386719 \"/>\n",
       "<path style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(26.666667%,26.666667%,26.666667%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 39.375 152.074219 L 20 20 \"/>\n",
       "<path style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(26.666667%,26.666667%,26.666667%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 105.496094 106.386719 L 20 20 \"/>\n",
       "<path style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(26.666667%,26.666667%,26.666667%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 39.375 152.074219 L 152.570312 41.007812 \"/>\n",
       "<path style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(26.666667%,26.666667%,26.666667%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 105.496094 106.386719 L 152.570312 41.007812 \"/>\n",
       "<path style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(26.666667%,26.666667%,26.666667%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 20 20 L 152.570312 41.007812 \"/>\n",
       "<path style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(26.666667%,26.666667%,26.666667%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 39.375 152.074219 L 180 180 \"/>\n",
       "<path style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(26.666667%,26.666667%,26.666667%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 105.496094 106.386719 L 180 180 \"/>\n",
       "<path style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(26.666667%,26.666667%,26.666667%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 152.570312 41.007812 L 180 180 \"/>\n",
       "<path style=\"fill-rule:nonzero;fill:rgb(100%,0%,0%);fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 49.375 152.074219 C 49.375 157.597656 44.898438 162.074219 39.375 162.074219 C 33.851562 162.074219 29.375 157.597656 29.375 152.074219 C 29.375 146.550781 33.851562 142.074219 39.375 142.074219 C 44.898438 142.074219 49.375 146.550781 49.375 152.074219 \"/>\n",
       "<path style=\"fill-rule:nonzero;fill:rgb(100%,0%,0%);fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 115.496094 106.386719 C 115.496094 111.910156 111.019531 116.386719 105.496094 116.386719 C 99.972656 116.386719 95.496094 111.910156 95.496094 106.386719 C 95.496094 100.863281 99.972656 96.386719 105.496094 96.386719 C 111.019531 96.386719 115.496094 100.863281 115.496094 106.386719 \"/>\n",
       "<path style=\"fill-rule:nonzero;fill:rgb(100%,0%,0%);fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 30 20 C 30 25.523438 25.523438 30 20 30 C 14.476562 30 10 25.523438 10 20 C 10 14.476562 14.476562 10 20 10 C 25.523438 10 30 14.476562 30 20 \"/>\n",
       "<path style=\"fill-rule:nonzero;fill:rgb(100%,0%,0%);fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 162.570312 41.007812 C 162.570312 46.53125 158.09375 51.007812 152.570312 51.007812 C 147.050781 51.007812 142.570312 46.53125 142.570312 41.007812 C 142.570312 35.488281 147.050781 31.007812 152.570312 31.007812 C 158.09375 31.007812 162.570312 35.488281 162.570312 41.007812 \"/>\n",
       "<path style=\"fill-rule:nonzero;fill:rgb(100%,0%,0%);fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 190 180 C 190 185.523438 185.523438 190 180 190 C 174.476562 190 170 185.523438 170 180 C 170 174.476562 174.476562 170 180 170 C 185.523438 170 190 174.476562 190 180 \"/>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<igraph.drawing.Plot at 0x7f864c32c7f0>"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "igraph.drawing.plot(igraph.Graph.Barabasi(5,3), bbox=[0,0,200,200])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we need to write a simulation funtion that generates random graphs and enumerates all neighbors of each vertex in the graph (while computing running time), for each of three different graph data structures (adjacency matrix, adjacency list, and edge list). The function's sole argument \"n\" is the number of vertices.\n",
    "It returns a length-three list containing the average running time for enumerating the neighbor vertices of a vertex in the graph. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def do_sim_ms(n):\n",
    "\n",
    "    retlist = []\n",
    "    \n",
    "    nrep = 10\n",
    "    nsubrep = 10\n",
    "    \n",
    "    # this is (sort of) a Python way of doing the R function \"replicate\":\n",
    "    for _ in itertools.repeat(None, nrep):\n",
    "        \n",
    "        # make a random undirected graph with fixed (average) vertex degree = 5\n",
    "        g = igraph.Graph.Barabasi(n, 5)\n",
    "        \n",
    "        # get the graph in three different representations\n",
    "        g_matrix = np.matrix(g.get_adjacency().data)\n",
    "        g_adj_list = g.get_adjlist()\n",
    "        g_edge_list = np.array(g.get_edgelist())\n",
    "    \n",
    "        start_time = timeit.default_timer()\n",
    "    \n",
    "        for _ in itertools.repeat(None, nsubrep):\n",
    "            for i in range(0, n):\n",
    "                enumerate_matrix(g_matrix, i)\n",
    "    \n",
    "        matrix_elapsed = timeit.default_timer() - start_time\n",
    "        \n",
    "        start_time = timeit.default_timer()\n",
    "        \n",
    "        for _ in itertools.repeat(None, nsubrep):\n",
    "             for i in range(0, n):\n",
    "                enumerate_adj_list(g_adj_list, i)        \n",
    "        \n",
    "        adjlist_elapsed = timeit.default_timer() - start_time\n",
    "        \n",
    "        start_time = timeit.default_timer()\n",
    "        \n",
    "        for _ in itertools.repeat(None, nsubrep):\n",
    "             for i in range(0, n):\n",
    "                enumerate_edge_list(g_edge_list, i)        \n",
    "        \n",
    "        edgelist_elapsed = timeit.default_timer() - start_time\n",
    "        \n",
    "        retlist.append([matrix_elapsed, adjlist_elapsed, edgelist_elapsed])\n",
    "\n",
    "        resarray = 1000 * np.mean(np.array(retlist), axis=0)/n\n",
    "\n",
    "        resdict = {'adjacency matrix': resarray[0],\n",
    "                   'adjacency list': resarray[1],\n",
    "                   'edge list': resarray[2]}\n",
    "        # average over replicates and then\n",
    "        # divide by n so that the running time results are on a per-vertex basis\n",
    "    return resdict"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A simulation with 1000 vertices clearly shows that adjacency list is fastest:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'adjacency matrix': 0.15857457559905014,\n",
       " 'adjacency list': 0.0009786342969164252,\n",
       " 'edge list': 0.39372085049981254}"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "do_sim_ms(1000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's quadruple \"n\". We see the expected behavior, with the running time for the adjacency-matrix and edge-list formats going up when we increase \"n\", but there is hardly any change in the running time for the graph stored in adjacency list format:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'adjacency matrix': 0.3456842259489349,\n",
       " 'adjacency list': 0.0010989339258230756,\n",
       " 'edge list': 0.7524919939503889}"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "do_sim_ms(4000)"
   ]
  }
 ],
 "metadata": {
  "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.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}