sec26-27-DS-graphs-traversal.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Graphs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In nutshell: **nodes** + **connection**\n",
    "\n",
    "Terminologies:\n",
    "- Vertex: the node\n",
    "- Edge: connection\n",
    "- Undirected graph: no direction, so can go two-way\n",
    "- Directed graph: direction, could be uni/bi-directional\n",
    "- Weighted/ Unweighted: there is a weight on the edge \n",
    "\n",
    "Two ways to store the data:\n",
    "- Adjacency matrix\n",
    "- Adjacency list\n",
    "\n",
    "This code will only undirected implemented adjacency list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Adding `addVertex`, `addEdge`, `removeEdge`, `removeVertex`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# This implentation disregard any error handlings\n",
    "class Graph:\n",
    "    def __init__(self):\n",
    "        self.adjacencyList = {}\n",
    "        \n",
    "    def addVertex(self, vertex):\n",
    "        if vertex not in self.adjacencyList.keys(): \n",
    "            self.adjacencyList[vertex] = []\n",
    "    \n",
    "    def addEdge(self, vertex1, vertex2):\n",
    "        self.adjacencyList[vertex1].append(vertex2)\n",
    "        self.adjacencyList[vertex2].append(vertex1)\n",
    "    \n",
    "    def removeEdge(self, vertex1, vertex2):\n",
    "        self.adjacencyList[vertex1].remove(vertex2)\n",
    "        self.adjacencyList[vertex2].remove(vertex1)\n",
    "\n",
    "    def removeVertex(self, vertex):\n",
    "        while len(self.adjacencyList[vertex]) > 0:\n",
    "            for edge in self.adjacencyList[vertex]:\n",
    "                self.removeEdge(vertex, edge) # Check later why I can't simply iterate 20210226, it skipped some value\n",
    "                \n",
    "        del self.adjacencyList[vertex]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "g = Graph()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# == addVertex and addEdge ==\n",
    "g.addVertex('Tokyo')\n",
    "g.addVertex('Osaka')\n",
    "g.addVertex('Sendai')\n",
    "g.addVertex('Kyoto')\n",
    "g.addVertex('Kyushuu')\n",
    "g.addVertex('Hiroshima')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "g.addEdge('Tokyo', 'Sendai')\n",
    "g.addEdge('Tokyo', 'Osaka')\n",
    "g.addEdge('Tokyo', 'Kyoto')\n",
    "g.addEdge('Tokyo', 'Kyushuu')\n",
    "g.addEdge('Tokyo', 'Hiroshima')\n",
    "\n",
    "g.addEdge('Kyoto', 'Sendai')\n",
    "g.addEdge('Kyoto', 'Kyushuu')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('Tokyo', ['Sendai', 'Osaka', 'Kyoto', 'Kyushuu', 'Hiroshima'])\n",
      "('Osaka', ['Tokyo'])\n",
      "('Sendai', ['Tokyo', 'Kyoto'])\n",
      "('Kyoto', ['Tokyo', 'Sendai', 'Kyushuu'])\n",
      "('Kyushuu', ['Tokyo', 'Kyoto'])\n",
      "('Hiroshima', ['Tokyo'])\n"
     ]
    }
   ],
   "source": [
    "# Checking graph content\n",
    "for k in g.adjacencyList.items():\n",
    "    print(k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# == removeEdge and removeVertex =="
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "g.removeEdge('Tokyo', 'Sendai')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "g.removeVertex('Tokyo')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('Osaka', [])\n",
      "('Sendai', ['Kyoto'])\n",
      "('Kyoto', ['Sendai', 'Kyushuu'])\n",
      "('Kyushuu', ['Kyoto'])\n",
      "('Hiroshima', [])\n"
     ]
    }
   ],
   "source": [
    "# Checking graph content\n",
    "for k in g.adjacencyList.items():\n",
    "    print(k)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Graph Traversal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- There is no root, arbitrary start point\n",
    "- No guarantee there is one path to go to our goal\n",
    "\n",
    "Some use of graph traversal:\n",
    "- Peer to peer networking\n",
    "- Web crawlers\n",
    "- etc."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `DFSRecursive`, `DFSIterative` and `BFS`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "# This implentation disregard any error handlings\n",
    "class Graph:\n",
    "    def __init__(self):\n",
    "        self.adjacencyList = {}\n",
    "        \n",
    "    def addVertex(self, vertex):\n",
    "        if vertex not in self.adjacencyList.keys(): \n",
    "            self.adjacencyList[vertex] = []\n",
    "    \n",
    "    def addEdge(self, vertex1, vertex2):\n",
    "        self.adjacencyList[vertex1].append(vertex2)\n",
    "        self.adjacencyList[vertex2].append(vertex1)\n",
    "    \n",
    "    def removeEdge(self, vertex1, vertex2):\n",
    "        self.adjacencyList[vertex1].remove(vertex2)\n",
    "        self.adjacencyList[vertex2].remove(vertex1)\n",
    "\n",
    "    def removeVertex(self, vertex):\n",
    "        while len(self.adjacencyList[vertex]) > 0:\n",
    "            for edge in self.adjacencyList[vertex]:\n",
    "                self.removeEdge(vertex, edge) # Check later why I can't simply iterate 20210226, it skipped some value\n",
    "                \n",
    "        del self.adjacencyList[vertex]\n",
    "        \n",
    "    def DepthFirstRecursive(self, start):\n",
    "        result = []\n",
    "        visited = {}\n",
    "        \n",
    "        adjList = self.adjacencyList\n",
    "        \n",
    "        def DFS(vertex):\n",
    "            if len(adjList[vertex]) == 0:\n",
    "                return None\n",
    "\n",
    "            result.append(vertex)\n",
    "            visited[vertex] = True\n",
    "\n",
    "            for edge in adjList[vertex]:\n",
    "                if edge not in visited:\n",
    "                    DFS(edge)\n",
    "        \n",
    "        # Run DFS on starting vertex 'A'\n",
    "        DFS(start)\n",
    "        \n",
    "        return result\n",
    "    \n",
    "    def DepthFirstIterative(self, start):\n",
    "        adjList = self.adjacencyList\n",
    "        stack   = []\n",
    "        result  = []\n",
    "        visited = {}\n",
    "\n",
    "        # Starting vertex\n",
    "        stack.append(start)\n",
    "        visited[start] = True\n",
    "\n",
    "        while stack:\n",
    "            currentVertex = stack.pop()\n",
    "            result.append(currentVertex)\n",
    "\n",
    "            for edge in adjList[currentVertex]:\n",
    "\n",
    "                if edge not in visited:\n",
    "                    stack.append(edge)\n",
    "                    visited[edge] = True\n",
    "\n",
    "        return result \n",
    "    \n",
    "    def BFS(self, start):\n",
    "        adjList = self.adjacencyList\n",
    "\n",
    "        queue   = []\n",
    "        result  = []\n",
    "        visited = {}\n",
    "\n",
    "        queue.append(start)\n",
    "        visited[start] = True\n",
    "\n",
    "        while queue:\n",
    "            currentVertex = queue.pop(0)\n",
    "\n",
    "            result.append(currentVertex)\n",
    "\n",
    "            for edge in adjList[currentVertex]:\n",
    "                if edge not in visited:\n",
    "                    queue.append(edge)\n",
    "                    visited[edge] = True\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Copying the graph structure from udemy to make checking result easier\n",
    "g = Graph()\n",
    "\n",
    "g.addVertex('A')\n",
    "g.addVertex('B')\n",
    "g.addVertex('C')\n",
    "g.addVertex('D')\n",
    "g.addVertex('E')\n",
    "g.addVertex('F')\n",
    "\n",
    "g.addEdge('A', 'B')\n",
    "g.addEdge('A', 'C')\n",
    "g.addEdge('B', 'D')\n",
    "g.addEdge('C', 'E')\n",
    "g.addEdge('D', 'E')\n",
    "g.addEdge('D', 'F')\n",
    "g.addEdge('E', 'F')\n",
    "\n",
    "#     A\n",
    "#   /  \\\n",
    "#  B    C\n",
    "#  |    |\n",
    "#  D----E\n",
    "#  \\   /\n",
    "#    F"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['A', 'B', 'D', 'E', 'C', 'F']"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g.DepthFirstRecursive(start='A')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['A', 'C', 'E', 'F', 'D', 'B']"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g.DepthFirstIterative(start='A')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['A', 'B', 'C', 'D', 'E', 'F']"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g.BFS(start='A')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'A': ['B', 'C'],\n",
       " 'B': ['A', 'D'],\n",
       " 'C': ['A', 'E'],\n",
       " 'D': ['B', 'E', 'F'],\n",
       " 'E': ['C', 'D', 'F'],\n",
       " 'F': ['D', 'E']}"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g.adjacencyList"
   ]
  },
  {
   "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.7.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}