You will implement a binary heap in C program based implementation of Dijkstra’s

ID: 3695312 • Letter: Y

Question

You will implement a binary heap in C program based implementation of Dijkstra’s 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 user’s 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 Dijkstra’s 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 user’s current location (vertex name)

Prints the user-specified destination (vertex name)

Prints the minimum distance from the user’s 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 user’s 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.

User’s 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.

<number-of-vertices>

<vertex-name> <vertex-name> <edge-length>

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):

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:

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 <stdio.h>
#include <stdlib.h>
#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);
}

(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 Dijkstra’s 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 user’s current location (vertex name)

Prints the user-specified destination (vertex name)

Prints the minimum distance from the user’s 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 user’s 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.

User’s current location is updated.

Explanation / Answer

#include <stdio.h>
#include <stdlib.h>
#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;
};

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;
}

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);
}

int valid_id(PQ * pq, int id) {
if(id >= pq->capacity || id < 0) {
return 0;
}
return 1;
}

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;
}

void swap_node(NODE **heap, int i, int dest) {

heap[i]->i = heap[dest]->i;
heap[dest]->i = i;
// swap nodes
NODE *tmp = heap[dest];
heap[dest] = heap[i];
heap[i] = tmp;
}

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(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);
}
}
}
}

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);
}

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;
}

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;
}

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;
}

int pq_capacity(PQ * pq) {
return pq->capacity;
}

int pq_size(PQ * pq) {
return pq->size;
}

int pq_contains(PQ * pq, int id) {
double p;
return pq_get_priority(pq, id, &p);
}

Navigate

You will implement a binary heap based implementation of Dijkstra’s algorithm to

You will implement a binary search tree data structure in C++, and turn in a pro

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

You will implement a binary heap in C program based implementation of Dijkstra’s

Question

Explanation / Answer

Related Questions

Navigate