Your program should take one of the following four commands from the standard in

Question

Your program should take one of the following four commands from the standard input, and execute corresponding functions. • S • R • W • P s t On reading S, the program stops. On reading R, the program reads in an edge weighted directed graph from file GRAPHinput.txt to build the adjacency lists, and waits for the next command. The file GRAPHinput.txt is a text file. The first line of the file contains two integers n and m, which indicates the number of vertices and the number of edges on the graph, respectively. It is followed by m lines, where each line contains three integers: u, v, and w. These three integers indicate the information of an edge: there is an edge pointing from u to v, with weight w. Please note that the vertices of the graph are indexed from 1 to n (not from 0 to n 1). On reading W, the program writes the graph information to the screen, and waits for the next command. The screen output format of W is as follows: The first line should contain two integers, n and m, where n is the number of vertices and m is the number of edges. It should be followed by n lines, where each of these n lines has the following format: u : (v1 w1) (v2 w2) ... (vx, wx) 1 On reading P s t, the program runs Dijkstra’s shortest path algorithm to compute a shortest s-t path, and prints out the shortest path information from s to t to the screen, and waits for the next command. The screen output format of P s t is as follows: There are two lines. The first line contains an integer dist, which is the length of the shortest path computed. The next line contains the indexes of all vertices along the path direction, starting from src and ending with dest, in format of: s v1 v2 ... t Please note that your program should read in only one graph, but may be asked to compute s-t shortest paths for different pairs of s and t. Therefore, during the computation of the s-t shortest path, your program should not modify the given graph. You should use modular design. At the minimum, you should have • the main program as main.cpp and the corresponding main.h; • the heap functions heap.cpp and the corresponding heap.h; • the graph functions graph.cpp and the corresponding graph.h; • various utility functions util.cpp and the corresponding util.h. You should also provide a Makefile which compile the files into an executable file named run. Grading policies: (Sample test cases will be posted soon.) (10 pts) Documentation: You should provide sufficient comment about the variables and algorithms. (10 pts) Makefile (10 pts) Modular Design (10 pts) Graph I/O (20 pts) Shortest Path Length (20 pts) Shortest Path Path Above all, you need to write a working program to correctly parse the commands specified in the project. Without this, your program will not be graded.

Explanation / Answer

int main()
{
FILE *file_pointer, *ft;
   int n=5,m=5;   //Giving Initial Values
char next, option;
file_pointer=fopen("input.dat","rb+");

if (file_pointer == NULL) {
file_pointer = fopen("input.dat","wb+");

if (file_pointer==NULL)
{
puts("Cannot open file");
return 0;
}
}
   while(1) {
system("cls");

printf( " ====== S R W P ======");
printf( " S. Stop the Program");
printf( " R. Read Graph");
printf( " W. Write Graph");
printf( " P. Print Dijkstra");
cout<<" ======================");
printf( " ");
printf( " Select Your option ::");
fflush(stdin);
option = getche();
   int arr[][]=new int [n][m];       //Read n and m values from file! First Line
switch(option)
{
case 'W' :
       printf("Displaying Your Array");
for(int i=0;i<n;i++)
               for(int j=0;j<m;j++)
                   {
                       printf(arr[i][j]);
                   }
break;
case 'R':
system("cls");
rewind(file_pointer);
printf( "=== Read the Graph ===";
printf( " ";
       size_t len = 0;
           ssize_t read;

while ((read = getline(&line, &len, file_pointer)) != -1) {
  
               char** tokens = str_split(line, ',');

  
               int u = *(tokens+0) -'a';
               int v = *(tokens+1) -'a';
               int w = *(tokens+2) -'a';
               arr[u][v]=w;
   }
}
printf( " ";
system("pause");
break;

case 'P' :
system("cls");
next = 'Y';
       printf(" Enter the starting node:: ");
           scanf("%d", &u);
my_Dij_Func(arr,n,u);
break;
      
       case 'S':
fclose(file_pointer);
printf( " ";
printf( " STOPPING. EXITING. Thanks!";
printf( " ";
exit(0);
}
}

}

void my_Dij_Func(int G[MAX][MAX], int n, int initial)
{
   int value[MAX][MAX], dist[MAX], pred[MAX];
   int touched[MAX], count, mindistance, next, i,j;
   for(i=0;i < n;i++)
       for(j=0;j < n;j++)
           if(G[i][j]==0)
               value[i][j]=INFINITY;
           else
               value[i][j]=G[i][j];
  
   for(i=0;i< n;i++)
   {
       dist[i]=value[initial][i];
       pred[i]=initial;
       touched[i]=0;
   }
   dist[initial]=0;
   touched[initial]=1;
   count=1;
   while(count < n-1){
       mindistance=INFINITY;
       for(i=0;i < n;i++)
           if(dist[i] < mindistance&&!touched[i])
           {
               mindistance=dist[i];
               next=i;
           }
       touched[next]=1;
       for(i=0;i < n;i++)
           if(!touched[i])
               if(mindistance+value[next][i] < dist[i])
               {
                   dist[i]=mindistance+value[next][i];
                   pred[i]=next;
               }
           count++;
   }

   for(i=0;i < n;i++)
       if(i!=initial)
       {
           printf(" Distance of %d = %d", i, dist[i]);
           printf(" Path = %d", i);
           j=i;
           do
           {
               j=pred[j];
               printf(" <-%d", j);
           }
           while(j!=initial);
       }
}

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.