Need help to implement a binary heap based implementation of Dijkstras algorithm to support a toy application in which a traveler walks around a graph starting from a user-specified start vertex and with a target destination (also user-specified) in mind.

From the users point of view, vertices are identified by strings (internally, your code will also have an integer vertex-id for each vertex).

Edges between vertices are undirected (an edge (u,v) can be traversed from u to v or from v to u).

Edges are also weighted with non-negative floating point numbers indicating some measure of distance of time it takes to traverse the edge.

The application takes a single command line argument: a file containing the graph specification (file format has its own section below).

After reading the graph (assuming there are no errors), the application does the following (an example is given in a later section which might be the best place to start):

(Setup)

Prints a list of all of the vertices in the graph by name.

Asks the user for their current location which the user enters as a vertex name.

Asks the user for their destination (also specified by vertex name).

Next, the program runs Dijkstras shortest paths algorithm on the graph. Exactly how you should run Dijkstra is discussed below (to enable the features/behavior I am about to describe).

If the destination vertex is not reachable from the start vertex, then prints an appropriate message and terminates.

Otherwise (destination reachable), it then reports the shortest path-length from the given start vertex to the given destination.

It then prints the (technically an) optimal path as a sequence of vertices (starting from the given start vertex to the given destination of course).

Then...

(interactive loop)

As long as the user has not arrived at their destination, the program repeatedly does the following:

Prints the users current location (vertex name)

Prints the user-specified destination (vertex name)

Prints the minimum distance from the users current location to the specified destination.

Lists user options for their next move: give up or select one of the vertices directly connected to the current location.

Option 0 is always I give up. This just terminates the program.

Options 1, 2, 3 and so on correspond to the neighboring vertices of the users current location. For each of these options, the vertex name and the length of that edge is displayed.

Gives a recommended move (i.e., vertex on a shortest path to the destination).

Reads the user selection (as an integer).

Assuming it is a valid selection, the state is updated:

Total distance traveled is updated.

Users current location is updated.

File Format

Recall that we will be working with undirected, edge-weighted graphs.

Input files follow the general format below where vertex-names are strings and edge lengths are non-negative floating point numbers.

.

.

.

Thus, the file first tells you the number of vertices in the graph and then lists all of the edges.

An actual example (suppose this is the contents of a file graph1.txt):

7

locA locB 7.9

locB locC 10.1

locA locD 8.2

locD locC 11.0

locB locD 9.1

locB locE 19.9

locA locE 8.0

locF locE 12.2

locC locF 8.0

locG locF 11.7

locD locF 15.4

Another example:

3

Chi Mil 90.0

Mil Min 120

Min Chi 180

Example Program Behavior

was an accident

$ ./travel graph1

Welcome to travel planner.

Vertices:

locA locB locC locD locE locF locG

SELECT YOUR CURRENT LOCATION: locG

SELECT YOUR DESTINATION : locA

You can reach your destination in ____ units.

TIME TO TRAVEL!

CURRENT LOCATION: locG

DESTINATION: locA

MINIMUM DISTANCE TO DESTINATION: _____

POSSIBLE MOVES:

0. I give up!

locD (11.7 units)

locF (15.4 units)

RECOMMENDED MOVE: _____

SELECT A MOVE (ENTER A NUMBER): 2

TOTAL DISTANCE TRAVELED: 15.4 units

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

CURRENT LOCATION: locF

DESTINATION: locA

MINIMUM DISTANCE TO DESTINATION: _____

POSSIBLE MOVES:

0. I give up!

locE (12.2 units)

locG (11.7 units)

locC (8 units)

RECOMMENDED MOVE: _____

SELECT A MOVE (ENTER A NUMBER): 1

TOTAL DISTANCE TRAVELED: 23.9 units

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

CURRENT LOCATION: locE

DESTINATION: locA

MINIMUM DISTANCE TO DESTINATION: _____

POSSIBLE MOVES:

0. I give up!

locF (12.2 units)

locB (19.9 units)

locA (8.0 units)

