Internal Exam 2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Instruction\n",
    "\n",
    "__Never__ use an additional import statement."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Graph Class\n",
    "\n",
    "The following class is used for inputting graphs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Graph:\n",
    "    def __init__(self, edges, directed=False):\n",
    "        self.adj_list = {}\n",
    "        self.directed = directed\n",
    "        \n",
    "        for u, v, k in edges:\n",
    "            self.add_edge(u, v, k)\n",
    "            \n",
    "    def _add_edge_single(self, u, v, k):\n",
    "        \"\"\"Internal function. Do not use directly.\n",
    "        Add a single edge to the graph.\n",
    "        \"\"\"\n",
    "        if u not in self.adj_list:\n",
    "            self.adj_list[u] = []\n",
    "        self.adj_list[u].append((v, k))        \n",
    "                \n",
    "    def add_edge(self, u, v, k):\n",
    "        \"\"\"Add an edge to the graph. Add the reverse edge \n",
    "        when the graph is undirected.\"\"\"\n",
    "        self._add_edge_single(u, v, k)\n",
    "        if not self.directed:\n",
    "            self._add_edge_single(v, u, k)\n",
    "    \n",
    "    def neighbors(self, u):\n",
    "        \"\"\"Return the list of neighbors and the \n",
    "        corresponding weights of u\"\"\"\n",
    "        return self.adj_list[u]\n",
    "    \n",
    "    \n",
    "    def vertices(self):\n",
    "        \"\"\"Return the set of vertices of the graph\"\"\"\n",
    "        return self.adj_list.keys()\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Question 1\n",
    "\n",
    "Implement the Kruskal's algorithm for computing minimum spanning tree. Your function should return the sum of the weights of all the edges _not_ present in the final MST."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Add any functions/classes as necessary.\n",
    "\n",
    "def kruskal_edge_sum(graph):\n",
    "    # return the sum of weights of edges missing from the final MST."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test\n",
    "\n",
    "graph = Graph([(0, 1, 4), (0, 7, 8), (1, 2, 8), (1, 7, 11), (2, 3, 7), (2, 8, 2), (2, 5, 4), (3, 4, 9), (3, 5, 14), (4, 5, 10), (5, 6, 2), (6, 7, 1), (6, 8, 6), (7, 8, 7)])\n",
    "\n",
    "assert kruskal_edge_sum(graph) == 56\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Question 2\n",
    "\n",
    "Implement the Dijkstra's algorithm. The weight of each node may change during execution of the algorithm. Your function should keep track of all the weights, not just the latest weight. The function should return a dictionary mapping nodes to their list of weights. Use Python's _float('inf')_ to represent infinite weights."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Add any functions/classes as necessary.\n",
    "\n",
    "def dijkstra_trace(graph, s):\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test\n",
    "\n",
    "graph = Graph( [(0, 1, 10), (0, 4, 5), (1, 2, 1), (1, 4, 2), (2, 3, 4), (3, 2, 6), (3, 0, 7), (4, 1, 3), (4, 2, 9), (4, 3, 2)], directed=True )\n",
    "\n",
    "trace = dijkstra_trace(graph)\n",
    "\n",
    "inf = float('inf')\n",
    "\n",
    "assert trace[0] == [0]\n",
    "assert trace[1] == [inf, 10, 8]\n",
    "assert trace[2] == [inf, 14, 13, 9]\n",
    "assert trace[3] == [inf, 7]\n",
    "assert trace[4] == [inf, 5]"
   ]
  }
 ],
 "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}