Expected input Expected output Your program should take one of the following fou

Question

Expected input

Expected output

Your program should take one of the following four commands from the standard input, and execute corresponding functions. 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 ma, 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) (var, wz)

Explanation / Answer

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include<iostream>
#include<stdio.h>
using namespace std;

// A structure to represent a node in adjacency list
struct AdjListNode
{
    int dest;
    int weight;
    struct AdjListNode* next;
};

// A structure to represent an adjacency liat
struct AdjList
{
    struct AdjListNode *head; // pointer to head node of list
};

// A structure to represent a graph. A graph is an array of adjacency lists.
// Size of array will be V (number of vertices in graph)
struct Graph
{
    int V;
    struct AdjList* array;
};

// A utility function to create a new adjacency list node
struct AdjListNode* newAdjListNode(int dest, int weight)
{
    struct AdjListNode* newNode =
            (struct AdjListNode*) malloc(sizeof(struct AdjListNode));
    newNode->dest = dest;
    newNode->weight = weight;
    newNode->next = NULL;
    return newNode;
}

// A utility function that creates a graph of V vertices
struct Graph* createGraph(int V)
{
    struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
    graph->V = V+1;

    // Create an array of adjacency lists. Size of array will be V
    graph->array = (struct AdjList*) malloc((V+1) * sizeof(struct AdjList));

     // Initialize each adjacency list as empty by making head as NULL
    for (int i = 0; i <= V; ++i)
        graph->array[i].head = NULL;

    return graph;
}

// Adds an edge to an directed graph
void addEdge(struct Graph* graph, int src, int dest, int weight)
{
    // Add an edge from src to dest. A new node is added to the adjacency
    // list of src. The node is added at the begining
    struct AdjListNode* newNode = newAdjListNode(dest, weight);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;
}

// Structure to represent a min heap node
struct MinHeapNode
{
    int v;
    int dist;
};

// Structure to represent a min heap
struct MinHeap
{
    int size;      // Number of heap nodes present currently
    int capacity; // Capacity of min heap
    int *pos;     // This is needed for decreaseKey()
    struct MinHeapNode **array;
};

// A utility function to create a new Min Heap Node
struct MinHeapNode* newMinHeapNode(int v, int dist)
{
    struct MinHeapNode* minHeapNode =
           (struct MinHeapNode*) malloc(sizeof(struct MinHeapNode));
    minHeapNode->v = v;
    minHeapNode->dist = dist;
    return minHeapNode;
}

// A utility function to create a Min Heap
struct MinHeap* createMinHeap(int capacity)
{
    struct MinHeap* minHeap =
         (struct MinHeap*) malloc(sizeof(struct MinHeap));
    minHeap->pos = (int *)malloc(capacity * sizeof(int));
    minHeap->size = 0;
    minHeap->capacity = capacity;
    minHeap->array =
         (struct MinHeapNode**) malloc(capacity * sizeof(struct MinHeapNode*));
    return minHeap;
}

// A utility function to swap two nodes of min heap. Needed for min heapify
void swapMinHeapNode(struct MinHeapNode** a, struct MinHeapNode** b)
{
    struct MinHeapNode* t = *a;
    *a = *b;
    *b = t;
}

// A standard function to heapify at given idx
// This function also updates position of nodes when they are swapped.
// Position is needed for decreaseKey()
void minHeapify(struct MinHeap* minHeap, int idx)
{
    int smallest, left, right;
    smallest = idx;
    left = 2 * idx + 1;
    right = 2 * idx + 2;

    if (left < minHeap->size &&
        minHeap->array[left]->dist < minHeap->array[smallest]->dist )
      smallest = left;

    if (right < minHeap->size &&
        minHeap->array[right]->dist < minHeap->array[smallest]->dist )
      smallest = right;

    if (smallest != idx)
    {
        // The nodes to be swapped in min heap
        MinHeapNode *smallestNode = minHeap->array[smallest];
        MinHeapNode *idxNode = minHeap->array[idx];

        // Swap positions
        minHeap->pos[smallestNode->v] = idx;
        minHeap->pos[idxNode->v] = smallest;

        // Swap nodes
        swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]);

        minHeapify(minHeap, smallest);
    }
}

// A utility function to check if the given minHeap is ampty or not
int isEmpty(struct MinHeap* minHeap)
{
    return minHeap->size == 0;
}

// Standard function to extract minimum node from heap
struct MinHeapNode* extractMin(struct MinHeap* minHeap)
{
    if (isEmpty(minHeap))
        return NULL;

    // Store the root node
    struct MinHeapNode* root = minHeap->array[0];

    // Replace root node with last node
    struct MinHeapNode* lastNode = minHeap->array[minHeap->size - 1];
    minHeap->array[0] = lastNode;

    // Update position of last node
    minHeap->pos[root->v] = minHeap->size-1;
    minHeap->pos[lastNode->v] = 0;

    // Reduce heap size and heapify root
    --minHeap->size;
    minHeapify(minHeap, 0);

    return root;
}

