===== GraphFunctions.py =====
<code python>
# -*- coding: utf8 -*-
from __future__ import division, print_function
import math, random, time, scipy.stats
import numpy as np
import matplotlib.pyplot as plt
from random import randint
import Queue
import sys

class Node(object):
	
	def __init__(self, graph, name, gnb, gel, cEdges=[], dist=float("inf"), ancestor=None, unvisited=True):
		#Für Dijkstra-Algorithmus
		self.dist = dist
		self.ancestor = ancestor
		self.unvisited=unvisited
		
		self.graph = graph
		self.name = name
		#nördl. Breite
		self.gnb=gnb
		#östl. Länge
		self.gel=gel
		#Index-Liste mit verbundenen Kanten
		self.cEdges=[]
	
	#Fügt eine neue Kante zwischen dieser Node und der gegebenen Node 'node' hinzu.
	def addEdgeTo(self, node):
		self.cEdges.append(self.graph.addEdge(self, node, 1))
	
	#Berechnet die geographische Distanz zwischen dieser Node und der übergebenen Node (otherNode).
	def calcGeoDist(self, otherNode):
		#Pythagoras
		#Konstanten für Abstand der Breiten- bzw. Längenkreise
		#konbr=111300**2 --> Absolutzahlen vorher berechnen
		konbr=12387690000
		#Längenabstand variiert nach geograph. Breite; hier etwa 71.5
		#konla=(111.3 * cos((self.gnb+other.gnb)/2*math.pi/180))**2 --> Absolutzahlen vorher berechnen
		konla=12387690000*math.cos((self.gnb+otherNode.gnb)*0.008726646)**2
		return math.sqrt(konbr*(self.gnb-otherNode.gnb)**2+konla*(self.gel-otherNode.gel)**2)
	
	#Gibt eine Liste der Nodes zurück, die durch eine Edge mit dieser Node verbunden sind.
	def findNeighbors(self):
		neighbors=[]
		for i in self.cEdges:
			if(isinstance(i, Edge)):
				if i.node1==self:
					neighbors.append([i,i.node2])
				else:
					neighbors.append([i,i.node1])
			else:
				print("Typfehler!", str(type(i)));
		return neighbors
	
	#Gibt (wenn existent) die Edge zwischen dieser Node und der übergebenen Node 'neighbor' zurück. 
	def findEdgeTo(self, neighbor):
		for e in self.cEdges:
			if self.graph.findNode(e.getSecondNode(self))==neighbor:
				return e
		print("There is no Edge between %s and %s!"%(self.name, neighbor))
		time.sleep(2)
	
	#Gibt zurück, ob diese Node noch nicht besucht wurde.
	def getunvisited(self):
		return self.unvisited
	
	
class Edge(object):
	
	def __init__(self, graph, node1, node2, typ, entf, importance=0):
		self.graph = graph
		#erster Knoten
		self.node1=node1
		#zweiter Knoten
		self.node2=node2
		#Art des Ausbaus (v in m/s)
		self.typ=typ
		#Länge in m
		self.entf=entf
		self.dist=entf/typ
		self.importance=importance
	
	#Gibt die Node zurück, die sich gegenüber von 'firstNode' an dieser Edge befindet.
	def getSecondNode(self, firstNode):
		if self.node1==firstNode:
			return self.node2
		else:
			return self.node1
	
	#Gibt die Kosten zurück um die Stufe dieser Edge zu erhöhen.
	def upgradeExpense(self, typ, step=1, expenses=None):
		back=0
		
		if expenses==None:
			expenses=loadExpenses()
		for i in expenses:
			if i[0]<=typ:
				back=self.entf*i[1]
		for i in expenses:
			if i[0]>=self.typ+step:
				return i[1]-back+isend(self, typ)*100*i[1]
		return float("inf")

