{
"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
}