RECOMMENDED MOVE: 3

SELECT A MOVE (ENTER A NUMBER): 3

TOTAL DISTANCE TRAVELED: 31.9 units

YOU MADE IT.

(OPTIMAL DISTANCE: ______)

GOODBYE.

$

Data Structures

Task	Data Structure	Comments
Mapping from vertex name to vertex id	hmap	Component of graph data structure
Mapping from vertex-id to vertex name	Array indexed by vertex-id
Mapping from vertex-id to list of neighbors	Array indexed by vertex-id. Can (should?) be same array as for above task. Entries in the list contain vertex-id and edge length.
Priority Queue	Heap-Based Priority Queue (i.e., part-I of this assignment!)	Enables Fast Implementation of Dijkstra. Conceptually, does not belong to the graph data structure.
Data Structure Encapsulating Result of Dijkstra -- a report of sorts.	Captures: source vertex s Shortest distances to each reachable vertex from s (d-values) Shortest paths tree (implicitly or explicitly). pointer to the graph on which Dijkstra was run to generate the report.	Allows post-facto extraction of shortest paths, etc. Conceptually, is associated with a graph, but not owned by that graph. Recall how the sample bfs code achieved this.

Making changes for the following code:

#include #include #include "pq.h"

typedef struct pq_node { int id; double priority; int i; // index in heap } NODE;

struct pq_struct { int capacity; int min_heap; int size; NODE **heap; NODE **ids; };

/** * Function: pq_create * Parameters: capacity - self-explanatory * min_heap - if 1 (really non-zero), then it is a min-heap * if 0, then a max-heap * * Returns: Pointer to empty priority queue with given capacity and min/max behavior as specified */ PQ * pq_create(int capacity, int min_heap) { PQ * pq = malloc(sizeof(struct pq_struct)); pq->capacity = capacity; pq->min_heap = min_heap; pq->size = 0; pq->ids = malloc(sizeof(NODE*) * capacity); pq->heap = malloc(sizeof(NODE*) * capacity);

int i; for(i = 0; i <= pq->capacity; i++) { pq->ids[i] = NULL; // will have extra at end pq->heap[i] = NULL; // will have extra at begining }

return pq; } /** * Function: pq_free * Parameters: PQ_PTR pq * Returns: -- * Desc : deallocates all memory associated with passed priority queue. */ void pq_free(PQ * pq) { int i; for(i = 0; i <= pq->size; i++) { free(pq->heap[i]); } free(pq->ids); free(pq->heap); free(pq); }

// checks if id is with in range int valid_id(PQ * pq, int id) { if(id >= pq->capacity || id < 0) { return 0; } return 1; }

// if the node has children the index with the highest // priority is returned int has_children(PQ * pq, int k, int i) { NODE **heap = pq->heap; NODE *l = heap[i*2];

if((i*2) > pq->size || l == NULL) { return -1; }

NODE *r = heap[(i*2)+1];

if((i*2)+1 <= pq->size && r != NULL) { if((l->priority)*k < (r->priority)*k) { return r->i; } } return l->i; }

// swaps 2 nodes positions in the heap void swap_node(NODE **heap, int i, int dest) { // update indecies heap[i]->i = heap[dest]->i; heap[dest]->i = i; // swap nodes NODE *tmp = heap[dest]; heap[dest] = heap[i]; heap[i] = tmp; }

// keeps highest priority (relative to min_heap) at top void prioritize(PQ * pq, int i) { NODE **heap = pq->heap; int k = 1; // modifier if(pq->min_heap == 1) { k = -1; // makes largest pri smallest }

// if the priority of i is greater than its parent switch them if(i != 1 && (heap[i]->priority)*k > (heap[i/2]->priority)*k) { swap_node(heap, i, i/2); prioritize(pq, i/2); } else { int h = has_children(pq, k, i);

if(h != -1) { if((heap[i]->priority)*k < (heap[h]->priority)*k) { swap_node(heap, i, h); prioritize(pq, h); } } } }

