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));
}

Simple program for a crawler for saving google search to local database

Class conn

import java.sql.*;
import java.util.ArrayList;
import java.util.Properties;

class conn
{
    /* the default framework is embedded*/
    private String framework = "embedded";
    private String driver = "org.apache.derby.jdbc.EmbeddedDriver";
    private String protocol = "jdbc:derby:";
 


    public void go(int link_id,int word_id,String link ,String title,String Snippet)
    {
       

        System.out.println("DBworks starting in " + framework + " mode");
        loadDriver();

       
        Connection conn = null;
    ArrayList statements = new ArrayList(); // list of Statements, PreparedStatements
        PreparedStatement psInsert = null;
        PreparedStatement psUpdate = null;
        Statement s = null;
        ResultSet rs = null;
        try
        {
            Properties props = new Properties();
            props.put("user", "user1");
            props.put("password", "user1");
            String dbName = "crawler";

          
            conn = DriverManager.getConnection(protocol + dbName
                    + ";create=true", props);

            System.out.println("Connected to and created database " + dbName);

            conn.setAutoCommit(false);

           
            s = conn.createStatement();
            statements.add(s);
              rs = s.executeQuery("SELECT link_id,word_id,title ,snippet,link  FROM links ORDER BY link_id");       
            if (!rs.next())
            {
             s.execute("create table links(link_id int,word_id int,link varchar(80),title  varchar(40), snippet varchar(150))");
            System.out.println("Created table links");
              
            }
        
            psInsert = conn.prepareStatement("insert into links values (?, ? ,? ,?,?)");
            statements.add(psInsert);

            psInsert.setInt(1,1);
            psInsert.setInt(2,2);
            psInsert.setString(3, "qwerty");
            psInsert.setString(4, "qwerty");
            psInsert.setString(5, "qwerty");
            psInsert.executeUpdate();
            System.out.println("Inserted qwerty");
           
            rs = s.executeQuery("SELECT link_id,word_id,title ,snippet,link  FROM links ORDER BY link_id");        
            boolean failure = false;
              int number;
            if (!rs.next())
            {
                failure = true;
                reportFailure("No Data In Database");
            }

            if ((number = rs.getInt(1)) != 1)
            {
                failure = true;
                reportFailure(
                        "Wrong row returned, expected link_id=1, got " + number);
            }
       
                       if (!failure) {
                System.out.println("Verified the rows");
            }

            s.execute("drop table links");
            System.out.println("Dropped table links");

          
            conn.commit();
            System.out.println("Committed the transaction");
            if (framework.equals("embedded"))
            {
                try
                {   
                    DriverManager.getConnection("jdbc:derby:;shutdown=true");
                }
                catch (SQLException se)
                {
                    if (( (se.getErrorCode() == 50000)&& ("XJ015".equals(se.getSQLState()) )))
                          {
                             System.out.println("Derby shut down normally");
                          }
                    else  {
                             System.err.println("Derby did not shut down normally");
                             printSQLException(se);
                          }
                }
            }
        }
        catch (SQLException sqle)
        {
            printSQLException(sqle);
        } finally {
            // release all open resources to avoid unnecessary memory usage

            // ResultSet
            try {
                if (rs != null) {
                    rs.close();
                    rs = null;
                }
            } catch (SQLException sqle) {
                printSQLException(sqle);
            }

            // Statements and PreparedStatements
            int i = 0;
            while (!statements.isEmpty()) {
                // PreparedStatement extend Statement
                Statement st = (Statement)statements.remove(i);
                try {
                    if (st != null) {
                        st.close();
                        st = null;
                    }
                } catch (SQLException sqle) {
                    printSQLException(sqle);
                }
            }

            //Connection
            try {
                if (conn != null) {
                    conn.close();
                    conn = null;
                }
            } catch (SQLException sqle) {
                printSQLException(sqle);
            }
        }
    }


    private void loadDriver() {
        try {
            Class.forName(driver).newInstance();
            System.out.println("Loaded the appropriate driver");
        } catch (ClassNotFoundException cnfe) {
            System.err.println("\nUnable to load the JDBC driver " + driver);
            System.err.println("Please check your CLASSPATH.");
            cnfe.printStackTrace(System.err);
        } catch (InstantiationException ie) {
            System.err.println(
                        "\nUnable to instantiate the JDBC driver " + driver);
            ie.printStackTrace(System.err);
        } catch (IllegalAccessException iae) {
            System.err.println(
                        "\nNot allowed to access the JDBC driver " + driver);
            iae.printStackTrace(System.err);
        }
    }

    private void reportFailure(String message) {
        System.err.println("\nData verification failed:");
        System.err.println('\t' + message);
    }

  
    public static void printSQLException(SQLException e)
    {
      
        while (e != null)
        {
            System.err.println("\n----- SQLException -----");
            System.err.println("  SQL State:  " + e.getSQLState());
            System.err.println("  Error Code: " + e.getErrorCode());
            System.err.println("  Message:    " + e.getMessage());
            e = e.getNextException();
        }
    }
}

