Visualisieren Sie Eisenbahnstreckendaten und lösen Sie kürzeste Streckenprobleme (Python + Pandas + NetworkX)

Einführung

Die Routenkarte und das Grafiknetz passen gut zusammen. Wenn Sie versuchen, über etwas in der Routenkarte nachzudenken, werden Sie das kürzeste Routenproblem ansprechen, an das jeder denken kann.

Verwandeln Sie die Eisenbahnkarte in ein einfaches Grafikproblem und verwenden Sie die Dyxtra-Methode, um die kürzeste Route zu finden. Die Python-Bibliothek NetworkX verfügt über eine integrierte Dyxtra-Methode, die praktisch ist. Wir werden sie dieses Mal verwenden.

Das Programm wurde in Google Colaboratory hochgeladen, damit es im Browser ausgeführt werden kann. Hier https://nbviewer.jupyter.org/github/galileo15640215/train/blob/master/train_dijkstra.ipynb

fließen

Obwohl es sich um eine Routenkarte handelt, ist sie zu groß, um nationale Daten plötzlich zu verarbeiten. Bevor wir Routen landesweit in Betracht ziehen, extrahieren und erstellen wir zunächst die Metro-Routen in Tokio als kleines Problem.

Auftrag · Datenverarbeitung ・ Streckenkarte innerhalb der Tokyo Metro ・ Die kürzeste Route im Großraum Tokio ・ Bundesweite Streckenkarte ・ Die kürzeste Route im ganzen Land

Benötigte Daten

Von der Station data.jp https://ekidata.jp/ Geschäftsdaten company20200309.csv Routendaten line20200306free.csv Stationsdaten station20200316free.csv Daten der Verbindungsstation join20200306.csv Herunterladen. (CSV-Dateiname ab 1. Mai 2020)

Darauf aufbauend erstellen wir die notwendigen Daten.

Programm

#Erforderliche Module
import pandas as pd
import matplotlib.pyplot as plt
import japanize_matplotlib
import numpy as np
import networkx as nx

#Erstellen Sie eine Pandsa-Format-Tabelle aus einer CSV-Datei
station = pd.read_csv("station20200316free.csv")
join = pd.read_csv("join20200306.csv")
#pref = pd.read_csv("pref.csv")
line = pd.read_csv("line20200306free.csv")
company = ("company20200309.csv")

Bisher haben wir die erforderlichen Daten in die Pandas-Tabelle aufgenommen.

Tokyo Metro Version

Als nächstes extrahieren Sie die Daten nur für Tokyo Metro.

#Tokyo Metro, die landesweit nur Tokyo Metro-Stationen von Stationen extrahiert...company_cd == 18
metro = station[["station_cd", "station_name", "line_cd", "lon", "lat"]]
metro = pd.merge(metro, line, on = 'line_cd')
metro = metro[metro["company_cd"] == 18]
metro = metro[["station_cd", "station_name", "line_cd", "lon_x", "lat_x", "line_name", "line_color_c", "line_color_t"]]
lon = metro["lon_x"]
lat = metro["lat_x"]
metro["lon"] = lon
metro["lat"] = lat
metro = metro[["station_cd", "station_name", "line_cd", "lon", "lat", "line_name"]]

#Route zum Extrahieren der Verbindungsseite der Tokyo Metro...line_cd == 28001---28010
metro_join = join[(join["line_cd"]==28001)|(join["line_cd"]==28002)|(join["line_cd"]==28003)|(join["line_cd"]==28004)|(join["line_cd"]==28005)|(join["line_cd"]==28006)|(join["line_cd"]==28007)|(join["line_cd"]==28008)|(join["line_cd"]==28009)|(join["line_cd"]==28010)]
metro_join = metro_join[["station_cd1", "station_cd2"]]

Erstellen Sie von hier aus ein Diagramm der U-Bahn-Streckenkarte von Tokio.

#Diagrammdeklaration
G = nx.Graph()
#Machen Sie oben den Stationsnamen
G.add_nodes_from(metro["station_name"])
#Legen Sie die Plotkoordinaten fest
pos={}
for i, j, k in zip(metro["station_name"], metro["lon"], metro["lat"]):
  pos[i] = (j, k)
