Lab program 3a: Obtain the Topological ordering of vertices in a given digraph.

Description:

Topological sort is an ordering of the vertices in a directed acyclic graph, such that, if there is a path from u to v, then v appears after u in the ordering.

The graphs should be directed: otherwise for any edge (u,v) there would be a path from u to v and also from v to u, and hence they cannot be ordered.

The graphs should be acyclic: otherwise for any two vertices u and v on a cycle u would precede v and v would precede u.

Using Source Removal algorithm:

1. Compute the indegrees of all vertices
2. Find a vertex U with indegree 0 and print it (store it in the ordering)
3. If there is no such vertex then there is a cycle and the vertices cannot be ordered. Stop.
4. Remove U and all its edges (U,V) from the graph.
5. Update the indegrees of the remaining vertices.
6. Repeat steps 2 through 4 while there are vertices to be processed.

Solution:

  #include<stdio.h>

   int temp[10],k=0;

  

void topo(int n,int indegree[10],int a[10][10])

   {

   int i,j;

   for(i=1;i<=n;i++)

     {

               if(indegree[i]==0)

                {

                indegree[i]=1;

                  temp[++k]=i;

                        for(j=1;j<=n;j++)

                           {

                            if(a[i][j]==1&&indegree[j]!=-1)

                             indegree[j]--;

                           }

                           i=0;

                  }

       }

   }

  void main()

   {

   int i,j,n,indegree[10],a[10][10];

   printf("enter the number of vertices:");

   scanf("%d",&n);

   for(i=1;i<=n;i++)

   indegree[i]=0;

   printf("\n enter the adjacency matrix\n");

   for(i=1;i<=n;i++)

   for(j=1;j<=n;j++)

   {

      scanf("%d",&a[i][j]);

      if(a[i][j]==1)

      indegree[j]++;

   }

   topo(n,indegree,a);

   if(k!=n)

   printf("topological ordering is not possible\n");

 

else

   {

      printf("\n topological ordering is :\n");

      for(i=1;i<=k;i++)

      printf("v%d\t",temp[i]);

    }

  }

Using DFS algorithm:

1. Run DFS(G), computing finish time for each vertex
2. As each vertex is finished, insert it onto the front of a list

Solution:

#include<stdio.h>

int i,visit[20],n,adj[20][20],s,topo_order[10];

void dfs(int v)

{

  int w;

  visit[v]=1;

  for(w=1;w<=n;w++)

    if((adj[v][w]==1) && (visit[w]==0))

      dfs(w);

  topo_order[i--]=v;

}

void main()

{

  int v,w;

  printf("Enter the number of vertices:\n");

  scanf("%d",&n);

  printf("Enter the adjacency matrix:\n");

  for(v=1;v<=n;v++)

    for(w=1;w<=n;w++)

      scanf("%d",&adj[v][w]);

  for(v=1;v<=n;v++)

      visit[v]=0;

  i=n;

  for(v=1;v<=n;v++)

  {

   if(visit[v]==0)

      dfs(v);

  }

  printf("\nTopological sorting is:");

  for(v=1;v<=n;v++)

     printf("v%d ",topo_order[v]);

}

  

OUTPUT 1 :

Enter the number of vertices:

5

Enter the adjacency matrix

0 0 1 0 0

0 0 1 0 0

0 0 0 1 1

0 0 0 0 1

0 0 0 0 0

Topological ordering is v1 v2 v3 v4 v5

OUTPUT 2 :

enter the number of vertices:

3

Enter the adjacency matrix

0 1 0

0 0 1

1 0 0

Topological ordering is not possible

Lab program 3b. Compute the transitive closure of a given directed graph using Warshall's algorithm.

Description

Suppose we have a directed graph G = (V, E). It's useful to know, given a pair of vertices u and w, whether there is a path from u to w in the graph. A nice way to store this information is to construct another graph, call it G* = (V, E*), such that there is an edge (u, w) in G* if and only if there is a path from u to w in G. This graph is called the transitive closure of G.

Let n be the size of V. For k in 0..n, let t(k) be an adjacency matrix such that, if there is a path in G from any vertex i to any other vertex j going only through vertices in { 1, 2,..., k }, then t(k)[i,j] = True, False otherwise.

This set { 1, 2, ..., k } contains the intermediate vertices along the path from one vertex to another. This set is empty when k=0, so our previous definition of t(0) is still valid. When k=n, this is the set of all vertices, so t(n)[i,j] is True if and only if there is a path from i to j through any vertex. Thus t(n) is the adjacency matrix for the transitive closure of G.

The transitive closure is calculated using the formula for k >= 1:

t^(k)[i,j] = t^(k-1)[i,j] OR (t^(k-1)[i,k] AND t^(k-1)[k,j])

Solution:

#include<stdio.h>

void wars();

int a[20][20],n,i,j,k;

