C++ Programming Code Examples
C++ > Algorithms Code Examples
Graphic Simulation for Shortest & 2nd shortest path in a Weighted Graph
/* Graphic Simulation for Shortest & 2nd shortest path in a Weighted Graph */
#include<stdio.h>
#include<conio.h>
#include<graphics.h>
#include<dos.h>
float
sum=0,w=0,s,wn,v[8],td=0,e,i,j,n,w1[8],j1[8],arr[8],arr1[8],e1,count,d2,y1
;
float var,a[8][8],d[8],p[8],n1,c,c1,w2;
void main()
{
int gd=DETECT,gm;
clrscr();
void draw(float,float);
void dijkstra(float s,float e,float v1[8],float d1[8],float p1[8],float
a1[8][8],float n);
void ssp();
void path();
void initial();
printf("There are 8 routers in each subnet
");
n=8;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
a[i][j]=32767;
}}
printf("Enter the weight between 0 & 1 : ");
scanf("%f",&a[0][1]);
a[1][0]=a[0][1];
printf("Enter the weight between 0 & 3 : ");
scanf("%f",&a[0][3]);
a[3][0]=a[0][3];
printf("Enter the weight between 1 & 5 : ");
scanf("%f",&a[1][5]);
a[5][1]=a[1][5];
printf("Enter the weight between 1 & 2 : ");
scanf("%f",&a[1][2]);
a[2][1]=a[1][2];
printf("Enter the weight between 2 & 4 : ");
scanf("%f",&a[2][4]);
a[4][2]=a[2][4];
printf("Enter the weight between 2 & 3 : ");
scanf("%f",&a[2][3]);
a[3][2]=a[2][3];
printf("Enter the weight between 3 & 7 : ");
scanf("%f",&a[3][7]);
a[7][3]=a[3][7];
printf("Enter the weight between 4 & 5 : ");
scanf("%f",&a[4][5]);
a[5][4]=a[4][5];
printf("Enter the weight between 4 & 7 : ");
scanf("%f",&a[4][7]);
a[7][4]=a[4][7];
printf("Enter the weight between 5 & 6 : ");
scanf("%f",&a[5][6]);
a[6][5]=a[5][6];
printf("Enter the weight between 6 & 7 : ");
scanf("%f",&a[6][7]);
a[7][6]=a[6][7];
printf("Enter source and destination node from network 1 ");
scanf("%f %f",&s,&e);
clrscr();
initgraph(&gd,&gm,"c:\tc\bgi");
setcolor(WHITE);
fillellipse(20,100,7,7);fillellipse(85,50,7,7);
fillellipse(150,100,7,7);fillellipse(85,150,7,7);
fillellipse(320,100,7,7);fillellipse(385,50,7,7);
fillellipse(450,100,7,7);fillellipse(385,150,7,7);
w1[0]=20;w1[1]=85;w1[2]=150;w1[3]=85;w1[4]=320;
w1[5]=385;w1[6]=450;w1[7]=385;
j1[0]=100;j1[1]=50;j1[2]=100;j1[3]=150;j1[4]=100;j1[5]=50;
j1[6]=100;j1[7]=150;
initial();
setcolor(GREEN);
for(i=0;i<n;i++)
{
v[i]=32767;
d[i]=32767;
p[i]=0;
}
w=s;
d[s]=0;
v[s]=s;
td=0;
dijkstra(s,e,v,d,p,a,n);
path();
c=w1[e];
c1=j1[e];
printf("One more packet ?(Type 1 if yes) ");
scanf("%f",&count);
path();
if(count==1)
ssp();
path();
w=e;
setcolor(GREEN);
count=0;
printf("Enter source and destination node from network 2 ");
scanf("%f %f",&s,&e);
a[0][1]=2;
a[0][3]=6;
a[1][2]=2;
a[1][5]=7;
a[2][3]=1;
a[2][4]=2;
a[4][5]=3;
a[5][6]=3;
a[4][7]=2;
a[6][7]=2;
a[3][7]=4;
a[1][0]=2;
a[3][0]=6;
a[2][1]=2;
a[5][1]=7;
a[3][2]=1;
a[4][2]=2;
a[5][4]=3;
a[6][5]=3;
a[7][4]=2;
a[7][6]=2;
a[7][3]=4;
setcolor(WHITE);
fillellipse(20,400,7,7);fillellipse(85,350,7,7);
fillellipse(150,400,7,7);fillellipse(85,450,7,7);
fillellipse(320,400,7,7);fillellipse(385,350,7,7);
fillellipse(450,400,7,7);fillellipse(385,450,7,7);
w1[0]=20;w1[1]=85;w1[2]=150;w1[3]=85;w1[4]=320;
w1[5]=385;w1[6]=450;w1[7]=385;
j1[0]=400;j1[1]=350;j1[2]=400;j1[3]=450;j1[4]=400;j1[5]=350;
j1[6]=400;j1[7]=450;
initial();
setcolor(GREEN);
for(i=0;i<n;i++)
{
v[i]=32767;
d[i]=32767;
p[i]=0;
}
w=s;
d[s]=0;
v[s]=s;
td=0;
line(c,c1,w1[s],j1[s]);
delay(2000);
dijkstra(s,e,v,d,p,a,n);
path();
if(count==1)
ssp();
path();
getch();
}
void dijkstra(float s,float e,float v1[8],float d1[8],float p1[8],float
a1[8][8],float n)
{
while((p1[e])==0)
{
for(i=0;i<n;i++)
{
if((a1[w][i]+td)<d1[i]&&i!=w&&a1[w][i]!=32767)
{
d1[i]=a1[w][i]+td;
d2=d1[i];
v1[i]=w;
}}
sum=32767;
for(i=0;i<n;i++)
{
if(d1[i]<sum&&i!=s&&p1[i]!=1)
{
sum=d1[i];
wn=i;
}}
p1[wn]=1;
td=d1[wn];
w=wn;
}
}
void draw(float w,float v1)
{
float s,x,y;
s=(j1[v1]-j1[w])/(w1[v1]-w1[w]);
if(s<0)
s=s*-1;
x=w1[w];
y=j1[w];
moveto(x,y);
if(x==w1[v1])
{
while(y!=j1[v1])
{
if(y>j1[v1])
{
line(x,y,x,y-1);
delay(10);
y=y-1;
}
else
{
line(x,y,x,y+1);
delay(10);
y=y+1;
}}}
if(y==j1[v1])
{
while(x!=w1[v1])
{
if(x>w1[v1])
{
line(x,y,x-1,y);
delay(10);
x=x-1;
}
else
{
line(x,y,x+1,y);
delay(10);
x=x+1;
}}}
if(x<w1[v1]&&y<j1[v1])
{
while(x!=w1[v1])
{
line(x,y,x+1,y+s);
delay(10);
x=x+1;
y=y+s;
}}
if(x>w1[v1]&&y>j1[v1])
{
while(x!=w1[v1])
{
line(x,y,x-1,y-s);
delay(10);
x=x-1;
y=y-s;
i=i+1;
}}
if(x>w1[v1]&&y<j1[v1])
{
while(x!=w1[v1])
{
line(x,y,x-1,y+s);
delay(10);
x=x-1;
y=y+s;
i=i+1;
}}
if(x<w1[v1]&&y>j1[v1])
{
while(x!=w1[v1])
{
line(x,y,x+1,y-s);
delay(10);
x=x+1;
y=y-s;
i=i+1;
}
}}
void ssp()
{
d2=y1=32767;
setcolor(RED);
e1=e;
for(i=0;i<n;i++)
{
arr1[i]=v[i];
arr[i]=v[i];
}
while(e1!=s)
{
var=a[e1][arr1[e1]]=a[arr1[e1]][e1];
a[e1][arr1[e1]]=a[arr1[e1]][e1]=32767;
for(i=0;i<n;i++)
{
v[i]=32767;
d[i]=32767;
p[i]=0;
}
w=s;d[s]=0;
v[s]=s;
td=0;
dijkstra(s,e,v,d,p,a,n);
if(d2<y1)
{
y1=d2;
for(i=0;i<n;i++)
arr[i]=v[i];
}
a[e1][arr1[e1]]=a[arr1[e1]][e1]=var;
e1=arr1[e1];
}}
void path()
{
while(w!=s)
{
if(count==0)
{
draw(w,v[w]);
w=v[w];
}
else
{
draw(w,arr[w]);
w=arr[w];
}}}
void initial()
{
line(w1[0],j1[0],w1[1],j1[1]);
line(w1[0],j1[0],w1[3],j1[3]);
line(w1[1],j1[1],w1[5],j1[5]);
line(w1[1],j1[1],w1[2],j1[2]);
line(w1[2],j1[2],w1[4],j1[4]);
line(w1[2],j1[2],w1[3],j1[3]);
line(w1[3],j1[3],w1[7],j1[7]);
line(w1[4],j1[4],w1[5],j1[5]);
line(w1[4],j1[4],w1[7],j1[7]);
line(w1[5],j1[5],w1[6],j1[6]);
line(w1[6],j1[6],w1[7],j1[7]);
}
To create a program in Graphics Mode, the first step would be to include the header file graphics.h. This file is required for Graphics programming. After this, the graphics have to be initialized. C Language supports 16 Bit's MS-DOS environment. Initializing the Graphics mode is to call various functions, one such is called initgraph. initgraph initializes the graphics system by loading a graphics driver from disk (or validating a registered driver), and putting the system into graphics mode. To start the graphics system, first call the initgraph function. initgraph loads the graphics driver and puts the system into graphics mode. You can tell initgraph to use a particular graphics driver and mode, or to autodetect the attached video adapter at run time and pick the corresponding driver. If you tell initgraph to autodetect, it calls detectgraph to select a graphics driver and mode. initgraph also resets all graphics settings to their defaults (current position, palette, color, viewport, and so on)
#include is a way of including a standard or user-defined file in the program and is mostly written at the beginning of any C/C++ program. This directive is read by the preprocessor and orders it to insert the content of a user-defined or system header file into the following program. These files are mainly imported from an outside source into the current program. The process of importing such files that might be system-defined or user-defined is known as File Inclusion. This type of preprocessor directive tells the compiler to include a file in the source code program.
C supports nesting of loops in C. Nesting of loops is the feature in C that allows the looping of statements inside another loop. Any number of loops can be defined inside another loop, i.e., there is no restriction for defining any number of loops. The nesting level can be defined at n times. You can define any type of loop inside another loop; for example, you can define 'while' loop inside a 'for' loop. A loop inside another loop is called a nested loop. The depth of nested loop depends on the complexity of a problem. We can have any number of nested loops as required. Consider a nested loop where the outer loop runs n times and consists of another loop inside it. The inner loop runs m times. Then, the total number of times the inner loop runs during the program execution is n*m.
It is a predefined function in "conio.h" (console input output header file) used to clear the console screen. It is a predefined function, by using this function we can clear the data from console (Monitor). Using of clrscr() is always optional but it should be place after variable or function declaration only. It is often used at the beginning of the program (mostly after variable declaration but not necessarily) so that the console is clear for our output.
A program shall contain a global function named main, which is the designated start of the program in hosted environment. main() function is the entry point of any C++ program. It is the point at which execution of program is started. When a C++ program is executed, the execution control goes directly to the main() function. Every C++ program have a main() function.
The header file graphics.h contains line() function which is used to draw a line from a point(x1, y1) to point(x2, y2) i.e. (x1, y1) and (x2, y2) are end points of the line. The function line() draws a line on the graphics screen between two specified points. So this function requires four parameters namely x1, y1, x2, and y2 to represent two points. This function draws a line from (x1, y1) coordinates to (x2, y2) coordinates on the graphics screen.
Logical Operators are used to compare and connect two or more expressions or variables, such that the value of the expression is completely dependent on the original expression or value or variable. We use logical operators to check whether an expression is true or false. If the expression is true, it returns 1 whereas if the expression is false, it returns 0. Assume variable A holds 1 and variable B holds 0:
An array is a collection of data items, all of the same type, accessed using a common name. A one-dimensional array is like a list; A two dimensional array is like a table; The C++ language places no limits on the number of dimensions in an array, though specific implementations may. Some texts refer to one-dimensional arrays as vectors, two-dimensional arrays as matrices, and use the general term arrays when the number of dimensions is unspecified or unimportant. (2D) array in C++ programming is also known as matrix. A matrix can be represented as a table of rows and columns. In C/C++, we can define multi dimensional arrays in simple words as array of arrays. Data in multi dimensional arrays are stored in tabular form (in row major order).
In computer programming, we use the if statement to run a block code only when a certain condition is met. An if statement can be followed by an optional else statement, which executes when the boolean expression is false. There are three forms of if...else statements in C++: • if statement, • if...else statement, • if...else if...else statement, The if statement evaluates the condition inside the parentheses ( ). If the condition evaluates to true, the code inside the body of if is executed. If the condition evaluates to false, the code inside the body of if is skipped.
Draws an ellipse using (x,y) as a center point and xradius and yradius as the horizontal and vertical axes, and fills it with the current fill color and fill pattern. The header file graphics.h contains fillellipse() function which draws and fills an ellipse with center at (x, y) and (xradius, yradius) as x and y radius of ellipse. Where, (x, y) is center of the ellipse. (xradius, yradius) are x and y radius of ellipse.
In while loop, condition is evaluated first and if it returns true then the statements inside while loop execute, this happens repeatedly until the condition returns false. When condition returns false, the control comes out of loop and jumps to the next statement in the program after while loop. The important point to note when using while loop is that we need to use increment or decrement statement inside while loop so that the loop variable gets changed on each iteration, and at some point condition returns false. This way we can end the execution of while loop otherwise the loop would execute indefinitely. A while loop that never stops is said to be the infinite while loop, when we give the condition in such a way so that it never returns false, then the loops becomes infinite and repeats itself indefinitely.
delay() function is used to hold the program's execution for given number of milliseconds, it is declared in dos.h header file. There can be many instances when we need to create a delay in our programs. C++ provides us with an easy way to do so. We can use a delay() function for this purpose in our code. We can run the code after a specific time in C++ using delay() function.
Function moves the current position(cp) to (x,y). The header file graphics.h contains moveto() function which changes the current position to (x, y). Means if you want to move a point from the current position to a new position then you can use this function. outtext is the function used to display the given string on graphics mode. It uses the font style set by settextstyle and the current position. The current position can be changed with moveto function. Alternatively you can use outtextxy function which takes xpos, ypos and string for displaying at a particular location. outtextxy does the work of both moveto and outtext functions.
In computer programming, loops are used to repeat a block of code. For example, when you are displaying number from 1 to 100 you may want set the value of a variable to 1 and display it 100 times, increasing its value by 1 on each loop iteration. When you know exactly how many times you want to loop through a block of code, use the for loop instead of a while loop. A for loop is a repetition control structure that allows you to efficiently write a loop that needs to execute a specific number of times.
The getch() is a predefined non-standard function that is defined in conio.h header file. It is mostly used by the Dev C/C++, MS- DOS's compilers like Turbo C to hold the screen until the user passes a single value to exit from the console screen. It can also be used to read a single byte character or string from the keyboard and then print. It does not hold any parameters. It has no buffer area to store the input character in a program. The getch() function does not accept any parameter from the user. It returns the ASCII value of the key pressed by the user as an input.
setcolor() function is used to set the foreground color in graphics mode. After resetting the foreground color you will get the text or any other shape which you want to draw in that color. setcolor sets the current drawing color to color, which can range from 0 to getmaxcolor. The current drawing color is the value to which pixels are set when lines, and so on are drawn. The drawing colors shown below are available for the CGA and EGA, respectively.
Insertion sort algorithm sort data by inserting them one by one into the List. This algorithm is based on sorting playing cards by picking & inserting them one by one. Here we take data
This algorithm takes the input of the number of 'Vertexes' and their corresponding degree. Checks various 'constraints', tries to build the graph. If it fails, no valid graph can be created
Check if this graph is Eulerian or not. Check if all non-zero degree vertices are connected. If graph has no "odd degree vertex", there is at least one Eulerian Circuit. And if graph as two
Program to implement "Jarvis March" to find convex hull. The idea of Jarvis's Algorithm is simple, we start from the 'leftmost point' (or point with minimum x coordinate value) and
To convert binary to hexadecimal in C++, you have to ask to the user to "enter any number" in binary to convert it into hexadecimal, then display the equivalent hexadecimal value on