class Graph(object):
	
	def __init__(self):
		self.nodes = []
		self.edges = []
		self.inodes = []
		self.vinodes = []
		self.rate=-1
	
	#Füllt 'inodes' mit 'number' zufällig ausgewählten Nodes.
	def defineINodesRandom(self, number=1000):
		numberofnodes=len(self.nodes)
		for i in range(number):
			self.inodes.append(self.nodes[random.randint(0,numberofnodes-1)])
	
	#Füllt 'vinodes' mit 'number' zufällig ausgewählten Nodes.
	def defineVINodesRandom(self, number=100):
		numberofnodes=len(self.nodes)
		for i in range(number):
			self.vinodes.append(self.nodes[random.randint(0,numberofnodes-1)])
	
	#Speichert die Node-Liste 'nodeList' in der Datei 'filename'.
	def saveNodeList(self, nodeList, filename=None):
		if filename==None:
			aktZeit=time.localtime();
			datum="%04i%02i%02i" % (aktZeit[0], aktZeit[1], aktZeit[2])
			zeit="%02i%02i%02i" % (aktZeit[3], aktZeit[4], aktZeit[5])
			filename=("NodeList_%s_%s") % (datum, zeit)
		f = open(filename, "w+")
		for node in nodeList:
			print("%s" %(node.name), file=f)
	
	#Speichert die Node-Listen 'inodes' und 'vinodes'.
	def saveAllNodeLists(self, filename=None):
		if filename==None:
			aktZeit=time.localtime();
			datum="%04i%02i%02i" % (aktZeit[0], aktZeit[1], aktZeit[2])
			zeit="%02i%02i%02i" % (aktZeit[3], aktZeit[4], aktZeit[5])
			filenameI=("INodeList_%s_%s") % (datum, zeit)
			filenameVI=("VINodeList_%s_%s") % (datum, zeit)
		f=open(filenameI, "w+")
		for node in self.inodes:
			print("%s" %(node.name), file=f)
		f.close()
		f=open(filenameVI, "w+")
		for node in self.vinodes:
			print("%s" %(node.name), file=f)
	
	#Speichert die Bewertung dieses Graphen in 'filename'.
	def saverate(self, filename=None):
		if filename==None:
			aktZeit=time.localtime();
			datum="%04i%02i%02i" % (aktZeit[0], aktZeit[1], aktZeit[2])
			zeit="%02i%02i%02i" % (aktZeit[3], aktZeit[4], aktZeit[5])
			filename=("NodeList_%s_%s") % (datum, zeit)
		f = open(filename, "w+")
		print("%s" %(self.rate), file=f)
	
	#Bestimmt die Bewertung dieses Graphen.
	def rateGraph(self):
		self.defineINodesRandom(1000)
		self.defineVINodesRandom(50)
		inodes=self.inodes
		vinodesself.vinodes
		distsum=0
		distprod=1
	
		numList =[]
		dist=[]
		counter=0
		for snode in vinodes:
			dist.append(dijkstra(self, snode, inodes))
			self.clearNodes()
			counter+=1
	
		counter=0
		for i in dist:
			for numb in i:
				if numb != -1:
					numList.append(numb)
		arithmetic=np.mean(numList)
		geometric=scipy.stats.mstats.gmean(numList)
		self.rate=(geometric, arithmetic)
		self.saverate
	
	#Lädt eine Node-Liste aus der Datei 'filename' und gibt diese zurück.
	def loadNodeList(self, filename="NodeList1"):
		nodeList=[]
		with open(filename) as f:
			lines = f.readlines();
		for line in lines:
			nodeList.append((int)(line))
		return nodeList
	
	#Fügt diesem Graphen eine Node mit den gegebenen Parametern hinzu.
	def addNode(self, name, gnb, gel, dist=float("inf"), ancestor=None, unvisited=True):
		n = Node(self, name, gnb, gel, dist=dist, ancestor=ancestor, unvisited=unvisited)
		self.nodes.append(n)
		return n
	
	#Fügt diesem Graphen, wenn sie nicht schon existiert, eine Node mit den gegebenen Parametern hinzu.
	def addNodeSafe(self, name, gnb, gel, dist=float("inf"), ancestor=None, unvisited=True):
		if not self.existNode(name):
			n = Node(self, name, gnb, gel, dist=dist, ancestor=ancestor, unvisited=unvisited)
			self.nodes.append(n)
			return n
		else:
			return self.findNode(name)
	
	#Gibt zurück ob die gegebene Edge 'edge' in diesem Graphen existiert.
	def existEdge(self, edge):
		if edge in self.edges:
			return True
		return False
	
	#Gibt zurück ob die gegebene Node 'node' in diesem Graphen existiert.
	def existNode(self, node):
		if(isinstance(node, str)):
			if(any(n.name == node for n in self.nodes)):
				return True
			else:
				return False
		else:
			return False
	
	#Gibt, falls sie existiert, die gesuchte Node als Node-Objekt zurück.
	def findNode(self, node):
		if(self.existNode(node)):
			for n in self.nodes:
				if(n.name==node):
					return n
		elif(isinstance(node, Node)):
				return node
	
	#Fügt eine Edge zwischen den übergebenen Nodes 'node1' und 'node2' mit den gegebenen Parametern ein.
	def addEdge(self, node1, node2, typ, entf=None):
		if(entf==None): entf = node1.calcGeoDist(node2)
		newedge=Edge(self, node1, node2, typ, entf)
		self.edges.append(newedge)
		node1.cEdges.append(newedge)
		node2.cEdges.append(newedge)
	
	#Gibt die Node zurück, die die kleinste Entfernung besitzt.
	def findMinUnvisited(self):
		mindist=float("inf")
		no=None
		for i in self.nodes:
			if i.getunvisited() and i.dist<mindist:
				mindist=i.dist
				no=i
		return no
	
	#Resettet die Wegfinde-Attribute der Nodes dieses Graphen auf den Ausgangszustand.
	def clearNodes(self):
		for n in self.nodes:
			n.ancestor = None
			n.unvisited = True
			n.dist = float("inf")
	
	#Resettet das 'importance' Attribut der Edges dieses Graphen auf 0.
	def clearEdges(self):
		for e in self.edges:
			e.importance=0
	
	#Plottet die Node-Listen 'vinodes' und 'inodes' auf einem Graphen.
	def plotNodeLists(self):
		nodeList1=self.vinodes
		nodeList2=self.inodes
		for nodeCode in nodeList1:
			node=self.findNode(nodeCode)
			plt.plot(node.gel, node.gnb, 'bo')
		
		for nodeCode in nodeList2:
			node=self.findNode(nodeCode)
			plt.plot(node.gel, node.gnb, 'r+')
		plt.show()
	
	#Gibt die Edge mit dem höchsten 'importance' Attribut zurück.
	def mostImportantEdge(self):
		maximp=0
		maxedge=None
		for e in self.edges:
			if e.importance>maximp:
				maxedge=e
				maximp=e.importance
		return maxedge
	
	#Gibt die 'n' Edges mit den höchsten 'importance' Attribut zurück.
	def mostNImportantEdges(self, n):
		es = []
		for i in range(0, n):
			es.append(Edge(None, None, None, 1, 0, -1))
		for e in self.edges:
			if(e.importance > es[-1].importance):
				i = 0
				while(es[i].importance > e.importance):
					i = i + 1
				shiftList(es, i)
				es[i] = e
		return es
	
	#Gibt die 'n' Edges mit den höchsten 'importance' Attribut zurück.
	def mostNImportantNMEdges(self, n):
		es = []
		for i in range(0, n):
			es.append(Edge(None, None, None, 1, 0, -1))
		for e in self.edges:
			if(e.importance > es[-1].importance and e.upgradeExpense(e.typ)<float("inf")):
				i = 0
				while(es[i].importance > e.importance):
					i = i + 1
				shiftList(es, i)
				es[i] = e
		return es

