class02c_find_python3.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# CS446/546 Class Session 2 \n",
    "\n",
    "## Adjacency Forests\n",
    "\n",
    "## Exploring the average running time for testing if there is an edge between an arbitrary pair of vertices, for different graph data structures"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this exercise, we'll compare the asymptotic computational running time for testing if there is an edge between a pair of vertices, averaged over all pairs of vertices in the graph. We'll do it for a series of undirected graphs (each generated using an Barabasi-Albert model), each with 1000 vertices. We will vary the number of edges in the graph; each graph will have a different average number of vertex neighbors for a vertex (i.e., each graph will have a different average vertex degree). We will time how long it takes to test all possible pairs of vertices for whether or not there is an edge between them, for each of four different graph data structures (adjacency matrix, adjacency list, edge list, and adjacency forest)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We'll need the \"bintrees\" python module in order to get an implementation of a binary search tree (AVLTree is the class that we will use)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import igraph\n",
    "import timeit\n",
    "import itertools\n",
    "import bintrees "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we will need to define some functions for testing a pair of vertices to see if they have an edge between them, for each of three different kinds of data structures for representing the graph.\n",
    "\n",
    "First, we need to create a function, `find_matrix`, that accepts an adjacency matrix (`np.matrix`) `gmat` and a row index `i` and a column index `j`, and returns `True` if there is an edge between vertices `i` and `j` (or `False` otherwise). You'll probably want to use array indexing here."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_matrix(gmat, i, j):\n",
    "    return (gmat[i,j] == 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, we need to create a function, `find_adj_list`, that accepts an adjacency list `adj_list` (which is actually a list of lists of integer vertex IDs). Your function should return `True` if there is an edge between vertex `i` and vertex `j`, or `False` otherwise). You may wisth to use the built-in keyword `in`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_adj_list(adj_list, i, j):\n",
    "    return j in adj_list[i]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, we need to create a function, `find_edge_list`, that accepts an edge list argument `edge_list` (which is actually a `numpy.array` of lists (each of length two) containing the vertex IDs of vertices that are connected in the graph). Your function should return `True` if there is an edge between vertex `i` and vertex `j`, or `False` otherwise). You will want to use the functions `numpy.where`, `tolist`, and the keyword `in`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_edge_list(edge_list, i, j):\n",
    "    return (([i,j] in edge_list) or ([j,i] in edge_list))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next we need to create a function, `find_bst_forest`, that accepts an \"adjacency forest\" argument `bst_forest` (which is actually a list of objects of class `bintrees.AVLTree`). Your function should return `True` if there is an edge between vertex `i` and vertex `j`, or `False` otherwise). You'll want to use the class method `__contains__(j)`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_bst_forest(bst_forest, i, j):\n",
    "    return bst_forest[i].__contains__(j)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, we will need a function, `get_bst_forest`, that can create an adjacency forest representation for a graph given an adjacency list as input.  *Important NOTE:* I have deleted the code to create the AVL tree. You should add it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_bst_forest(theadjlist):\n",
    "    g_adj_list = theadjlist\n",
    "    n = len(g_adj_list)\n",
    "    theforest = []\n",
    "    for i in range(0,n):        \n",
    "        itree = bintrees.AVLTree()\n",
    "        for j in g_adj_list[i]:\n",
    "            itree.insert(j,1)\n",
    "        theforest.append(itree)\n",
    "    return theforest"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is the code to run the simulation (generate the graph and obtain timing statistics). To keep the code running time reasonable, I decided to only compare the running times for the \"adjacency list\" and \"adjacency forest\" (aka \"adjacency trees\") graph data structures.  The parameter \"n\" is the number of vertices (fixed at 1000) and the parameter \"k\" is the average vertex degree (which we will vary in this exercise). For speed, I have turned off replication (by setting nrep=1 and nsubrep=1), but you can try it with larger values of nrep to see if the results hold up (I expect they will):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def do_sim(n, k):\n",
    "\n",
    "    retlist = []\n",
    "    \n",
    "    nrep = 1\n",
    "    nsubrep = 1\n",
    "    \n",
    "    for _ in itertools.repeat(None, nrep):\n",
    "      \n",
    "        # make the random undirected graph\n",
    "        g = igraph.Graph.Barabasi(n, k)       \n",
    "        \n",
    "        # get the graph in three different representations\n",
    "        g_matrix = np.matrix(g.get_adjacency().data)\n",
    "\n",
    "        g_adj_list = g.get_adjlist()\n",
    "        \n",
    "        g_bst_forest = get_bst_forest(g_adj_list)\n",
    "        \n",
    "        start_time = timeit.default_timer()\n",
    "        \n",
    "        # inner loop only needs to go from i+1 to n, since the graph is undirected        \n",
    "        for _ in itertools.repeat(None, nsubrep):\n",
    "            for i in range(0, n):\n",
    "                for j in range(i+1, n):\n",
    "                    find_matrix(g_matrix, i, j)     \n",
    "        \n",
    "        matrix_elapsed = timeit.default_timer() - start_time\n",
    "        \n",
    "        start_time = timeit.default_timer()\n",
    "        \n",
    "        # inner loop only needs to go from i+1 to n, since the graph is undirected        \n",
    "        for _ in itertools.repeat(None, nsubrep):\n",
    "            for i in range(0, n):\n",
    "                for j in range(i+1, n):\n",
    "                    find_adj_list(g_adj_list, i, j)     \n",
    "        \n",
    "        adjlist_elapsed = timeit.default_timer() - start_time\n",
    "            \n",
    "        start_time = timeit.default_timer()\n",
    "        \n",
    "        # inner loop only needs to go from i+1 to n, since the graph is undirected\n",
    "        for _ in itertools.repeat(None, nsubrep):\n",
    "            for i in range(0, n):\n",
    "                for j in range(i+1, n):\n",
    "                    j in g_bst_forest[i]\n",
    "                    \n",
    "        forest_elapsed = timeit.default_timer() - start_time\n",
    "        \n",
    "        retlist.append([matrix_elapsed, adjlist_elapsed, forest_elapsed])\n",
    "\n",
    "        # get the results in seconds, and make sure to divide by number of vertex pairs\n",
    "    return 1000000*np.mean(np.array(retlist), axis=0)/(n*(n-1)/2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Compare the results for differing average degree (i.e., k) values.  At k=50, the \"adjacency forest\" method (aka \"adjacency tree\" method) is a bit faster than the adjacency list method. By k=100, the \"adjacency forest\" method is substantially faster than the \"adjacency list\" method."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([1.38406959, 0.25522564, 1.3513726 ])"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "do_sim(1000,5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([1.33125983, 0.33512479, 1.44965533])"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "do_sim(1000,10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([1.36232461, 0.56983606, 1.66950122])"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "do_sim(1000,20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([1.31820861, 1.01326204, 1.76006516])"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "do_sim(1000,50)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([1.36256145, 1.77881304, 1.83688102])"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "do_sim(1000,100)"
   ]
  }
 ],
 "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
}