class crawler with main class

 

    import java.awt.*;

    import java.awt.event.*;

    import java.util.*;

    import java.net.*;

    import java.io.*;

    import javax.swing.*;

  

    import java.net.URL;

    import java.net.MalformedURLException;

    import java.util.regex.Pattern;

    import java.util.regex.Matcher;

    public class Crawler extends conn

    {

         public static void main(String [] args)

         {

              JFrame frame = new EditorPaneFrame();

              frame.show();

                        

         }

    }

    class EditorPaneFrame extends JFrame

    {

       

         conn connection = new conn();

         private JTextField url;

         private JButton loadButton;

         private JButton backButton;

         private JEditorPane editorPane;

         private Stack urlStack = new Stack();

    

    

         public EditorPaneFrame()

         {

              setTitle("Web Crawler");

              setSize(600,400);

              addWindowListener(new WindowAdapter()

              {

                   public void windowClosing(WindowEvent e)

                   {

                        System.exit(0);

                   }

          } );

    

             

              // set up text field and load button for typing in URL

    

             url = new JTextField(30);

    

              loadButton = new JButton("Search");

              loadButton.addActionListener(new ActionListener()

              {

                   public void actionPerformed(ActionEvent event)

                   {  

                         try

                         {

String  search = "https://www.googleapis.com/customsearch/v1?key=YPUR-GOOGLE-API-KEY&cx=013036536707430787589:_pqjad5hr1a&q="+url.getText()+"&alt=json";

                    

                          URL url = new URL(search);

                          URLConnection link = url.openConnection();

                           

                          BufferedReader reader = new BufferedReader( new InputStreamReader(link.getInputStream()));

                           Pattern linkPattern = Pattern.compile("[\"]link[\"]:.*");

                           Pattern titlePattern = Pattern.compile("[\"]title[\"]:.*");

                           Pattern snippetPattern = Pattern.compile("[\"]snippet[\"]:.*");

                                                                

                          String line;

                          String newlink;

                           String title;

                            String snippet;

                             while ((line =reader.readLine()) != null)

                             {  Matcher l = linkPattern.matcher(line);

                                Matcher t =titlePattern.matcher(line);

                                Matcher s = snippetPattern.matcher(line);

                                while(l.find())

                                {   newlink=l.group();

                                    newlink=newlink.replaceAll("[\"]link[\"]: [\"]", "");

                                  System.out.println(newlink);

                                

                                }

                                while(t.find())

                                {  title=t.group();

                                    title=title.replaceAll("[\"]title[\"]: [\"]", "");

                                  System.out.println(title);

                                

                                }

                                while(s.find())

                                {  snippet=s.group();

                                    snippet=snippet.replaceAll("[\"]snippet[\"]: [\"]", "");

                                  System.out.println(snippet);                                

                                } 

                  

                             }                             

                             reader.close();                           

                         }                      

                     catch (MalformedURLException e)

                              {

                                  e.printStackTrace();

                              }

                     catch (IOException e)

                             {

                                  e.printStackTrace();

                             }                                         

    };

   });

    

              // set up back button and button action

    

              backButton = new JButton("Back");

              backButton.addActionListener(new ActionListener()

              {

                   public void actionPerformed(ActionEvent event)

                   {

                        if(urlStack.size()<=1) return;

                        try

                        {

                             urlStack.pop();

                             String urlString = (String)urlStack.peek();

                             url.setText(urlString);

                             editorPane.setPage(urlString);

                        }

                        catch(IOException e)

                        {

                             editorPane.setText("Error : " +e);

                        }

                   }

              });

    

              editorPane = new JEditorPane();

              editorPane.setEditable(false); 

              Container contentPane = getContentPane();

              contentPane.add(new JScrollPane(editorPane), "Center");

              JPanel panel = new JPanel();

              panel.add(new JLabel("Search Term"));

              panel.add(url);

              panel.add(loadButton);

              panel.add(backButton);

    

              contentPane.add(panel,"South");

         }

    

    }    

 

 

 

 

 

Implementation of Cohen-Sutherland Line clipping Algorithm

#include<graphics.h>
#include<conio.h>
#include<iostream.h>
const int t=1, b=2, r=4, l=8 ;
float xmin,ymin,xmax,ymax;
int calcode (float x,float y)
{ int code =0;
  if(y> ymax) code |=t;
  else if(y<ymin) code |= b;
  else if(x>xmax) code |= r;
  else if(x<xmin) code |= l;
  return(code);
}

