Comments / Profile of sakhar / Habr

Как выглядело бы Московское метро в трехмерном мире

Sakhar October 10, 2019 at 01:09 PM

0

Ссылка на схему на javascript в шапке, дублирую тут https://alexankharin.github.io/
Здесь можно и самому схему покрутить

Как выглядело бы Московское метро в трехмерном мире

87

Sakhar October 9, 2019 at 08:36 PM

0

Это сделать можно, и скорее всего сработало бы, если учитывались бы времена только между соседними станциями; Время тогда можно было бы считать просто как сумму длин ребер графа пути от одной станции к другой. В двумерном пространстве даже такая задача не всегда решается. Пример — 4 станции, каждая связана с каждой и есть 4 времени перехода. В 2д случае такая задача не решается в общем виде, в 3d она решается при некоторых ограничениях на соотношения длин (комент снизу). В случае, когда оптимизация идет по всем парам станций, нарисовать адекватный граф в 2d еще труднее, и нужно больше степеней свободы для более точного построения для точного графа. Поэтому выбрано 3d пространство. Но никто не мешает запустить алгоритм с гораздо худшими результатами на 2д схеме (результат оптимизации 2д — последняя картинка в посте)

Как выглядело бы Московское метро в трехмерном мире

87

Sakhar October 9, 2019 at 08:16 PM

0

Спасибо большое за ценное замечание! Действительно, для евклидовых пространств утверждение, что «для любого графа существует такое пространство, что можно таким образом расставить точки, чтобы расстояние между любыми двумя ними было равно указанным длинам ребер графа» неверно. Нужно либо вводить дополнительные ограничение, чтобы удовлетворялось неравенство треугольника для любой тройки точек либо еще какое-то или смотреть на другие пространства с другими метриками.

Как выглядело бы Московское метро в трехмерном мире

87

Sakhar October 8, 2019 at 10:08 PM

0

добавил ссылку на схему метро на js Добавить js скрипт непосредственно в html поста не получилось — похоже на хабре это запрещено из соображений безопасности.

Как выглядело бы Московское метро в трехмерном мире

87

Sakhar October 8, 2019 at 05:28 PM

0

Я немного опасаюсь того, что взял информацию из apk-файла яндекс метро для андроида, поэтому не знаю, можно ли выложить граф, полученный из него. Граф можно сохранить, выполнив следующий код

names = json.loads(codecs.open( "l10n.json", "r", "utf_8_sig" ).read() )
graph = json.loads(codecs.open( "data.json", "r", "utf_8_sig" ).read() )
G=nx.Graph()
for node in graph['nodes']['items']:
    G.add_node(node['id'])
#graph['links']
for link in graph['links']['items']:
    #G.add_edges_from([(link['fromNodeId'],link['toNodeId'])])
    G.add_edge(link['fromNodeId'], link['toNodeId'], length=link['attributes']['time'])
nodestoremove=[]
for node in G.nodes():
    if len(G.edges(node))<2:
        nodestoremove.append(node)
for node in nodestoremove:
    G.remove_node(node)
labels={}
for node in G.nodes():
    try:
        labels[node]=names['keysets']['generated'][nodeStdict[node]+'-name']['ru']
    except: labels[node]='error'
G = nx.relabel_nodes(G, labels)
nx.write_gml(G, "path_where_graph_should_be_saved.gml")

Файлы с JSON из приложения должны находиться в той же папке что и код. В результате генерируется граф в формате gml с названиями, связями и временами в пути.

Как выглядело бы Московское метро в трехмерном мире

87

Sakhar October 8, 2019 at 02:40 PM

+4

Единицы измерения в этом пространстве — часы. Расстояние между любой парой станций по прямой равно времени, которое нужно затратить на поездку с учётом пересадок (в часах)

Sakhar

Profile

Posts 1

Comments 6

Bookmarks

Info

Contribution to hubs

Your account

Sections

Info

Services