Merge pull request #1 from prashantsinalkar/masterHEADmaster

Initial commit

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
+}