void main()

{

            printf("ENTER THE NO OF NODES");

            scanf("%d",&n);

            printf("ENTER THE ADJECENCY MATRIX\n");

            for(i=0;i<n;i++)

            {

                        for(j=0;j<n;j++)

                        {

                                    scanf("%d",&a[i][j]);

                        }

            }

            wars();

}

void wars()

{

            int k;

            for(k=0;k<n;k++)

            for(i=0;i<n;i++)

            for(j=0;j<n;j++)

            a[i][j]=(a[i][k]&&a[k][j])||a[i][j];

            printf("THE TRANSITIVE MATRIX IS\n");

            for(i=0;i<n;i++)

            {

                        for(j=0;j<n;j++)

                        {

                                    printf("%d\t",a[i][j]);

                        }

                        printf("\n");

            }

            return;

}

OUTPUT :

ENTER THE NO OF NODES4

ENTER THE ADJECENCY MATRIX

0 1 0 0

0 0 0 1

0 0 0 0

1 0 1 0

THE TRANSITIVE MATRIX IS

1       1       1       1

1       1       1       1

0       0       0       0

1       1       1       1

Lab program 4: Implement 0/1 Knapsack problem using Dynamic Programming.

Description:

Problem Statement: A thief robbing a store and can carry a maximal weight of W into their knapsack. There are n items and i^th  item weigh w and is worth v dollars. What items should thief take?

There are two versions of problem

Fractional knapsack problem:    The setup is same, but the thief can take fractions of items, meaning that the items can be broken into smaller pieces so that thief may decide to carry only a fraction of xi of item i, where 0 ≤ xi ≤ 1.

0-1 knapsack problem:    The setup is the same, but the items may not be broken into smaller pieces, so thief may decide either to take an item or to leave it (binary choice), but may not take a fraction of an item.

Dynamic-Programming Solution to the 0-1 Knapsack Problem:

Let i be the highest-numbered item in an optimal solution S for W pounds. Then S` = S - {i} is an optimal solution for W - wi pounds and the value to the solution S is Vi plus the value of the subproblem.

We can express this fact in the following formula: define c[i, w] to be the solution for items  1,2, . . . , i and maximum weight w. Then

	0	if i = 0 or w = 0
c[i,w]  =	c[i-1, w]	if wi ≥ 0
	max [vi + c[i-1, w-wi], c[i-1, w]}	if i>0 and w ≥  wi

Solution:

#include<stdio.h>

void kpsk(int ,int ,int[],int[],int[][100]);

void opt(int,int,int[],int[][100]);

int max(int,int);

void main()

{

            int w[20],p[20],n,m,i,v[10][100];

            printf("Enter the no of elements\n");

            scanf("%d",&n);

            printf("Enter the capacity of knapsack\n");

            scanf("%d",&m);

            printf("Enter the weight of elements\n");

            for(i=1;i<=n;i++)

                        scanf("%d",&w[i]);

            printf("Enter the profit of elements\n");

            for(i=1;i<=n;i++)

            {

                        scanf("%d",&p[i]);

            }

            kpsk(n,m,w,p,v);

            opt(n,m,w,v);

}

void kpsk(int n,int m,int w[],int p[],int v[][100])

{

            int i,j;

            for(i=0;i<=n;i++)

            for(j=0;j<=m;j++)

            {

                        if(i==0 || j==0)

                        v[i][j]=0;

                        else if(j<w[i])

                                    v[i][j]=v[i-1][j];

                        else

                        v[i][j]=max(v[i-1][j],p[i]+v[i-1][j-w[i]]);

            }

            for(i=0;i<=n;i++)

            {

                        for(j=0;j<=m;j++)

                        {

                                    printf("%d\t",v[i][j]);

                        }

                        printf("\n");

            }

}

void opt(int n,int m,int w[],int v[][100])

{

            int i,j,x[10];

            printf("The optimal solution is %d\n",v[n][m]);

            for(i=0;i<n;i++)

            x[i]=0;

            i=n;

            j=m;

            while((i!=0)&& (j!=0))

            {

                        if(v[i][j]!=v[i-1][j])

                        {

                                    x[i]=1;

                                    j=j-w[i];

                        }

                        i=i-1;

            }

            printf("The objects selected are \n");

            for(i=1;i<=n;i++)

            {

                        if(x[i]==1)

                                    printf("%d ",i);

            }

 }

 int max(int a, int b)

 {

            return(a>b? a:b);

 }

OUTPUT :

enter the no of elements

4

enter the capacity of knapsack

5

enter the wt of elements

2 1 3 2

enter the profit of elements

12 10 20 15

0       0       0       0       0       0

0       0       12      12      12      12

0       10      12      22      22      22

0       10      12      22      30      32

0       10      15      25      30      37

The optimal solution is 37

The objects selected are 1 2 4