class04_storage_python3.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Class Session 4 Exercise:\n",
    "## Comparing asymptotic running time for enumerating neighbors of all vertices in a graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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."
   ]
  },
  {
   "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):"
   ]
  },
  {
   "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`:"
   ]
  },
  {
   "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": [
    "This next function is the simulation funtion.  \"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(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",
    "        # average over replicates and then\n",
    "        # divide by n so that the running time results are on a per-vertex basis\n",
    "    return np.mean(np.array(retlist), axis=0)/n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A simulation with 1000 vertices clearly shows that adjacency list is fastest:\n",
    "(I multiply by 1000 just so the results are in ms.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 0.13381058,  0.00126239,  0.36279364])"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "do_sim(1000)*1000"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 0.20205601,  0.00127165,  0.51099831])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "do_sim(2000)*1000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}