/** * Function: pq_insert * Parameters: priority queue pq * id of entry to insert * priority of entry to insert * Returns: 1 on success; 0 on failure. * fails is already an entry for id * there is already an entry for id * succeeds otherwise * Desc : self-explanatory * * Runtime : 0(logn ) * */ int pq_insert(PQ * pq, int id, double priority) { if(!valid_id(pq, id) || pq->ids[id] != NULL) { return 0; }

NODE *n = malloc(sizeof(NODE)); n->id = id; n->priority = priority;

pq->size++; n->i = pq->size;

pq->ids[id] = n; pq->heap[pq->size] = n;

prioritize(pq, n->i); }

/** * Function: pq_change_priority * Parameters: priority queue ptr pq * element id * new_priority * Returns: 1 on success; 0 on failure * Desc : If there is an entry for the given id, its associated * priority is changed to new_priority and the data * structure is modifeid accordingly. * Otherwise, it is a failure (id not in pq or out of range) * Runtime : O(log n) * */

int pq_change_priority(PQ * pq, int id, double new_priority) { if(!valid_id(pq, id) || pq->ids[id] == NULL) { return 0; } NODE *n = pq->ids[id]; n->priority = new_priority; prioritize(pq, n->i); return 1; }

/** * Function: pq_remove_by_id * Parameters: priority queue pq, * element id * Returns: 1 on success; 0 on failure * Desc: If there is an entry for the given id, its associated * priority is changed to new_priority and the data * structure is modifeid accordingly * Otherwide, it is a failure (id not in pq or out of range) * Runtime : O(log n) * */ int pq_remove_by_id(PQ * pq, int id) { if(!valid_id(pq, id) || pq->ids[id] == NULL) { return 0; }

NODE *n = pq->ids[id]; pq->ids[id] = NULL;

if(n->i < pq->size) { // there is a node lower in the heap pq->heap[n->i] = pq->heap[pq->size]; pq->heap[n->i]->i = n->i; // update index pq->heap[pq->size] = NULL;

prioritize(pq, n->i); }

pq->size--; free(n); return 1; }

/** * Function: pq_get_priority * Parameters: priority queue pq * elment id * double pointer priority ("out" param) * Returns: 1 on success; 0 on failure * Desc : if there is an entry for give id, *priortiy is assigned * the associated priority and 1 is returned. * Otherwise 0 is returned and *priority has no meaning. * Runtime: O(1) */ int pq_get_priority(PQ * pq, int id, double *priority) { if(!valid_id(pq, id) || pq->ids[id] == NULL) { return 0; } *priority = pq->ids[id]->priority; return 1; }

/** * Function: pq_delete_top * Parameters: priority queue pq * int pointers id and priority ("out" parameters) * Returns: 1 on success; 0 on failure (empty priority queue) * Desc: if queue is non-empty the "top" element is deleted and * its id and priority are stored in *id and *priority; * The "top" element will be either min or max (wrt priority) * depending on how the priority queue was configured. * * If queue is empty, 0 is returned. * * Runtime: O(long n) */ int pq_delete_top(PQ * pq, int *id, double *priority) { if(pq->heap[1] == NULL) { return 0; }

NODE *n = pq->heap[1]; *id = n->id; *priority = n->priority;

pq_remove_by_id(pq, n->id); return 1; }

/** * Function: pq_capacity * Parameters: priority queue pq * Returns: capacity of priority (as set on creation) * Desc : see returns * * Runtime: O(1) */ int pq_capacity(PQ * pq) { return pq->capacity; }

/** * Function: pq_size * Parameters: priority queue pq * Returns : number of elements currently in queue * Desc: see above * * Runtime: O(1) */ int pq_size(PQ * pq) { return pq->size; }

/** * Function: pq_contains * Parameters: priority queue pq * element id * Returns: 1 if there is an entry in the queue for given id * 0 otherwise * Desc : see above * * Runtime: 0(1) * * Note: same return value as pa_get_priority * */ int pq_contains(PQ * pq, int id) { double p; return pq_get_priority(pq, id, &p); }