#Verschiebt alle Elemente >k um einen Schritt in der Liste 'l'
def shiftList(l, k):
	for i in reversed(range(k+1, len(l))):
		l[i] = l[i-1]

#Gibt die Aufstufungs-Kosten relativ zur Edge('edge')-Wichtigkeit zurück.
def upgradeGoodness(edge, expenses=None):
	return edge.importance/edge.upgradeExpense(edge.typ, 1, expenses)

#Gibt zurück ob die Distanz-Liste 'distancesList' vollständig ausgefüllt wurde.
def testunfilled(distancesList):
	for i in distancesList:
		if i==-1:
			return True
	return False

#Führt den Dijkstra-Algorithmus auf dem Graphen 'karte' von der 'startnode' mit den Ziel(en) 'target' aus.
def dijkstra_alg(karte, startnode, target=None):
	startnode.dist=0;
	nrvisited=1
	tovisit = Queue.PriorityQueue(len(karte.nodes))
	distancesList=[]
	unfilled=True
	
	for i in range(len(target)):
		distancesList.append(-1)
	
	tovisit.put((0, startnode))
	while(not tovisit.empty() and unfilled):
		node = tovisit.get()[1]
		if(not node.unvisited):
			continue
		node.unvisited=False;
		for t in node.findNeighbors():
			if node.dist+t[0].dist<t[1].dist:
				t[1].dist=node.dist+t[0].dist
				t[0].importance+=1
				if t[1].ancestor!=None:
						t[1].findEdgeTo(t[1].ancestor).importance-=1
				t[1].ancestor=node
				tovisit.put((t[1].dist, t[1]))
		if(node in target or target == None):
			distancesList[target.index(node)]=node.dist
			unfilled=testunfilled(distancesList)
		nrvisited+=1
	return distancesList

