Graph Coloring Technique

   GRAPH COLORING TECHNIQUE

DEFINATION:-

A coloring of a graph means assigning of a color to each vertex of the graph so that no two adjacent vertices are given the same color.In order to accomplish this we need the minimum number of colors to color the adjacent vertices which is called as the Chromatic Number of the graph.

PROCEDURE:-

Lets consider a un-directed graph G having V number of vertices and E number of  edges.

--> Enter the number of vertices of the graph.

--> Create an adjacency matrix of the above un-directed graph representing the             connected adjacent vertices.

  

--> Assign  Color 1 the nth vertices.

--> Check whether nth vertex is connected to any of previous (n-1) vertices 
      using  backtracking.

-->If connected then assign a color x[i]+1 where x[i] is the color of i th vertex          that is connected with nth vertex.

 SOURCE CODE USING C :-

#include<stdio.h>
#include<stdlib.h>

int col[100];
int adj[100][100];

void chkcolour(int v)
{
        int i;
        col[v]=1;
        for(i=0;i<v;i++)
        {
                if(adj[v][i]!=0 && col[v]==col[i])
                {
                        col[v]=col[i]+1;
                }
        }
}
void print_color(int v)
{
        int i;
        printf(" Printing the vertex colours:\n");
        for(i=0;i<v;i++)
        {
                 printf("Nodevertex-->[%d] has color --> :%d\n",i+1,col[i]);
        }

}

int main()
{
        int i,j,v;
        printf("enter the no of vertices:\n");
        scanf("%d",&v);
       printf("Start entering the values for adjacency matrix:\n");
        printf("________________________________________________\n");
        for(i=0;i<v;i++)
        {
                for(j=0;j<v;j++)
                {
                        scanf("%d",&adj[i][j]);
                }
        }

        printf("_______________________________\n");

        printf("The entered adjacency matrix is:\n ");
        for(i=0;i<v;i++)
        {
                for(j=0;j<v;j++)
                {
                        printf("%d",adj[i][j]);
                }
                printf("\n");
        }
        for(i=0;i<v;i++)
        {
                chkcolour(i);
        }
        chkcolour(v);
        printf("_______________________________\n");
        print_color(v);
        printf("_______________________________\n");


        return 0;
}



OUTPUT:

enter the no of vertices:
7
Start entering the values for adjacency matrix:
________________________________________________
0 1 1 0 1 1 1
1 0 1 0 0 0 0
1 1 0 1 1 0 0
0 0 1 0 1 1 0
1 0 1 1 0 1 0 
1 0 0 1 1 0 1
1 0 0 0 0 1 0
_______________________________
The entered adjacency matrix is:
 0110111
1010000
1101100
0010110
1011010
1001101
1000010
_______________________________
 Printing the vertex colours:
Nodevertex-->[1] has color --> :1
Nodevertex-->[2] has color --> :2
Nodevertex-->[3] has color --> :3
Nodevertex-->[4] has color --> :1
Nodevertex-->[5] has color --> :2
Nodevertex-->[6] has color --> :3
Nodevertex-->[7] has color --> :2

_______________________________

**********************************************************************************

Computational Geometry Problem To Find Out The Closest Set Of Points.

Closest Set Of Points Promblem

The closest pair of points problem is a problem of computational geometry promblem: given n points in metric space, find a pair of points with the smallest distance between them. 

suppose we are given an array of n points in the plane, and the problem is to find out the closest pair of points in the array. Recall the following formula for distance between two points p and q.

This problem arises in a number of applications. For example, in air-traffic control, you may want to monitor planes that come too close together, since this may indicate a possible collision so we need to track out the closest pair between them.

we know that the closest pair of points can be computed in O (n²) time by performing a brute-force approach. To do that, one could compute the distances between all the n(n − 1) / 2 pairs of points, then pick the pair with the smallest distance, as illustrated below.

minDist = infinity
for i = 1 to length(P) - 1
 for j = i + 1 to length(P)
  let p = P[i], q = P[j]
  if dist(p, q) < minDist:
   minDist = dist(p, q)
   closestPair = (p, q)
return closestPair

