Implementation of topological sorting in c++

topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge u->v from vertex u to vertex v, u comes before v in the ordering.

The canonical application of topological sorting  is in scheduling a sequence of jobs or tasks based on their dependencies;


#include<iostream.h>
int n,adj[100][100];
int front = -1,rear = -1,queue[100];
void main()
{
 int i,j = 0,k;
 int topsort[100],indeg[100];
 create_graph();
 cout<<"The adjacency matrix is:"<<"/n";
 display();
 for(i=1;i<+n;i++)
 {
  indeg[i]=indegree(i);
  if(indeg[i]==0)
   insert_queue(i);
 }
 while(front<=rear)
 {
  k=delete_queue();
  topsort[j++]=k;
  for(i=1;i<=n;i++)
  {
   if(adj[k][i]==1)
   {
    adj[k][i]=0;
    indeg[i]=indeg[i]-1;
    if(indeg[i]==0)
     insert_queue(i);
   }
  }
 }
 cout<<"Nodes after topological sorting are:\n");
 for(i=0;i<=n;i++)
  cout<<topsort[i];
 cout<<"\n";
}
create_graph()
{
 int i,max_edges,origin,destin;
 cout<<"\n Enter number of vertices:";
 scamf("%d",&n);
 max_edges = n * (n - 1);
 for(i = 1;i <= max_edges;i++)
 {
  cout<<"\n Enter edge "<<i<<" (00 to quit):";
  cin>>origin>>destin;
  if((origin == 0) && (destin == 0))
  {
   cout<<"Invalid edge!!\n";
   i–-;
  }
  else
   adj[origin][destin] = 1;
 }return;
}
display()
{
 int i,j;
 for(i = 0;i <= n;i++)
 {
  for(j = 1;jrear)
  {
   cout<<"Queue Underflow”;
   return;
  }
  else
  {
   del_item = queue[front];
   front = front + 1;
   return del_item;
  }
 }
 int indegree(int node)
 {
  int i,in_deg = 0;
  for(i = 1;i <= n;i++)
   if(adj[i][node] == 1)
    in_deg++;
  returnin_deg;
 }

Liang - Barsky Plygon clipping Algorithm

algorithm for Clipping Polygon Segments
INPUT : HSA=<h1,h2,...hn> (Half-segment Array)
 w = Rectangle
OUTPUT: cHSA = clipped half-segments and the half-segments
 resulting from the evaluation of turning points
cHSA = Ø;
turningPointSets = Ø;
FOR i=1 TO n DO
 IF (hi has left dominating point) THEN
 IF (SutherlandCohenLineClipping(hi, w, clippedhs, intersection-point,
 isIntersectionPoint)) THEN
 IF (isIntersectionPoint) THEN
 EvaluateTurningPoint(w, intersectionPoint, turningPointSets, hi);
 ELSE
 cHSA.Add(clippedhs);

algorithm to  EvaluateTurningPoint 
INPUT : w = a rectangle described by the coordinates (xmin, ymin) and (xmax, ymax)
 p = Point
 turningPointSets = for each window egde there is a set recording the
 turning point of the edge
 h = halfsegment that the point p belongs to
OUTPUT: If the point is evaluated as a turning point it is added to the Turning
 Point Set of the edge
 tp = p;
IF (p.x = w.xmin) THEN //left edge
 IF (h.insideAbove) THEN
 tp.direction = UP;
 ELSE
 Tp. direction = DOWN;
 END-IF;
 turningPointSets[LEFT].add(tp);
ELSE //right edge
 IF (h.insideAbove) THEN
 tp. direction = UP;
 ELSE
 tp. direction = DOWN;
 END-IF;
 turningPointSets[RIGHT].add(tp);
END-IF;
IF (p.y = w.ymin) THEN //bottom edge
 IF (h.leftPoint > w.ymin) THEN
 tp.direction = GetDirection(p, h.leftPoint, xmin, ymin, h.insideAbove);
 ELSE
 tp.direction = GetDirection(p, h.rightPoint, xmin, ymin, h.insideAbove);
 END-IF;
 turningPointSets[BOTTOM].add(tp);
ELSE
 IF (p.y = w.ymax) THEN //top edge
 IF (h.leftPoint > w.ymin) THEN
 tp.direction = GetDirection(p, h.leftPoint, xmin, ymin, h.insideAbove);
 ELSE
 tp.direction = GetDirection(p, h.rightPoint, xmin, ymin, h.insideAbove);
 END-IF;
 turningPointSets[BOTTOM].add(tp);
 END-IF;
END-IF;

algorithm to Get Direction 
INPUT: tp = turning point
 p = point of the same half segment that the turning point tp belongs
 and is above tp
 (x, y) = the left coordinate of the vertex of the window edge
 insideAbove = insideAbove flag’s value
IF (insideAbove) THEN
 IF (tp.x > p.x) THEN
 return RIGHT;
 ELSE
 return LEFT;
 END-IF;
ELSE
 IF (tp.x > p.x) THEN
 return LEFT;
 ELSE
 return RIGHT;
 END-IF;

algorithm to Create NewSegments
INPUT: edge = indicates which edge is been handled(LEFT, RIGHT, TOP or
 BOTTOM)
 bPoint,ePoint = end points of the edge
 turningPointSet = a set of the turning points of the edge
 cHSA = set of half segments in which the new half segments will be added

OUTPUT: cHSA with the new half segments
 IF edge == TOP or edge == LEFT THEN
 InsideAbove = false;
 ELSE /*RIGHT or BOTTOM edges*/
 InsideAbove = true;
 END-IF;
 begin = 0;
 end = turningPointSet.size();
 tp = turningPointSet[begin];
 IF (tp.Direction== LEFT or tp.Direction == DOWN) and not tp.Rejected THEN
 cHSA.addHalfSegments(tp,bPoint,InsideAbove);
 DiscardTurningPoints(turningPointSet, tp, ASCENDIN_GORDER, begin);
 END-IF;
 tp = turningPointSet[end];
 IF (tp.Direction== RIGHT or tp.Direction == UP) and not tp.Rejected
 and there is no rejected turning point equals to tp THEN
 cHSA.addHalfSegments(tp,ePoint,InsideAbove);
 DiscardTurningPoints(turningPointSet, DESCENDING_ORDER, end);
 END-IF;
 WHILE (begin<end) DO
tp1 = GetNotRejectedTurningPoint(turningPointSet, ASCENDING_ORDER, begin);
IF tp1 == NULL THEN
 return;
END-IF;
tp2 = GetNotRejectedTurningPoint(turningPointSet, DESCENDING_ORDER, end);
IF tp2 == NULL THEN
 return;
END-IF;
cHSA.addHalfSegments(tp1,tp2,InsideAbove);
END-WHILE;

algorithm for  Polygon Reconstruction 

INPUT: HSA=<h1,h2,...hn> (Halfsegment Array) 

OUTPUT: HSA = each halfsegment has the face, cycle, and edge numbers set 

VARIABLES: face = array that stores in position i the last cycle number of the 

 face i 

 hsSet = array that stores in the position i if the half segment hi 

 had already the face number, the cycle number and the edge 

 number set. This array is initialized with values false. 

 IF HSA is not sorted in halfsegment order THEN 

 Sort HSA in halfsegment order; 

END-IF; 

IF the halfsegments of HSA do not have the partner number set THEN 

 Set partner number of the halfsegments of HSA; 

END-IF; 

face[0] = 0; /*0 is assigned to the first cycle of the first face */ 

lastFaceNumber = 0; 

isFirstHS = true; 

 FOR i=1 TO n DO 

 IF hi has left dominating point and not hsSet[i] THEN 

 IF isFirstHS THEN 

 isFirstHS = false; 

 hi.faceNumber = 0; 

 hi.cycleNumber = 0; 

 ELSE 

 existingFaceNumber = GetFaceNumber(HSA, hi, hsSet, i); 

 IF existingFaceNumber is equal to -1 THEN 

 lastFaceNumber++; 

 hi.faceNumber = lastFaceNumber; 

 hi.cycleNumber = 0; 

 /*to store the first cycle number of the face lastFace*/ 

 face[faceNumber-1]=0; 

 ELSE 

 hi.faceNumber = existingFaceNumber; 

 face[faceNumber]++; 

 hi.cycleNumber = face[faceNumber]; 

 END-IF; 

 END-IF; 

 hi.edgeNumber = 0; 

 ComputeCycle(HSA, hi, hsSet); 

 END-IF; 

 END-FOR; 

window clipping in 

Signature: (line x rect) -> line, (region x rect) --> region 

Syntax: windowclippingin( _, _ ) 

Meaning: computes the part of the object that is inside the window. 

Example: query Flaechen feed extend[InWindow: windowclippingin( 

 .geoData, bbox(thecenter))] project[InWindow] 

 filter[not(isempty(.InWindow))] consume 

 window clipping out 

Signature: (line x rect) -> line, (region x rect) --> region 

Syntax: windowclippingout( _, _ ) 

Meaning: computes the part of the object that is outside the window. 

Example: query windowclippingout(trajectory(train7), bbox(thecenter)) 

Why the Look of the google home page is so simple

Errors in programs of computer graphics related to GRAPHICS.H

Some of the Errors Startup and New Programmers face while writing Graphics programs in C or C++  :

• Messages like  " Cannot open include file < graphics.h > " .
• Linker errors relating to < graphics.h > .
• Messages like : Graphics not initialized .

To overcome the above errors and many others, try the following steps

1. Copy the file [ egavga.bgi ] from the folder BGI to BIN folder 
2. GoTo OPTIONS >   LINKER > LIBRARIES and mark the Graphics option
3. Use int gdriver , gmode = DETECT;  initgraph( &gdriver, &gmode, "" ) ;                       before writing any graphics code ;

                                       

Implementation of Dijkstra's Single Source Shortest Path Algorithm in C++

#include<iostream.h>
#include<limits.h>
#include<assert.h>
#define max_vertex 100
#define  infinite 999999999

typedef struct Node
{
        int vertex,distance;
}Node;

Node heap[1000000];
int visited[max_vertex];
int heapSize;

void Init()
{
        heapSize = 0;
        heap[0].distance = -INT_MAX;
        heap[0].vertex  = -1;
}

void Insert(Node element)
{
        heapSize++;
        heap[heapSize] = element;

        int now = heapSize;
        while(heap[now/2].distance > element.distance) 
        {
                heap[now] = heap[now/2];
                now /= 2;
        }
        heap[now] = element;
}
Node DeleteMin()
{
       
        Node minElement,lastElement;
        int child,now;
        minElement = heap[1];
        lastElement = heap[heapSize--];
  
  
        for(now = 1; now*2 <= heapSize ;now = child)
        {
               
                child = now*2;
               
                if(child != heapSize && heap[child+1].distance < heap[child].distance ) 
                {
                        child++;
                }
              
                if(lastElement.distance > heap[child].distance)
                {
                        heap[now] = heap[child];
                }
                else /* It fits there */
                {
                        break;
                }
        }
        heap[now] = lastElement;
        return minElement;
}
int main()
{
        int graph[max_vertex][max_vertex],size[max_vertex]={0},distance[max_vertex]={0},cost[max_vertex][max_vertex];
        int vertices,edges,weight;
        int iteration;
    
        cin>>vertices>>edges;
        int from,to;
        for(iteration=0;iteration<edges;iteration++)
        {
                cin>>from>>to>>weight;
                assert(from>=0 && from<vertices);
                assert(to>=0 && to<vertices);
                graph[from][size[from]] = to;
                cost[from][size[from]] = weight;
                size[from]++;
        }
        int source;
        cin>>source;
        Node temp;
        for(iteration=0;iteration<vertices;iteration++)
        {
                if(iteration==source)
                {
                        temp.distance = 0;
                        distance[0]=0;
                }
                else
                {
                        temp.distance = infinite;
                        distance[iteration]= infinite;
                }
                temp.vertex = iteration;
                Insert(temp);
        }
        while(heapSize)
        {
                Node min = DeleteMin();
                int presentVertex = min.vertex;
                if(visited[presentVertex])
                {
                        
                        continue;
                }
                visited[presentVertex] = 1;
                for(iteration=0;iteration<size[presentVertex];iteration++)
                {
                        int to = graph[presentVertex][iteration];
                        if(distance[to] > distance[presentVertex] + cost[presentVertex][iteration])
                        {
                                distance[to] = distance[presentVertex] + cost[presentVertex][iteration];
                               
                                temp.vertex = to;
                                temp.distance = distance[to];
                                Insert(temp);
                        }
                }
        }
        for(iteration=0;iteration<vertices;iteration++)
        {
                cout<<"vertex is "<<iteration<<" , its distance is "<<iteration,distance[iteration]<<endl;
        }

        return 0;
}

Implementation of Banker's algorithm in C++

It is a deadlock avoidance strategy utilized to check where whether the given state of the system having certain maximum request and availability of the resources is safe or if it can lead to a deadlock;

For the Banker's algorithm to work, it needs to know three things:

• Maximum no. of instances a process is allowed to hold [MAX]
• Resources each process is currently holding[ALLOCATED]
• Resources currently available in the system [AVAILABLE]

Either MAX is given or REQUEST is given

if  REQUEST are given  then MAX=allocated+request;

From these [NEED] of each process is calculated.

need=max-allocated

Resources are allocated to a process  if :

• need≤ available

#include<iostream.h>

#include<conio.h>

void main()

{

int instance[5],count,sequence[10],safe,s=0,j,completed;

int available[5],allocation[10][5],max[10][5];

int need[10][5],process,P[10],countofr,countofp,running[10];

clrscr();

cout<<"\n Enter the number of resources (<=5): ";

cin>> countofr;

for(int i=0;i<countofr;i++)

{  cout<<"\n enter the max instances of  resource R["<<i<<"] :";

   cin>>instance[i];

   available[i]=instance[i];

}

cout<<"\n Enter the number of processes (<=10): ";

cin>> countofp;

cout<<"\n Enter the allocation matrix \n     ";

 

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

   { cout<<"FOR THE PROCESS :P["<<i<<"]"<<endl;

     for(int j=0;j<countofr;j++)

    {  cout<<"allocation of resource R["<<j<<"] is : " ;

  cin>>allocation[i][j];

  available[j]-=allocation[i][j];

}

   }

cout<<"\nEnter the MAX matrix \n\n";

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

       { cout<<"FOR THE PROCESS P["<<i<<"]"<<endl;

for(int j=0;j<countofr;j++)

 {   cout<<"max demand of resource R["<<j<<"] is : ";

     cin>>max[i][j];

 }

       }

clrscr();

cout<<"\n the given data are : \n";

cout<<endl<<"\nTotal resources in system : \n\n  ";

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

   cout<<" R["<<i<<"]  ";

   cout<<endl;

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

   cout<<"     "<<instance[i];

cout<<"\n\n ALLOCATION matrix \n\n\t";

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

   cout<<"R["<<j<<"]  ";

   cout<<endl;

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

{  cout<<"P["<<i<<"]  ";

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

      cout<<"    "<<allocation[i][j];

   cout<<endl;

 }

 cout<<"\n\n MAX matrix \n\n\t";

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

   cout<<"R["<<j<<"]  ";

   cout<<endl;

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

{  cout<<"P["<<i<<"]  ";

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

      cout<<"    "<<max[i][j];

   cout<<endl;

 }

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

       { 

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

 {   

     need[i][j]=max[i][j]-allocation[i][j];

 }

}

 cout<<"\n\n NEED matrix \n\n\t";

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

   cout<<"R["<<j<<"]  ";

   cout<<endl;

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

{  cout<<"P["<<i<<"]  ";

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

      cout<<"    "<<need[i][j];

   cout<<endl;

 }

 cout<<"\n NOW to  check whether above state is safe";

 cout<<"\n sequence in which above requests can be fulfilled";

 cout<<"\n press any key to continue";

 getch();

count=countofp;

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

    { running[i]=1;}

while(count)

    {   safe=0;

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

  { if(running[i])

      {  completed=1;

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

    {   if(need[i][j]> available[j])

  { completed=0;

    break;

  }

    }

if(completed)

                {

   running[i]=0;

                    count--;

   safe=1;

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

                    {

                        available[j]+=allocation[i][j];

                    }

   sequence[s++]=i;

   cout<<"\n\n Running process P["<<i<<"]";

   cout<<endl<<"\n\nTotal resources now available:\n\n";

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

   cout<<" R["<<i<<"]  ";

   cout<<endl;

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

   cout<<"     "<<available[i];

                    break;

                }

            }

        }    

         if(!safe)

         break;

     }

if(safe)

 {

            cout<<"\nThe System is in safe state";

   cout<<"\nSafe sequence is :";

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

            {

                cout<<"\t"<<"P["<<sequence[i]<<"]";

            }

 }

else

 {

   cout<<"\nThe System is in unsafe state";

 }

       getch();

}

Program to implement Extended Euclidean algorithm

This version is for RSA public-key encryption method.
e*d mod z =1

it takes the value of e or d and returns the value of  d or e respectively.

#include <stdio.h>
#include <string.h>
int z,ed;
int ee_algo(int x1,int x2,int x3,int y1,int y2,int y3)
{ int q=x3/y3;
     int tx1=y1;
     int tx2=y2;
     int tx3=y3;
     y1=x1-q*y1;
     y2=x2-q*y2;
     y3=x3-q*y3;
   
    if(y3==1)
    { if(y2>0)
       return y2;
       else return y2+z;

    }
  else
  {   x1=tx1;
     x2=tx2;
     x3=tx3;
       
      return ee_algo(x1,x2,x3,y1,y2,y3);
  }

}
main()
{
    z=2400;

  ed=29;
   printf("%d",ee_algo(1,0,z,0,1,ed));
}