VORBEREITENDES - First things fist
Mein System ist wie folgt aufgebaut. Ich importiere:
- Daten der Wiener Linien zu UBahn-Stationen. Es handelt sich um CSV-Daten die online abgerufen werden. Die wichtigen Daten für mich aus diesem Import sind: Stationsname, ID, Koordinaten
- Daten von Wikidata zum UBahn-Systen in Wien. Dies ist eine SPARQL Abfrage. Die wichtigen Daten aus der Abfrage: ID, benachbarte Stationen (um die Linie nachzubauen), Linien die mit der Station verbunden sind.
- weiter unten werden dann noch 2 weitere CSV-Dateien von data.gv.at importiert. Die Informationen zu Trinkwasserbrunnen in Wien und die Informationen zu Freibädern in Wien. Bei den Trinkbrunnen interessieren mich nur die Koordinaten und bei den Bädern Name und Koordinaten.
All das soll zusammengeführt werden, sodass sich die Möglichkeit ergibt zu sagen welche Station sich in der Nähe von einem Bad befindet wobei im Umkreis des Bades sich auch ein Trinkwasserbrunnen befinden soll. Das coole an dem Ganzen wird sein, dass man im Endeffekt angeben kann wo man startet und in welchem Bezirk man schwimmen gehen möchte. Ausgehend vom Standort wird das näheste Bad mit Trinkwasserbrunnen gewünschten Bezirk vorgeschlagen.
Weiters wird das Programm dazu in der Lage sein den Benutzer zur ausgegebenen Zielstation zu navigieren. Das Programm wird angeben welche Linie man nehmen muss, wieviele Stationen man fahren muss, wo und in welche Linie man umsteigen muss und auch in welche Richtung man jeweils fahren muss um zu seiner Zielstation zu kommen.
Zuerst importiere ich einige Math Module die notwendig sein werden. Ich definiere eine Funktion die die Differenz (in Metern) zwischen 2 Koordinaten berechnet. Die Funktion erhält 4 String-Koordinaten die innerhalb der Funktion in int umgewandelt werden. Python sei dank, klappt typeconversion ja viel einfacher als zB in Java.
from IPython.core.display import display, HTML
display(HTML("<style>.container { width:100% !important; }</style>"))
from math import radians, cos, sin, asin, sqrt
def haversine(coords):
lat1 = float(coords[0])
lon1 = float(coords[1])
lat2 = float(coords[2])
lon2 = float(coords[3])
lon1, lat1, lon2, lat2 = map(radians, [lon1, lat1, lon2, lat2])
# haversine formula
dlon = lon2 - lon1
dlat = lat2 - lat1
a = sin(dlat/2)**2 + cos(lat1) * cos(lat2) * sin(dlon/2)**2
c = 2 * asin(sqrt(a))
# Radius of earth in kilometers is 6378
m = 6378* c * 1000
return m
distance = haversine(['16.368679459080123', '48.200461908387354', '16.44325652441458', '48.25022254396772'])
print("Karlsplatz und Kagraner Platz sind " + str(round(distance, 2)) + " Meter voneinander entfernt")
WIe man hier sieht habe ich die Formel für Karlsplatz und Kagraner Platz getestet. Ein vielversprechendes Ergebnis.
ZWEITER TEIL - IMPORTING CSV FILE FROM "Echtzeitdaten Wr. Linien" bzw. data.gv.at
Jetzt wird pandas, csv and sqlite3 importiert. Alle 3 sind notwendig um die CSV Datei und die SPARQL Abfrage (später) durchzuführen. Natürlich wird auch die SQL Extansion geladen sowie die Verbindung zu einer DB namens "stations" hergestellt. Um die Tabellen importieren zu können wird noch die conn-Variable gesetzt.
import pandas as pd
import csv
import sqlite3
import codecs
%load_ext sql
%sql sqlite:///stations.db
conn = sqlite3.connect('stations.db')
um sicherzustellen, dass das Notebook richtig arbeitet:
%%sql
PRAGMA foreign_keys = ON;
drop table if exists stations_blank
Nun wird die CSV Datei von der Online Ressource importiert. (data.gv.at) data.gv.at hat immer wieder Aussetzer. Es kann manchmal vorkommen, dass Daten nicht geladen werden können. Sollte das länger der Fall sein habe ich alle CSV Dateien zur Not gesichert und kann Ihnen schnell das Notebook umschreiben, sodass es mit offline Daten arbeitet.
import requests
r = requests.get('https://data.wien.gv.at/daten/geo?service=WFS&request=GetFeature&version=1.1.0&typeName=ogdwien:UBAHNHALTOGD&srsName=EPSG:4326&outputFormat=csv')
#r = requests.get('D:/uni/SS2020/Data & Knowledge Engineering/Abschlussarbeit/UBAHNHALTOGD.csv')
f = open('stations_blank.csv', 'wb')
f.write(r.content)
f.close()
pd.read_csv('stations_blank.csv').to_sql('stations_blank', conn, index = False)
Arbeitet wie erwartet. Die Datei wurde in die SQLite Table "stations_blank" importiert.
queryStations = %sql select * from stations_blank limit 11
print(queryStations)
Ich bin mit dem Ergebnis sehr zufrieden. Im nächsten Codeblock sortiere ich die Stationen nach der Ubahn-Linie. Das ist zwar nicht unbedingt notwendig aber ich finde es so cleaner.
def sortLines(unsortedStations):
sortedLines = []
for i in range(1, 7):
for row in queryStations:
if row[3] == i:
sortedLines.append(row)
return sortedLines
w = sortLines(queryStations)
print(w)
count = 0;
for row in sortLines(queryStations):
count += 1
print(row, count)
Allright! First part is done. Der importiert hat sehr gut funktioniert. Die Stationen sind sortiert nach UBahn-Linie.
THIRD PART - SPARQL QUERY its time to import the sparql query
from SPARQLWrapper import SPARQLWrapper, JSON, CSV
sparql = SPARQLWrapper("https://query.wikidata.org/sparql")
Anmerkungen zur SPARQL-Abfrage. Die Abfrage ist in erster Linie wichtig um die benachbarten Stationen zu erhalten. Zuerst habe ich mir UBahn-Stationen herausgesucht die sich in Österreich befinden. EIne weitere Einschränkung ist nicht nötig weil ja nur in Wien eine UBahn vorhanden ist. Somit habe ich einmal alle UBahn-Stationen. Weiters werden die benachbarten Stationen einer Station importiert und diese werden gruppiert damit es keine Dubletten gibt. Außerdem werden auch die betreffenden Linien einer Station gruppiert. zB Praterstern = U1 und U2. Ich habe noch ein wenig zu den einzelnen SPARQL Zeilen kommentiert was genau passiert.
sparql.setQuery("""
#Metro Stations
#because there are more than just 1 adjacent station i will need to group the adjacent station as well as the lines
#else i would have 2 rows for every station and/or every line -> redundancies
SELECT ?item ?itemLabel (group_concat(distinct ?stationName;separator=',') as ?stationNames) ?id
(group_concat(?nextStation) as ?nextStations)
(group_concat(?line) as ?lines)
(group_concat(distinct ?lineName;separator=',') as ?lineNames)
#to avoid duplicates in the nextStations as well as in the lines "array" i use the distinct keyword.
WHERE
{
#query all items which are instance of (P31) a metro station (q928830)
#query only metro stations located in austia. gives back all 400 stations!
#get the station id
?item wdt:P296 ?id .
#filter station id by length AND only if it not contains " " .
#because there are some other id's also in the wiki database like "E3 H2" or "DK"
#for my key i need the 5 digits number
filter(((strlen(?id)) = 5) && !contains(?id, " ") ) .
#item has to be an instance of "metro station"
?item wdt:P31 wd:Q928830 .
#item has to be located in austria
?item ?austria wd:Q40 .
#give back the value of the adjacent stations. sometimes 1 most times 2.
?nextStation wdt:P197 ?item .
#filter only next stations which are a metro station and not eg. SBAHN Stations
?nextStation wdt:P31 wd:Q928830 .
?nextStation rdfs:label ?stationName .
filter(lang(?stationName) = 'de') .
?item wdt:P81 ?line .
?line rdfs:label ?lineName .
?line wdt:P361 wd:Q209400 .
filter(lang(?lineName) = 'en') .
SERVICE wikibase:label { bd:serviceParam wikibase:language "[AUTO_LANGUAGE],en". }
}
group by ?item ?itemLabel ?id
LIMIT 150
""")
sparql.setReturnFormat(JSON)
stationsWithAdjacents = sparql.query().convert()
Mal sehen wie diese Query funktioniert hat. Alles so wie geplant. Um mit dem Outcome zu arbeiten exportiere ich die Daten in eine neue CSV File.
from IPython.display import HTML, display
tab = '<table>'
for res in stationsWithAdjacents["results"]["bindings"]:
tab += '<tr><td>%s<td>%s<td>%s<td>%s' % (res["itemLabel"]["value"],
res["stationNames"]["value"],
res["lineNames"]["value"],
res["id"]["value"])
display(HTML(tab+'</table>'))
#create new table
f = open('stationsWithAdjacents.csv', "w", encoding='utf8')
f.write("station;adjacent;line;key\n")
for res in stationsWithAdjacents["results"]["bindings"]:
f.write(res["itemLabel"]["value"] + ";" + res["stationNames"]["value"] + ";" + res["lineNames"]["value"] + ";" + res["id"]["value"] + "\n")
f.close()
%sql drop table if exists stationsWithAdjacents;
#csv to sql
pd.read_csv('stationsWithAdjacents.csv', delimiter=";").to_sql('stationsWithAdjacents', conn, index = False)
# new variable with the selection of all items in the new sql table
stationsWithAdjacents = %sql SELECT * from stationsWithAdjacents
Durch die Gruppierungen habe ich bereits quasi "Arrays" für die Nachbarsstationen und die Linien. Das finde ich sehr cool. Um mit den Daten dann weiterzuarbeiten ist das eine große Hilfe. Die letzte Spalte ist für den Schlüssel. Ich möchte nun die bereits importierte CSV von data.gv.at mit dieser Tabelle vereinen. Das gelingt über den Schlüssel. Damit habe ich dann die Koordinaten und die benachbarten Stationen in einer Tabelle. Dort wollte ich hin. Die OBJECTID aus der 1. csv Tabelle war auf wikidata leider nicht vorhanden. Ich habe lange überlegt wie ich die beiden Tabellen ohne exakten Schlüssel verbinden kann. Alle recherchierten Varianten schienen aber eher schlecht als recht zu sein. Hier wäre ich über ein Feedback sehr dankbar wie man solche Dinge zusammenführen kann. Meine Gedanken gingen in Richtung Teilstring des Stationsnamen abgleichen mit dem Stationsnamen aus Wikidata. Ich glaube das hätte nicht sonderlich gut funktioniert.
Ich habe mich schlussendlich dazu entschieden der Allgemeinheit (und mir) einen Gefallen zu tun und habe die OBJECTID auf Wikidata implementiert. Ich hoffe andere Nutzer können von diesen Informationen profitieren. Dazu habe ich die OBJECTID von den Wiener Linien verwendet und auf Wikidata auch die Echtzeitdaten der Wiener Linien als Referenz angegeben.
Es ist zwar nicht ganz sauber aber ich denke diese Vorgehensweise könnte sich auch bei einem echten Projekt als sinnvoll herausstellen zumal die Daten ja überschaubar sind. Wie gesagt wäre ich aber froh hier zu erfahren wie man das besser macht. Ich gehe davon aus, dass ich in meiner zukünftigen Tätigkeit öfters mit solchen Problemen konfrontiert bin.
UPDATE zur OBJECTID: Ich habe mich mit den Wiener Linien dbzgl. zusammen gesprochen. Die OBJECTID ist leider nicht als Referenzschlüssel geeignet da sich dieser ab und an ändern kann. Sollte sich die OBJECTID während dem Benoten meiner Arbeit ändern und somit alles nicht mehr funktionieren geben Sie mir bitte Bescheid. Dann ändere ich die OBJECTID nochmal kurz zum Benoten. Nach der Benotung werde ich die OBJECTID wieder von Wikidata löschen. Ich habe noch ein Telefongespräch nächste Woche mit den Wiener Linien dbzgl. Hier wird mir hoffentlich mitgeteilt was man als Schlüssel verwenden kann. Ich werde das weiter verfolgen und einen entsprechenden Key auf Wikidata einfügen.
FOURTH PART - COMBINING THE 2 TABLES stations_blank and stationsWithAdjacents
%%sql
select HTXT, adjacent, line, SHAPE, OBJECTID from stations_blank JOIN stationsWithAdjacents on OBJECTID = key;
Nachdem der Code ja eindeutig ist, ist die Verbindung der beiden Tabellen kein Problem mehr. Es handelt sich quasi um die finalen Daten. Deshalb hat die Abfrage den Namen finalQuery erhalten. Alles was ich für die weitere Bearbeitung benötige habe ich nun. Ich habe nur die Daten selektiert die ich in weiterer Folge benötigen werde.
finalQuery = %sql select HTXT, adjacent, line, SHAPE, OBJECTID from stations_blank JOIN stationsWithAdjacents on OBJECTID = key
Ich prüfe nun ob alle Stationen tatsächlich vorhanden sind. Die originale CSV Datei von den Wr Linien hat 99 Einträge aber es gibt einen redundanten Eintrag in dieser Liste. Die Station Karlsplatz ist 2x vorhanden. Meine Tabelle ist deshalb korrekt mit 98 Einträgen. Karlsplatz hat auch 2 OBJECTID's in der CSV Datei der Wiener Linien. Ich werde versuchen dies den Verantwortlichen der Wiener Linien mitzuteilen weil dies bestimmt nicht beabsichtigt ist.
countFinal = 0
for row in finalQuery:
countFinal += 1
print(row[0], row[1], row[2], row[4], countFinal)
FIFTH PART - Create the Class STATION
Für diesen Part ist der Plan eine Stationsklasse zu erstellen. Die Klasse soll dann als Fields alle Daten haben die ich importiert habe. Für jede Station wird automatisch ein Objekt erstellt. Das field "name" der jeweiligen Station wird automatisch generiert.
class Station:
def __init__(self, name, objectId=None, line=None, coords=None, changeLine=None, adjacentStation=None, hasWater=None, hasPool=None):
self.name = name.lower()
self.objectId = objectId or 123456
self.line = line or "UBAHN not defined"
self.coords = coords or ["12.34567890", "12.34567890"]
self.changeLine = changeLine or []
self.adjacentStation = adjacentStation or ["testStation1", "testStation2"]
self.hasWater = hasWater or False
self.hasPool = hasPool or False
Hier wird die Klasse konstruiert. Untenstehend wird ein Array erstellt aus allen Namen (Spalte HTXT aus der Abfrage).
classNamesStation = []
for i in range(len(finalQuery)):
classNamesStation.append(finalQuery[i][0])
print(classNamesStation)
Weiters wird dann über dieses Array iteriert und mit den Namen alle Stationsobjekte erstellt. Die anderen Felder haben erstmal Standardwerte. Die korrekten Werte werden später eingetragen.
stationsObj = []
for name in classNamesStation:
stationsObj.append(Station(name))
Untenstehend werden folgende Schritte ausgeführt: Die Linien und die Koordinaten werden in alle Stationen eingefügt. Für die Koordinaten wird ein Substring verwendet der dann auch noch gesplittet wird. Somit erhält meine Instanz der Stationsklasse in den Korrdinaten ein Array mit 2 Strings. Die Daten sind bereits so formatiert, dass sie an meine Formel zur Berechnung der Distanz übergeben werden können. Auch die benachbarten Stationen werden gleich gesplittet und sind somit als String Array enthalten. changeLine = Line. Eigentlich wäre das ja somit nicht notwendig. Evtl. nehme ich das also noch raus. (das ist mir beim Kommentieren aufgefallen)
for i in range(len(finalQuery)):
stationsObj[i].line = (finalQuery[i][2]).split(",")
stationsObj[i].coords = ((((finalQuery[i][3])[7:])[:-1]).split(" "))
stationsObj[i].adjacentStation = (finalQuery[i][1]).split(",")
stationsObj[i].changeLine = stationsObj[i].line
stationsObj[i].objectId = int(finalQuery[i][4])
Untenstehend ein Test. WIe Sie sehen wurde die Station Praterstern korrekt implementiert. Ein Test über Google Maps hat gezeigt, dass auch die Koordinaten stimmen.
print(stationsObj[47].name)
print(stationsObj[47].line)
print(stationsObj[68].coords)
print(stationsObj[68].adjacentStation)
print(stationsObj[47].changeLine)
stationsObj[51].adjacentStation
SIXTH PART - STATIONSOBJEKTE ALS benachbarte Stationen einfügen
Das Ziel ist es in diesem Abschnitt die String-Stationen im Array adjacentStation mit den Objekten der Stationen selbst zu ersetzen. Jetzt sind leider ein paar händische Korrekturen notwendig. Die benachbarten Stationen beginnen manchmal mit "Wien" oder "U-Bahn-Station" Um das auszugleichen wird das hier entfernt.
TEIL A - vorbereitung und Korrekturen der Daten
Das ist nicht besonders schön und man kann das sicher besser machen. Da mein Hauptaugenmerk aber nicht daruaf liegt belasse ich dies so und gebe mich damit zufrieden.
for i in range(len(stationsObj)):
adjacent = len(stationsObj[i].adjacentStation)
for station in range(adjacent):
stationsObj[i].adjacentStation[station] = stationsObj[i].adjacentStation[station].lower()
if "u-bahn-station" in stationsObj[i].adjacentStation[station]:
print(stationsObj[i].adjacentStation[station])
stationsObj[i].adjacentStation[station] = stationsObj[i].adjacentStation[station][15:]
for i in range(len(stationsObj)):
adjacent = len(stationsObj[i].adjacentStation)
for station in range(adjacent):
if "ottakring" in stationsObj[i].adjacentStation[station] :
print(stationsObj[i].adjacentStation[station])
stationsObj[i].adjacentStation[station] = stationsObj[i].adjacentStation[station][13:]
for i in range(len(stationsObj)):
adjacent = len(stationsObj[i].adjacentStation)
for station in range(adjacent):
if "wien " in stationsObj[i].adjacentStation[station]:
print(stationsObj[i].adjacentStation[station])
stationsObj[i].adjacentStation[station] = stationsObj[i].adjacentStation[station][5:]
Hier werden noch einige Namensprobleme beseitigt. Erneut, hier gibt es Potential um das besser zu machen. Vor allem automatisiert aber ich wollte nicht zu viel Zeit dafür vergeuden.
stationsObj[68].name = "praterstern"
stationsObj[32].name = "hauptbahnhof"
stationsObj[22].name = "messe-prater"
stationsObj[58].name = "landstraße"
stationsObj[65].name = "meidling"
stationsObj[87].name = "währinger straße"
stationsObj[63].name = "ober st. veit"
stationsObj[36].name = "ottakring"
stationsObj[36].name
for station in stationsObj[88].adjacentStation:
if type(station) != str:
print(station.name)
TEIL B - Überführen der Stationsobjekte als benachbarte Stationen, bis hier waren es ja nur Strings
stationsObj[0].name
stationsObj[0].adjacentStation
for testi in range(len(stationsObj)):
for station in range(len(stationsObj[testi].adjacentStation)):
for i in range(len(stationsObj)):
if stationsObj[testi].adjacentStation[station] == stationsObj[i].name:
stationsObj[testi].adjacentStation[station] = stationsObj[i]
Untenstehend soll geprüft werden ob tatsächlich alles funktioniert hat. Beim unten stehenden Beispiel sieht man schön, dass die Station Ottakring als benachbarte Stationen nun 2 Objekte hat. Ich habe alle Stationen durchgetestet und bin dabei auf einige Namensprobleme gestoßen. Deshalb weiter oben die Korrekturen. Nachdem alle Stationen durchgetetstet sind bin ich sehr froh über das Ergebnis. Ich bin meinem Ziel, dass U-Bahn-System Wiens nachzubauen ein sehr großes Stück näher gekommen. Jetzt kann ich mich daran machen die Linien zu bauen.
print(stationsObj[4].adjacentStation)
for station in stationsObj[4].adjacentStation:
print(station)
print(station.name)
#automated test if every station has a object as adjacent Sation and not a string
for i in range(len(stationsObj)):
for station in stationsObj[i].adjacentStation:
print(type(station), stationsObj[i].name)
Abschließend, da jetzt alle Stationsobjekte fertig sind noch ein kurzer Test ob die Formel von mir funktionieren wird:
stationsObj[77].adjacentStation
haversine(stationsObj[34].coords + stationsObj[0].coords)
Great! Das sind die Punkte: Am Schöpfwerk und Kagran. Ich habe in einem Online Berechnungsprogramm für Distanzen mein Ergebnis verglichen. Meine Kalkulation liegt nur um einen Meter neben der Online Berechnung. Ich bin mit dem Ergebnis sehr zufrieden und denke, dass mein Projekt ein Erfolg wird :)
SIXTH PART - DOUBLY LINKED LIST ERSTELLEN
In diesem Part möchte ich die Linien erstellen. Dazu benötige ich allerdings 2 neue Klassen um eine doppelt verkettete Liste zu erstellen. Ich denke für eine UBahn Linie macht das Konzept der doubly linked list viel Sinn! Die erste Klasse beschreibt einen Knoten. Die doubly linked list erhält dann einige Funktionen die dann wichtig sind. Ich habe also eine Endstation (oder Startstation, je nach Sichtweise) die nur eine benachbarte Station hat. Von diesem Startpunkt aus folge ich den benachbarten Stationen bis ich am Ende der Linie ankomme. Das ist dann der Fall wenn auf der selben Linie keine weitere benachbarte Station mehr vorhanden ist.
Anmerkung: Die Klasse DoublyLinkedList wurde im Verlauf der weiteren Bearbeitung um immer mehr Funktionen erweitert.
class Node:
def __init__(self, station):
self.station = station
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.start_node = None
#insert a new node in an empty list
def insert_in_emptylist(self, data):
if self.start_node is None:
new_node = Node(data)
self.start_node = new_node
else:
print("list is not empty")
#insert a new node at the end of the list
def insert_at_end(self, data):
if self.start_node is None:
new_node = Node(data)
self.start_node = new_node
return
n = self.start_node
while n.next is not None:
n = n.next
# for adjacent in n.station.adjacentStation:
# if adjacent == data.name:
new_node = Node(data)
n.next = new_node
new_node.prev = n
def get_lastStation(self):
if self.start_node is None:
print("Nothin in List")
n = self.start_node
while n.next is not None:
n = n.next
return n
def get_nextLastStation(self, startStation):
current = self.search_node(startStation)
while current.next is not None:
current = current.next
return current.station
def get_prevLastStation(self, startStation):
current = self.search_node(startStation)
while current.prev is not None:
current = current.prev
return current.station
def get_prevStation(self, searchedStation):
if self.start_node is None:
print("Nothin in List")
n = self.start_node
while n.next is not None:
if n.station == searchedStation:
return n.station.prev.station.name
n = n.next
if n is None:
print("not in list")
def traverse_list(self):
if self.start_node is None:
print("List has no element")
return
else:
n = self.start_node
while n is not None:
print(n.station.name , " ")
n = n.next
def search_list(self, element):
current = self.start_node
index = 1
while current != None:
if current.station == element:
return index
current = current.next
index += 1
return - 1
######################################################### Start Navigation Algorithm
def search_node(self, element):
current = self.start_node
while current != None:
if current.station == element:
return current
current = current.next
def search_lineNext(self, line, startStation):
#the var line is the line which i am looking for. i want to find a station where it is possible to change to the needed line. eg im searching for U2 if i want to get to WU Wien from U1.
#current node = Result of search node. Eg. Praterstern is in the middle of the Line. I want to start my search from Praterstern not from Leopoldau or Oberlaa
current = self.search_node(startStation)
index = 0
travelTo = []
while current != None:
for changeline in current.station.line:
if changeline == line:
travelTo.append(current.station)
travelTo.append(index)
return travelTo
current = current.next
index += 1
return -1
def search_linePrev(self, line, startStation):
#the var line is the line which i am looking for. i want to find a station where it is possible to change to the needed line. eg im searching for U2 if i want to get to WU Wien from U1.
#current node = Result of search node. Eg. Praterstern is in the middle of the Line. I want to start my search from Praterstern not from Leopoldau or Oberlaa
current = self.search_node(startStation)
index = 0
travelTo = []
while current != None:
for changeline in current.station.line:
if changeline == line:
travelTo.append(current.station)
travelTo.append(index)
return travelTo
current = current.prev
index += 1
return -1
def search_stationNext(self, startStation, targetStation):
current = self.search_node(startStation)
index = 0
travelTo = []
while current is not None:
if current.station == targetStation:
travelTo.append(index)
return index
current = current.next
index += 1
return -1
def search_stationPrev(self, startStation, targetStation):
current = self.search_node(startStation)
index = 0
travelTo = []
while current is not None:
if current.station == targetStation:
travelTo.append(index)
return index
current = current.prev
index += 1
return -1
def search_knotNext(self, startStation):
current = self.search_node(startStation)
index = 0
travelTo = []
while current is not None:
if len(current.station.line) > 1 and startStation != current.station:
travelTo.append(current.station)
travelTo.append(index)
return travelTo
current = current.next
index += 1
travelTo = [-1]
return travelTo
def search_knotPrev(self, startStation):
current = self.search_node(startStation)
index = 0
travelTo = []
while current is not None:
if len(current.station.line) > 1 and startStation != current.station:
travelTo.append(current.station)
travelTo.append(index)
return travelTo
current = current.prev
index += 1
travelTo = [-1]
return travelTo
SEVENTH PART - FUNKTION UM LINIEN AUTOMATISCH ZU ERSTELLEN
Hier geht es jetzt ziemlich ans Eingemachte. Mein Ziel war es eine Linie als String zu übergeben und für diese Linie dann automatisch die komplette Linie zu erstellen. Zurückgegeben wird eine fix und fertige Linked List für zb die U1. Jede Linie klappte eigentlich gut. Ich hatte aber ein Problem mit der Linie U2. Die Endstation Karlsplatz stellte mich Herausforderungen. Meine While-Schleife geht so lange bis eine Station nur mehr eine Nachbarstation hat. Das klingt zwar vernünftig weil ja jede Endstation normalerweise nur einen Nachbarn hat. Das klappt aber nicht bei Karlsplatz denn der hat 5 Nachbarstationen ist aber dennoch Endstation der U2. Ich habe dann eine Kondition implementiert die mitzählt wie oft die Linie (in diesem Fall die U2) NICHT in den Nachbarstationen vorkommt. Wenn dies für alle Nachbarstationen bis auf eine zutrifft und der Counter somit gleich groß ist wie die Anzahl der (Nachbarstationen)-1 ist klar, dass es sich hier um eine Endstation handelt. Und somit habe ich auch das geschafft. Die Linien können nun automatisiert erstellt werden.
#insert the first Node. I search for a station with only one adjacent station. This has to be an endstation.
#the if loop breaks when found one. i dont need the second endstation. from here on i will walk trough
#the adjacent stations and insert the next adjacent station into the linked list till there are no more
#stations to add
def createLine(line):
u = DoublyLinkedList()
for i in range(len(stationsObj)):
if ((len(stationsObj[i].adjacentStation) < 2) and (line in stationsObj[i].line) and u.start_node == None):
u.insert_in_emptylist(stationsObj[i])
if len(u.get_lastStation().station.adjacentStation) < 2 and u.get_lastStation().prev == None:
u.insert_at_end(u.get_lastStation().station.adjacentStation[0])
lastStation = u.get_lastStation()
while len(lastStation.station.adjacentStation) > 1 and lastStation.station.adjacentStation:
for station in lastStation.station.adjacentStation:
#the search function gives back -1 if the new station is not already in the linked list.
#so the next station which follows must fulfill 2 conditions: it is not in the list already and the current line is in the line field of the station.
#this could only be true for exact one adjacent station. every other station cannot have the same line in its line field.
if u.search_list(station) < 0 and line in station.line:
u.insert_at_end(station)
lastStation = u.get_lastStation()
#in case a endstation has more than 1 adjacent station. eg karlsplatz. i need another condition.
#else i would be stuck in an endless loop cause there are always more than 1 adjacentstation in this last station
counter = 0
for everyAdjacent in lastStation.station.adjacentStation:
if line not in everyAdjacent.line:
counter += 1
if counter == len(lastStation.station.adjacentStation)-1:
return u
return u
Ich wollte es unbedingt schaffen die Linien automatisch zu erstellen. Dazu habe ich eine kleine Schleife geschrieben die ein Array mit allen Linien erstellt. Danach wird anhand dieses Arrays ein dictionary erstellt mit den Linien als Key und der Funktion die eine Linie erstellt als value. Der Key wird gleichzeitig als Argument übergeben weil dieses für die Erstellung der Linie ja benötigt wird. Die Funktion gibt die fertige Linie zurück und alle Linien sind fertig. Nun habe ich ein navigierbares UBahnsystem.
baseLines = []
for station in stationsObj:
for line in station.line:
if line not in baseLines:
baseLines.append(line)
finalLines = { i : createLine(i) for i in baseLines }
print(finalLines)
Beispielhaft die U4 sowie die U6:
print("UBAHN LINIE U4")
finalLines["U4"].traverse_list()
print(" ")
print("UBAHN LINIE U6")
finalLines["U6"].traverse_list()
EIGHTH PART - Import Koordinaten der Trinkbrunnen und der öffentlichen Bäder
Die Dateien gibt es wieder online und zwar in mehreren Formaten. Ich importiere erneut im csv Format.
%%sql sqlite:///stations.db
%sql drop table if exists water
%sql drop table if exists communalPool
conn = sqlite3.connect('stations.db')
r = requests.get('https://data.wien.gv.at/daten/geo?service=WFS&request=GetFeature&version=1.1.0&typeName=ogdwien:TRINKBRUNNENOGD&srsName=EPSG:4326&outputFormat=csv')
f = open('water.csv', 'wb')
f.write(r.content)
f.close()
pd.read_csv('water.csv').to_sql('water', conn, index = False)
%sql SELECT * FROM water limit 10
water = %sql SELECT SHAPE, NAME from water
Das Funktioniert ausgezeichnet. Schleife unten gibt Die UBahn Stationen aus in deren Umkreis von 250m ein Wasserbrunnen ist. Die Stationsobjekte bekommen ein "True" in ihrem hasWater-field
for i in range(len(stationsObj)):
for row in range(len(water)):
if haversine(stationsObj[i].coords + water[row][0][7:][:-1].split(" ")) < 250:
stationsObj[i].hasWater = True
print(str(int(haversine(stationsObj[i].coords + water[row][0][7:][:-1].split(" ")))) + " meter" )
print(stationsObj[i].name)
print(water[row][1])
print("")
r = requests.get('https://data.wien.gv.at/daten/geo?service=WFS&request=GetFeature&version=1.1.0&typeName=ogdwien:SCHWIMMBADOGD&srsName=EPSG:4326&outputFormat=csv')
f = open('communalPool.csv', 'wb')
f.write(r.content)
f.close()
pd.read_csv('communalPool.csv').to_sql('communalPool', conn, index = False)
%sql select SHAPE, NAME, BEZIRK, AUSLASTUNG_AMPEL_KAT_TXT_0, WEBLINK1 from communalPool limit 10
pools = %sql select SHAPE, NAME, BEZIRK, AUSLASTUNG_AMPEL_KAT_TXT_0, WEBLINK1 from communalPool
Nun kann auch schon die Kombination erfolgen. Ich gleiche alle Stationskoordinaten mit allen Koordinaten der Bäder ab. Die Entfernung soll unter 1000m liegen und der Bezirk kann mittels Argument übergeben werden wenn die Funktion aufgerufen wird. Der Output passt super. Ich habe das wieder mittels Google Maps verglichen und meine Ergebnisse sind aussagekräftig. Ich packe das in eine Funktion weil ich das dann später noch verwende! Außerdem füge ich den Stationsobjekten noch im Field hasPool ein True hinzu.
for i in range(len(stationsObj)):
for row in range(len(pools)):
if haversine(stationsObj[i].coords + pools[row][0][7:][:-1].split(" ")) < 1000:
stationsObj[i].hasPool = True
print(str(int(haversine(stationsObj[i].coords + pools[row][0][7:][:-1].split(" ")))) + " meter" )
print(stationsObj[i].name)
print(pools[row][1])
print("")
def searchForPoolsWithWater(district):
result = []
for i in range(len(stationsObj)):
for row in range(len(pools)):
if haversine(stationsObj[i].coords + pools[row][0][7:][:-1].split(" ")) < 1000 and pools[row][2] == district:
stationsObj[i].hasPool = True
#print(str(int(haversine(stationsObj[i].coords + pools[row][0][7:][:-1].split(" ")))) + " meter" )
#print(stationsObj[i].name)
#print(pools[row][1])
#print("")
result.append([stationsObj[i], pools[row][1]])
return result
Unten ein Test der Funktion. Die Funktion retourniert das station Objekt samt Name des Bades in einem Array von Arrays.
searchForPoolsWithWater(13)
def calcDistancePools(district):
stationsPools = []
for i in range(len(stationsObj)):
for row in range(len(pools)):
if haversine(stationsObj[i].coords + pools[row][0][7:][:-1].split(" ")) < 1000:
#print(stationsObj[i].name)
#print(pools[row][1])
stationsPools.append(stationsObj[i])
return stationsPools
stationsWithWaterAndPoolONE = []
stationsWithWaterAndPoolALL = []
m = (calcDistancePools(10))
for row in m:
if row.hasWater == True:
if row not in stationsWithWaterAndPoolONE:
stationsWithWaterAndPoolONE.append(row)
stationsWithWaterAndPoolALL.append(row)
for stations in stationsWithWaterAndPoolONE:
print(stations.name)
print(len(stationsWithWaterAndPoolONE))
Diese Liste spiegelt UBahn Stationen wieder die im Umkreis von 1000m ein Freibad haben. Außerdem befindet sich im Umkreis von 250m auch ein Wasserbrunnen. Die 37 Bäder sind für meine Navigationsfunktion relevant. Nur zu einer von diesen Stationen führt mich die Navigation.
Hier berechne ich wieviele Stationen einen Trinkbrunnen im Umkreis von 250 Meter haben 67 ist ein guter Wert. Ich lasse die Distanz so eingestellt.
waterCount = 0
for station in stationsObj:
if station.hasWater == True:
waterCount += 1
print(waterCount)
NINTH PART - create new ONTOLOGY + knowledge Graph (Grakn)
Hier soll ein neuer knowledge Graph erstellt werden. Ich wusste zu Beginn nicht wie Grakn genau funktioniert. Ich dachte ich kann einen KG einfach in dem uns bekannten Format ala n3 importieren. Dem ist nicht so. Ich hatte zu diesem Zeitpunkt aber schon mit einem KG begonnen weshalb ich Ihnen das nicht vorenthalten will. Weiter unten dann die Implementierung eines Grakn Schemas.
summerOnt = """
@prefix rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#> .
@prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#> .
@prefix foaf: <http://xmlns.com/foaf/0.1/> .
@base <http://my.org/> .
@prefix : <#> .
"""
summerOnt += """
:Station a rdfs:Class .
:Pool a rdfs:Class .
:Fountain a rdfs:Class .
:adjacent a rdfs:Property .
:isNearby a rdfs:Property .
:hasWater a rdfs:Property .
:located a rdfs:Property .
"""
for station in stationsWithWaterAndPoolONE:
summerOnt += """
:{} a :Station .
:{} :adjacent :Fountain .
:{} :adjacent :Pool .
""".format("".join(station.name.split()), "".join(station.name.split()), "".join(station.name.split()))
import rdflib
g = rdflib.Graph()
g.parse(data=summerOnt, format='turtle')
print(len(g))
Wie man sieht hat das einfügen funktioniert. 118 Einträge sind nun in meinem Graphen zu finden. AN dieser Stelle breche ich das hier ab und gehe weiter zu Grakn.
Hier nun die GRAKN Implementierung:
Erstellen 2 neuer CSV Dateien mit den Daten aus den Stationsobjekten. Diese Dateien werden dann in VS-Code und Grakn Console und Grakn Base weiter bearbeitet.
Die Dateien wurden exportiert. Ich spare mir jetzt das erneute importieren und lasse Ihnen das Ergebnis meiner GRAKN-Abfrage stattdessen zukommen!
with open('stationWithWaterPool.csv', 'w', newline='', encoding='utf-8') as file:
writer = csv.writer(file)
writer.writerow(['station', 'objectID', 'hasWater', 'hasPool'])
for station in stationsObj:
writer.writerow([station.name, int(station.objectId), str(station.hasWater).lower(), str(station.hasPool).lower() + "'"])
with open('lineHas.csv', 'w', newline='', encoding='utf-8') as file:
writer = csv.writer(file)
writer.writerow(['line', 'objectID'])
for station in stationsObj:
for line in station.line:
writer.writerow([line, int(station.objectId)])
Unten die Abbildung des Schemas.
Hier das Ergebnis im Workbase mit der Abfrage nach Stationen an der U1 mit Zugang zu einem Freibad und Zugang zu einem Wasserbrunnen. Insgesamt 9 Stationen.
Eine zweite Abfrage für die U2. Hier nur Zugang zu Bädern da es die Kombination hier nur 2 mal gibt. 4 Stationen aber mit Zugang zu Bädern.
10th PART - letzter Teil, NAVIGATION
Das Ziel für diesen Teil ist klar. Ich möchte eine beliebige Station eingeben und mein Algorithmus soll mich zum nächst gelegenen Bad mit Trinkwasserbrunnen in dem von mir gewählten Bezirk führen. Das Programm liefert die Wegstrecke zu der nähesten UBahn-Station im gewählten Bezirk welche beide Kriterien erfüllt. Die Entfernung wird dabei vom aktuellen Standpunkt berechnet (Luftlinie). Der Algorithmus sucht dann in meinen Linien nach der Station und navigiert mich zur Zielstation.
Als erstes werden einige Funktionen für die Pfadsuche erstellt. Insgesamt soll versucht werden, einen möglichst kurzen Weg, gemessen an den Stationen (häufiges Umsteigen wird nicht berücksichtigt) zu finden. Anmerkung zu der Endfunktionalität. Da es nicht so viele Stationen mit Wasserzugang und Bad gibt in Wien (37) kann die volle Vielfalt des Programms nicht ausgespielt werden. Es werden natürlich bei weitem nicht alle Stationen angefahren. Aber ich habe alle Stationen auf Funktionalität überprüft. Jede mögliche Kombination von Start und Endstation hat geklappt. Vor allem schwierig war das bei Praterstern und Gumpendorfer Straße. Beide Stationen bieten die Möglichkeit in 2 Richtungen zu starten falls sich die Zielstation nicht auf der selben Linie befindet da der nächste Knotenpunkt sowohl vorwärts als auch rückwärts genau gleich weit entfernt ist. Es gäbe somit grundsätzlich 2 gültige Varianten. Überhaupt schwierig ist es von Praterstern zur U6. Da gibt es erstmal 2 Varianten. Nämlich U2 und U1. Beide bringen einen zur U4 die ich benötige um zur U6 zu gelangen. An der U4 angelangt bieten beide Varianten aber jeweils 2 weitere Varianten um zur U6 zu kommen. Alle könnten die Kürzesten sein also müssen alle berücksichtigt werden. Das hat mir am meisten Kopfzerbrechen bereitet.
Über ipywidgets war es mir möglich eine kleine Benutzeroberfläche zu basteln. Damit kann man das Programm ganz gut bedienen. Die Eingabemaske ist ganz am Ende des Notebooks. Nun zu den Funktionen!
from ipywidgets import widgets
Die checkIfOnSameLine macht ihrem Namen alle Ehre. Sie überprüft ob die Linien der Startstation sich mit den Linien der Zielstation kreuzen. Ist das der Fall befindet sich die Zielstation auf der selben Linie und man muss nicht umsteigen. Es wird dann einfach die entspprechende Funktion in der doubly linked list aufgerufen. Das macht dann auch schon die 2 Funktion. Nämlich onSameLine. Die kann also aufgerufen werden wenn ich weiß, dass ich auf der selben Linie bin. Zurück kommt die Anzahl an Stationen die ich zurücklegen muss aber auch die Endstation der Linie. Dies um im Endeffekt auszugeben in welche Richtung ich fahren soll.
def checkIfOnSameLine(targetLines, startLines):
sameLine = [False, "Ux"]
for targetLine in targetLines:
if targetLine in startLines:
sameLine[0] = True
sameLine[1] = targetLine
return sameLine
def onSameLine(startStation, targetStation, targetLine):
searchNext = finalLines[targetLine].search_stationNext(startStation, targetStation)
searchPrev = finalLines[targetLine].search_stationPrev(startStation, targetStation)
if searchNext != -1:
endstation = (finalLines[targetLine].get_nextLastStation(startStation).name)
return([[startStation, searchNext], targetStation, targetLine, endstation])
if searchPrev != -1:
endstation = (finalLines[targetLine].get_prevLastStation(startStation).name)
return([[startStation, searchPrev], targetStation, targetLine, endstation])
Ist man bereits auf der richtigen Linie ist man auch schon am Ende angekommen. Es wird dann diese Funktion ausgeführt und man erfährt wieviele Stationen man in welche Richtung fahren muss um sein Ziel zu erreichen.
def onSameLineDepth0and1(startStation, targetStation, targetLine):
searchNext = finalLines[targetLine].search_stationNext(startStation, targetStation)
searchPrev = finalLines[targetLine].search_stationPrev(startStation, targetStation)
if searchNext != -1:
endstation = (finalLines[targetLine].get_nextLastStation(startStation).name)
return(startStation.name + " ist auf der selben Linie wie " + targetStation.name + ". Nehmen Sie die " + targetLine + " und fahren Sie für " + str(searchNext) + " Stationen zu " + targetStation.name + " in Richtung " + endstation)
if searchPrev != -1:
endstation = (finalLines[targetLine].get_prevLastStation(startStation).name)
return(startStation.name + " ist auf der selben Linie wie " + targetStation.name + ". Nehmen Sie die " + targetLine + " und fahren Sie für " + str(searchPrev) + " Stationen zu " + targetStation.name + " in Richtung " + endstation)
An meiner Namensgebung muss ich arbeiten aber hier soll überprüft werden welcher Weg der Kürzeste ist. Allerdings ist mit dem shortestHalwayPath gemeint, dass hier die Hälfte bereits zurückgelegt ist und ich schon weiß, dass ich mit dem Umsteigen auf der Linie der Zielstation bin. Hier findet keine Gesamtüberprüfung der Länge der Route statt da sich herausgestellt hat, dass in diesen Fällen zwar zu ein paar schlechteren Ergebnissen kommen kann aber es hält sich sehr in Grenzen.
def shortestHalfwayPath(paths):
currentLowestNumber = 100
currentLowestPath = [-1, -1]
for entry in paths:
if entry == -1:
break
if entry[1] < currentLowestNumber:
currentLowestNumber = entry[1]
currentLowestPath[0] = entry[0]
currentLowestPath[1] = entry[1]
return currentLowestPath
Der Name ist wieder besser gewählt. Wurde festgestellt, dass die Zielstation nicht auf der selben Linie ist wird diese Funktion ausgeführt. Sie gibt zurück die nächste Kreuzung die meiner Ziellinie entspricht. Falls dies nicht der Fall ist, die Ziellinie also überhaupt nicht erreicht werden kann über die Startlinie wird -1 zurückgegeben. Und man muss tiefer suchen.
def notOnSameLine(startStation, targetStation, startLines, targetLines):
print(startStation.name + " ist NICHT auf der selben Linie wie " + targetStation.name + "!")
searchNext = []
searchPrev = []
for startLine in startLines:
for i in range(len(targetLines)):
#append every result to the next or prev array. if there is one positive number in any of the 2 arrays the line is found on a knot on the current line
#and we found our target Line. If that the case the searchStationNext and searchStationPrev will be called.
searchNext.append(finalLines[startLine].search_lineNext(targetLines[i], startStation))
searchPrev.append(finalLines[startLine].search_linePrev(targetLines[i], startStation))
return searchNext, searchPrev
die FlattenList ist dazu da um eine verschachtelte Liste wieder schlanker zu machen. Ich arbeite viel mit ineinander verschachtelten Arrays und hierbei ist diese Funktion sehr hilfreich gewesen. Um ehrlich zu sein hab ich dann im späteren Verlauf den Überblick verloren und mir ist nicht mehr ganz klar wieso in manchen Fällen derart verschachtelte Infos zurückgegeben wurden. Aber mit dieser Funktion kann man das Problem lösen. Hier zeigt sich das bei größeren Projekte eine gewissenhafte Vorausplanung essentiell ist. Damit kann man solche Probleme gleich entschärfen aber naja, learning by doing.
def flattenList(listToFlat):
flattenedList = []
if "FAILURE" in listToFlat:
flattenedList.append(-1)
return flattenedList
for sublist in listToFlat:
for item in sublist:
flattenedList.append(item)
return flattenedList
wenns also tiefer hinein geht in die Suche kann diese Funktion verwendet werden um den kürzesten Pfad zu berechnen. Alle möglichen Routen werden ihr übergeben und returned wird die Kürzeste Route.
def shortestPathDepth2(routes):
shortestNumber = 100
shortestRoute = []
for route in routes:
if (route[0][1] + route[1][1] + route[2][1]) < shortestNumber:
shortestNumber = route[0][1] + route[1][1] + route[2][1]
shortestRoute = route
return shortestRoute
Diese Funktion hängt sehr stark mit einer Funktion 3 Zellen weiter unten zusammen. Dies ist die Folgefunktion der Funktion searchFurther. SearchFurther hat die Aufgabe nach der nächsten Station zu suchen die ein Knoten ist. Nämlich dann, wenn man weder auf der Ziellinie ist und die aktuelle Linie auch nicht die Ziellinie kreuzt. Dann wird also einfach nach dem nächsten Knoten gesucht. Wenn es da mehrere Möglichkeiten gibt werden alle berücksichtigt. Also maximal 2 natürlich nur. Bis eben eine Kreuzung gefunden wurde in beide Richtungen. Danach wird dann searchDeeper aufgerufen. Hiermit ist gemeint, dass nun von dem gefundenen Knoten aus auf den dort befindlichen Linien nach der Ziellinie gesucht wird.
def searchDeeper(linesNextKnot, targetLines, newStartStation):
testNext = []
testPrev = []
if -1 in linesNextKnot:
return "FAILURE"
for startLine in linesNextKnot[0].line:
for i in range(len(targetLines)):
#append every result to the next or prev array. if there is one positive number in any of the 2 arrays the line is found on a knot on the current line
#and we found our target Line. If that the case the searchStationNext and searchStationPrev will be called.
n = finalLines[startLine].search_lineNext(targetLines[i], newStartStation)
p = finalLines[startLine].search_linePrev(targetLines[i], newStartStation)
if n not in testNext:
testNext.append(n)
if p not in testPrev:
testPrev.append(p)
return testNext, testPrev
Hier wird jetzt das Ergebnis aus notOnSameLine weiter verarbeitet. Ein loggedPath wird returniert.
def searchStationWithTargetLineOnCurrentLine(start, target, startLines, targetLines):
temp = flattenList(notOnSameLine(start, target, startLines, targetLines))
searchStationWithTargetLine = []
for entry in temp:
if entry != -1:
searchStationWithTargetLine.append(entry)
loggedPath = (shortestHalfwayPath(searchStationWithTargetLine))
return loggedPath
stuckLine betrifft einen Spezialfall. Nämlich den, dass vom nächsten Knoten aus keine Verbindung zu Ziellinie gefunden werden kann. Da kommt nur einmal vor in der Wiener UBahn. Nämlich wenn man von der U2 startet und zwar östlich von Praterstern und man zur U6 will. Also alles ab Messe-Prater. Denn die U2 bietet keine Verbindung zu der U6. Somit wird der nächste Knoten gesucht. Das ist Praterstern aber auch vom Praterstern aus kann man die U6 nicht finden. Somit wird hier einfach erneut zum nächsten Knoten gesprungen. Im Fall von Praterstern und der U2 ist es dann Schottenring. Schottenring hat eine Verbindung zur U6.
def stuckLine(loggedPath, startLines, targetLines):
newLoggedPath = []
newLoggedPath.append(flattenList(loggedPath))
tempNext = []
tempPrev = []
for startLine in startLines:
tempNext.append(finalLines[startLine].search_knotNext(loggedPath[0][0]))
tempPrev.append(finalLines[startLine].search_knotPrev(loggedPath[0][0]))
flattenList(tempNext)
flattenList(tempPrev)
if tempNext[0][0] != -1:
newLoggedPath.append(flattenList(tempNext))
if tempPrev[0][0] != -1:
newLoggedPath.append(flattenList(tempPrev))
return newLoggedPath
def searchFurther(loggedPath, startLines, targetLines, startStationObj, targetStationObj):
loggedPath = []
tempNext = []
tempPrev = []
for startLine in startLines:
tempNext.append(finalLines[startLine].search_knotNext(startStationObj))
tempPrev.append(finalLines[startLine].search_knotPrev(startStationObj))
searchNextKnot = tempNext
searchPrevKnot = tempPrev
for entry in searchNextKnot:
if -1 not in entry:
loggedPath.append(entry)
for entry in searchPrevKnot:
if -1 not in entry:
loggedPath.append(entry)
allPossiblePaths = []
for i in range(len(loggedPath)):
allPossiblePaths.append(flattenList(searchDeeper(loggedPath[i], targetLines, loggedPath[i][0])))
deeperPath = []
for entry in flattenList(allPossiblePaths):
if entry != -1:
loggedPath.append(entry)
if (startStationObj == (stationsObj[47]) and targetStationObj == stationsObj[68]):
del loggedPath[2]
return loggedPath
Die calcRoute ist eine der wichtigsten Funktionen. Die hat mich viel Zeit gekostet und Hirnschmalz auch glaube ich. Ganz astrein und sauber ist das da alles nicht. Das ist mir bewusst aber besser hab ich es jetzt nicht mehr hinbekommen. Der Code gehört sowieso refactored. Die Funktion betrifft nur Routen bei denen man 2 mal umsteigen muss. >=4 bedeutet, dass es mehr als eine Möglichkeit gibt. ==2 bedeutet, dass es für nur eine Route gibt. Mehrere mögliche Routen werden hier verglichen und die beste Route ausgewählt. Dieser Funktion geht die Funktion darunter vor.
def calcRoute(routes, targetLines, startStationObj, targetStationObj):
correctLines = []
if len(routes) >= 4:
temp1 = [routes[0], routes[1]]
temp2 = [routes[2], routes[3]]
routes = [temp1, temp2]
for route in routes:
correctLines.append(checkIfOnSameLine(targetLines, route[1][0].line))
#append all the information to all the routes. Path for first, second and third line. StartingStation, Endline and Endstation of Endline to give back the correct direction.
for route in range(len(routes)):
#print(targetStationObj.name
temp = onSameLine(routes[route][1][0], targetStationObj, correctLines[route][1])
#print((routes[route][1][0].name, targetStationObj.name, correctLines[route][1]))
for entry in temp:
routes[route].append(entry)
#print(entry)
shortestPath = (shortestPathDepth2(routes))
routes = []
#print(shortestPathDepth2)
if len(routes) == 2:
correctLines.append(checkIfOnSameLine(targetLines, routes[1][0].line))
temp = onSameLine(routes[1][0], targetStationObj, correctLines[0][1])
for entry in temp:
routes.append(entry)
shortestPath = routes
isSameLineDepth1 = checkIfOnSameLine(shortestPath[0][0].line, startStationObj.line)
isSameLineDepth2 = checkIfOnSameLine(shortestPath[1][0].line, shortestPath[0][0].line)
isSameLineDepth3 = checkIfOnSameLine(targetStationObj.line, shortestPath[2][0].line)
firstSection = onSameLine(startStationObj, shortestPath[0][0], isSameLineDepth1[1])
secondSection = onSameLine(shortestPath[0][0], shortestPath[1][0], isSameLineDepth2[1])
thirdSection = onSameLine(shortestPath[1][0], targetStationObj, isSameLineDepth3[1])
print("")
print("Sie müssen zweimal Umsteigen:")
print("Nehmen Sie als erstes die {0} in Richtung {1}. Fahren Sie für {2} Stationen bis zur Station {3}.".format(firstSection[2], firstSection[3], firstSection[0][1], secondSection[0][0].name))
print("")
print("Nun fahren Sie mit der {0} in Richtung {1}. Fahren Sie für {2} Stationen bis zur Station {3}.".format(secondSection[2], secondSection[3], secondSection[0][1], thirdSection[0][0].name))
print("")
print("Ein letztes mal umsteigen. Nehmen Sie die {0} in Richtung {1}. Fahren Sie für {2} Stationen bis zu Ihrem Ziel {3}.".format(thirdSection[2], thirdSection[3], thirdSection[0][1], targetStationObj.name))
Hier werden alle möglichen Routen berechnet. Besser ausgedrückt werden sie zusammengestellt. Hier blieb mir ncihts andere übrig als viele Szenarien zu berücksichtigen. Ich hätte das gerna automatisiert aber das war mir nicht möglich in der Zeit. Da hätte ich nochmal von vorne beginnen müssen. Deshalb auch hier die ein oder andere Unschärfe. Am Ende der Funktion hat man ein Array mit den diversen Routen. Das wird dann an die calcRoute Funktion übergeben die sich dann darum kümmert den besten, kürzesten Pfad zu finden.
def searchSecondDepth(loggedPath, startLines, targetLines, startStationObj, targetStationObj):
if len(loggedPath) == 1:
#U2 wants to U6 AND IS STUCK ON PRATERSTERN CAUSE U1 not CONNECTED TO U6! NEED TO SEARCH FOR THE NEXT KNOT AGAIN!
#search for connection to targetLine on next Knot (from Startline). if the current Line has no next knot it would not be possible to access the targetLine from this line. so this scenario
#is only theoretical because every station is accessible from every station in the vienna ubahn
stuck = flattenList(stuckLine(loggedPath, startLines, targetLines))
countStations = stuck[1] + stuck[3]
correctKnot = stuck[2]
loggedPath = [correctKnot, countStations]
temp = flattenList(searchDeeper(loggedPath, targetLines, loggedPath[0]))
for entry in temp:
if entry != -1:
loggedPath.append(entry)
if isinstance(loggedPath[1], int):
loggedPath[0] = [loggedPath[0], loggedPath[1]]
del loggedPath[1]
if len(loggedPath) == 2:
calcRoute(loggedPath, targetLines, startStationObj, targetStationObj)
if len(loggedPath) == 3:
route1 = []
route1.append(loggedPath[0])
route1.append(loggedPath[1])
route2 = []
route2.append(loggedPath[0])
route2.append(loggedPath[2])
routes = [route1, route2]
calcRoute(flattenList(routes), targetLines, startStationObj, targetStationObj)
if len(loggedPath) == 4 and isinstance(loggedPath[-1], list):
if loggedPath[3][1] == loggedPath[2][1]:
route1 = []
route1.append(loggedPath[0])
route1.append(loggedPath[1])
route2 = []
route2.append(loggedPath[2])
route2.append(loggedPath[3])
if loggedPath[3][1] != loggedPath[2][1]:
route1 = []
route1.append(loggedPath[0])
route1.append(loggedPath[2])
route2 = []
route2.append(loggedPath[1])
route2.append(loggedPath[3])
routes = [route1, route2]
calcRoute(flattenList(routes), targetLines, startStationObj, targetStationObj)
if len(loggedPath) == 5 and isinstance(loggedPath[-1], list):
route1 = []
route1.append(loggedPath[0])
route1.append(loggedPath[2])
route2 = []
route2.append(loggedPath[1])
route2.append(loggedPath[3])
route3 = []
route3.append(loggedPath[1])
route3.append(loggedPath[4])
routes = [route1, route2, route3]
calcRoute(flattenList(routes), targetLines, startStationObj, targetStationObj)
if len(loggedPath) == 6 and isinstance(loggedPath[-1], list):
route1 = []
route1.append(loggedPath[0])
route1.append(loggedPath[2])
route2 = []
route2.append(loggedPath[0])
route2.append(loggedPath[3])
route3 = []
route3.append(loggedPath[1])
route3.append(loggedPath[4])
route4 = []
route4.append(loggedPath[1])
route4.append(loggedPath[5])
routes = [route1, route2, route3, route4]
calcRoute(flattenList(routes), targetLines, startStationObj, targetStationObj)
Und das ist die Startfunktion. Ihr werden die Startstation und die Zielstation als String übergeben. Als erstes sucht sich die Funktion ein paar Variablen und checkt dann gleich mal ob man sich bereits auf der richtigen Linie befindet. Falls ja wird der korrekt Weg zur Zielstation, bzw. die Stationen dahin, ausgegeben.
Falls nicht wird der weitere Code in Gang gesetzt.
def searchPath(startingStation, target):
linesStart = []
linesTarget = []
startStationObj = -1
targetStationObj = -1
collectAll = [linesTarget, linesStart, startStationObj]
for i in range(len(stationsObj)):
if stationsObj[i].name == startingStation:
startStationObj = stationsObj[i]
for line in stationsObj[i].line:
linesStart.append(line)
for i in range(len(stationsObj)):
if stationsObj[i].name == target:
targetStationObj = stationsObj[i]
for line in stationsObj[i].line:
linesTarget.append(line)
sameLine = checkIfOnSameLine(collectAll[0], collectAll[1])
if sameLine[0] == True:
print(onSameLineDepth0and1(startStationObj, targetStationObj, sameLine[1]))
#case start and target are NOT on same line
if sameLine[0] == False:
#loggedPath will be calculated. loggedPath will be -1 if no knot is found at wich you can change to the targetLine.
#this means that i have to search deeper. if it is not -1 a path to the target line was found.
loggedPath = searchStationWithTargetLineOnCurrentLine(startStationObj, targetStationObj, collectAll[1], collectAll[0])
#serch for the shortest path in both directions.
if loggedPath[1] != -1:
sameLineHalfWay = checkIfOnSameLine(loggedPath[0].line, collectAll[1])
arrivedAtCorrectLine = checkIfOnSameLine(collectAll[0], loggedPath[0].line)
print("")
print("Sie müssen einmal Umsteigen:")
print(onSameLineDepth0and1(startStationObj, loggedPath[0], sameLineHalfWay[1]))
print("")
print("Steigen Sie nun um in die " + arrivedAtCorrectLine[1])
print(onSameLineDepth0and1(loggedPath[0], targetStationObj, arrivedAtCorrectLine[1]))
print("")
print("Sie haben Ihr Ziel erreicht")
#case NO connection to targetLine on next line. in this case i will search for the nearest knot. from where the targetLine is reachable.
#you can reach every station from everywhere if you change the line for two times.
if loggedPath[1] == -1:
loggedPath = searchFurther(loggedPath, collectAll[1], collectAll[0], startStationObj, targetStationObj)
searchFurther(loggedPath, collectAll[1], collectAll[0], startStationObj, targetStationObj)
searchSecondDepth((loggedPath), collectAll[1], collectAll[0], startStationObj, targetStationObj)
Und das war es auch schon mit der Navigationsfunktion. Unten noch eine Funktion die ausgeführt werden wenn man dann nach einem Bad sucht. Sie sucht nach der nähesten Station im gewählten Bezirk. Ist in einem Bezirk keine Station mit den genannten Kriterien verfügbar wird im Bezirk +1 gesucht. Danach im Bezirk -1. Sollte auch dann kein Bad gefunden werden muss ein neuer Bezirk eingegeben werden. Spezialfall 23. Bezirk. Hier wird natürlich nicht im 24. Bezirk gesucht sondern im 14. Ich habe ein paar Varianten durchgespielt und der 14. scheint sinnvoll zu sein. Der 10. würde natürlich auch gehen.
def startSearchToPool(startingStation, district):
startObj = None
for station in stationsObj:
if station.name == startingStation:
startObj = station
startCoords = startObj.coords
nearestStationInNeededDistrict = None
lowestDistance = 50000
possiblePoolsWithStations = searchForPoolsWithWater(int(district))
if len(possiblePoolsWithStations) < 1 and district != "23":
print("Es konnten keine entsprecheden Bäder im {}. gefunden werden. Es wird im {}. Bezirk gesucht...".format(district, str(int(district)+1)))
possiblePoolsWithStations = searchForPoolsWithWater(int(district) + 1)
if len(possiblePoolsWithStations) < 1 and district != "23":
print("Auch im {}. Bezirk wurde kein entprechender Bäder gefunden. Es wird im {}. Bezirk gesucht...".format(str(int(district)+1), str(int(district)-1)))
possiblePoolsWithStations = searchForPoolsWithWater(int(district) - 1)
if len(possiblePoolsWithStations) < 1 and district == "23":
print("Es konnten keine entsprecheden Bäder im {}. gefunden werden. Es wird im {}. Bezirk gesucht...".format(district, str(int(district)-9)))
possiblePoolsWithStations = searchForPoolsWithWater(int(district) - 9)
if len(possiblePoolsWithStations) < 1:
print("Immer noch nichts gefunden. Bitte wählen Sie einen anderen Bezirk und starten die Abfrage erneut")
if len(possiblePoolsWithStations) >= 1:
for possiblePoolStation in possiblePoolsWithStations:
temp = haversine(possiblePoolStation[0].coords + startObj.coords)
if nearestStationInNeededDistrict == None or lowestDistance > temp:
lowestDistance = temp
nearestStationInNeededDistrict = possiblePoolStation
print("")
print("Von Ihrem Standpunkt {} aus ist das nächst gelegene Bad (mit Wasserbrunnen in der Nähe) das {}. Dazu fahren Sie bis zur Station {}. Untenstehend eine Wegbeschreibung:".format(startingStation, nearestStationInNeededDistrict[1], nearestStationInNeededDistrict[0].name))
print("")
searchPath(startingStation, nearestStationInNeededDistrict[0].name)
Das Untenstehende ist jetzt nur mehr für das User Interface notwendig.
#todo evtl ein filter für die stationen damit es keine probleme gibt beim eintippen
print("Bitte tippen Sie ihre Start-Ubahn-Station ein.")
print("Achtung! Sollte es zu Problemen mit dem Namen kommen versuchen Sie bitte eine andere Schreibweise. Groß und Kleinschreibung kann unberücksichtigt bleiben.")
print("")
print("Schwierige Stationen:")
print("Südtiroler Platz bitte Hauptbahnhof verwenden")
print("Schottentor-Universität bitte Schottentor verwenden")
print("Messe Prater bitte Messe-Prater verwenden")
text = widgets.Text()
display(text)
print("In welchem Bezirk möchten Sie schwimmen gehen?")
district = widgets.Dropdown(
options=['1010', '1020', '1030', '1040', '1050', '1060', '1070', '1080', '1090', '1100', '1110', '1120', '1130', '1140', '1150', '1160', '1170', '1180', '1190', '1200', '1210', '1220', '1230'],
value='1010',
disabled=False,
)
display(district)
def handle_submit(sender):
station = text.value.lower()
dist = district.value
if dist[1] == "0":
startSearchToPool(station, dist[2])
else: startSearchToPool(station, dist[1:][:-1])
#text.on_submit(handle_submit)
button = widgets.Button(description="Suche starten")
display(button)
def on_button_clicked(b):
handle_submit(text)
button.on_click(on_button_clicked)
falls Sie möchten können Sie mit dem Funktionsaufruf unten eigene Stationen eingeben. Dazu muss die station aber in Kleinbuchstaben angegeben werden. lower() habe ich nur für die Benutzeroberfläche verwendet!
searchPath("karlsplatz", "praterstern")