#Liste e zur Station_Name und Station_CD und Link speichern
e = []
for i, j in zip(metro["station_name"], metro["station_cd"]):
  e.append([i, j])
#Fügen Sie dem Diagramm Kanteninformationen hinzu
for i, j in zip(metro_join["station_cd1"], metro_join["station_cd2"]):
    for k in e:
      if k[1] == i:
        for l in e:
          if l[1] == j:
            G.add_edge(k[0], l[0])
#Einstellungen für die Grafikausgabe
plt.figure(figsize=(10,10),dpi=200)
plt.title('Tokyo Metro', fontsize=20)
plt.axes().set_aspect('equal', 'datalim')
nx.draw_networkx(G, pos, node_color='b', alpha=0.8, node_size=10, font_size=5, font_family='IPAexGothic')
plt.show()

Ich konnte die Streckenkarte der Tokyo Metro visualisieren. Geben Sie dem Diagramm von hier aus die Informationen, die zur Lösung des Problems der kürzesten Route erforderlich sind.

Geben Sie Informationen zum Diagramm

#Datenerstellung, um den Abstand zwischen Stationen als Gewicht auf der Seite anzugeben
dist = []
cd1_lat = []
cd1_lon = []
cd2_lat = []
cd2_lon = []
not_exist = [] #Station, die in der Join-Tabelle, aber nicht in der Stationstabelle vorhanden ist_CD speichern
for i, j in zip(metro_join["station_cd1"], metro_join["station_cd2"]):
  flag = True
  for k, l, m in zip(metro["station_cd"], metro["lat"], metro["lon"]):
    if i == k:
      cd1_x = l
      cd1_y = m
      cd1_lat.append(l)
      cd1_lon.append(m)
      flag = False
    if j == k:
      cd2_x = l
      cd2_y = m
      cd2_lat.append(l)
      cd2_lon.append(m)
  if flag:
    not_exist.append([i, j])
    #print(i, j)
  else:
    dist.append(((cd1_x-cd2_x)**2 + (cd1_y-cd2_y)**2)**0.5)
#Wenn Sie es so ausführen, wie es ist, wird ein Fehler ValueError angezeigt: Length of values does not match length of index
#Anscheinend"station_cd" ==2800701 und 2800702 wurden entfernt, da sie in der Stationstabelle nicht vorhanden und in der Verknüpfungstabelle nicht erforderlich sind
#Die folgenden zwei Zeilen...metro_join = metro_join[metro_join["station_cd1"] != 2800701]...Gleichwertig
for i in range(len(not_exist)):
  metro_join = metro_join[metro_join["station_cd1"] != not_exist[i][0]]
#Spalte zur Verknüpfungstabelle hinzufügen
metro_join["cd1_lat"] = cd1_lat
metro_join["cd1_lon"] = cd1_lon
metro_join["cd2_lat"] = cd2_lat
metro_join["cd2_lon"] = cd2_lon
metro_join["distance"] = dist

Ich werde dem Diagramm das Gewicht der Kante geben

#nodes is station_name
#Geben Sie die Kantengewichte des Diagramms an
for i, j, m in zip(metro_join["station_cd1"], metro_join["station_cd2"], metro_join["distance"]):
    for k in e:
      if k[1] == i:
        for l in e:
          if l[1] == j:
            G.add_edge(k[0], l[0], weight=m)

Die Bibliothek von NetworkX, Networkx.dijkstra_path (), die zur Lösung des Problems der kürzesten Route benötigt wird, scheint nicht der Spitze des Japanischen zu entsprechen. Ändern Sie die Scheitelpunkte von station_name in station_cd und deklarieren Sie ein neues Diagramm.

#nodes is station_cd
G = nx.Graph()
G.add_nodes_from(metro["station_cd"])
pos={}
for i, j, k in zip(metro["station_cd"], metro["lon"], metro["lat"]):
  pos[i] = (j, k)
for i, j, m in zip(metro_join["station_cd1"], metro_join["station_cd2"], metro_join["distance"]):
  G.add_edge(i, j, weight=m)
#station_Station mit dem gleichen Namen, wenn sich die CD oben befindet_Auch mit Namen, Station für jede Linie_Da cd eingestellt ist, hat es keine Verbindungsseite mit anderen Leitungen wie es ist
#Verbinden Sie daher gleichnamige Stationen mit einer Gewichtung von 0.
for i, j in zip(metro["station_name"], metro["station_cd"]):
  for k, l in zip(metro["station_name"], metro["station_cd"]):
    if i == k and j != l:
      G.add_edge(j, l, weight=0)