// Function to decreasy dist value of a given vertex v. This function
// uses pos[] of min heap to get the current index of node in min heap
void decreaseKey(struct MinHeap* minHeap, int v, int dist)
{
    // Get the index of v in heap array
    int i = minHeap->pos[v];

    // Get the node and update its dist value
    minHeap->array[i]->dist = dist;

    // Travel up while the complete tree is not hepified.
    // This is a O(Logn) loop
    while (i && minHeap->array[i]->dist < minHeap->array[(i - 1) / 2]->dist)
    {
        // Swap this node with its parent
        minHeap->pos[minHeap->array[i]->v] = (i-1)/2;
        minHeap->pos[minHeap->array[(i-1)/2]->v] = i;
        swapMinHeapNode(&minHeap->array[i], &minHeap->array[(i - 1) / 2]);

        // move to parent index
        i = (i - 1) / 2;
    }
}

// A utility function to check if a given vertex
// 'v' is in min heap or not
bool isInMinHeap(struct MinHeap *minHeap, int v)
{
   if (minHeap->pos[v] < minHeap->size)
     return true;
   return false;
}

void printPath(int parent[], int j)
{
    // Base Case : If j is source
    if (parent[j]==-1)
        return;

    printPath(parent, parent[j]);

    printf("%d ", j);
}

// The main function that calulates distances of shortest paths from src to all
// vertices. It is a O(ELogV) function
void dijkstra(struct Graph* graph, int src,int dest)
{
    int V = graph->V;// Get the number of vertices in graph
    int dist[V];      // dist values used to pick minimum weight edge in cut
    int parent[V];    //printing path

    // minHeap represents set E
    struct MinHeap* minHeap = createMinHeap(V);

    // Initialize min heap with all vertices. dist value of all vertices
    for (int v = 0; v < V; ++v)
    {
        parent[src] = -1;
        dist[v] = INT_MAX;
        minHeap->array[v] = newMinHeapNode(v, dist[v]);
        minHeap->pos[v] = v;
    }

    // Make dist value of src vertex as 0 so that it is extracted first
    minHeap->array[src] = newMinHeapNode(src, dist[src]);
    minHeap->pos[src]   = src;
    dist[src] = 0;
    decreaseKey(minHeap, src, dist[src]);

    // Initially size of min heap is equal to V
    minHeap->size = V;

    // In the followin loop, min heap contains all nodes
    // whose shortest distance is not yet finalized.
    while (!isEmpty(minHeap))
    {
        // Extract the vertex with minimum distance value
        struct MinHeapNode* minHeapNode = extractMin(minHeap);
        int u = minHeapNode->v; // Store the extracted vertex number

        // Traverse through all adjacent vertices of u (the extracted
        // vertex) and update their distance values
        struct AdjListNode* pCrawl = graph->array[u].head;
        while (pCrawl != NULL)
        {
            int v = pCrawl->dest;

            // If shortest distance to v is not finalized yet, and distance to v
            // through u is less than its previously calculated distance
            if (isInMinHeap(minHeap, v) && dist[u] != INT_MAX &&
                                          pCrawl->weight + dist[u] < dist[v])
            {
                parent[v] = u;
                dist[v] = dist[u] + pCrawl->weight;

                // update distance value in min heap also
                decreaseKey(minHeap, v, dist[v]);
            }
            pCrawl = pCrawl->next;
        }
    }

    // print the calculated shortest distances
   cout<<dist[dest]<<endl;
cout<<src<<" ";
   printPath(parent,dest);
cout<<endl;
}

void printGraph(struct Graph* graph)
{
    int v;
  
    for (v =1 ; v <graph->V; ++v)
    {      
        cout<<v<<" : ";
         struct AdjListNode* t =graph->array[v].head;
        while (t!=NULL)
        {
            cout<<" ("<<t->dest<<" "<<t->weight<<" )";
            t=t->next;
        }
        cout<<endl;
    }
}

------------------------------------------

maincpp

#include <iostream>
#include <fstream>
#include <string>
#include<vector>
#include<algorithm>
#include"graph.h"
#include <iostream>     // std::cout
#include <sstream>      // std::istringstream
using namespace std;

int main (int argc,char **argv)
{
string line,cmd;
string c[3];
int so,d;
vector<string> v;
ifstream myfile ("GRAPHinput.txt");
int a[2];
int l[3];
int i=0;
if (myfile.is_open())
{
    getline (myfile,line);
    istringstream iss(line);
    string s;

    //Parsing of no vertices and no of edges
    while ( getline( iss, s, ' ' ) )
   {
     a[i++]=stoi(s);
   }

//Creation of graph
     struct Graph* graph = createGraph(a[0]);
  
    while ( getline (myfile,line) )
    {
      if(line.empty())
       break;
      i=0;
      istringstream iss(line);
      string s;
    //Parsing of edges along with their weight
    while ( getline( iss, s, ' ' ) )
   {
     l[i++]=stoi(s);
   }

    //Add an edge into graph
    addEdge(graph,l[0],l[1],l[2]);

    } //while close

   printGraph(graph);

while( getline (cin,cmd))
{
//Parse P s t command
   istringstream isss(cmd);
      string ss;
     int j=0;
     while ( getline( isss, ss, ' ' ) )
   {
     c[j++]=ss;
   }

   if(c[0].compare("s")==0)
     exit(0);
   so=atoi(c[1].c_str());
   d=atoi(c[2].c_str());
   dijkstra(graph,so,d);

}
    myfile.close();
}

else cout << "Unable to open file";

  

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

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