Skip to content

Instantly share code, notes, and snippets.

@arjunprakash027

arjunprakash027/python_dataStructs.ipynb

Last active November 21, 2023 15:19
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save arjunprakash027/de287ba7fb277c6a780a82fd320b52bd to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save arjunprakash027/de287ba7fb277c6a780a82fd320b52bd to your computer and use it in GitHub Desktop.
Download ZIP
A small notebook containing the most important data structures used in python
Display the source blob
Display the rendered blob
Raw
python_dataStructs.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Linked List"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. \n",
"\n",
"A linked list is represented by a pointer to the first node of the linked list. The first node is called the head. If the linked list is empty, then the value of the head is NULL. Each node in a list consists of at least two parts:\n",
"\n",
"- Data\n",
"- Pointer (Or Reference) to the next node"
]
},
{
"cell_type": "code",
"execution_count": 75,
"metadata": {},
"outputs": [],
"source": [
"class Node:\n",
"\n",
" def __init__(self,data):\n",
" self.data = data\n",
" self.next = None\n",
"\n",
"class LinkedList:\n",
"\n",
" def __init__(self):\n",
" self.head = None\n",
"\n",
" def __str__(self) -> str:\n",
" if self.head is None:\n",
" raise Exception(\"List is empty\")\n",
" temp = self.head\n",
" while (temp):\n",
" print(temp.data)\n",
" temp = temp.next\n",
" return \" \"\n",
" \n",
" def len(self) -> int:\n",
" if self.head is None:\n",
" raise Exception(\"List is empty\")\n",
" temp = self.head\n",
" count = 0\n",
" while (temp):\n",
" count += 1\n",
" temp = temp.next\n",
" return count\n",
"\n",
" def position(self,element:int) -> int:\n",
" if self.head is None:\n",
" raise Exception(\"List is empty\")\n",
" temp = self.head\n",
" count = 0\n",
" while (temp):\n",
" if temp.data == element:\n",
" return count\n",
" count += 1\n",
" temp = temp.next\n",
" return -1\n",
" \n",
" def findElement(self,position:int) -> int:\n",
" if self.head is None:\n",
" raise Exception(\"List is empty\")\n",
" temp = self.head\n",
" count = 0\n",
" while (temp):\n",
" if count == position:\n",
" return temp.data\n",
" count += 1\n",
" temp = temp.next\n",
" return -1\n",
" \n",
" def insert(self,data:int,position:int) -> None:\n",
" if position > self.len():\n",
" raise Exception(\"out of bound error\")\n",
"\n",
" newNode = Node(data)\n",
" \n",
" if position == 0:\n",
" newNode.next = self.head\n",
" self.head = newNode\n",
" return\n",
" \n",
" count = 1\n",
" temp = self.head\n",
"\n",
" while(True):\n",
" if count == position:\n",
" newNode.next = temp.next\n",
" temp.next = newNode\n",
" return\n",
" temp = temp.next\n",
" count += 1\n",
" \n",
" def remove(self,position:int) -> None:\n",
" \n",
" if position > self.len():\n",
" raise Exception(\"out of bound error\")\n",
" \n",
" if position == 0:\n",
" self.head = self.head.next\n",
" return\n",
" \n",
" count = 1\n",
" temp = self.head\n",
" while(True):\n",
" if count == position:\n",
" temp.next = temp.next.next\n",
" return\n",
" temp = temp.next\n",
" count += 1\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 76,
"metadata": {},
"outputs": [],
"source": [
"llist = LinkedList()\n",
"\n",
"llist.head = Node(30)\n",
"llist.head.next = Node(40)\n",
"llist.head.next.next = Node(50)\n",
"llist.head.next.next.next = Node(60)\n",
"llist.insert(69,2)"
]
},
{
"cell_type": "code",
"execution_count": 77,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"5\n",
"3\n",
"50\n"
]
}
],
"source": [
"print(llist.len())\n",
"print(llist.position(50))\n",
"print(llist.findElement(3))"
]
},
{
"cell_type": "code",
"execution_count": 78,
"metadata": {},
"outputs": [],
"source": [
"llist.remove(1)"
]
},
{
"cell_type": "code",
"execution_count": 79,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"<__main__.LinkedList at 0x7f1c500a5060>"
]
},
"execution_count": 79,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"llist"
]
},
{
"cell_type": "code",
"execution_count": 80,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"30\n",
"69\n",
"50\n",
"60\n",
" \n"
]
}
],
"source": [
"print(llist)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Stack"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- Python stack can be implemented using the deque class from the collections module. \n",
"- Deque is preferred over the list in the cases where we need quicker append and pop operations from both the ends of the container, as deque provides an O(1) time complexity for append and pop operations as compared to list which provides O(n) time complexity. "
]
},
{
"cell_type": "code",
"execution_count": 87,
"metadata": {},
"outputs": [],
"source": [
"def aFunction(a,b):\n",
" return a+b"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from random import randint\n",
"from collections import deque\n",
"stack = deque()\n",
"for x in range(20):\n",
" stack.append(aFunction(randint(100,200),randint(200,300)))\n",
"\n",
"for x in range(20):\n",
" print(stack.pop())\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from queue import LifoQueue\n",
"\n",
"stack = LifoQueue()\n",
"\n",
"for x in range(20):\n",
" stack.put(aFunction(randint(100,200),randint(200,300)))\n",
"\n",
"while not stack.empty():\n",
" print(stack.get())"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Queue"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"first in first out"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": []
},
{
"cell_type": "code",
"execution_count": 96,
"metadata": {},
"outputs": [],
"source": [
"def WrapperFun(a:int,b:int):\n",
" def InnerFun():\n",
" return a+b\n",
" return InnerFun"
]
},
{
"cell_type": "code",
"execution_count": 99,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"5\n"
]
}
],
"source": []
},
{
"cell_type": "code",
"execution_count": 94,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1\n",
"2\n",
"3\n"
]
}
],
"source": [
"queue = []\n",
"\n",
"queue.append(1)\n",
"queue.append(2)\n",
"queue.append(3)\n",
"\n",
"print(queue.pop(0))\n",
"print(queue.pop(0))\n",
"print(queue.pop(0))"
]
},
{
"cell_type": "code",
"execution_count": 102,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"2308\n",
"549\n",
"950\n",
"7899\n",
"982\n",
"10015\n",
"1138\n",
"965\n",
"2608\n",
"9807\n",
"430\n",
"962\n",
"345\n",
"7225\n",
"9802\n",
"4206\n",
"9154\n",
"9320\n",
"1465\n",
"7525\n"
]
}
],
"source": [
"from queue import Queue\n",
"\n",
"q = Queue()\n",
"\n",
"for x in range(20):\n",
" q.put(WrapperFun(randint(0,100),randint(3,10000)))\n",
"\n",
"for x in range(20):\n",
" print(q.get()())\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Priority Queue"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Priority Queues are abstract data structures where each data/value in the queue has a certain priority. For example, In airlines, baggage with the title “Business” or “First-class” arrives earlier than the rest. Priority Queue is an extension of the queue with the following properties.\n",
"\n",
"- An element with high priority is dequeued before an element with low priority.\n",
"- If two elements have the same priority, they are served according to their order in the queue."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": []
},
{
"cell_type": "code",
"execution_count": 103,
"metadata": {},
"outputs": [],
"source": [
"def WrapperFun(a:int,b:int):\n",
" def InnerFun():\n",
" return a+b\n",
" return InnerFun"
]
},
{
"cell_type": "code",
"execution_count": 112,
"metadata": {},
"outputs": [],
"source": [
"from typing import *\n",
"\n",
"PRIORITYOBJECT = Tuple[Any,int]"
]
},
{
"cell_type": "code",
"execution_count": 113,
"metadata": {},
"outputs": [],
"source": [
"class PriorityQueue(object):\n",
" def __init__(self) -> None:\n",
" self.queue = []\n",
" \n",
" def __str__(self) -> str:\n",
" return ' '.join([str(i) for i in self.queue])\n",
" \n",
" def isEmpty(self) -> bool:\n",
" return len(self.queue) == 0\n",
" \n",
" def put(self,PriObject:PRIORITYOBJECT) -> None:\n",
" self.queue.append(PriObject)\n",
"\n",
" def get(self):\n",
" try:\n",
" max = 0\n",
" for i in range(len(self.queue)):\n",
" if self.queue[i].priority > self.queue[max].priority:\n",
" max = i\n",
" return_func = self.queue[max].function\n",
" del self.queue[max]\n",
" return return_func\n",
" except IndexError:\n",
" print()\n",
" exit()\n",
"\n",
" \n",
" "
]
},
{
"cell_type": "code",
"execution_count": 115,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"130"
]
},
"execution_count": 115,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"\n",
"from collections import namedtuple\n",
" \n",
"# Declaring namedtuple()\n",
"PriorityObject = namedtuple('PriorityObject',['function','priority'])\n",
" \n",
"# Adding values\n",
"f1 = PriorityObject(WrapperFun(20,30),19)\n",
"f2 = PriorityObject(WrapperFun(40,50),10)\n",
"f3 = PriorityObject(WrapperFun(60,70),90)\n",
"f4 = PriorityObject(WrapperFun(80,90),80)\n",
"\n",
"myQueue = PriorityQueue()\n",
"myQueue.put(f1)\n",
"myQueue.put(f2)\n",
"myQueue.put(f3)\n",
"myQueue.put(f4)\n",
"\n",
"myQueue.get()()\n",
" "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Binary Trees"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"A tree is a hierarchical data structure that looks like the below figure – \n",
"\n",
" tree\n",
" ----\n",
" j <-- root\n",
" / \\\n",
" f k \n",
" / \\ \\\n",
"a h z <-- leaves\n",
"- The topmost node of the tree is called the root whereas the bottommost nodes or the nodes with no children are called the leaf nodes. The nodes that are directly under a node are called its children and the nodes that are directly above something are called its parent.\n",
"\n",
"- A binary tree is a tree whose elements can have almost two children. Since each element in a binary tree can have only 2 children, we typically name them the left and right children. A Binary Tree node contains the"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"#defining a bianry tree\n",
"\n",
"class Node:\n",
" def __init__(self,data):\n",
" self.value=data\n",
" self.left=None\n",
" self.right=None"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[11, 10, 9, 8, 7, 6, 5, 4, 1]\n",
"4\n"
]
}
],
"source": [
"datas = [1,4,5,6,7,8,9,10,11]\n",
"datas.sort(reverse=True)\n",
"print(datas)\n",
"\n",
"root = Node(datas[0])\n",
"stack = [root]\n",
"\n",
"i = 1\n",
"\n",
"while i<len(datas):\n",
" current = stack.pop(0)\n",
" \n",
" \n",
" current.left = Node(datas[i])\n",
" stack.append(current.left)\n",
" \n",
" i+=1\n",
"\n",
" current.right = Node(datas[i])\n",
" stack.append(current.right)\n",
" \n",
" i+=1\n",
"\n",
"\n",
"print(root.left.left.left.value)\n"
]
},
{
"cell_type": "code",
"execution_count": 51,
"metadata": {},
"outputs": [],
"source": [
"#defining a binary tree that can self insert into the tree based on the value\n",
"\n",
"class Node:\n",
"\n",
" def __init__(self, data):\n",
" self.left = None\n",
" self.right = None\n",
" self.data = data\n",
"\n",
" def insert(self, data):\n",
" if self.data:\n",
"\n",
" if data < self.data:\n",
" if self.left is None:\n",
" self.left = Node(data)\n",
" else:\n",
" self.left.insert(data)\n",
" elif data > self.data:\n",
" if self.right is None:\n",
" self.right = Node(data)\n",
" else:\n",
" self.right.insert(data)\n",
" else:\n",
" self.data = data\n",
"\n",
" def printtree(self):\n",
" if self.left:\n",
" self.left.printtree()\n",
" print(self.data)\n",
"\n",
" if self.right:\n",
" self.right.printtree()\n",
" \n",
" #traversal algorithms\n",
"\n",
" def inorder(self,root):\n",
" res = []\n",
" if root:\n",
" res = self.inorder(root.left)\n",
" res.append(root.data)\n",
" res = res + self.inorder(root.right)\n",
" return res\n",
" \n",
" def preorder(self,root):\n",
" res = []\n",
" if root:\n",
" res.append(root.data)\n",
" res = res + self.preorder(root.left)\n",
" res = res + self.preorder(root.right)\n",
" \n",
" return res\n",
" \n",
" def postorder(self,root):\n",
" res = []\n",
" if root:\n",
" res = self.postorder(root.left)\n",
" res = res + self.postorder(root.right)\n",
" res.append(root.data)\n",
"\n",
" return res\n"
]
},
{
"cell_type": "code",
"execution_count": 52,
"metadata": {},
"outputs": [],
"source": [
"root = Node(20)\n",
"root.insert(30)\n",
"root.insert(40)\n",
"root.insert(50)\n",
"root.insert(10)\n",
"root.insert(70)\n",
"root.insert(35)"
]
},
{
"cell_type": "code",
"execution_count": 53,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"10\n",
"20\n",
"30\n",
"35\n",
"40\n",
"50\n",
"70\n"
]
}
],
"source": [
"root.printtree()"
]
},
{
"cell_type": "code",
"execution_count": 54,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"40\n"
]
}
],
"source": [
"print(root.right.right.data)"
]
},
{
"cell_type": "code",
"execution_count": 55,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[10, 20, 30, 35, 40, 50, 70]\n"
]
}
],
"source": [
"\n",
"print(root.inorder(root))"
]
},
{
"cell_type": "code",
"execution_count": 56,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[20, 10, 30, 40, 35, 50, 70]\n"
]
}
],
"source": [
"print(root.preorder(root))"
]
},
{
"cell_type": "code",
"execution_count": 58,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[10, 35, 70, 50, 40, 30, 20]\n"
]
},
{
"ename": "",
"evalue": "",
"output_type": "error",
"traceback": [
"\u001b[1;31mThe Kernel crashed while executing code in the the current cell or a previous cell. Please review the code in the cell(s) to identify a possible cause of the failure. Click <a href='https://aka.ms/vscodeJupyterKernelCrash'>here</a> for more info. View Jupyter <a href='command:jupyter.viewOutput'>log</a> for further details."
]
}
],
"source": [
"print(root.postorder(root))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Graphs"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Graphs are something that has vertices and edges. Vertices are data points where as the edges are connections of the data points."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Representing graphs"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [],
"source": [
"#representation of a weighted graph using adjacent matrix\n",
"from typing import List\n",
"\n",
"class Graph:\n",
" def __init__(self,numvertex:int) -> None:\n",
" self.adjMatrix = [[-1]*numvertex for x in range(numvertex)]\n",
" self.numvertex = numvertex\n",
" self.vertexlist = [0]*numvertex\n",
" self.vertices = {}\n",
"\n",
" def set_vertex(self,vtx:int,val:str) -> None:\n",
" if 0<=vtx<=self.numvertex:\n",
" self.vertexlist[vtx] = val\n",
" self.vertices[val] = vtx\n",
"\n",
" def set_edge(self,v1:str,v2:str,weight:int) -> None:\n",
" frm = self.vertices[v1]\n",
" to = self.vertices[v2]\n",
" self.adjMatrix[frm][to] = weight\n",
" self.adjMatrix[to][frm] = weight\n",
"\n",
" def get_vertex(self):\n",
" return self.vertexlist\n",
" \n",
" def get_edges(self)->List:\n",
" edges = []\n",
"\n",
" for i in range(self.numvertex):\n",
" for j in range(self.numvertex):\n",
" if (self.adjMatrix[i][j] > -1):\n",
" edges.append((self.vertexlist[i],self.vertexlist[j],self.adjMatrix[i][j]))\n",
" return edges\n",
" \n",
" def get_matrix(self):\n",
" return self.adjMatrix\n",
" \n",
"\n",
" \n",
"\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Vertices of Graph\n",
"['a', 'b', 'c', 'd', 'e', 'f']\n",
"Edges of Graph\n",
"[('a', 'c', 20), ('a', 'e', 10), ('b', 'c', 30), ('b', 'e', 40), ('c', 'a', 20), ('c', 'b', 30), ('d', 'e', 50), ('e', 'a', 10), ('e', 'b', 40), ('e', 'd', 50), ('e', 'f', 60), ('f', 'e', 60)]\n",
"Adjacency Matrix of Graph\n",
"[[-1, -1, 20, -1, 10, -1], [-1, -1, 30, -1, 40, -1], [20, 30, -1, -1, -1, -1], [-1, -1, -1, -1, 50, -1], [10, 40, -1, 50, -1, 60], [-1, -1, -1, -1, 60, -1]]\n"
]
}
],
"source": [
"G =Graph(6)\n",
"G.set_vertex(0,'a')\n",
"G.set_vertex(1,'b')\n",
"G.set_vertex(2,'c')\n",
"G.set_vertex(3,'d')\n",
"G.set_vertex(4,'e')\n",
"G.set_vertex(5,'f')\n",
"G.set_edge('a','e',10)\n",
"G.set_edge('a','c',20)\n",
"G.set_edge('c','b',30)\n",
"G.set_edge('b','e',40)\n",
"G.set_edge('e','d',50)\n",
"G.set_edge('f','e',60)\n",
" \n",
"print(\"Vertices of Graph\")\n",
"print(G.get_vertex())\n",
" \n",
"print(\"Edges of Graph\")\n",
"print(G.get_edges())\n",
" \n",
"print(\"Adjacency Matrix of Graph\")\n",
"print(G.get_matrix())"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [],
"source": [
"# using adjacency list\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [],
"source": [
"\n",
"class AdjNode:\n",
" def __init__(self, data):\n",
" self.vertex = data\n",
" self.next = None\n",
" \n",
"\n",
"class Graph:\n",
" def __init__(self, vertices):\n",
" self.V = vertices\n",
" self.graph = [None] * self.V\n",
"\n",
" def add_edge(self, src, dest):\n",
" \n",
" node = AdjNode(dest)\n",
" node.next = self.graph[src]\n",
" self.graph[src] = node\n",
" \n",
" node = AdjNode(src)\n",
" node.next = self.graph[dest]\n",
" self.graph[dest] = node\n",
" \n",
" print(src,self.graph[src],dest,self.graph[dest])\n",
"\n",
" "
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"before\n",
"0 None 1 None\n",
"1 node next-> None\n",
"0 node next-> None\n",
"after\n",
"0 <__main__.AdjNode object at 0x000001A5D9C5C3D0> 1 <__main__.AdjNode object at 0x000001A5DA2C7890>\n",
"before\n",
"0 <__main__.AdjNode object at 0x000001A5D9C5C3D0> 2 None\n",
"2 node next-> <__main__.AdjNode object at 0x000001A5D9C5C3D0>\n",
"0 node next-> None\n",
"after\n",
"0 <__main__.AdjNode object at 0x000001A5D9C26490> 2 <__main__.AdjNode object at 0x000001A5D9C25590>\n",
"before\n",
"1 <__main__.AdjNode object at 0x000001A5DA2C7890> 2 <__main__.AdjNode object at 0x000001A5D9C25590>\n",
"2 node next-> <__main__.AdjNode object at 0x000001A5DA2C7890>\n",
"1 node next-> <__main__.AdjNode object at 0x000001A5D9C25590>\n",
"after\n",
"1 <__main__.AdjNode object at 0x000001A5D9C25910> 2 <__main__.AdjNode object at 0x000001A5DA296AD0>\n",
"before\n",
"0 <__main__.AdjNode object at 0x000001A5D9C26490> 3 None\n",
"3 node next-> <__main__.AdjNode object at 0x000001A5D9C26490>\n",
"0 node next-> None\n",
"after\n",
"0 <__main__.AdjNode object at 0x000001A5D9D10110> 3 <__main__.AdjNode object at 0x000001A5DA2E7C50>\n"
]
}
],
"source": [
"V = 4\n",
"graph = Graph(V)\n",
"graph.add_edge(0, 1)\n",
"graph.add_edge(0, 2)\n",
"graph.add_edge(1, 2)\n",
"graph.add_edge(0,3)\n"
]
},
{
"cell_type": "code",
"execution_count": 39,
"metadata": {},
"outputs": [],
"source": [
"#differetn approch\n",
"# a non weigheted graph\n",
"\n",
"class Vertex:\n",
" def __init__(self,value):\n",
" self.value = value\n",
" self.vertices = []\n",
"\n",
" def add_n(self,n):\n",
" self.vertices.append(n)\n",
"\n",
" def __str__(self):\n",
" return '{} neibghours: {}'.format(\n",
" self.value,\n",
" [vertex for vertex in self.vertices]\n",
" )\n",
"\n",
" def get_connections(self):\n",
" return self.vertices\n",
" \n",
"class Graph:\n",
" def __init__(self):\n",
" self.vertices_present = {}\n",
"\n",
" def add_vertex(self,vertex):\n",
" self.vertices_present[vertex.value] = vertex\n",
"\n",
" def add_edge(self,frm,to):\n",
" if frm not in self.vertices_present or to not in self.vertices_present:\n",
" raise ValueError('One of the vertices is missing')\n",
" \n",
" self.vertices_present[frm].add_n(self.vertices_present[to])\n",
" \n",
" def get_vertices(self):\n",
" return self.vertices_present.keys()\n",
" \n",
" def __iter__(self):\n",
" return iter(self.vertices_present.values())\n",
" \n",
"\n",
" \n",
"\n",
" "
]
},
{
"cell_type": "code",
"execution_count": 55,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0 -> 1\n",
"0 -> 2\n",
"1 -> 2\n",
"2 -> 4\n",
"3 -> 2\n"
]
}
],
"source": [
"g = Graph()\n",
"\n",
"for i in range(5):\n",
" g.add_vertex(Vertex(i))\n",
"\n",
"g.vertices_present\n",
"\n",
"g.add_edge(0,1)\n",
"g.add_edge(1,2)\n",
"g.add_edge(0,2)\n",
"g.add_edge(2,4)\n",
"g.add_edge(3,2)\n",
"\n",
"for v in g:\n",
" for w in v.get_connections():\n",
" print(f'{v.value} -> {w.value}')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Graph Traversal"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [],
"source": [
"#breth frist traversal\n",
"from collections import defaultdict\n",
"\n",
"class Graph:\n",
" def __init__(self):\n",
" self.vertices = defaultdict(list)\n",
" \n",
" def addEdge(self,frm,to):\n",
" self.vertices[frm].append(to)\n",
" \n",
" def __str__(self) -> str:\n",
" return '{}'.format(self.vertices)\n",
" \n",
" def bfs(self,start):\n",
"\n",
" visited = [False] * (max(self.vertices)+1)\n",
"\n",
" queue = []\n",
"\n",
" queue.append(start)\n",
" visited[start] = True\n",
"\n",
" while queue:\n",
"\n",
" visited_element = queue.pop(0)\n",
" print(visited_element,end=\" \")\n",
"\n",
" for next_element in self.vertices[visited_element]:\n",
" if visited[next_element] == False:\n",
" queue.append(next_element)\n",
" visited[next_element] = True\n",
"\n",
" def dfsutil(self,v,visited):\n",
"\n",
" visited.add(v)\n",
"\n",
" print(v,end=\" \")\n",
"\n",
" for n in self.vertices[v]:\n",
" if n not in visited:\n",
" self.dfsutil(n,visited)\n",
" \n",
" def dfs(self,start):\n",
"\n",
" visited = set()\n",
"\n",
" self.dfsutil(start,visited)\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"defaultdict(<class 'list'>, {0: [1, 2], 1: [2], 2: [0, 3], 3: [3]})\n",
"\n",
"\n",
"2 0 3 1 \n",
"\n",
"2 0 1 3 "
]
}
],
"source": [
"g = Graph()\n",
"g.addEdge(0, 1)\n",
"g.addEdge(0, 2)\n",
"g.addEdge(1, 2)\n",
"g.addEdge(2, 0)\n",
"g.addEdge(2, 3)\n",
"g.addEdge(3, 3)\n",
"\n",
"print(g)\n",
"print('\\n')\n",
"g.bfs(2)\n",
"print('\\n')\n",
"g.dfs(2)"
]
},
{
"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.11.3"
}
},
"nbformat": 4,
"nbformat_minor": 2
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment