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