#Start- und Zielstationen einstellen
st_name = "Ogikubo"
go_name = "Nishifunabashi"
#station_vom Namen zum Bahnhof_CD suchen
for i, j in zip(metro["station_name"], metro["station_cd"]):
  if i == st_name:
    st = j
  if i == go_name:
    go = j
#Suchen Sie nach der kürzesten Route
dij = nx.dijkstra_path(G, st, go)
out = []
for k in range(len(dij)):
  for i, j in zip(metro["station_name"], metro["station_cd"]):
    if j == dij[k]:
      out.append(i)
print(out)
#Deklarieren Sie das Diagramm für die kürzeste Route
G_root = nx.Graph()
G_root.add_nodes_from(dij)
pos_root = {}
for l in dij:
  for i, j, k in zip(metro["station_cd"], metro["lon"], metro["lat"]):
    if l == i:
      pos_root[l] = (j, k)
for i in range(len(dij)-1):
  G_root.add_edge(dij[i], dij[i+1])

plt.figure(figsize=(10,10),dpi=200)
plt.title('Tokyo Metro', fontsize=20)
plt.axes().set_aspect('equal', 'datalim')
nx.draw_networkx(G, pos, node_color='b', alpha=0.3, node_size=10, with_labels= False)
c = ['green' if n==st else 'red' if n!=go else'yellow' for n in G_root.nodes()]
n_size = [30 if n==st else 10 if n!=go else 30 for n in G_root.nodes()]
nx.draw_networkx(G_root, pos_root, node_color=c, alpha=0.9, node_size=n_size, with_labels= False)
plt.show()

Ausführungsergebnis ['Ogikubo', 'Minami Asagaya', 'Shinkoenji', 'Higashikoenji', 'Shin Nakano', 'Nakano Sakagami', 'Nishi Shinjuku', 'Shinjuku', 'Shinjuku Sanchome', 'Shinjuku Gyoenmae', "Yotani 3-chome", "Yotsuya", "Akasaka Mitsuke", "Vor dem Parlamentsgebäude", "Vor dem Parlamentsgebäude", "Kasumigaseki", "Hibiya", "Hibiya", "Ginza", "Ginza", "Kyobashi" , "Nihonbashi", "Nihonbashi", "Kayabacho", "Monzen Nakamachi", "Kiba", "Toyocho", "Minamisago", "Nishi Kasai", "Kasai", "Urayasu", "Minami Gyotoku", "Gyotoku", "Myonori", "Log Nakayama", "Nishifunabashi"]

Ich konnte die kürzeste Strecke in der Metro von Tokio zeichnen. Wie verhält es sich mit der aktuellen App für exzellente Transferführung?

Das Programm hat mehr Transfers. Die Route ist jedoch für eine kleine wie die Tokyo Metro fast dieselbe.

Als nächstes die nationale Version

Das gleiche wird landesweit gemacht.

zen_join = join
zen = station[["station_cd", "station_name", "line_cd", "lon", "lat"]]
zen = pd.merge(zen, line, on='line_cd')
zen = zen[["station_cd", "station_name", "line_cd", "lon_x", "lat_x", "line_name"]]
lon = zen["lon_x"]
lat = zen["lat_x"]
zen["lon"] = lon
zen["lat"] = lat
zen = zen[["station_cd", "station_name", "line_cd", "lon", "lat", "line_name"]]
cd1_lat = []
cd1_lon = []
cd2_lat = []
cd2_lon = []
dist = []
not_exist = []
for i, j in zip(zen_join["station_cd1"], zen_join["station_cd2"]):
  flag = True
  for k, l, m in zip(zen["station_cd"], zen["lat"], zen["lon"]):
    if i == k:
      cd1_x = l
      cd1_y = m
      cd1_lat.append(l)
      cd1_lon.append(m)
      flag = False
    if j == k:
      cd2_x = l
      cd2_y = m
      cd2_lat.append(l)
      cd2_lon.append(m)
  if flag:
    not_exist.append([i, j])
    #print(i, j)
  else:
    dist.append(((cd1_x-cd2_x)**2 + (cd1_y-cd2_y)**2)**0.5)
