Trend Posts
Author
View LUQMAN's profile
Showing posts with label DAA Lab Programming. Show all posts
Showing posts with label DAA Lab Programming. Show all posts
Monday, July 21, 2014
/*Computer the Transitive closure of a given directed graph using warshall’s algorithm*/
#include<stdio.h>
void warshall(int);
long int ad[10][10];
void main()
{
int i, j,n;
printf("\n****Warshalls Algorithm****\n");
printf("Enter the number of nodes\n\n");
scanf("%d",&n);
printf("\nEnter the graphs in the form of adjacency matrix\n\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%ld",&ad[i][j]);
printf("\n\nThe adjacency matrix is:\n\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%ld\t",ad[i][j]);
printf("\n");
}
warshall(n);
printf("\nThe transitive closure of given directed graph is\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%ld\t",ad[i][j]);
printf("\n");
}
}
void warshall(int n)
{
int i,j,k;
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
ad[i][j]=ad[i][j]||ad[i][k]&&ad[k][j];
}
/*Obtain the Topological ordering of vertices in a given digraph*/
#include<stdio.h>
int ad[10][10];
void main()
{
int i,j,n,f=1,in=1,k,v[50000],count=0,flag;
printf("\n\nEnter the number of nodes\n\n");
scanf("%d",&n);
printf("\n\nEnter the graph in the form of adjacency matrix\n\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&ad[i][j]);
printf("\nThe adjacency matrix is:\n\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d\t",ad[i][j]);
printf("\n");
}
while(f)
{
count++;
for(j=1;j<=n;j++)
{
flag=0;
for(i=1;i<=n;i++)
{
if(ad[i][j]==1||v[i]==j)
{
flag=1;
break;
}
}
if(flag==0)
{
v[in++]=j;
for(k=1;k<=n;k++)
ad[j][k]=0;
}
}
if(count==n)
f=0;
}
if(in<n)
printf("\nThere is no topological order\n\n");
else
{
printf("\nThere is a topological order and it is::\t");
for(i=1;i<=n;i++)
printf("%d\t",v[i]);
}
printf("\n\n");
}
/*Implement any scheme to find the solution for the TravelingSalesperson in the approximation method*/
#include<stdio.h>
void tspaprx(int);
int n,cost[100][100],s,count=0,mincost,visited[100],u,i,j,min;
void main()
{
printf("\nEnter the number of nodes\n");
scanf("%d",&n);
printf("\nEnter the cost matrix\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&cost[i][j]);
printf("\nEntered cost matrix is:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d\t",cost[i][j]);
printf("\n");
}
printf("\nThe approximate tour is:\n");
tspaprx(1);
}
void tspaprx(int s)
{
visited[s]=1;
count++;
printf("%d->",s);
if(count==n)
{
printf("1");
mincost+=cost[s][1];
printf("\nThe minimum tour cost is %d",mincost);
return;
}
min=999;
for(i=1;i<=n;i++)
{
if(cost[s][i]<min && !visited[i])
{
min=cost[s][i];
u=i;
}
}
mincost+=min;
tspaprx(u);
}
/*Find a subset of a given set S = {sl, s2,.....,sn} of n positive integerswhose sum is equal to a given positive integer d. For example, if S={1, 2, 5, 6, 8} and d = 9 there are two solutions{1,2,6}and{1,8}.Asuitable message is to be displayed if the given problem instancedoesn't have a solution.*/
#include<stdio.h>
void subset(int,int,int);
int i,w[10],n,sum=0,x[10],c=0,k,r,d;
void main()
{
printf("\nEnter the number of elements\n");
scanf("%d",&n);
printf("\nEnter the elements in the ascending order\n");
for(i=0;i<n;i++)
scanf("%d",&w[i]);
printf("\nEnter the sum:\n");
scanf("%d",&d);
for(i=0;i<n;i++)
sum=sum+w[i];
if(sum<d || d<w[0])
printf("\nSubset is not possible\n");
subset(0,0,sum);
if(c==0)
printf("\nSubset is not possible\n");
}
void subset(int cs,int k,int r)
{
x[k]=1;
if(cs+w[k]==d)
{
printf("\nSolution %d is: {",++c);
for(i=0;i<=k;i++)
if(x[i]==1)
printf("%d,",w[i]);
printf("\b }");
}
else if(cs+w[k]+w[k+1]<=d)
subset(cs+w[k],k+1,r-w[k]);
if(cs+r-w[k]>=d && cs+w[k+1]<=d)
{
x[k]=0;
subset(cs,k+1,r-w[k]);
}
}
/*From a given vertex in a weighted connected graph, find shortest paths to other vertices using Dijkstra's algorithm.*/
#include<stdio.h>
int cost[10][10],n,sv,i,j,v,count=0,w,min,t,w,dist[10],visited[10],path[10];
void dj();
void print();
void main()
{
printf("\n\nEnter the number of nodes\n\n");
scanf("%d",&n);
printf("\n\nEnter the cost matrix\n\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&cost[i][j]);
printf("\nEntered cost matrix is:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d\t",cost[i][j]);
printf("\n");
}
printf("\nEnter the source node\n");
scanf("%d",&sv);
dj();
print();
}
void dj()
{
for(i=1;i<=n;i++)
{
visited[i]=0;
dist[i]=cost[sv][i];
if(cost[sv][i]==999)
path[i]=0;
else
path[i]=sv;
}
visited[sv]=1;
while(count<=n)
{
min=999;
for(w=1;w<=n;w++)
if(dist[w]<=min&&!visited[w])
{
min=dist[w];
v=w;
}
visited[v]=1;
count++;
for(w=1;w<=n;w++)
if(dist[w]>dist[v]+cost[v][w])
{
dist[w]=dist[v]+cost[v][w];
path[w]=v;
}
}
}
void print()
{
for(w=1;w<=n;w++)
if(visited[w]==1 && w!=sv)
{
printf("\nThe sorted distance between %d-->%d=%d",sv,w,dist[w]);
t=path[w];
printf("\nThe path is:\n");
printf("%d",w);
while(t!=sv)
{
printf("-->%d",t);
t=path[t];
}
printf("<-->%d",sv);
}
}
/* Implement All-Pairs Shortest Paths Problem using Floyd's algorithm. Parallelize this algorithm, implement it using OpenMP and determine the speed-up achieved.*/
#include<stdio.h>
#include<omp.h>
#include<time.h>
void floyds(int);
int min(int,int);
int cost[10][10],n,i,j,k,a,b;
double start,end,dur;
void main()
{
printf("Enter the number of nodes\n\n");
scanf("%d",&n);
printf("\nEnter the cost matrix\n\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&cost[i][j]);
printf("\n\nThe cost matrix is:\n\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d\t",cost[i][j]);
printf("\n");
}
start=clock();
for(i=1;i<=100000;i++)
floyds(n);
end=clock();
dur=(end-start)/CLOCKS_PER_SEC;
printf("\nTime taken is:%f\t\n",dur);
printf("\nThe minimum cost matrix is:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d\t",cost[i][j]);
printf("\n");
}
}
void floyds(int n)
{
omp_set_num_threads(4);
#pragma omp parallel for private(i,j,k)
for(k=1;k<=n;k++)
{
usleep(100);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j]);
}
}
int min(int a,int b)
{
if(a>b)
return b;
else
return a;
}
/*Check whether a given graph is connected or not using DFSmethod.*/
#include<stdio.h>
void dfs(int i);
int i,j,adj[1000][1000],v[1000],w,n,count;
void main()
{
printf("\nEnter the number of nodes\n");
scanf("%d",&n);
printf("\nEnter the graph in the form of adjacency matrix\n\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&adj[i][j]);
printf("\n\nThe adjacency matrix is:\n\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d\t",adj[i][j]);
printf("\n");
}
for(i=1;i<=n;i++)
{
count=0;
for(j=1;j<=n;j++)
v[j]=0;
dfs(i);
if(count==n)
{
printf("\nThe entered graph is connected\n");
return;
}
}
printf("\nThe entered graph is not connected\n");
}
void dfs(int i)
{
int w;
count++;
v[i]=1;
for(w=1;w<=n;w++)
if(adj[i][w]==1 && !v[w])
dfs(w);
}
/*Print all the nodes reachable from a given starting node in a digraph using BFS method.*/
#include<stdio.h>
int i,j,s,a[100][100],q[100],visited[100],u,rear,front,n;
void bfs();
void main()
{
printf("\nEnter the number of nodes:\n");
scanf("%d",&n);
printf("\nEnter the adjacency matrix:\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
printf("\nThe entered adjacency matrix is:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d\t",a[i][j]);
printf("\n");
}
printf("\nEnter the source vertex:\n");
scanf("%d",&s);
bfs();
for(i=1;i<=n;i++)
{
if(visited[i])
printf("\nNode %d is reachable from source node %d",i,s);
else
printf("\nNode %d is not reachable from source node %d",i,s);
}
}
void bfs()
{
q[rear]=s;
visited[s]=1;
while(front<=rear)
{
u=q[front];
front=front+1;
for(i=1;i<=n;i++)
if(a[u][i] && !visited[i])
{
rear=rear+1;
q[rear]=i;
visited[i]=1;
}
}
}
Subscribe to:
Posts (Atom)