Datastrukturer_Algoritmer/Dijkstra/graf.cpp

/************************************************
*	 Laboration 4 i
*	 Datastrukturer och Algoritmer
*	 Dijkstras Shortest Path
*************************************************
*	 Christian Ohlsson
*	 Karlstads universitet, 1999
*
*   graf.cpp
*   Innehåller de funktioner programmet
*   använder sig av för att beräkna
*   den kortaste vägen
*************************************************/

#include "header.h"
/*===============================================
* graphNode
*  Construktor.
*  Skapar en graphNode
-------------------------------------------------*/
graphNode::graphNode() {
	startCity = -1;
	endCity = -1;
	Start = 0;
	End = 0;
}

/*===============================================
* Operator ==
*  Operatoröverlagring
-------------------------------------------------*/

int graphNode::operator==(graphNode node) {
	if(Start != node.Start || End != node.End ||
		startCity != node.startCity || endCity != node.endCity)
		return false;
	return true;
}

/*===============================================
* Operator =
*  Operatoröverlagring
-------------------------------------------------*/
void graphNode::operator=(graphNode node) {
	startCity = node.startCity;
	endCity = node.endCity;
	Start = node.Start;
	End = node.End;
}

/*===============================================
* Operator >
*  Operatoröverlagring
-------------------------------------------------*/
int graphNode::operator>(graphNode node) {
	if(Start <= node.Start)
		return false;
	return true;
}

/*===============================================
* dijkstraNode
*  Construktor.
*  Skapar en Dijkstra node
-------------------------------------------------*/
dijkstraNode::dijkstraNode() {
	deleted = false;
	lastCity = 0;
	Totaltime = MAXINT;                            //Tiden sätts till max
}

/*===============================================
* ~dijkstraNode
*  Destruktor.
*  Tar bort en nod
-------------------------------------------------*/
dijkstraNode::~dijkstraNode() {}

/*===============================================
* graph
*  Construktor
*  Skapar en graph
-------------------------------------------------*/
graph::graph() {
	visitedCities = 0;
	table = NULL;
	lastPath = NULL;
	prevSize = 0;
	lastTime = 0;
}

/*===============================================
* ~graph
*  Destruktor
*  Anropar deleteGraph
-------------------------------------------------*/
graph::~graph() {	deleteGraph(); }

/*===============================================
* deleteGraph
*  Tömmer grafen på info
-------------------------------------------------*/
void graph::deleteGraph() {
	if(table != NULL)
		delete[] table;
	if(lastPath != NULL)
		delete[] lastPath;
	table = NULL;
	lastPath = NULL;
	visitedCities = 0;
	prevSize = 0;
	lastTime = 0;
}

/*===============================================
* makeGraph
*  Skapar en graf med size stycken städer.
*  Tar först bort eventuell gammal graf.
*  Returnerar true om allt gick bra
-------------------------------------------------*/
int graph::makeGraph(int size) {
	deleteGraph();
	table = new list<graphNode>*[size];
	if(table == NULL)
		return false;
	for(int index = 0; index < size; index++)
		table[index] = new list<graphNode>[size];
	if(table == NULL)
		return false;
	visitedCities = size;
	return true;
}

/*===============================================
* connect
*  Skapar förbindelse mellan noderna i grafen
-------------------------------------------------*/
void graph::connect(int startvertex, int endvertex, graphNode node) {
	if(startvertex < 0 || startvertex > visitedCities-1 ||
		endvertex < 0 || endvertex > visitedCities-1)
			return;
	node.startCity = startvertex;
	node.endCity = endvertex;
	table[startvertex][endvertex].insert(node);
}

