Graph.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "b1174696",
   "metadata": {},
   "source": [
    "## Graph\n",
    "\n",
    "A Graph is a non-linear data structure consisting of nodes and edges. The nodes are sometimes also referred to as vertices and the edges are lines or arcs that connect any two nodes in the graph."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "50fc2a4a",
   "metadata": {},
   "source": [
    "The main difference between Tree and graph that is "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e1f834a6",
   "metadata": {},
   "source": [
    "|Graph|Tree|\n",
    "|----|-----|\n",
    "|There is no unique node called root in graph.|There is a unique node called root in trees.|\n",
    "|A cycle can be formed.|There will not be any cycle.|\n",
    "|Each node can have any number of edges.|General trees consist of the nodes having any number of child nodes. But in case of binary trees every node can have at the most two child nodes.|"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "3c6ce4c3",
   "metadata": {},
   "outputs": [],
   "source": [
    "## Genral idea with LinkedIn example\n",
    "## representation of graph\n",
    "\n",
    "MyLinkedIn = {\n",
    "    \"friend1\" : ['friend2','friend3'],\n",
    "    \"friend2\" : ['friend4','friend5']\n",
    "}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "102d4a88",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['friend2', 'friend3']"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MyLinkedIn['friend1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "823a1d57",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Graph:\n",
    "    def __init__(self,gdict=None):\n",
    "        self.gdict = gdict\n",
    "    def AddConnection(self,vertex,edge):\n",
    "         self.gdict[vertex].append(edge)\n",
    "    def CountConnection(self,node):\n",
    "         return len(MyLinkedIn[node])\n",
    "    def AddNode(self,NewConnection):\n",
    "        self.gdict[NewConnection] = []\n",
    "        \n",
    "    ## traversal: BFS or DFS\n",
    "    def showNode(self):\n",
    "        return self.gdict.keys()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "c514d758",
   "metadata": {},
   "outputs": [],
   "source": [
    "obj = Graph(MyLinkedIn)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "3cca7969",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'friend1': ['friend2', 'friend3', 'friend4'],\n",
       " 'friend2': ['friend4', 'friend5']}"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "obj.gdict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "024c7ba3",
   "metadata": {},
   "outputs": [],
   "source": [
    "## i want friend1 add friend4 as connection\n",
    "\n",
    "obj.AddConnection('friend1','friend4')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "a0bceadd",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'friend1': ['friend2', 'friend3', 'friend4'],\n",
       " 'friend2': ['friend4', 'friend5']}"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "obj.gdict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "88237ce0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "## count friends connections\n",
    "obj.CountConnection(\"friend1\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "6dc29b28",
   "metadata": {},
   "outputs": [],
   "source": [
    "## add new connections\n",
    "obj.AddNode('vimal_sir')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "12863105",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'friend1': ['friend2', 'friend3', 'friend4'],\n",
       " 'friend2': ['friend4', 'friend5'],\n",
       " 'vimal_sir': []}"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MyLinkedIn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "a1c298b2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "dict_keys(['friend1', 'friend2', 'vimal_sir'])"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "## show our connections\n",
    "obj.showNode()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "309c49f8",
   "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.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}