#Gelöscht, weil es nicht in der Stationstabelle vorhanden ist und in der Join-Tabelle nicht erforderlich ist
for i in range(len(not_exist)):
  zen_join = zen_join[zen_join["station_cd1"] != not_exist[i][0]]# & zen_join["station_cd2"] != not_exist[i][1]]
zen_join["cd1_lat"] = cd1_lat
zen_join["cd1_lon"] = cd1_lon
zen_join["cd2_lat"] = cd2_lat
zen_join["cd2_lon"] = cd2_lon
zen_join["distance"] = dist

#nodes is station_cd
G = nx.Graph()
G.add_nodes_from(zen["station_cd"])
pos={}
for i, j, k in zip(zen["station_cd"], zen["lon"], zen["lat"]):
  pos[i] = (j, k)
for i, j, m in zip(zen_join["station_cd1"], zen_join["station_cd2"], zen_join["distance"]):
  G.add_edge(i, j, weight=m)
for i, j, m in zip(zen["station_name"], zen["station_cd"], zen["lat"]):
  for k, l, n in zip(zen["station_name"], zen["station_cd"], zen["lat"]):
    if i == k and j != l and m == n:
      #print(i, j, k, l)
      G.add_edge(j, l, weight=0)
plt.figure(figsize=(10,10),dpi=200)
plt.title('Ganz Japan', fontsize=20)
plt.axes().set_aspect('equal', 'datalim')
nx.draw_networkx(G, pos, alpha=0.0, with_labels=False)
nx.draw_networkx_edges(G, pos)
plt.show()

st_name = "Nemuro"
go_name = "Kagoshima"
for i, j in zip(zen["station_name"], zen["station_cd"]):
  if i == st_name:
    st = j
  if i == go_name:
    go = j
dij = nx.dijkstra_path(G, st, go)
out = []
for k in range(len(dij)):
  for i, j in zip(zen["station_name"], zen["station_cd"]):
    if j == dij[k]:
      out.append(i)
print(out)

#nodes is station_cd
plt.figure(figsize=(50,50),dpi=200)
G_root = nx.Graph()
G_root.add_nodes_from(dij)
pos_root = {}
for l in dij:
  for i, j, k in zip(zen["station_cd"], zen["lon"], zen["lat"]):
    if l == i:
      pos_root[l] = (j, k)
for i in range(len(dij)-1):
  G_root.add_edge(dij[i], dij[i+1])

plt.figure(figsize=(10,10),dpi=200)
plt.title('Ganz Japan', fontsize=20)
plt.axes().set_aspect('equal', 'datalim')
nx.draw_networkx(G, pos, alpha=0.0, with_labels=False)
nx.draw_networkx_edges(G, pos, alpha=0.3)
nx.draw_networkx(G_root, pos_root, alpha=0.0, with_labels=False)
nx.draw_networkx_edges(G_root, pos_root, alpha=1.0, edge_color='r')
plt.show()

Komplett. Es ist unrealistisch, tatsächlich eine Verbindung herzustellen, und wenn Sie kein großer Zugliebhaber sind, ist es die Hölle. Es ist fertig. Dank des Hokkaido Shinkansen können Sie Honshu durch den Seikan-Tunnel erreichen. Apropos kürzeste Zeit, es ist natürlich, nach Tohoku Shinkansen und Tokaido Shinkansen zu wechseln, aber wenn die Route die kürzeste ist, scheint es, dass Sie mit einer konventionellen Linie ohne Verwendung des Tohoku Shinkansen zur Seite des Japanischen Meeres fahren.

Zusammenfassung

Die Nebeninformation war diesmal die Entfernung, aber wenn Sie sie als Zeit verwenden, können Sie so etwas wie die kürzeste Zeit für die Übertragungsführung festlegen. Ich würde es gerne versuchen, wenn ich Zeitdaten erstellen kann. To be continued...

Referenzierte Site

Visualisieren Sie mit Cytoscape 1 Eisenbahnstreckendaten als Grafik https://qiita.com/keiono/items/29286f49b15a5b13c987 Informationen zur Verarbeitung der Stationsdaten finden Sie hier.