s

[dakman96]

I have been given the assignment at the following link:

http://www.cs.ecu.edu/~karl/3300/fall15/Assignments/Assignment6/assn6.html

I have completed everything in a way that I believe should work... Please let me know if you see what's wrong or have any suggestions, I'd really appreciate it.

dijkstra.cpp

// File:       dijkstra.cpp
#include <cstdio>
#include <iostream>
#include "event.h"
#include "pqueue.h"
using namespace std;

int TraceLevel = 1;

struct AdjacencyList
{
	int vertex;
	PQPriorityType weight;
	AdjacencyList* next;

	AdjacencyList(int j, double w, AdjacencyList* n)
	{
		vertex = j;
		weight = w;
		next = n;
	}
	AdjacencyList()
	{
		vertex = 0;
		weight = 0;
		next = NULL;
	}
};

struct VertexInfo
{
	AdjacencyList* list;
	int distance;
	int previous;

	VertexInfo()
	{
		list = NULL;
		distance = -1;
		previous = 0;
	}
};

struct Graph
{
	int numVerticies;
	int numEdges;
	VertexInfo* vInfo;

	Graph(int v)
	{
		numVerticies = v;
		numEdges = 0;
		vInfo = new VertexInfo[v];
	}
};

//Takes in input of the first vertex, the second vertex, and the weight.

void input(Graph* g)
{
	
	PQPriorityType weight;
	int v1, v2;
	while (true)
	{
		cin >> v1;
		if (v1 == 0)
		{
			break;
		}
		cin >> v2;
		cin >> weight;
		if (g->vInfo[v1].list == NULL)
		{
			AdjacencyList* tempList = new AdjacencyList(v2, weight, NULL);
			g->vInfo[v1].list = tempList;
		}
		else
		{
			AdjacencyList* tempList = new AdjacencyList(v2, weight, g->vInfo[v1].list);
			g->vInfo[v1].list = tempList;
		}
		if (g->vInfo[v2].list == NULL)
		{
			AdjacencyList* tempList = new AdjacencyList(v1, weight, NULL);
			g->vInfo[v2].list = tempList;
		}
		else
		{
			AdjacencyList* tempList = new AdjacencyList(v1, weight, g->vInfo[v2].list);
			g->vInfo[v2].list = tempList;
		}
	}
}

//Prints the values of Graph g.

void printGraph(Graph* g)
{
	Graph* temp = g;
	int i = 0;
	cout << "There are " << temp->numVerticies - 1 << " vertices." << endl;
	cout << "The edges are as follows." << endl <<endl;
	while (i < temp->numVerticies)
	{
		if (temp->vInfo[i].list == NULL)
		{
			i++;
		}
		else 
		{
			if (i < temp->vInfo[i].list->vertex)
			{
				cout << "(" << i << ",";
				cout << temp->vInfo[i].list->vertex << ") ";
				cout << "weight " << temp->vInfo[i].list->weight << endl;
			}
			temp->vInfo[i].list = temp->vInfo[i].list->next;
		}
	}
}

//Creates new events from an adjacenecy list and then inserts the events into PriorityQueue queue.

void createEvents(PriorityQueue& queue, AdjacencyList* list, PQItemType temp)
{
	if (list != NULL)
	{
		if (TraceLevel == 1)
		{
			cout << "Signal is being sent from " << temp->to << " to " << list->vertex << " at time " << temp->time << "." << endl << "Arriving at " << list->weight + temp->time << endl;
		}
		Event* e = new Event(temp->to, list->vertex, list->weight + temp->time);
		insert(queue, e, temp->time);
		createEvents(queue, list->next, temp);
	}
}

//Takes the event queue and finds the shortest path from a start node to an end node

void shortestPath(Graph* g, int f, int l, PriorityQueue queue)
{
	Event* firstEvent = new Event(0, f, 0.0);
	insert(queue, firstEvent, 0.0);
	g->vInfo[0].distance = 0;
	while (!isEmpty(queue))
	{
		PQItemType temp1;
		PQPriorityType temp2;
		remove(queue, temp1, temp2);
		createEvents(queue, g->vInfo[temp1->to].list, temp1);
		if (temp1->time > -1)
		{
			if (TraceLevel == 1)
			{
				cout << "The signal arrives at " << temp1->to << " from " << temp1->from << " at time " << temp1->time << endl << endl;
			}
			g->vInfo[temp1->to].distance = temp1->time;
			g->vInfo[temp1->to].previous = temp1->from;
		}
		if (g->vInfo[l].distance != -1)
		{
			cout << "BREAK" << endl;
			break;
		}
	}
}