Although we can design it in various number of ways here is one of the possible ways where time complexity is O(n x (Logn)^2)

process:-

Input: An array of n points P[]
Output: The smallest distance between two points in the given array.

1) Find the middle point in the sorted array.

2) Divide the given array in two halves. The first subarray contains points from arr[0] to arr[n/2]. The second subarray contains points from arr[n/2+1] to arr[n-1].

3) Recursively find the smallest distances in both subarrays. Let the distances be dl and dr. Find the minimum of dl and dr. Let the minimum be d.

4) From above 3 steps, we have an upper bound d of minimum distance. Now we need to consider the pairs such that one point in pair is from left half and other is from right half. Consider the vertical line passing through passing through arr[n/2] and find all points whose x coordinate is closer than d to the middle vertical line. Build an array strip[] of all such points.

5) Sort the array strip[] according to y coordinates. This step is O(nLogn). It can be optimized to O(n) by recursively sorting and merging.

6) Find the smallest distance in S. 

c code to implement the closest set of points:-

#include<stdio.h>

#include<stdlib.h>

#include<math.h>

typedef struct

{

int x,y;

}point;

int main()

{

point *p;

int i,j,**d,n,min,s,t;

printf("\n Enter the no of points::\n");

scanf("%d",&n);

d=(int **)malloc(n*sizeof(int *));

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

        {

                d[i]=(int*)malloc(n*sizeof(int));

        }

p=(point*)malloc(n*sizeof(point));

printf("\n enter %d no of (x,y) co-ordinate points \n ",n);

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

{

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

}

printf("the distance matrix is:\n");

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

{

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

{

d[i][j]=sqrt(pow((p[i].x-p[j].x),2)+pow((p[i].y-p[j].y),2));

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

 

}

printf("\n");

}

min=9999;

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

        {

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

                {

                        if(i!=j)

{

if(min>d[i][j])

{

min=d[i][j];

s=i;

t=j;

}

}

                }

        }

 

printf("\n FROM  %d   to  %d  is the minimum distance =  %d ",s+1,t+1,min);

}

*********************************************************************************************************************

ieee representation of floating point numbers

IEEE REPRESENTATION OF FLOATING POINT NUMBER

An IEEE-754 float (4 bytes) or double (8 bytes) has three components (there is also an analogous 96-bit extended-precision format under IEEE-854):

-> a sign bit telling whether the number is positive or negative, 

->an exponent giving its order of magnitude,

->an mantissa specifying the actual digits of the number. 

Using single-precision floats(32 bit) as an example, here is the bit layout:-

we have to represent it in form of ->1.M *2^(+/-E)

where:-

 ->M is the mantissa which is to be represented in 23 bit for single precision number.

->E is the exponent  which is to be represented in 8 bit for single precision number.

eg 1:

now suppose the floating point no: is 11.27

->signbit in 1 bit is: 1

->mantissa in 23 bit is: :0 1 1 0 1 0 0 0 1 0 1 0 0 0 1 1 1 1 0 1 0 1 1 

->exponent is 8 bit: 10000010

eg 2:

now suppose the floating point no: is 157.38
->signbit in 1 bit is: 1

->mantissa in 23 bit is: :0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 1 1 1 

->exponent is 8 bit: 10000110

C CODE FOR IEEE REPRESENTATION OF FLOATING POINT NUMBER

#include<stdio.h>

#include<stdlib.h>

#include<math.h>

static int r[23],mant[24];

int dec2bin(int n,int *arr)

{

int i,p;

p=n;

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

arr[i]=0;

i=22;

do

{

arr[i]=n%2;

n=n/2;

i--;

}

while(n!=0);

if(p<0)

{

printf("****negative number****\n");

printf("do enter a positive number\n");

}

else

{

printf("the binary equivalent of %d is:",p);

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

printf("%d",arr[i]);

}

printf("\n");

}

int dec2bin4exp(int n,int *arr)

{

        int i,p;

        p=n;

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

        arr[i]=0;

        i=7;

        do

        {

                arr[i]=n%2;

                n=n/2;

                i--;

        }

        while(n!=0);

                printf("the binary equivalent of %d is ",p);

printf("(i.e the exponent part in 8 bit is:)");

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

                printf("%d",arr[i]);

        

                printf("\n");

}

