{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# MCL summer workshop in graph theory\n",
    "# Lab 6/29/16\n",
    "\n",
    "At this point you have several options for what to work on:\n",
    "* [Monday's lab](http://homepages.math.uic.edu/~scole3/summer2016/labs/Lab%206-27-16.ipynb)\n",
    "* [Codecademy Python tutorial](https://www.codecademy.com/learn/python)\n",
    "* New lab below.  Feel free to work on this even if you didn't finish Monday's lab."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise 1: Implementing BFS\n",
    "\n",
    "Recall that BFS is an algorithm that calculates the *distance* from a single start vertex $s$ to *every* other vertex.\n",
    "\n",
    "Write a function ``BFS( ``$G$ ``,`` $s$ ``)`` which performs a BFS in $G$ starting at $s$.  Assume that the vertices of $G$ are 0, 1, 2, ...  It should return a list whose $i$th element is the distance from $s$ to $i$.  You can use -1 or `None` (the Python equivalent of `null` in Java) to signify vertices whose distances have not been set.\n",
    "\n",
    "For example, for $K_3$ `BFS` starting at vertex 0 should return `[0, 1, 1]`, since vertex 0 is distance 0 from itself and distance 1 from vertices 1 and 2.\n",
    "\n",
    "Use the `CompleteGraph`, `Path`, and `RandomGraph` functions from last time for testing.  If you didn't finish that part of the lab, or if you're afraid you didn't do it correctly, I added those functions to graphs.py so you can use them.  You can download the latest version [here](http://homepages.math.uic.edu/~scole3/summer2016/labs/graphs.py)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from graphs import *\n",
    "\n",
    "def BFS(G, s):\n",
    "    \n",
    "    n = G.numVertices()\n",
    "    dists = [-1 for i in range(n)]\n",
    "    \n",
    "    # distance from s to itself is 0\n",
    "    dists[s] = 0\n",
    "    \n",
    "    toVisit = [s]\n",
    "    \n",
    "    for d in range(n):\n",
    "        \n",
    "        ##### YOUR CODE HERE #####\n",
    "        \n",
    "        # For each vertex at distance d\n",
    "            # Mark all unmarked neighbors as distance d + 1\n",
    "            # Hint: G.neighbors(v) gives you a list of v's neighbors\n",
    "               \n",
    "    return dists\n",
    "\n",
    "###### Testing ######\n",
    "n = 10\n",
    "G = CompleteGraph(n) # Try changing this to Path, Cycle, and RandomGraph\n",
    "startVertex = 0\n",
    "L = BFS(G, startVertex)\n",
    "\n",
    "print(\"Graph:\")\n",
    "print(G)\n",
    "print(\"Start vertex: \" + str(startVertex))\n",
    "print(\"Vertex distances: \" + str(L))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise 2: Weighted coins\n",
    "\n",
    "You can skip this exercise if you are using my [updated graphs.py](http://homepages.math.uic.edu/~scole3/summer2016/labs/graphs.py).\n",
    "\n",
    "Write a function `weightedCoin(` $p$ `)` which returns `True` with probability $p$, `False` with probability $1 - p$.\n",
    "\n",
    "Hint: use the function `random.rand()`, which returns a random decimal between 0 and 1.  The probability that it is between 0 and $p$ is $p$..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "def weightedCoin(p):\n",
    "    \n",
    "    # Your code here\n",
    "    \n",
    "    return False\n",
    "\n",
    "#### Testing ####\n",
    "\n",
    "p = .2\n",
    "n = 100\n",
    "\n",
    "# Flip n coins; keep track of number of heads\n",
    "print(\"Flipping \" + str(n) + \" coins...\")\n",
    "numHeads = 0\n",
    "for i in range(n):\n",
    "    if weightedCoin(p):\n",
    "        numHeads += 1\n",
    "\n",
    "print(\"Proportion that came up heads: \" + str(numHeads / n) + \" (should be approx. \" + str(p) + \")\" )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now modify your `RandomGraph` function from last time to add edges with probability $p$ instead of $1/2$.  Again, be careful not to flip coins for both $uv$ and $vu$!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from graphs import *\n",
    "\n",
    "def RandomGraph(n, p):\n",
    "    \n",
    "    # Your code here\n",
    "    \n",
    "###### Testing ######\n",
    "\n",
    "print(RandomGraph(10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise 3: One connected component\n",
    "\n",
    "Write a function `connectedComponent(` $G, v$ `)` which returns a list of vertices in the same connected component as $v$.\n",
    "\n",
    "Hint: use `BFS` from Exercise 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from graphs import *\n",
    "\n",
    "def connectedComponent(G, v):\n",
    "    \n",
    "    CC = [v] # v is always in its own connected component\n",
    "    \n",
    "    # Your code here\n",
    "    \n",
    "    return CC\n",
    "\n",
    "###### Testing ######\n",
    "\n",
    "n = 10\n",
    "G = RandomGraph(n, .2) \n",
    "startVertex = 0\n",
    "L = connectedComponent(G, startVertex)\n",
    "\n",
    "print(\"Graph:\")\n",
    "print(G)\n",
    "print(\"Start vertex: \" + str(startVertex))\n",
    "print(\"Connected component: \" + str(L))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise 4: Connected components\n",
    "\n",
    "Now write a function `connectedComponents(` $G$ `)` which returns *all* connected components of $G$.  It should return a list of lists, with each inner list being one of the connected components.\n",
    "\n",
    "Hint: use Exercise 3 to find the connected components one by one!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from graphs import *\n",
    "\n",
    "def connectedComponents(G):\n",
    "    CCs = []\n",
    "    \n",
    "    # Your code here\n",
    "    \n",
    "    return CCs\n",
    "\n",
    "######## Testing ########\n",
    "\n",
    "n = 10\n",
    "G = RandomGraph(n, .2) \n",
    "L = connectedComponents(G)\n",
    "\n",
    "print(\"Graph:\")\n",
    "print(G)\n",
    "print(\"Connected components: \" + str(L))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise 5: Matrix multiplication\n",
    "\n",
    "You can use a 2D list `A` to represent a matrix $A$ in Python, with `A[i][j]` corresponding to $a_{ij}$.  Write a function `mult(` $A, B$ `)` which multiplies $A$ and $B$ (using matrix multiplication) and returns the resulting matrix.  You can assume that $A$ and $B$ are both $n \\times n$, if that makes life easier."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def mult(A, B):\n",
    "    n = len(A)\n",
    "    \n",
    "    # Start with an n x n matrix of 0s\n",
    "    AB = [[0 for j in range(n)] for i in range(n)]\n",
    "    \n",
    "    for i in range(n):\n",
    "        for j in range(n):\n",
    "            \n",
    "            # Calculate the correct value of AB[i][j]\n",
    "    \n",
    "    return AB\n",
    "\n",
    "###### Testing ######\n",
    "\n",
    "def printMatrix(A):\n",
    "    \"\"\"Pretty print a matrix A\"\"\"\n",
    "    for row in A:\n",
    "        print(row)\n",
    "    print(\"\")\n",
    "        \n",
    "A = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]\n",
    "B = [[1, -1, 1], [-1, 1, 1], [1, -1, 1]]\n",
    "print(\"A = \")\n",
    "printMatrix(A)\n",
    "print(\"B = \")\n",
    "printMatrix(B)\n",
    "print(\"AB = \")\n",
    "printMatrix(mult(A, B))\n",
    "print(\"BA = \")\n",
    "printMatrix(mult(B, A))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise 6: Adjacency matrices\n",
    "\n",
    "**Definition.**  Let $G$ be a graph on $n$ vertices.  The *adjacency matrix* of $G$ is an $n \\times n$ matrix $A$ such that $a_{ij}$ is the number of edges from vertex $i$ to vertex $j$\n",
    "\n",
    "Draw the graph represented below and then write down its adjacency matrix."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0: [8, 1, 3, 7]\n",
      "1: [0]\n",
      "2: [6]\n",
      "3: [0, 9, 5, 6]\n",
      "4: [5]\n",
      "5: [3, 4]\n",
      "6: [2, 3]\n",
      "7: [0, 8]\n",
      "8: [0, 7]\n",
      "9: [3]\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print(RandomGraph(10, .25))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now write a function that returns the adjacency matrix of a graph $G$.  Since our `Graph` class does not allow multiple edges, all entries will be 0 or 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from graphs import *\n",
    "\n",
    "def adjacencyMatrix(G):\n",
    "    n = G.numVertices()\n",
    "    A = [[0 for j in range(n)] for i in range(n)]\n",
    "    \n",
    "    # Your code here\n",
    "    \n",
    "    return A\n",
    "\n",
    "###### Testing ######\n",
    "\n",
    "G = CompleteGraph(10) # Try with Path, Cycle, RandomGraph, etc.\n",
    "print(\"Graph:\")\n",
    "print(G)\n",
    "print(\"Adjacency matrix:\")\n",
    "printMatrix(adjacencyMatrix(G))\n",
    "    "
   ]
  }
 ],
 "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}