/*===============================================
* shortestPath
*  Letar reda på den kortaste
*  vägen mellan två noder
-------------------------------------------------*/
graphNode graph::shortestPath(int startvertex, int endvertex, int time) {
	int index, time1, time2;
	graphNode node1, node2;
	if(startvertex < 0 || startvertex > visitedCities-1 ||
		endvertex < 0 || endvertex > visitedCities-1)
			return node1;
	int connections = table[startvertex][endvertex].listLength();
	if(connections == 0)	return node1;
	node1 = table[startvertex][endvertex].printElement(1);
	time1 = getTime(node1, time);
	for(index = 2; index <= connections; index++) {
		node2 = table[startvertex][endvertex].printElement(index);
		time2 = getTime(node2, time);
		if(time1 > time2) {
			node1 = node2;
			time1 = time2;
		}
	}
	return node1;
}

/*===============================================
* getTime
*  Returnerar antalet timmar mellan tiden
*  time och tiden som finns i noden
-------------------------------------------------*/
int graph::getTime(graphNode node, int time) {
	int total;
	if(node.Start >= time && node.End > time && node.Start < node.End)
		total = node.End - time;
	else if(node.Start > node.End)
		total = ( (24 - time + node.Start) + (24 - node.Start + node.End) );
	else
		total = (24 - time + node.End);
	return total;
}

/*===============================================
* dijkstra
*  Beräknar den kortaste sträckan dvs. tiden
*  mellan två städer i NeverNeverLand
-------------------------------------------------*/
void graph::dijkstra(int startvertex, int endvertex, int time) {
	delPath();
	if(startvertex == endvertex || startvertex < 0 ||
		startvertex > visitedCities-1 || endvertex < 0 ||
		endvertex > visitedCities-1)
		return;

	dijkstraNode *temparray = new dijkstraNode[visitedCities];
	if(temparray == NULL)  return;
	int min, index, parent = 0, temptime;
	graphNode tempnode;
	temparray[startvertex].Totaltime = 0;
	temparray[startvertex].deleted = true;
	min = startvertex;
	while(min != endvertex) {
		for(index = 0; index < visitedCities; index++) {
			if(!temparray[index].deleted) {
				tempnode = shortestPath(min, index, time);
				if(tempnode.startCity != -1) {
					temptime = getTime(tempnode, time);
					if((temptime + temparray[min].Totaltime)
						< temparray[index].Totaltime) {
							 temparray[index].Totaltime =
							 temptime + temparray[min].Totaltime;
						if(parent == 0)
							temparray[index].lastCity = 0;
						else
							temparray[index].lastCity = min;
						temparray[index].Node = tempnode;
					}
				}
			}
		}
		min = getMinTime(temparray);
		temparray[min].deleted = true;
		time = temparray[min].Node.End;
		parent++;
	}
	calcPath(temparray, min);
}

/*===============================================
* calcPath
*  Skapar en array med information
*  om den kortaste vägen.
-------------------------------------------------*/
void graph::calcPath(dijkstraNode *array, int start) {
	graphNode *path = new graphNode[visitedCities];
	if(path == NULL)
		return;
	int temp = 1, index = start;
	while(array[index].lastCity > 0) {
		temp++;
		index = array[index].lastCity;
	}
	prevSize = temp;
	lastTime = array[start].Totaltime;
	for(index = temp-1; index >= 0; index--) {
		path[index] = array[start].Node;
		start = array[start].lastCity;
	}
	lastPath = path;
}

/*===============================================
* getMinIndex
*  Hittar den minsta noden i en array och
*  returnerar dess index i arrayen
-------------------------------------------------*/
int graph::getMinTime(dijkstraNode *temptable) {
	int temp = 0, index;
	while(temptable[temp].deleted)
		temp++;
	for(index = temp+1; index < visitedCities; index++) {
		if(!temptable[index].deleted) {
			if(temptable[temp].Totaltime > temptable[index].Totaltime)
				temp = index;
		}
	}
	return temp;
}

/*===============================================
* delPath
*  Tar bort det som lastpath pekar på
-------------------------------------------------*/
void graph::delPath() {
	if(lastPath != NULL)
		delete[] lastPath;
	lastPath = NULL;
	prevSize = 0;
}