int sign(float n)

{

int sign;

if(n>0)

sign=0;

else

sign=1;

printf("the signbit=%d\n",sign);

}

int rep(int *arr)

{

    

     int i,j,z=0,t=0,l,flag=0,power,sign,bias,k=0;

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

     {

            if(arr[i]==1)

            z=i;

   if(z>0)

   {

for(l=z+1;l<23;l++)

 mant[k++]=arr[l];

     break;

   }

     }

      bias=k+127;

      //printf("K=%d",k);

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

{

mant[k++]=r[j];

    }

printf("the mantissa part in 23 bit is:");

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

{

printf("%d ",mant[i]);

}

printf("\n");

printf("------------------------------------------------------\n");

printf(" bias value is=%d\n",bias);

dec2bin4exp(bias,r);

}

void pt2bin(double d)

{

int i;

static double ar[23],f=0.0;

ar[0]=d;

// printf("\nar=%f\n",ar[0]);

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

{

f=ar[i] *2;

r[i]=(int)f;

ar[i+1]=f-r[i];

}

printf("The binary equivalent of %lf is:",d);

int ii;

for(ii=0;ii<23;ii++)

printf("%d ",r[ii]);

printf("\n");

}

int main()

{

double f,deci;

int real,arr[23],arr1[5];

printf("enter a floating point number\n");

scanf("%lf",&f);

real=f;

deci=f-real;

printf("------------------------------------------------------\n");

printf("the real part of the number is:=%d\n",real);

printf("the decimal part of the number is:=%lf\n",deci);

printf("------------------------------------------------------\n");

dec2bin(real,arr);

pt2bin(deci);

printf("------------------------------------------------------\n");

sign(f);

rep(arr);

printf("------------------------------------------------------\n");

return 0;

}

Toeplitz matrix and its creation in c

                                                          Toeplitz matrix

defination:-

In linear algebra a Toeplitz matrix or diagonal-constant matrix is a matrix in which each desending diagonal from left to right is constant.  

lets consider a example which would make it clear how a toeplitz matrix looks like.

And its matrix equation form is:- c++ code to form this matrix and add two such matrixes                  CODING: #include<stdio.h> #include<stdlib.h> int main() { int b[10][10],a[10],a1[10],c[10][10],d[10][10],i,j,x=0,max;       /*  initialization  */ printf("Enter the maximum nos of element you want to input \n"); scanf("%d",&max); for(i=0;i<max;i++)                                                                    /* input to the 1st matrix  */ {                   printf("enter the element of the fist array\n");                   scanf("%d",&a[i]); } printf("The elements of the first toeplitz matrix is:\n");  for(i=0;i<max;i++) {                   for(j=0;j<max;j++)                   {                                     b[i][j]=a[x++];       /*passing up of single dimensional array into double array*/                                     x=x%max;                                     printf("%d",b[i][j]);                   }                   x=max-1-i;                   printf("\n"); } for(i=0;i<max;i++)                                                             /* input to 2nd matrix  */ {                   printf("enter the element of the second array\n");                    scanf("%d",&a1[i]); } printf("The element for the second toeplitz matrix:\n"); for(i=0;i<max;i++)                           /* arranging the element into the toeplitz matrix */ {                   for(j=0;j<max;j++)                   {                                     c[i][j]=a1[x++];                                     x=x%max;                                     printf("%d",c[i][j]);                   }                   x=max-1-i;                   printf("\n"); } printf("The addition of the two toeplitz matrix is:\n"); for(i=0;i<max;i++)                                         /* addition of the two toeplitz matrix  */ {                   for(j=0;j<max;j++)                   {                                     d[i][j]=b[i][j]+c[i][j];                                     } } for(i=0;i<max;i++)                         /*  printing the addition of the two toeplitz matrix */ {                   for(j=0;j<max;j++)                   {                                     printf("%d",d[i][j]);                                     }                   printf("\n"); } system("pause"); return 0; } ********************************************************************