Lab-05 Dijkstra and Bellman-Ford.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Dijkstra and Bellman-Ford\n",
    "\n",
    "\n",
    "This assignment is for implementing two single-source shortest paths algorithms: Dijkstra's and Bellman-Ford."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Graph Class\n",
    "\n",
    "The class used for inputting graphs is given below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "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",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Output Class\n",
    "\n",
    "For output, we will use a class for storing paths and weights."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class PathWeight:\n",
    "    def __init__(self, node, parent, weight):\n",
    "        self.node = node     # node's name.\n",
    "        self.parent = parent # parent node's PathWeight object.\n",
    "        self.weight = weight"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The output should be a dictionary which maps a node to its PathWeight object."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Dijkstra's Algorithm\n",
    "\n",
    "Implement the dijkstra's shortest-paths algorithm as follows."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Add any necessary classes (e.g., the PriorityQueue classes.)\n",
    "\n",
    "dijkstra(graph, s):\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test\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",
    "h = dijkstra(graph, 0)\n",
    "assert h[0].weight = 0\n",
    "assert h[1].weight == 8\n",
    "assert h[2].weight == 9\n",
    "assert h[3].weight == 7\n",
    "assert h[4].weight == 5\n",
    "\n",
    "assert (h[1].parent).node == 4\n",
    "assert (h[2].parent).node == 1\n",
    "assert (h[3].parent).node == 4\n",
    "assert (h[4].parent).node == 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Bellman-Ford Algorithm\n",
    "\n",
    "Next, we will implement the Bellman-Ford algorithm.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Add any functions necessary.\n",
    "\n",
    "def bellman_ford(graph, s):\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",
    "h = bellman_ford(graph, 0)\n",
    "assert h[0].weight = 0\n",
    "assert h[1].weight == 8\n",
    "assert h[2].weight == 9\n",
    "assert h[3].weight == 7\n",
    "assert h[4].weight == 5\n",
    "\n",
    "assert (h[1].parent).node == 4\n",
    "assert (h[2].parent).node == 1\n",
    "assert (h[3].parent).node == 4\n",
    "assert (h[4].parent).node == 0\n",
    "\n",
    "graph = Graph( [(0, 1, 6), (0, 4, 7), (1, 2, 5), (1, 4, 8), (1, 3, -4), (2, 1, -2), (3, 0, 2), (3, 2, 7), (4, 2, -3), (4, 3, 9)], directed=True )\n",
    "h = bellman_ford(graph, 0)\n",
    "assert h[0].weight = 0\n",
    "assert h[1].weight == 2\n",
    "assert h[2].weight == 4\n",
    "assert h[3].weight == -2\n",
    "assert h[4].weight == 7\n",
    "\n",
    "assert (h[1].parent).node == 2\n",
    "assert (h[2].parent).node == 4\n",
    "assert (h[3].parent).node == 1\n",
    "assert (h[4].parent).node == 0\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.6.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}