summaryrefslogtreecommitdiff
path: root/Data_Structures_Using_C_And_C_by_Y_Langsam/8-Graphs.ipynb
diff options
context:
space:
mode:
Diffstat (limited to 'Data_Structures_Using_C_And_C_by_Y_Langsam/8-Graphs.ipynb')
-rw-r--r--Data_Structures_Using_C_And_C_by_Y_Langsam/8-Graphs.ipynb459
1 files changed, 459 insertions, 0 deletions
diff --git a/Data_Structures_Using_C_And_C_by_Y_Langsam/8-Graphs.ipynb b/Data_Structures_Using_C_And_C_by_Y_Langsam/8-Graphs.ipynb
new file mode 100644
index 0000000..d5edadd
--- /dev/null
+++ b/Data_Structures_Using_C_And_C_by_Y_Langsam/8-Graphs.ipynb
@@ -0,0 +1,459 @@
+{
+"cells": [
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "# Chapter 8: Graphs"
+ ]
+ },
+{
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Example 8.1: Simple_Graph_Functions.sci"
+ ]
+ },
+ {
+"cell_type": "code",
+ "execution_count": null,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+"source": [
+"//Simple Graph Functions\n",
+"function[]=graph();\n",
+" \n",
+" i=1,j=1;\n",
+" adj=zeros(10000);\n",
+" for i=1:n\n",
+" for j=1:n\n",
+" \n",
+" adj((i-1)*n+j)=temp;\n",
+" end\n",
+" end\n",
+" for i=1:n\n",
+" for j=1:n\n",
+" if((adj((i-1)*n+j))==1)\n",
+" printf('Vertex %d is connected to vertex %d\n',i,j);\n",
+" end\n",
+" end\n",
+" end\n",
+" \n",
+"endfunction"
+ ]
+ }
+,
+{
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Example 8.2: Finding_The_Number_Of_Paths_From_One_VertexToOther.sci"
+ ]
+ },
+ {
+"cell_type": "code",
+ "execution_count": null,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+"source": [
+"//Finding The Number Of Paths From One Vertex To Another Of A Given Length\n",
+"\n",
+"function[b]=path(k,n,adj,i,j)\n",
+" b=0;\n",
+" if(k==1)\n",
+" b=adj((i-1)*n+j);\n",
+" else\n",
+" for c=1:n\n",
+" if(adj((i-1)*n+c)==1)\n",
+" b=b+path(k-1,n,adj,c,j);\n",
+" end\n",
+" end\n",
+" end\n",
+" printf('Number of paths from vertex %d to %d of length %d are %d',i,j,k,b);\n",
+" return b;\n",
+"endfunction\n",
+"//Calling Routine:\n",
+"n=3;\n",
+"adj=[0 1 1 0 0 1 0 0 0]\n",
+"b=path(1,n,adj,1,3)"
+ ]
+ }
+,
+{
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Example 8.3: Finding_The_Number_Of_Simple_Paths_From_One_Point.sci"
+ ]
+ },
+ {
+"cell_type": "code",
+ "execution_count": null,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+"source": [
+"//Finding The Number Of Simple Paths From One Point To Another In A Given Graph\n",
+"funcprot(0)\n",
+"function[]=sim_path(n,adj,i,j);\n",
+" l=0;\n",
+" m=1;\n",
+" for m=1:n\n",
+" l=l+path(m,n,adj,i,j);\n",
+" end\n",
+" printf('There are %d simple paths from %d to %d in the given graph\n',l,i,j);\n",
+"endfunction\n",
+"function[b]=path(k,n,adj,i,j)\n",
+" b=0;\n",
+" if(k==1)\n",
+" b=adj((i-1)*n+j);\n",
+" else\n",
+" for c=1:n\n",
+" if(adj((i-1)*n+c)==1)\n",
+" b=b+path(k-1,n,adj,c,j);\n",
+" end\n",
+" end\n",
+" end\n",
+" return b;\n",
+"endfunction\n",
+"n=3;\n",
+"adj=[0 1 1 0 0 1 0 0 0];\n",
+"b=sim_path(n,adj,1,3)\n",
+""
+ ]
+ }
+,
+{
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Example 8.4: Finding_Transitive_Closure.sci"
+ ]
+ },
+ {
+"cell_type": "code",
+ "execution_count": null,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+"source": [
+"//Finnding Transitive Closure\n",
+"funcprot(0)\n",
+"function[path]=Tranclose(adj,n);\n",
+" i=1,j=1;\n",
+" path=zeros(n*n,1);\n",
+" path=tranclose(adj,n);\n",
+" printf('Transitive Closure Of Given Graph is:\n');\n",
+" for i=1:n\n",
+" printf('For Vertex %d\n',i);\n",
+" for j=1:n\n",
+" printf(' %d %d is %d\n',i,j,path((i-1)*n+j));\n",
+" end\n",
+" end\n",
+" \n",
+"endfunction\n",
+"function[path]=tranclose(adj,n)\n",
+" adjprod=zeros(n*n,1);\n",
+" k=1;\n",
+" newprod=zeros(n*n,1);\n",
+" for i=1:n\n",
+" for j=1:n\n",
+" path((i-1)*n+j)=adj((i-1)*n+j);\n",
+" adjprod((i-1)*n+j)= path((i-1)*n+j);\n",
+" end\n",
+" end\n",
+" for i=1:n\n",
+" newprod=prod1(adjprod,adj,n);\n",
+" for j=1:n\n",
+" for k=1:n\n",
+" path((j-1)*n+k)=path((j-1)*n+k)|newprod((j-1)*n+k);\n",
+" end\n",
+" end\n",
+" for j=1:n\n",
+" for k=1:n\n",
+" adjprod((j-1)*n+k)=newprod((j-1)*n+k);\n",
+" end\n",
+" end\n",
+" end\n",
+"endfunction\n",
+"function[c]=prod1(a,b,n)\n",
+" for i=1:n\n",
+" for j=1:n\n",
+" val=0\n",
+" for k=1:n\n",
+" val=val|(a((i-1)*n+k)&b((k-1)*n+j));\n",
+" end\n",
+" c((i-1)*n+j)=val;\n",
+" end\n",
+" end\n",
+"endfunction\n",
+"//Calling Routine:\n",
+"n=3;\n",
+"adj=[0 1 0 0 0 1 0 0 0]\n",
+"path=Tranclose(adj,n)"
+ ]
+ }
+,
+{
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Example 8.5: Warshalls_Algorithm.sci"
+ ]
+ },
+ {
+"cell_type": "code",
+ "execution_count": null,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+"source": [
+"//Warshall's Algorithm\n",
+"funcprot(0)\n",
+"function[path]=transclose(adj,n)\n",
+" for i=1:n\n",
+" for j=1:n\n",
+" path((i-1)*n+j)=adj((i-1)*n+j);\n",
+" end\n",
+" end\n",
+" for k=1:n\n",
+" for i=1:n\n",
+" if(path((i-1)*n+k)==1)\n",
+" for j=1:n\n",
+" path((i-1)*n+j)=path((i-1)*n+j)|path((k-1)*n+j);\n",
+" end\n",
+" end\n",
+" end\n",
+" end\n",
+" printf('Transitive closure for the given graph is:\n');\n",
+" for i=1:n\n",
+" printf('For vertex %d \n',i);\n",
+" for j=1:n\n",
+" printf('%d %d is %d\n',i,j,path((i-1)*n+j));\n",
+" end\n",
+" end\n",
+"endfunction\n",
+"//Calling Routine:\n",
+"n=3;\n",
+"adj=[0 1 0 0 0 1 0 0 0]\n",
+"path=Tranclose(adj,n)"
+ ]
+ }
+,
+{
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Example 8.6: Depth_First_Search_Traversal.sci"
+ ]
+ },
+ {
+"cell_type": "code",
+ "execution_count": null,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+"source": [
+"//Depth First Search Traversal\n",
+"funcprot(0)\n",
+"function[]=Dfs(adj,n);\n",
+" i=1,j=1;\n",
+" colour=[];\n",
+" for i=1:n\n",
+" for j=1:n\n",
+" colour=[colour(:,:) 0];\n",
+" end\n",
+" end\n",
+" disp('The DFS traversal is');\n",
+"dfs(adj,colour,1,n); \n",
+"endfunction\n",
+"function[]=dfs(adj,colour,r,n)\n",
+" colour(r)=1;\n",
+" disp(r,' ');\n",
+" for i=1:n\n",
+" if(adj((r-1)*n+i)&(colour(i)==0))\n",
+" dfs(adj,colour,i,n);\n",
+" end\n",
+" end\n",
+" colour(r)=2;\n",
+"endfunction\n",
+"//Calling Routine:\n",
+"n=4;\n",
+"adj=[0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0]\n",
+"Dfs(adj,n)"
+ ]
+ }
+,
+{
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Example 8.7: BFS_Traversal.sci"
+ ]
+ },
+ {
+"cell_type": "code",
+ "execution_count": null,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+"source": [
+"////BFS Traversal\n",
+"funcprot(0)\n",
+"function[q2]=push(ele,q1)\n",
+" if(q1.rear==q1.front)\n",
+" q1.a=ele;\n",
+" q1.rear=q1.rear+1;\n",
+" else\n",
+" q1.a=[q1.a(:,:) ele];\n",
+" q1.rear=q1.rear+1;\n",
+" end\n",
+" q2=q1;\n",
+"endfunction\n",
+"function[ele,q2]=pop(q1)\n",
+" ele=-1;\n",
+" q2=0;\n",
+" if(q1.rear==q1.front)\n",
+" return;\n",
+" else\n",
+" ele=q1.a(q1.rear-q1.front);\n",
+" q1.front=q1.front+1;\n",
+" i=1;\n",
+" a=q1.a(1);\n",
+" for i=2:(q1.rear-q1.front)\n",
+" a=[a(:,:) q1.a(i)];\n",
+" end\n",
+" q1.a=a;\n",
+" end\n",
+" q2=q1;\n",
+"endfunction\n",
+"\n",
+"function[]=Bfs(adj,n);\n",
+" i=1,j=1;\n",
+" colour=[];\n",
+" for i=1:n\n",
+" for j=1:n\n",
+" colour=[colour(:,:) 0];\n",
+" end\n",
+" end\n",
+" disp('The BFS Traversal is');\n",
+"bfs(adj,colour,1,n); \n",
+"endfunction\n",
+"function[]=bfs(adj,colour,s,n)\n",
+" colour(s)=1;\n",
+" q=struct('rear',0,'front',0,'a',0);\n",
+" q=push(s,q);\n",
+" while((q.rear)-(q.front)>0)\n",
+" [u,q]=pop(q);\n",
+" disp(u,' ');\n",
+" for i=1:n\n",
+" if(adj((u-1)*n+i)&(colour(i)==0))\n",
+" colour(i)=1;\n",
+" q=push(i,q);\n",
+" end\n",
+" end\n",
+" colour(u)=2;\n",
+" end\n",
+"endfunction\n",
+"//Calling Routine:\n",
+"n=4;\n",
+"adj=[0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0]\n",
+"Bfs(adj,n)"
+ ]
+ }
+,
+{
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Example 8.8: Dijkstras_Algorithm.sci"
+ ]
+ },
+ {
+"cell_type": "code",
+ "execution_count": null,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+"source": [
+"//Dijkstras Algorithm\n",
+"funcprot(0)\n",
+"function[l]=short(adj,w,i1,j1,n)\n",
+" for i=1:n\n",
+" for j=1:n\n",
+" if(w((i-1)*n+j)==0)\n",
+" w((i-1)*n+j)=9999;\n",
+" end\n",
+" end\n",
+" end\n",
+" \n",
+" distance=[];\n",
+" perm=[];\n",
+" for i=1:n\n",
+" distance=[distance(:,:) 99999];\n",
+" perm=[perm(:,:) 0];\n",
+" end\n",
+" perm(i1)=1;\n",
+" distance(i1)=0;\n",
+" current=i1;\n",
+" while(current~=j1)\n",
+" smalldist=9999;\n",
+" dc=distance(current);\n",
+" for i=1:n\n",
+" if(perm(i)==0)\n",
+" newdist=dc+w((current-1)*n+i);\n",
+" if(newdist<distance(i))\n",
+" distance(i)=newdist;\n",
+" end\n",
+" if(distance(i)<smalldist)\n",
+" smalldist=distance(i);\n",
+" k=i;\n",
+" end\n",
+" end \n",
+" end\n",
+" current=k;\n",
+" perm(current)=1;\n",
+" end\n",
+" l=distance(j1);\n",
+" printf('The shortest path between %d and %d is %d',i1,j1,l);\n",
+"endfunction\n",
+"//Calling Routine:\n",
+"n=3;\n",
+"adj=[0 1 1 0 0 1 0 0 0]//Adjacency List\n",
+"w=[0 12 22 0 0 9 0 0 0]//weight list fill 0 for no edge\n",
+"short(adj,w,1,3,n);"
+ ]
+ }
+],
+"metadata": {
+ "kernelspec": {
+ "display_name": "Scilab",
+ "language": "scilab",
+ "name": "scilab"
+ },
+ "language_info": {
+ "file_extension": ".sce",
+ "help_links": [
+ {
+ "text": "MetaKernel Magics",
+ "url": "https://github.com/calysto/metakernel/blob/master/metakernel/magics/README.md"
+ }
+ ],
+ "mimetype": "text/x-octave",
+ "name": "scilab",
+ "version": "0.7.1"
+ }
+ },
+ "nbformat": 4,
+ "nbformat_minor": 0
+}
generated by cgit (git 2.34.1) at 2025-07-07 18:08:19 +0000