C++ Programming Tutorial

 
 
 
 
 # include <iostream.h>
 # include <graphics.h>
 # include   <string.h>
 # include   <stdlib.h>
 # include    <conio.h>
 # include     <math.h>


 //---------------------------  User-Defined  ----------------------------//


 # include \"Mouse.h\" // Included in source zip file
 # include \"Input.h\" // Included in source zip file

 # define MAX_VERTICES  10
 # define MAX_EDGES     15


 //-------------------------------  Vertex  ------------------------------//


 class Vertex
 {
    public:
       int x;
       int y;
       int label;

    private:
       char Label[5];

    public:
       Vertex( )   {  }
       ~Vertex( )  {  }

       void SetVertex(const int,const int,const int);
       void ShowVertex( );

       const int Hit( );
 };


 //-------------------------------  Edge  --------------------------------//


 class Edge
 {
    public:
       int weight;

       Vertex V1;
       Vertex V2;

    private:
       char Weight[5];

    public:
       Edge( )   { }
       ~Edge( )  { }

       void SetEdge(const Vertex,const Vertex,const int);
       void ShowEdge( );
 };



 //----------------------------  SetVertex( )  ---------------------------//


 void Vertex::SetVertex(const int _x,const int _y,const int _label)
 {
    x=_x;
    y=_y;
    label=_label;

    itoa((label+1),Label,10);
 }


 //----------------------------  ShowVertex( )  --------------------------//


 void Vertex::ShowVertex( )
 {
    HideMouseCursor( );

    setcolor(1);
    setfillstyle(1,1);
      pieslice(x,y,0,360,10);

    setcolor(9);
      circle(x,y,10);
      circle(x,y,11);

    setcolor(15);
    settextstyle(2,0,4);

    if(label<9)
       outtextxy((x-2),(y-6),Label);

    else if(label>=9)
       outtextxy((x-5),(y-6),Label);

    ShowMouseCursor( );
 }


 //--------------------------------  Hit( )  -----------------------------//


 const int Vertex::Hit( )
 {
    int _x=0;
    int _y=0;

    GetMousePosition(&_x,&_y);

    if(_x>=(x-10) && _x<=(x+10) && _y>=(y-10) && _y<=(y+10))
    {
       double d=sqrt(( powl((_x-x),2) + pow((_y-y),2) ));

       if(d<=10)
      return 1;
    }

    return 0;
 }


 //-----------------------------  SetEdge( )  ----------------------------//


 void Edge::SetEdge(const Vertex _V1,const Vertex _V2,const int _weight)
 {
    V1=_V1;
    V2=_V2;

    weight=_weight;

    itoa(weight,Weight,10);
 }


 //----------------------------  ShowEdge( )  ----------------------------//


 void Edge::ShowEdge( )
 {
    HideMouseCursor( );

    setlinestyle(0,0,3);

    setcolor(1);
      line(V1.x,V1.y,V2.x,V2.y);

    setlinestyle(0,0,0);

    V1.ShowVertex( );
    V2.ShowVertex( );

    int x=(((V1.x+V2.x)/2)-6);
    int y=(((V1.y+V2.y)/2)-8);

    setcolor(11);
    settextstyle(2,0,7);
      outtextxy(x,y,Weight);
      outtextxy((x+1),y,Weight);
      outtextxy((x+1),(y+1),Weight);

    ShowMouseCursor( );
 }



 //----------------------------  PrintText( )  ---------------------------//


 void PrintText(const int x,const int y,const int number,const int color=15)
 {
    char Number[10]={NULL};

    itoa(number,Number,10);

    moveto(x,y);

    setcolor(color);
    settextstyle(2,0,4);
      outtext(Number);
 }


 int main( )
 {
    int driver=VGA;
    int mode=VGAHI;
    int error_code;

    initgraph(&driver,&mode,\"..\\\\Bgi\");

    error_code=graphresult( );

    if(error_code!=grOk)
    {
       restorecrtmode( );
       textmode(BW80);
       clrscr( );

       cout<<\" \\n Fatal Error  : Graphic Driver not initialized\"<<endl;
       cout<<\" Error Reason : \"<<grapherrormsg(error_code)<<endl;
       cout<<\" \\n Press any key to exit...\";

       getch( );
       exit(1);
    }

    cleardevice( );

    setcolor(15);
      rectangle(5,5,635,32);
      rectangle(5,35,635,455);
      rectangle(5,458,635,476);

    setfillstyle(1,7);
      bar(6,6,634,31);

    setfillstyle(1,8);
      bar(6,459,634,475);
      bar(23,80,180,83);

    settextstyle(2,0,7);
      setcolor( 9);
    outtextxy(119,6,\"*****  Kruskal\'s Algorithm  *****\");
    outtextxy(120,6,\"*****  Kruskal\'s Algorithm  *****\");
    outtextxy(120,7,\"*****  Kruskal\'s Algorithm  *****\");

      setcolor(11);
    outtextxy(24,60,\"Prerequisites:\");
    outtextxy(25,60,\"Prerequisites:\");
    outtextxy(25,61,\"Prerequisites:\");

    int vertices=0;
    int edges=0;

    setcolor(15);
    settextstyle(2,0,4);
      outtextxy(25,96,\"Enter the Total Number of Vertices ( 1-10 ) = \");

    vertices=atoi(GetInput(295,95,2,15,0));

    vertices=((vertices<1)?1:vertices);
    vertices=((vertices>10)?10:vertices);

    setcolor(15);
    settextstyle(2,0,4);
      outtextxy(25,115,\"Enter the Total Number of Edges ( 1-15 ) = \");

    edges=atoi(GetInput(295,114,2,15,0));

    edges=((edges<0)?0:edges);
    edges=((edges>15)?15:edges);

    setfillstyle(1,8);
      bar(23,380,115,383);

    setcolor(11);
    settextstyle(2,0,7);
      outtextxy(24,360,\"Read Me:\");
      outtextxy(25,360,\"Read Me:\");
      outtextxy(25,361,\"Read Me:\");

    setcolor(15);
    settextstyle(2,0,4);
      outtextxy(25,390,\"* Press LeftMouseKey where you want to place a Vertex.\");
      outtextxy(25,405,\"* To draw an Edge, Click on a Vertex and Drag the Mouse Pointer to the other Vertex and Release the\");
      outtextxy(25,418,\"  LeftMouseKey, then enter the Weight of the Edge.\");

    setcolor(14);
    settextstyle(2,0,4);
      outtextxy(15,461,\"Press any Key to Continue...\");

    getch( );

    setfillstyle(0,1);
      bar(6,36,634,454);

    setfillstyle(1,8);
      bar(6,459,634,475);

    setcolor(14);
    settextstyle(2,0,4);
      outtextxy(15,461,\"Mark the Vertices Positions...\");

    Vertex  V[MAX_VERTICES];
    Edge    E[MAX_EDGES];

    InitMouse( );
    ShowMouseCursor( );
    SetMousePosition(320,240);
    SetMouseRange(20,50,620,440);

    int x;
    int y;

    for(int count=0;count<vertices;count++)
    {
       while(!LeftMouseKeyPressed( ));

       GetMousePosition(&x,&y);

       while(LeftMouseKeyPressed( ));

       HideMouseCursor( );

       V[count].SetVertex(x,y,count);
       V[count].ShowVertex( );

       ShowMouseCursor( );
    }

    HideMouseCursor( );

    setfillstyle(1,8);
      bar(6,459,634,475);

    setcolor(14);
    settextstyle(2,0,4);
      outtextxy(15,461,\"Draw the Edges and enter their weights.\");

    ShowMouseCursor( );

    int i;
    int j;
    int flag=0;
    int weight;

    for(count=0;count<edges;)
    {
       flag=0;

       do
       {
      while(!LeftMouseKeyPressed( ));

      for(i=0;i<vertices;i++)
      {
         if(V[i].Hit( ) && LeftMouseKeyPressed( ))
         {
        GetMousePosition(&x,&y);

        HideMouseCursor( );

        setcolor(11);
          circle(V[i].x,V[i].y,10);

        ShowMouseCursor( );

        flag=1;
        break;
         }
      }

      if(flag)break;
       }
       while(1);

       setwritemode(1);
       setcolor(11);

       int x_end=x;
       int y_end=y;
       int prev_x=x;
       int prev_y=y;

       while(LeftMouseKeyPressed( ))
       {
      GetMousePosition(&x_end,&y_end);

      if(x_end!=prev_x || y_end!=prev_y)
      {
         HideMouseCursor( );

         line(x,y,prev_x,prev_y);
         line(x,y,x_end,y_end);

         ShowMouseCursor( );

         prev_x=x_end;
         prev_y=y_end;
      }
       }

       flag=0;

       for(j=0;j<vertices;j++)
       {
      if(V[j].Hit( ) && j!=i)
      {
         HideMouseCursor( );

         setcolor(11);
           circle(V[j].x,V[j].y,10);

         ShowMouseCursor( );

         flag=1;
         break;
      }
       }

       if(flag)
       {
      for(int k=0;k<count;k++)
      {
         if((E[k].V1.label==i && E[k].V2.label==j) ||
                      (E[k].V2.label==i && E[k].V1.label==j))
         {
        flag=0;
        break;
         }
      }
       }

       setwritemode(0);

       HideMouseCursor( );

       if(flag)
       {
      line(x,y,x_end,y_end);

      setfillstyle(1,8);
        bar(6,459,634,475);

      setcolor(15);
      settextstyle(2,0,4);
        outtextxy(15,461,\"Enter the Edge Weight = \");

      weight=atoi(GetInput(145,460,3,15,8));

      setfillstyle(1,8);
        bar(6,459,634,475);

      if(count<(edges-1))
      {
         setcolor(14);
         settextstyle(2,0,4);
           outtextxy(15,461,\"Draw the Edges and enter their weights.\");
      }

      weight=((weight<=0)?0:weight);

      E[count].SetEdge(V[i],V[j],weight);
      count++;
       }

       setfillstyle(0,1);
     bar(6,36,634,454);

       ShowMouseCursor( );

       for(i=0;i<vertices;i++)
      V[i].ShowVertex( );

       for(i=0;i<count;i++)
      E[i].ShowEdge( );
    }

    HideMouseCursor( );

    setfillstyle(1,8);
      bar(6,459,634,475);

    setcolor(14);
    settextstyle(2,0,4);
      outtextxy(15,461,\"Press any Key to apply Kruskal\'s Algorithm...\");

    getch( );

    setfillstyle(0,1);
      bar(6,36,634,454);

    setfillstyle(1,8);
      bar(6,459,634,475);

    setcolor(15);
    settextstyle(2,0,4);
      outtextxy(15,461,\"Applying Kruskals\'s Algorithm...\");

    ShowMouseCursor( );

    for(count=0;count<vertices;count++)
       V[count].ShowVertex( );

    for(i=0;i<edges;i++)
    {
       for(int j=0;j<(edges-1);j++)
       {
      if(E[j].weight>=E[(j+1)].weight)
      {
         Edge Temp;

         Temp=E[j];
         E[j]=E[(j+1)];
         E[(j+1)]=Temp;
      }
       }
    }

    int e_count=0;
    int cycle_flag=0;

    Edge _E[MAX_EDGES];

    int mst[MAX_VERTICES][MAX_VERTICES]={0};

    for(i=0;i<=vertices;i++)
    {
       mst[i][0]=i;

       for(int j=1;j<vertices;j++)
      mst[i][j]=-1;
    }

    for(count=0;count<edges;count++)
    {
       cycle_flag=0;

       for(i=1;i<vertices;i++)
       {
      if(mst[E[count].V1.label][i]==E[count].V2.label ||
                   mst[E[count].V2.label][i]==E[count].V1.label)
         cycle_flag=1;
       }

       if(!cycle_flag)
       {
      _E[e_count]=E[count];
      _E[e_count].ShowEdge( );

      e_count++;

      for(i=1;i<vertices;i++)
      {
         if(mst[E[count].V1.label][i]==E[count].V2.label)
        break;

         if(mst[E[count].V1.label][i]==-1)
         {
        mst[E[count].V1.label][i]=E[count].V2.label;

        break;
         }
      }

      for(i=1;i<vertices;i++)
      {
         if(mst[E[count].V2.label][i]==E[count].V1.label)
        break;

         if(mst[E[count].V2.label][i]==-1)
         {
        mst[E[count].V2.label][i]=E[count].V1.label;

        break;
         }
      }

      for(i=0;i<vertices;i++)
      {
         for(int j=0;j<vertices;j++)
         {
        for(int k=1;k<vertices;k++)
        {
           if(mst[j][k]!=-1)
           {
              for(int l=1;l<vertices;l++)
              {
             if(mst[mst[j][k]][l]!=-1)
             {
                for(int m=0;m<vertices;m++)
                {
                   if(mst[mst[j][k]][l]==mst[j][m])
                  break;

                   if(mst[j][m]==-1)
                   {
                  mst[j][m]=mst[mst[j][k]][l];

                  break;
                   }
                }
             }
              }
           }
        }
         }
      }

      HideMouseCursor( );

      settextstyle(2,0,4);

      do
      {
         setcolor(14);
           outtextxy(530,461,\"Press any Key...\");

         delay(250);

         setcolor(8);
           outtextxy(530,461,\"Press any Key...\");

         delay(250);
      }
      while(!kbhit( ));

      getch( );

      setfillstyle(1,8);
        bar(500,459,634,475);

      ShowMouseCursor( );
       }
    }

    HideMouseCursor( );

    setfillstyle(0,1);
      bar(6,36,634,454);

    setfillstyle(1,8);
      bar(6,459,634,475);
      bar(23,80,90,83);
      bar(23,230,122,233);

    setcolor(11);
    settextstyle(2,0,7);
      outtextxy(24,60,\"Given:\");
      outtextxy(25,60,\"Given:\");
      outtextxy(25,61,\"Given:\");

      outtextxy(24,210,\"Solution:\");
      outtextxy(25,210,\"Solution:\");
      outtextxy(25,211,\"Solution:\");

    setcolor(15);
    settextstyle(2,0,4);
      moveto(50,98);
    outtext(\"V = {\");

    for(count=0;count<vertices;count++)
    {
       PrintText((getx( )+3),gety( ),(count+1));

       if(count<(vertices-1))
       {
      moveto((getx( )+3),gety( ));
        outtext(\",\");
       }
    }

    moveto((getx( )+4),gety( ));
      outtext(\"}\");

    moveto(50,117);
      outtext(\"E = {\");

    for(count=0;count<edges;count++)
    {
       if(count==7 || count==14)
      moveto(83,(gety( )+15));

       else
      moveto((getx( )+3),gety( ));

       outtext(\"(\");

       PrintText((getx( )+2),gety( ),(E[count].V1.label+1));

       moveto((getx( )+2),gety( ));
     outtext(\",\");

       PrintText((getx( )+2),gety( ),(E[count].V2.label+1));

       moveto((getx( )+2),gety( ));
     outtext(\",\");

       PrintText((getx( )+2),gety( ),E[count].weight,14);

       setcolor(15);

       moveto((getx( )+2),gety( ));
     outtext(\")\");

       if(count<(edges-1))
       {
      moveto((getx( )+3),gety( ));
        outtext(\",\");
       }
    }

    moveto((getx( )+4),gety( ));
      outtext(\"}\");

    moveto(50,248);
      outtext(\"E = {\");

    for(count=0;count<e_count;count++)
    {
       if(e_count==7 || e_count==14)
      moveto(83,(gety( )+15));

       else
      moveto((getx( )+3),gety( ));

       outtext(\"(\");

       PrintText((getx( )+2),gety( ),(_E[count].V1.label+1));

       moveto((getx( )+2),gety( ));
     outtext(\",\");

       PrintText((getx( )+2),gety( ),(_E[count].V2.label+1));

       moveto((getx( )+2),gety( ));
     outtext(\",\");

       PrintText((getx( )+2),gety( ),_E[count].weight,14);

       setcolor(15);

       moveto((getx( )+2),gety( ));
     outtext(\")\");

       if(count<(e_count-1))
       {
      moveto((getx( )+3),gety( ));
        outtext(\",\");
       }
    }

    moveto((getx( )+4),gety( ));
      outtext(\"}\");

    moveto(50,267);
      outtext(\"Cost = \");

    int cost=0;

    for(count=0;count<e_count;count++)
    {
       cost+=_E[count].weight;

       PrintText((getx( )+3),gety( ),_E[count].weight);

       if(count<(e_count-1))
       {
      moveto((getx( )+3),gety( ));
        outtext(\"+\");
       }
    }

    moveto((getx( )+5),gety( ));
      outtext(\"=\");

    PrintText((getx( )+5),gety( ),cost);

    setcolor(14);
    settextstyle(2,0,4);
      outtextxy(15,461,\"Press any Key to Exit.\");

    getch( );
    closegraph( );
    return 0;
 }
[/Code]