#Führt den A*-Algorithmus auf dem Graphen 'karte' von der 'startnode' mit dem Ziel 'target' aus.
def astar_alg(karte, startnode, target=None, weight = 0.1):
	startnode.dist = 0
	nrvisited = 1
	tovisit = Queue.PriorityQueue(len(karte.nodes))
	tovisit.put((0, startnode))
	while(not tovisit.empty()):
		node = tovisit.get()[1]
		if(not node.unvisited):
			continue
		node.unvisited=False;
		for t in node.findNeighbors():
			if node.dist+t[0].dist<t[1].dist:
				t[1].dist=node.dist+t[0].dist
				t[1].ancestor=node
				tovisit.put((t[1].dist + (target.calcGeoDist(t[1]) * weight), t[1]))
		if(node == target):
			return [node.dist, nrvisited]
		nrvisited+=1
	return "Error"

#Oberfunktion für die Wegfindung, entscheidet anhand der Parameter ob Dijkstra oder A* gewählt wird.
def dijkstra(karte, startnode, target=None, weight = 0.1):
	if(target==None or not isinstance(target, Node)):
		return dijkstra_alg(karte, startnode, target)
	elif(isinstance(target, Node)):
		return astar_alg(karte, startnode, target, weight)

#Funktion um den A*-Algorithmus zu testen.
def testAstar(karte, iterations=50, minDis=1000, maxDis=float("inf")):
	randomize_rates(karte)
	totalmaxweight = 1
	testData = []
	for it in range(0, iterations):
		print("|Iteration: %3d/%3d                           |" %(it+1, iterations))
		startNode = None
		targetNode = None
		pathDis = None
		while(pathDis == None):
			karte.clearNodes()
			dis = 0
			while(dis < minDis or dis > maxDis):
				startNode = karte.nodes[randint(0, len(karte.nodes)-1)]
				targetNode = karte.nodes[randint(0, len(karte.nodes)-1)]
				if startNode == targetNode:
					dis = 0
				else:
					dis = startNode.calcGeoDist(targetNode)
			pathDis = dijkstra_alg(karte, startNode, [targetNode])[0]
		karte.clearNodes()
		steps = 100
		visMax = 0
		results = []
		for i in range(0, steps+1):
			result = [i/steps]
			if (result[0]*50)%1 == 0: 
				print("#", end='')
				sys.stdout.flush()
			result = result + astar_alg(karte, startNode, targetNode, result[0])
			if result[2] > visMax: visMax = result[2]
			results.append(result)
			karte.clearNodes()
			karte.clearEdges()
		print("")
		xaxis = []
		yaxis1 = []
		yaxis2 = []
		maxweight = 0.0
		bestweight = 1.0
		bestlength = visMax
		bestweightpath = 0.0
		for result in results:
			if result[0] > maxweight and result[1]/pathDis <= 1.0025:
				maxweight = result[0]
			if result[2] < bestlength:
				bestlength = result[2]
				bestweight = result[0]
				bestweightpath = result[1]
			xaxis.append(result[0])
			yaxis1.append(result[1]/pathDis)
			yaxis2.append(result[2]/visMax)
		testData.append([it+1, maxweight, pathDis])
		if maxweight < totalmaxweight:
			totalmaxweight = maxweight
		print("%3d: %1.3f %5.3f" %(it+1, maxweight, pathDis))
		plt.figure(it+1)
		lines = plt.plot(xaxis, yaxis1, "r-", xaxis, yaxis2, "b-")
		plt.axis([0, 1, 0, 1.6])
		plt.figlegend(lines, ("%5.3f / %5.3f" %(pathDis, bestweightpath), "%1.3f / %1.3f / %1.3f" %(maxweight, bestweight, results[len(results)-1][2]/visMax)), "upper right")
		plt.savefig(("plots/astar_plot_%03d.png" %(it+1)))
		plt.close(it+1)
		plt.figure(iterations+1)
		plt.plot(xaxis, yaxis1, "r-", xaxis, yaxis2, "b-")
		plt.axis([0, 1, 0, 1.6])
	plt.figure(iterations+1)
	plt.savefig(("plots/astar_plot_set.png"))
	plt.close(iterations+1)
	print("Total max weight: %1.3f" %totalmaxweight)
	f = open("plots/data.txt", "w+")
	print("It : Wght  pathDis", file=f)
	for e in testData:
		print("%3d: %1.3f %5.3f" %(e[0], e[1], e[2]), file=f)

