===== Optimize.py =====
<code python>
# -*- coding: utf8 -*-
from __future__ import division, print_function

import scipy, scipy.stats
import numpy as np

from GraphFunctions import *
from MapFunctions import *

def optimize(karte=None, money=9000):
	if karte==None:
		karte = load("Graph.save")
	
	#karte.inodes=karte.loadNodeList("inodes.dat")
	#karte.vinodes=karte.loadNodeList("vinodes.dat")
	karte.defineINodesRandom(100)
	karte.defineVINodesRandom(5)
	Exp=loadExpenses()
	arate=rateGraph(karte, False, karte.inodes, karte.vinodes)
	print(arate)
	print("BEGINN DES OPTIMIERUNGSPROZESSES")
	
	optBackbone(karte, 0.5*money)
	#0.5 das beste???
	
	for n in karte.vinodes:
		optsubnet(money*0.1, karte, n, 500)
	print("ENDE DES OPTIMIERUNGSPROZESSES")
	arate=rateGraph(karte, False, karte.inodes, karte.vinodes)
	print(arate)
		
def optsubnet(money=0, karte=None, node=None, maxEntf=500):
	explist=loadExpenses()
	if karte==None:
		print("Loading Graph...")
		karte = load("Graph.save")
		print("Graph loaded")
	inodeslist=splitGraph(karte, node, maxEntf)
	inodes=chooserandom(inodeslist, 200)
	oldmoney=-1
	while money>0 and money!=oldmoney:
		oldmoney=money
		print(money)
		karte.clearEdges()
		print(rateGraph(karte, False, inodes, [node]))
		iedges=karte.mostNImportantNMEdges(2000)
		bedges=findNBuildEdges(iedges, 600, explist)
		for e in bedges:
			money-=build(e[0], e[0].typ+1, explist)

def chooserandom(liste, number):
	returnlist=[]
	numberofnodes=len(liste)
	for i in range(number):
		returnlist.append(liste[random.randint(0,numberofnodes-1)])
	return returnlist
	
def optBackbone(karte, money):
	explist=loadExpenses()
	oldmoney=-1
	while money>0 and money!=oldmoney:
		oldmoney=money
		print(money)
		
		karte.clearEdges()
		print(rateGraph(karte, False, karte.vinodes, karte.vinodes))
		iedges=karte.mostNImportantNMEdges(2000)
		bedges=findNBuildEdges(iedges, 600, explist)
		for e in bedges:
			money-=build(e[0], e[0].typ+1, explist)
		

def splitGraph(karte=None, startnode=None, maxEntf=500):
	if karte==None:
		print("Loading Graph...")
		karte = load("Graph.save")
		print("Graph loaded")
	if startnode==None:
		startnode=karte.nodes[0]
	print("Building new Graph...")
	newMap=[]
	startnode.dist=0
	nrvisited=1
	tovisit=Queue.PriorityQueue(len(karte.nodes))
	
	tovisit.put((0,startnode))
	
	lastdist=0
	
	while(not tovisit.empty() and lastdist<maxEntf):
		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, t[1]))
				if not isin(t,newMap):
					newMap.append(t)
		if not isin(node,newMap):
			newnode=newMap.append(node)
		lastdist=node.dist
		
	#printMap(newMap, "splitted.osm")
	karte.clearNodes()
	print("Subnet building process finished")
	return newMap

def isin(item, li):
	for l in li:
		if l==item:
			return True
	return False
		
def build(edge, typ, expenses):
	oldtype=edge.typ
	edge.typ=typ
	edge.dist=edge.entf/typ
	back=0
	for i in expenses:
		if i[0]<=oldtype:
			back=edge.entf*i[1]
	
	
	for i in expenses:
		if i[0]>=typ:
			return edge.entf*i[1]-back+isend(edge, typ)*100*i[1]
	
def findNBuildEdges(elist, n=1, expenses=None):
	if expenses==None:
		expenses=loadExpenses()
	es = []
	for i in range(0, n):
		es.append((Edge(None, None, None, 1, 0, -1), 0))
	for e in elist:
		if(upgradeGoodness(e) > es[-1][1]):
			i = 0
			while(es[i][1] > upgradeGoodness(e, expenses)):
				i = i + 1
			shiftList(es, i)
			es[i] = (e, upgradeGoodness(e, expenses))
	return es

def rateGraph(g=None, undefined=True, inodes=None, vinodes=None):
	
	if g==None:
		g = ModMap.load("Graph.save")
	
	if undefined:
		g.defineINodesRandom(1000)
		g.defineVINodesRandom(50)
	
	if inodes==None:
		inodes=g.inodes
	
	if vinodes==None:
		vinodes=g.vinodes
	
	distsum=0
	distprod=1
	
	numList =[]
	dist=[]
	counter=0
	for snode in vinodes:
		dist.append(dijkstra(g, snode, inodes))
		g.clearNodes()
		counter+=1
		print(counter)
	
	counter=0
	if dist!=None:
		for i in dist:
			if i!=None:
				for numb in i:
					if numb != -1:
						numList.append(numb)
	
	arithmetic=np.mean(numList)
	geometric=scipy.stats.mstats.gmean(numList)
	g.saveAllNodeLists()
	g.saverate()
	return (geometric, arithmetic)

if __name__ == "__main__":	
	optimize()
</code>