Lab-04-Graphs - BFS and DFS - Solved.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Graphs - BFS, DFS\n",
    "\n",
    "In this assignment, we will define a Graph datastructure and implement the basic graph search algorithms."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Graph Class\n",
    "\n",
    "Here we define the Graph class. Internally, we represent the graph using adjacency lists. Corresponding to each vertex $u$, we keep a list of tuples $(v, k)$, where $v$ is a neighbor of $u$ and $k$ is the weight of the edge $(u, v)$. To initialize the graph, we pass a list of tuples $(u, v, k)$."
   ]
  },
  {
   "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": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "g = Graph([(\"u\", \"v\", 1), (\"v\", \"w\", 2)])\n",
    "g.add_edge(\"w\", \"x\", 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[('u', 1), ('w', 2)]\n"
     ]
    }
   ],
   "source": [
    "print(g.neighbors(\"v\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Vertices: \n",
      "u\n",
      "v\n",
      "w\n",
      "x\n"
     ]
    }
   ],
   "source": [
    "print(\"Vertices: \")\n",
    "for v in g.vertices():\n",
    "    print(v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[('u', 1), ('w', 2)]\n",
      "{'u': [('v', 1)], 'v': [('u', 1), ('w', 2)], 'w': [('v', 2), ('x', 5)], 'x': [('w', 5)]}\n",
      "dict_keys(['u', 'v', 'w', 'x'])\n"
     ]
    }
   ],
   "source": [
    "print(g.adj_list['v'])\n",
    "print(g.adj_list)\n",
    "print(g.vertices())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Data structure for BFS and DFS Results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Visit:\n",
    "    def __init__(self, node, parent, discover, finish=None):\n",
    "        self.node = node\n",
    "        self.parent = parent\n",
    "        self.discover = discover\n",
    "        self.finish = finish"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## BFS\n",
    "\n",
    "Implement BFS using the above graph class. The BFS function will get two arguments: the first argument will be an object of the graph class. The second argument will be a node in the graph. The function should return a list of the parents and depths of each node using the above datastructure.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bfs(graph, node):\n",
    "    startnode_name = node\n",
    "    visitedList = []\n",
    "    queue = []\n",
    "    finalList = []\n",
    "\n",
    "    startNode = Visit(startnode_name, None, 0)\n",
    "    visitedList.append(startnode_name)\n",
    "    queue.append(startNode)\n",
    "    finalList.append(startNode)\n",
    "\n",
    "    while queue:\n",
    "        currentNode = queue.pop(0)\n",
    "        for selectedNodeTuple in graph.neighbors(currentNode.node):\n",
    "            if selectedNodeTuple[0] not in visitedList:\n",
    "                selectedNode = Visit(selectedNodeTuple[0], currentNode.node, currentNode.discover + selectedNodeTuple[1])\n",
    "                queue.append(selectedNode)\n",
    "                visitedList.append(selectedNode.node)\n",
    "                finalList.append(selectedNode)\n",
    "\n",
    "    return(finalList)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test\n",
    "\n",
    "g = Graph([(\"r\", \"s\", 1), (\"r\", \"v\", 1), (\"s\", \"w\", 1), (\"w\", \"t\", 1), (\"w\", \"x\", 1), (\"t\", \"x\", 1), (\"t\", \"u\", 1), (\"x\", \"u\", 1), (\"x\", \"y\", 1), (\"y\", \"u\", 1)])\n",
    "\n",
    "h = {}\n",
    "for visit in bfs(g, \"s\"):\n",
    "    h[visit.node] = visit\n",
    "\n",
    "assert h[\"s\"].parent == None\n",
    "assert h[\"s\"].discover == 0\n",
    "assert h[\"w\"].parent == \"s\"\n",
    "assert h[\"w\"].discover == 1\n",
    "assert h[\"r\"].parent == \"s\"\n",
    "assert h[\"r\"].discover == 1\n",
    "assert h[\"t\"].parent == \"w\"\n",
    "assert h[\"t\"].discover == 2\n",
    "assert h[\"x\"].parent == \"w\"\n",
    "assert h[\"x\"].discover == 2\n",
    "assert h[\"v\"].parent == \"r\"\n",
    "assert h[\"v\"].discover == 2\n",
    "assert h[\"u\"].parent == \"t\"\n",
    "assert h[\"u\"].discover == 3\n",
    "assert h[\"y\"].parent == \"x\"\n",
    "assert h[\"y\"].discover == 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## DFS\n",
    "Similarly to the BFS function, implement DFS. Return the list of Visit objects with parents, discover and finish times."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [],
   "source": [
    "time = 0\n",
    "visitedList = []\n",
    "finalList = []\n",
    "\n",
    "def dfsVisit(graph, currentNode):\n",
    "    global time\n",
    "    global visitedList\n",
    "    global finalList\n",
    "\n",
    "    time += 1\n",
    "    currentNode.discover = time\n",
    "    for selectedNodeTuple in graph.neighbors(currentNode.node):\n",
    "\n",
    "        if selectedNodeTuple[0] not in visitedList:\n",
    "            selectedNode = Visit(selectedNodeTuple[0], currentNode.node, 0, 0)\n",
    "            visitedList.append(selectedNode.node)\n",
    "            dfsVisit(graph, selectedNode)\n",
    "\n",
    "    time += 1\n",
    "    currentNode.finish = time\n",
    "    finalList.append(currentNode)\n",
    "\n",
    "\n",
    "def dfs(graph, node):\n",
    "    global visitedList\n",
    "    global finalList\n",
    "\n",
    "    startnode_name = node\n",
    "    startNode = Visit(startnode_name, None, 0, 0)\n",
    "    visitedList.append(startnode_name)\n",
    "    dfsVisit(graph, startNode)\n",
    "\n",
    "    return finalList"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test\n",
    "\n",
    "g = Graph([(\"u\", \"v\", 1), (\"u\", \"x\", 1), (\"x\", \"v\", 1), (\"v\", \"y\", 1), (\"y\", \"x\", 1), (\"w\", \"y\", 1), (\"w\", \"z\", 1), (\"z\", \"z\", 1)], directed=True)\n",
    "\n",
    "h = {}\n",
    "for visit in dfs(g, \"u\"):\n",
    "    h[visit.node] = visit\n",
    "    \n",
    "assert h[\"u\"].parent == None\n",
    "assert h[\"u\"].discover == 1\n",
    "assert h[\"u\"].finish == 8\n",
    "\n",
    "assert h[\"v\"].parent == \"u\"\n",
    "assert h[\"v\"].discover == 2\n",
    "assert h[\"v\"].finish == 7\n",
    "\n",
    "assert h[\"y\"].parent == \"v\"\n",
    "assert h[\"y\"].discover == 3\n",
    "assert h[\"y\"].finish == 6\n",
    "\n",
    "assert h[\"x\"].parent == \"y\"\n",
    "assert h[\"x\"].discover == 4\n",
    "assert h[\"x\"].finish == 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x : y : 4 , 5\n",
      "y : v : 3 , 6\n",
      "v : u : 2 , 7\n",
      "u : None : 1 , 8\n"
     ]
    }
   ],
   "source": [
    "dfsList = h\n",
    "for k in dfsList:\n",
    "    print(dfsList[k].node, \":\", dfsList[k].parent,\":\", dfsList[k].discover, \",\", dfsList[k].finish)"
   ]
  }
 ],
 "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
}