#Randomiziert die Stufen der Edges von dem Graphen 'karte'.
def randomize_rates(karte, minRate=0, maxRate=50):
	for e in karte.edges:
		e.rate = randint(minRate, maxRate)

#Weitere Funktion um den A*-Algorithmus zu testen.
def checkWeight(karte, weight=0.2, minDis=1, maxDis=200, tofile=True):
	running = True
	iteration = 0
	results = []
	if(tofile):
		f = open("weightResults", "w+")
	while(running):
		print("Iteration: %d " %iteration, end='')
		startNode = None
		targetNode = None
		pathDis = None
		while(pathDis == None):
			karte.clearNodes()
			karte.clearEdges()
			dis = 0
			while(dis < minDis or dis > maxDis):
				startNode = karte.nodes[randint(0, len(karte.nodes)-1)]
				targetNode = karte.nodes[randint(0, len(karte.nodes)-1)]
				if startNode == targetNode:
					dis = 0
				else:
					dis = startNode.calcGeoDist(targetNode)
			pathDis = (dijkstra(karte, startNode, targetNode))
		pathDis = pathDis[0]
		karte.clearNodes()
		result = astar_alg(karte, startNode, targetNode, weight=weight)
		print("%1.2f, %5.3f" %(pathDis/result[0], pathDis))
		if(result[0] > pathDis):
			print("A* delivered worse result than Dijkstra")
			print("%5.3f > %5.3f" %(result[0], pathDis))
			results.append([iteration, result[0], pathDis, startNode.name, targetNode.name])
			if(tofile):
				print("%d %5.3f %5.3f %s %s" %(iteration, result[0], pathDis, str(startNode.name), str(targetNode.name)), file=f)
		iteration = iteration + 1

#Hauptfunktion um einen Pfad zwischen 'startnode' und 'target' im Graphen 'Karte' zu finden.
def navigator(startnode=None, target=None, Karte=None):
	if(startnode==None):
		startnode=(raw_input("Start: "))
	
	if(target==None):
		target=(raw_input("Ziel : "))

	if(Karte==None):
		print("Loading Karte")
		Karte = load("Graph.save")
		print("Loaded Karte with %d nodes and %d edges" %(len(Karte.nodes), len(Karte.edges)))
	
	start = Karte.findNode(startnode)
	end = Karte.findNode(target)
	print(dijkstra(Karte, start, end))
	printMapWithPath(Karte, end)
	Karte.clearNodes()

#Lädt die Aufstufungskosten aus der Datei 'filename' und gibt diese als Liste zurück.
def loadExpenses(filename="Exp.dat"):
	expList=[]
	finList=[]
	with open(filename) as f:
		lines = f.readlines();
	for line in lines:
		expList.append((int)(line))
	
	i=0
	while i+1<len(expList):
		finList.append([expList[i], expList[i+1]])
		i+=2
	
	return finList

#Überprüft, ob die Edge am Beginn eines ausgebauten Abschnitts liegt
def isend(edge, typ):
	end1=1
	end2=1
	if edge.node1!=None:
		for nn in edge.node1.cEdges:
			if nn.typ==typ:
				end1=0
	else:
		end1=0
	if edge.node2!=None:
		for nn in edge.node2.cEdges:
			if nn.typ==typ:
				end2=0
	else:
		end2=0
	return end1+end2

</code>