UW Lesson8 Graph Assignment Submission

Lesson8_GraphAssignment.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Adjacency List Representation of City Distances\n",
    "CityGraph = {\n",
    "    'cityA': [('cityB',10), ('cityC',5), ('cityD',1), ('cityG',100)],\n",
    "    'cityB': [('cityA',10), ('cityC',20), ('cityD',2), ('cityE',24), ('cityG',12)],\n",
    "    'cityC': [('cityA',5), ('cityB',20), ('cityD',18), ('cityF',14)],\n",
    "    'cityD': [('cityB',2), ('cityC',18), ('cityA',1), ('cityE',3)],\n",
    "    'cityE': [('cityB',24), ('cityD',3), ('cityF',6)],\n",
    "    'cityF': [('cityC',14), ('cityE',6)],\n",
    "    'cityG': [('cityA',100), ('cityB',12)]\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ShortestPath():\n",
    "    '''\n",
    "    O(V^2 + E).\n",
    "    '''\n",
    "    \n",
    "    def __init__(self, adjcency_list_data):\n",
    "        self.G = adjcency_list_data\n",
    "        \n",
    "    def find_min_city(self, unvisited, dist):\n",
    "        '''\n",
    "        O(V) search.\n",
    "        '''\n",
    "        min_city = None\n",
    "        min_dist = 1e8\n",
    "        for city in unvisited:\n",
    "            if dist.get(city, 1e8) < min_dist:\n",
    "                min_city = city\n",
    "                min_dist = dist[city]\n",
    "        return min_city, min_dist\n",
    "        \n",
    "    def compute_distances(self, cityX):\n",
    "        '''\n",
    "        compute distances and backpointers from cityX to all vertices.\n",
    "        O(V^2 + E)\n",
    "        '''\n",
    "        unvisited = list(self.G.keys())\n",
    "        dist = {cityX:0.,}\n",
    "        prev = {cityX:None,}\n",
    "        \n",
    "        while unvisited: # O(V)\n",
    "            curr_city, curr_dist = self.find_min_city(unvisited, dist)# O(V)\n",
    "            unvisited.remove(curr_city)\n",
    "            for neigh, neigh_dist in self.G[curr_city]: # O(E) in total\n",
    "                if neigh in unvisited:\n",
    "                    proposed_dist = curr_dist + neigh_dist\n",
    "                    if proposed_dist < dist.get(neigh, 1e8):\n",
    "                        dist[neigh] = proposed_dist\n",
    "                        prev[neigh] = curr_city\n",
    "\n",
    "        return dist, prev\n",
    "        \n",
    "    def query_distances(self, cityX, cityY):\n",
    "        '''\n",
    "        retrieve shortest path between two cities\n",
    "        O(V) to retreive path\n",
    "        '''\n",
    "        dist, prev = self.compute_distances(cityX)\n",
    "        curr_city = cityY\n",
    "        shortest_path_reversed = [curr_city] \n",
    "        while prev[curr_city]: # O(N)\n",
    "            shortest_path_reversed.append(prev[curr_city])\n",
    "            curr_city = prev[curr_city]\n",
    "        \n",
    "        return dist[cityY], list(reversed(shortest_path_reversed)) # O(V)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(4.0, ['cityA', 'cityD', 'cityE'])\n"
     ]
    }
   ],
   "source": [
    "SP = ShortestPath(CityGraph)\n",
    "print(SP.query_distances('cityA', 'cityE'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [],
   "source": [
    "import heapq\n",
    "\n",
    "class ShortestPathWithPriorityQueue():\n",
    "    '''\n",
    "    O(VlogV + E). Not using min heap.\n",
    "    '''\n",
    "    \n",
    "    def __init__(self, adjcency_list_data):\n",
    "        self.G = adjcency_list_data\n",
    "        \n",
    "    def find_min_city(self, heap):\n",
    "        '''\n",
    "        Using priority queue(min heap), can reduce to O(logV): O(1) retrieve, O(logV) to maintain.\n",
    "        '''\n",
    "        return heapq.heappop(heap)\n",
    "        \n",
    "    def compute_distances(self, cityX):\n",
    "        '''\n",
    "        compute distances and backpointers from cityX to all vertices.\n",
    "        '''\n",
    "        unvisited = list(self.G.keys())\n",
    "        dist = {cityX:0.,}\n",
    "        heap = [(0., cityX)]\n",
    "        prev = {cityX:None,}\n",
    "        \n",
    "        while unvisited: # O(V)\n",
    "            curr_dist, curr_city = self.find_min_city(heap)# O(logV)\n",
    "            if curr_city not in unvisited:\n",
    "                continue\n",
    "            unvisited.remove(curr_city)\n",
    "            for neigh, neigh_dist in self.G[curr_city]: # O(E) in total\n",
    "                if neigh in unvisited:\n",
    "                    proposed_dist = curr_dist + neigh_dist\n",
    "                    if proposed_dist < dist.get(neigh, 1e8):\n",
    "                        dist[neigh] = proposed_dist\n",
    "                        heapq.heappush(heap, (proposed_dist, neigh))\n",
    "                        prev[neigh] = curr_city\n",
    "\n",
    "        return dist, prev\n",
    "        \n",
    "    def query_distances(self, cityX, cityY):\n",
    "        '''\n",
    "        retrieve shortest path between two cities\n",
    "        O(V) to retreive path\n",
    "        '''\n",
    "        dist, prev = self.compute_distances(cityX)\n",
    "        curr_city = cityY\n",
    "        shortest_path_reversed = [curr_city] \n",
    "        while prev[curr_city]: # O(N)\n",
    "            shortest_path_reversed.append(prev[curr_city])\n",
    "            curr_city = prev[curr_city]\n",
    "        \n",
    "        return dist[cityY], list(reversed(shortest_path_reversed)) # O(V)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(4.0, ['cityA', 'cityD', 'cityE'])\n"
     ]
    }
   ],
   "source": [
    "SP = ShortestPathWithPriorityQueue(CityGraph)\n",
    "print(SP.query_distances('cityA', 'cityE'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [],
   "source": [
    "def test_Shortest_Path(SSP_impl):\n",
    "    SP = SSP_impl(CityGraph)\n",
    "    assert SP.query_distances('cityA', 'cityG')[0] == 15.\n",
    "    assert SP.query_distances('cityA', 'cityD')[0] == 1.\n",
    "    assert SP.query_distances('cityA', 'cityE')[0] == 4.\n",
    "    assert SP.query_distances('cityF', 'cityE')[0] == 6.\n",
    "    assert SP.query_distances('cityA', 'cityF')[0] == 10.\n",
    "    assert SP.query_distances('cityF', 'cityF')[0] == 0.\n",
    "    assert SP.query_distances('cityG', 'cityD')[0] == 14.\n",
    "    \n",
    "test_Shortest_Path(SSP_impl = ShortestPath)\n",
    "test_Shortest_Path(SSP_impl = ShortestPathWithPriorityQueue)"
   ]
  },
  {
   "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.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}