Graph/Graph.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Author: OMKAR PATHAK"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Graph\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Graph is a data structure that consists of following two components:\n",
    "    1. A finite set of vertices also called as **nodes.**\n",
    "    2. A finite set of ordered pair of the form (u, v) called as **edge**. The pair is ordered because (u, v) is not same as (v, u) in case of directed graph(di-graph). The pair of form (u, v) indicates that there is an edge from vertex u to vertex v. The edges may contain weight/value/cost.\n",
    "* Graphs can be represented by two ways:\n",
    "    1. **Adjacency Matrix**: A two-dimensional matrix, in which the rows represent source vertices and columns represent destination vertices. Data on edges and vertices must be stored externally. Only the cost for one edge can be stored between each pair of vertices.\n",
    "    2. **Adjacency List**: Vertices are stored as records or objects, and every vertex stores a list of adjacent vertices. This data structure allows the storage of additional data on the vertices. Additional data can be stored if edges are also stored as objects, in which case each vertex stores its incident edges and each edge stores its incident vertices."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Time Complexities:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_NOTE: AL = Adjacency List, AM = Adjacency Matrix, V = Vertex, E = Edge_\n",
    "* Store Graph: AL: O(|V| + |E|), AM: O(|V| * |V|)\n",
    "* Add Vertex: AL: O(1), AM: O(|V| * |V|)\n",
    "* Add Edge: AL: O(1), AM: O(1)\n",
    "* Remove Vertex: AL: O(|E|), AM: O(|V| * |V|)\n",
    "* Remove Edge: AL: O(|V|), AM: O(1)\n",
    "<br><br>\n",
    "* AL: Slow to remove vertices and edges, because it needs to find all vertices or edges\n",
    "* AM: Slow to add or remove vertices, because matrix must be resized/copied"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementation for Adjacency List"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 -> 1 -> 4\n",
      "1 -> 0 -> 4 -> 3 -> 2\n",
      "2 -> 3\n",
      "3 -> 4\n",
      "4 -> 1 -> 3\n"
     ]
    }
   ],
   "source": [
    "class AdjacencyList(object):\n",
    "    def __init__(self):\n",
    "        self.List = {}\n",
    "    \n",
    "    def addEdge(self, fromVertex, toVertex):\n",
    "        # check if vertex is already present\n",
    "        if fromVertex in self.List.keys():\n",
    "            self.List[fromVertex].append(toVertex)\n",
    "        else:\n",
    "            self.List[fromVertex] = [toVertex]\n",
    "    \n",
    "    def printList(self):\n",
    "        for i  in self.List:\n",
    "            print(i,'->',' -> '.join([str(j) for j in self.List[i]]))\n",
    "            \n",
    "al = AdjacencyList()\n",
    "al.addEdge(0, 1)\n",
    "al.addEdge(0, 4)\n",
    "al.addEdge(4, 1)\n",
    "al.addEdge(4, 3)\n",
    "al.addEdge(1, 0)\n",
    "al.addEdge(1, 4)\n",
    "al.addEdge(1, 3)\n",
    "al.addEdge(1, 2)\n",
    "al.addEdge(2, 3)\n",
    "al.addEdge(3, 4)\n",
    "\n",
    "al.printList()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Application of Graphs:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* In computer science, graphs are used to represent networks of communication, data organization, computational devices.\n",
    "* Graph theory is also used to study molecules in chemistry and physics.\n",
    "* In mathematics, graphs are useful in geometry.\n",
    "* Weighted graphs, are used to represent structures in which pairwise connections have some numerical values. Ex: Road Network.\n",
    "* Graph algorithms are useful for calculating the shortest path in Routing .\n",
    "* Maps – finding the shortest/cheapest path for a car from one city to another, by using given roads."
   ]
  }
 ],
 "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}