//Prints the shortest distance from a start node to and end node in the order it travels.

void printFinalPath(Graph* g, int f, int l)
{

}

int main(int argc, char** argv)
{
	int numVertices, x, first, last;
	PriorityQueue queue;
	x = 0;
	cin >> numVertices;
	numVertices = numVertices + 1;
	Graph* g = new Graph(numVertices);
	input(g);
	cin >> first;
	cin >> last;
	shortestPath(g, first, last, queue);
	printGraph(g);
	cout << "The shortest path from " << first << " to " << last << " is " << g->vInfo[last].distance << endl;
	//printFinalPath(g, first, last);
	return 0;
}

pqueue.cpp

// File:       pqueue.cpp
#include <cstdio>
#include <iostream>
#include "pqueue.h"

using namespace std;

struct PQCell
{
	PQItemType item;
	PQPriorityType priority;
	PQCell* next;

	PQCell(PQItemType i, PQPriorityType pri, PQCell* n)
	{
		item = i;
		priority = pri;
		next = n;
	}
};



//Inserts item x with priority pri into the linked list pointed to by p.

void insertCell(const PQItemType& x, PQPriorityType pri, PQCell*& p)
{
	if (p == NULL)
	{
		p = new PQCell(x, pri, NULL);
	}
	else if (pri <= p->priority)
	{
		p->next = new PQCell(x, pri, p->next);
	}
	else
	{
		insertCell(x, pri, p->next);
	}
}

//Returns true if q is empty.

bool isEmpty(PriorityQueue& q)
{
	return q.queue == NULL;
}


//Inserts x with the priority p into q.
void insert(PriorityQueue& q, const PQItemType& x, PQPriorityType p)
{
	if (q.queue == NULL || p <= q.queue->priority)
	{
		q.queue = new PQCell(x, p, q.queue);
	}
	else
	{
		insertCell(x, p, q.queue);
	}
}

//Removes the item from the queue with the lowest priority.

void remove(PriorityQueue& q, PQItemType& x, PQPriorityType& p)
{
	if (q.queue != NULL)
	{
		x = q.queue->item;
		p = q.queue->priority;
		PriorityQueue priQTemp;
		priQTemp.queue = q.queue;
		q.queue = priQTemp.queue->next;
		delete priQTemp.queue;
	}
}

//Prints the q, in order from lowest priority to highest priority

void printPriorityQueue(const PriorityQueue& q, ItemPrinter pi, PriorityPrinter pp)
{
	PriorityQueue temp;
	temp.queue = q.queue;
	while (temp.queue != NULL)
	{
		pi(temp.queue->item);
		cout << "\t";
		pp(temp.queue->priority);
		cout << endl;
		temp.queue = temp.queue->next;
	}
}

event.h

// File:       pqueue.h
#ifndef EVENT_H
#define EVENT_H

struct Event
{
	int from;
	int to;
	double time;

	Event(int f, int t, double ti)
	{
		from = f;
		to = t;
		time = ti;
	}
};

#endif 

pqueue.h

// File:       pqueue.h
#include "event.h"

typedef Event* PQItemType;
typedef double PQPriorityType;
typedef void (ItemPrinter)(const PQItemType&);
typedef void (PriorityPrinter)(PQPriorityType);

struct PQCell;

struct PriorityQueue
{
	PQCell* queue;

	PriorityQueue()
	{
		queue = nullptr;
	}
};

bool isEmpty(PriorityQueue& q);
void insert(PriorityQueue& q, const PQItemType& x, PQPriorityType p);
void remove(PriorityQueue& q, PQItemType& x, PQPriorityType& p);
void printPriorityQueue(const PriorityQueue& q, ItemPrinter pi, PriorityPrinter pp);