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

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

  • Как выглядело бы Московское метро в трехмерном мире
    0
    Это сделать можно, и скорее всего сработало бы, если учитывались бы времена только между соседними станциями; Время тогда можно было бы считать просто как сумму длин ребер графа пути от одной станции к другой. В двумерном пространстве даже такая задача не всегда решается. Пример — 4 станции, каждая связана с каждой и есть 4 времени перехода. В 2д случае такая задача не решается в общем виде, в 3d она решается при некоторых ограничениях на соотношения длин (комент снизу). В случае, когда оптимизация идет по всем парам станций, нарисовать адекватный граф в 2d еще труднее, и нужно больше степеней свободы для более точного построения для точного графа. Поэтому выбрано 3d пространство. Но никто не мешает запустить алгоритм с гораздо худшими результатами на 2д схеме (результат оптимизации 2д — последняя картинка в посте)
  • Как выглядело бы Московское метро в трехмерном мире
    0
    Спасибо большое за ценное замечание! Действительно, для евклидовых пространств утверждение, что «для любого графа существует такое пространство, что можно таким образом расставить точки, чтобы расстояние между любыми двумя ними было равно указанным длинам ребер графа» неверно. Нужно либо вводить дополнительные ограничение, чтобы удовлетворялось неравенство треугольника для любой тройки точек либо еще какое-то или смотреть на другие пространства с другими метриками.
  • Как выглядело бы Московское метро в трехмерном мире
    0
    добавил ссылку на схему метро на js Добавить js скрипт непосредственно в html поста не получилось — похоже на хабре это запрещено из соображений безопасности.
  • Как выглядело бы Московское метро в трехмерном мире
    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 с названиями, связями и временами в пути.
  • Как выглядело бы Московское метро в трехмерном мире
    +4

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