void lineclip(float x1,float y1,float x2,float y2)
{ unsigned int code1,code2,codeout;
  int accept = 0, done=0;
  code1 = calcode(x1,y1);
  code2 = calcode(x2,y2);
  do{ if(!(code1 | code2))
    { accept =1 ; done =1; }
    else if(code1 & code2) done = 1;
    else
    { float x,y;
       codeout = code1 ? code1 : code2;
       if(codeout & t)
    { x = x1 + (x2-x1)*(ymax-y1)/(y2-y1);y = ymax;}
       else if(codeout & b)
    {x=x1+(x2-x1)*(ymin-y1)/(y2-y1);y=ymin;}
       else if (codeout & r)
      {y=y1+(y2-y1)*(xmax-x1)/(x2-x1);x=xmax;}
       else
     {y=y1+(y2-y1)*(xmin-x1)/(x2-x1);x=xmin;}
       if(codeout == code1)
      {x1 = x; y1 = y;
      code1=calcode(x1,y1);}
       else
    {x2 = x; y2 = y;
     code2 = calcode(x2,y2);}
   }
  } while( done == 0);
  if(accept)
    line(x1,y1,x2,y2);
    rectangle(xmin,ymin,xmax,ymax);
}

main()
{ float x1,y1,x2,y2;
  int gd=DETECT,gm;
  clrscr();
  initgraph(&gd,&gm,"");
  cout<<"\n\n\t:::Enter the co-ordinates of Line::::\n\tx1 :";cin>>x1;
  cout<<"\n\ty1 :";cin>>y1;
  cout<<"\n\tx2 :";cin>>x2;
  cout<<"\n\ty2 :";cin>>y2;
  cout<<"\n\t:::Enter the co_ordinates of window:::\n ";
  cout<<"\n\txmin :";cin>>xmin;
  cout<<"\n\tymin :";cin>>ymin;
  cout<<"\n\txmax :";cin>>xmax;
  cout<<"\n\tymax :";cin>>ymax;
  clrscr();
  line(x1,y1,x2,y2);
  rectangle(xmin,ymin,xmax,ymax);
  getch();
  clrscr();
  lineclip(x1,y1,x2,y2);
  getch();
  closegraph();
  return 0;
}

Implementation of Sutherland–Hodgman Polygon Clipping Algorithm

#include <stdio.h>
#include <graphics.h>
#include <conio.h>
#include <math.h>
#include <process.h>
#define TRUE 1
#define FALSE 0
typedef unsigned int outcode;
outcode CompOutCode(float x,float y);
enum  {  TOP = 0x1,
BOTTOM = 0x2,
RIGHT = 0x4,
LEFT = 0x8
};
float xmin,xmax,ymin,ymax;
void clip(float x0,float y0,float x1,float y1)
{
outcode code1,code2,codeout;
int accept = FALSE,done = FALSE;
code1 = CompOutCode(x0,y0);
code2 = CompOutCode(x1,y1);
do
{
if(!(code1|code2))
{
accept = TRUE;
done = TRUE;
}
else
if(code1 & code2)
done = TRUE;
else
{
float x,y;
 
codeout = code1?code1:code2;
if(codeout & TOP)
{
x = x0+(x1-x0)*(ymax-y0)/(y1-y0);
y = ymax;
}
else
if(codeout & BOTTOM)
{
x = x0+(x1-x0)*(ymin-y0)/(y1-y0);
y = ymin;
}
else
if(codeout & RIGHT)
{
y = y0+(y1-y0)*(xmax-x0)/(x1-x0);
x = xmax;
}
else
{
y = y0+(y1-y0)*(xmin-x0)/(x1-x0);
x = xmin;
}
if(codeout==code1)
{
x0 = x;
y0 = y;
code1 = CompOutCode(x0,y0);
}
else
{
x1 = x;
y1 = y;
code2 = CompOutCode(x1,y1);
}
}
}while(done==FALSE);
if(accept)
line(x0,y0,x1,y1);
outtextxy(150,20,"POLYGON AFTER CLIPPING");
 
rectangle(xmin,ymin,xmax,ymax);
}
outcode CompOutCode(float x,float y)
{
outcode code = 0;
if(y>ymax)
code|=TOP;
else
if(y<ymin)
code|=BOTTOM;
if(x>xmax)
code|=RIGHT;
else
if(x<xmin)
code|=LEFT;
return code;
}
void main( )
{float x1,y1,x2,y2;
int gdriver = DETECT, gmode, n,poly[14],i;
clrscr( );
printf("Enter the no of sides of polygon:");
scanf("%d",&n);
printf("\nEnter the coordinates of polygon\n");
for(i=0;i<2*n;i++)
{scanf("%d",&poly[i]);}
poly[2*n]=poly[0];
poly[2*n+1]=poly[1];
printf("Enter the rectangular coordinates of clipping window\n");
scanf("%f%f%f%f",&xmin,&ymin,&xmax,&ymax);
initgraph(&gdriver, &gmode, "");
 
outtextxy(150,20,"POLYGON BEFORE CLIPPING");
drawpoly(n+1,poly);
rectangle(xmin,ymin,xmax,ymax);
getch( );
cleardevice( );
for(i=0;i<n;i++)
clip(poly[2*i],poly[(2*i)+1],poly[(2*i)+2],poly[(2*i)+3]);
getch( );
restorecrtmode( );
}