Program to implement the Prims Algorithm to solve Minimum Spanning Tree Problem (MST) using Graphics and with Mouse support

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

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

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



 //-------------------  Class Function Definitions  ----------------------//




 //----------------------------  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)
 {
    char Number[10]={NULL};

    itoa(number,Number,10);

    moveto(x,y);

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



 //------------------------------  main( )  ------------------------------//



 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(139,6,\"*****  Prim\'s Algorithm  *****\");
    outtextxy(140,6,\"*****  Prim\'s Algorithm  *****\");
    outtextxy(140,7,\"*****  Prim\'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 Prim\'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 Prim\'s Algorithm...\");

    ShowMouseCursor( );

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

    int U[MAX_VERTICES];
    int vertex_1[MAX_VERTICES];
    int vertex_2[MAX_VERTICES];
    int edge_weights[MAX_VERTICES];
    int resultant_weights[MAX_VERTICES];

    int flag_1=0;
    int flag_2=0;
    int u_count=1;
    int temp_vertex=0;
    int temp_vertex_1=0;
    int temp_vertex_2=0;
    int lowest_edge_weight=0;

    U[0]=0;

    do
    {
       count=0;

       for(int i=0;i<vertices;i++)
       {
      vertex_1[i]=0;
      vertex_2[i]=0;
      edge_weights[i]=0;
       }

       for(i=0;i<u_count;i++)
       {
      flag_1=0;

      for(int j=0;j<edges;j++)
      {
         if(E[j].V1.label==U[i] || E[j].V2.label==U[i])
         {
        flag_2=0;

        if(E[j].V1.label!=U[i])
        {
           temp_vertex=E[j].V1.label;
           temp_vertex_1=E[j].V2.label;
        }

        else
        {
           temp_vertex=E[j].V2.label;
           temp_vertex_1=E[j].V1.label;
        }

        for(int k=0;k<u_count;k++)
        {
           if(temp_vertex==U[k])
           {
              flag_2=-1;

              break;
           }
        }

        if(flag_2!=-1)
        {
           if(flag_1==0 || lowest_edge_weight>E[j].weight)
           {
              lowest_edge_weight=E[j].weight;
              temp_vertex_2=temp_vertex;
              flag_1=1;
           }
        }
         }
      }

      if(flag_1==1)
      {
         vertex_2[count]=temp_vertex_2;
         vertex_1[count]=temp_vertex_1;
         edge_weights[count]=lowest_edge_weight;

         count++;
      }
       }

       flag_1=0;

       for(i=0;i<count;i++)
       {
      if(flag_1==0 || lowest_edge_weight>edge_weights[i])
      {
         lowest_edge_weight=edge_weights[i];
         temp_vertex_1=vertex_1[i];
         temp_vertex_2=vertex_2[i];
         flag_1=1;
      }
       }

       if(flag_1==1)
       {
      U[u_count]=temp_vertex_2;
      u_count++;

      for(i=0;i<edges;i++)
      {
         if((E[i].V1.label==temp_vertex_1
                    && E[i].V2.label==temp_vertex_2) ||
        (E[i].V1.label==temp_vertex_2
                    && E[i].V2.label==temp_vertex_1) )
         {
        E[i].ShowEdge( );
        resultant_weights[(u_count-2)]=E[i].weight;

        settextstyle(2,0,4);

        HideMouseCursor( );

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

        break;
         }
      }
       }

       else
      break;
    }
    while(1);

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

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

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

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

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

    for(count=0;count<u_count;count++)
    {
       PrintText((getx( )+3),gety( ),(U[count]+1));

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

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

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

    int cost=0;

    for(count=0;count<(u_count-1);count++)
    {
       cost+=resultant_weights[count];

       PrintText((getx( )+3),gety( ),resultant_weights[count]);

       if(count<(u_count-2))
       {
      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]