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

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]
```