Специалистам по городскому планированию и урбанистам для проведения количественных исследований необходимо работать данными. Однако чиновники в РФ не спешат делиться городской статистикой открыто, выкладывая в открытый доступ только самый минимум информации. За рубежом ситуация обстоит чуть лучше, но все равно бывают случаи когда какого то датасета нет. (краткий обзор о необходимости и доступности открытых данных можно почитать тут.)
В этом случае приходится собирать данные самостоятельно. При этом не всегда речь идет о работе “в поле”, чаще всего вся информация и так есть в интернете, просто не все готовы ей делится. В этой статье я попытаюсь получить матрицу времен московского метрополитена, по пути реверсинжереним приложение Яндекс метро, а так же сделаем очень крутые визуализации полученной информации.
Постановка проблемы
Необходимо получить данные по времени в пути между любыми двумя станциями метро за любой год (так как Метро развивается, строятся новые станции, пересадки). Время в пути должно учитывать возможность пересадок (и их время).
Возможные решения
В метро ~300 станций, кажется что не особо много, но это C(300, 2) = 300! / (2! (300 - 2)!) = (300 * 299) / 2 = 44850 способов выбрать 2 из них. Любой ручной подсчет такого числа маршрутов обречен на провал. Использования API карт тоже сопряжённо с некоторыми проблемами - во-первых, оно учитывает время на спускса станции, во вторых у меня не будет доступа к архивным данным, так же для некоторых пар станций, маршрут на наземном транспорте окажется значительно быстрее чем с использованием подземки. Тогда путь на метро даже не будет предложен. Так же мне очень хотелось реверсинжинернуть какое-то мобильное приложение, так что идем к выбранному мной методу.
Приложения яндекс метро позволяет строить маршрут по подземке, а так же работает полностью офлайн - значит данные хранятся на телефоне пользователя. Запустив скачанный с компьютера и переброшенный по кабелю на телефон, не имеющий подключения к интернету, к радости для себя, обнаружил что приложение уже умело строить маршруты и ему не требовалось первичная синхронизация с сервером для подгрузки схем. Это означает что огромная база старых версий этой программы на 4pda позволит нам получить архивные данные о матрице времени метро почти любого города мира. Осталось только понять как это приложение устроено внутри.
APK файл
Я буду анализировать версию 2.05 за 2015 год. От версии к версии устройство базы данных, в которой хранится вся необходимая информация практический не менялось, вплоть до 2018 года. Тогда был произведен переход с sqlite на NoSQL базу данных, или проще говоря, данные стали хранить в JSONe (а структура осталось +- такой же).
Отрыв скачанный apk файл на компьютере с использованием zip архиватора мы увидим:
Папка метаинформация (META-INF): содержит файлы с подписями, сертификатами и манифестами приложения.
Папка ресурсы (res): содержит все ресурсы, такие как изображения, макеты и строки, используемые в приложении.
Код (classes.dex): содержит скомпилированный Java-код, который выполняет функции приложения.
Разное (lib): содержит библиотеки, которые используются приложением, например, для работы с изображениями или звуком.
Манифест (AndroidManifest.xml): содержит информацию о приложении, такую как имя пакета, разрешения и компоненты приложения.
Обратите внимание, что файлы в папке APK могут быть зашифрованы или сжаты, поэтому вы не сможете просто открыть их и прочитать содержимое. Если вы хотите изучить код и ресурсы приложения, вам нужно использовать специальные инструменты, такие как декомпилятор.
Однако в нашем случае база данных представляет собой незашифрованный sqlite файл по адресу res/raw/yandex2.db . В данном случае местонахождение этого файла было очевидным, однако для поиска в более сложных ситуациях можно использовать утилитами поиска по расширению и типу файла.
База данных
sqlite файлы проще всего изучать используя sqlitebrowser. Это свободное программное мультиплатформенная программное обеспечение с простым графическим интерфейсам смогло отрыть и нашу базу данных. Структура этой базы данных тоже не вызывает вопросов. Таблица stations содержит информацию о станциях, с указанием их названия, местоположения итп. Информация о пересадках содержится в таблице Transfer. Все оказалось сильно проще чем могло бы быть.
Новые версии
Данные хранятся в папке assets/metrokit/. Теперь JSON файлы прочтем Python-ом, переведя в Networkx Graph, тем более @Sakhar уже написал удобный скрипт, когда строил трехмерную карту метро.
names = json.loads(codecs.open( "l10n.json", "r", "utf_8_sig" ).read())
graph = json.loads(codecs.open( "data.json", "r", "utf_8_sig" ).read())nodeStdict={}
for stop in graph['stops']['items']:
nodeStdict[stop['nodeId']]=stop['stationId']
G=nx.Graph()
for node in graph['nodes']['items']:
G.add_node(node['id'])
for link in graph['links']['items']:
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'Давайте посмотрим что у нас вышло:
nx.draw(G)
Схемка, конечно, попонятнее чем от Артемия Лебедева, но к концу статьи мы ее сделаем еще лучше. (Зато теперь понятно как появился логотип хабра, прим acsent1)
Теперь научимся строить маршрут между двумя станциями. Для этого можно использовать алгоритм Дейкстры. Про то, как он работает, написано уже тысячи статей (например тык), так что не будем на этом останавливаться, тем более он уже реализован в нашей библиотеке.
def calc_time(st1, st2):
return nx.dijkstra_path_length(G, source=st1, target=st2, weight="length")/60
print(labels) # ... 'nd89811596': 'Римская', 'nd79168908': 'Крестьянская Застава', ...
calc_time("nd89811596", "nd79168908") # 4Как мы видим, получили ответ 4. Именно столько минут занимает путь между этими станциями. (Запрос через сайт выдает 5 минут в пути, однако возомжно он использует какую-то информацию о количестве подвижного состава в реальном времени.
Давайте теперь вычислим искомую матрицу. Очевидным решением было бы рассмотреть всевозможные пары станций и попытаться построить маршрут:
Однако такой способ жутко неэффективен. Если А и В соседние станции, а С находится в отдолении, то строя оптимальный маршрут А - С мы уже знаем (или почти знаем) время в пути по В - С, из-за приципов работы алгоритма Дейкстры. Однако мы про эту информацию “забываем” и строим маршрут заново. Для решения нашей задачи подойдет алгоритм Флойда — Уоршелла. (вот кстати та причина, по которой даже с использованием выскокоуровневых библиотек хорошо бы хотя бы представлять как работают алгоритмы.) NetworkX из коробки умеет и такое:
res: dict = nx.floyd_warshall(G)
print(res)
Давайте попытаемся сделать что еще. Например найти количество станций в 20-и минутной окресности от данной. Решим в лоб
res = {}
counter = {}
for st1_id, st1_name in labels.items():
res[f"{st1_id}_{st1_name}"] = []
counter[f"{st1_id}_{st1_name}"] = 0
for st2_id, st2_name in labels.items():
if st1_id != st2_id and calc_time(st1_id, st2_id) < 20:
res[f"{st1_id}_{st1_name}"].append(f"{st2_id}_{st2_name}")
counter[f"{st1_id}_{st1_name}"] += 1
print(st1_name, st2_name)Теперь можно попытаться его оптимизировать. Тут решение немного попроще - обход в ширину. (можно использовать nx.bfs_edges() или реализовать самим):
def get_stations_within_distance(G, source_node, distance):
visited = set()
queue = [(source_node, 0)]
while queue:
node, dist = queue.pop(0)
visited.add(node)
if dist < distance:
neighbors = nx.neighbors(G, node)
for neighbor in neighbors:
if neighbor not in visited:
queue.append((neighbor, dist + G[node][neighbor]['length']))
return visitedТеперь попытаемся визуализировать полученные данные. Немного магии компьютерного зрения и пару команд PIL позволяют построить вот такую красоту (исходник):
https://i.postimg.cc/szcs3D75/mcd-scheme-crop.png?dl=1
Тут размер круга пропорционален количеству других станций в 20-и минутном интервале. На этой картинке хорошо видно безумную разницу между центром города (где за 20 минут можно попасть на 100+ станций) и спальниками (где есть только один путь - в центр. Разумеется, всегда будут какие станции с большим, а какие-то с меньшим количеством удачных пересадок, плохо когда 100% хабов находятся в центре города
Метро Лондона, для справки
Так же использовать полученные нами данные можно, чтобы сделать более удобную карту метро. По ней можно будет оценить время в пути просто мелько взглянув на карту, без использования мобильных приложений или интерактивных экранов. В чем идея?
На каждой не кольцевой кольца мы пишем время в минутах, которое требуется для поездки до кольцевой на этой линии.
На каждой кольцевой станции мы пишем время в пути до какой-то фиксированной станции метро (например до Комсомольской).
Теперь что бы рассчитать время маршрута достаточно просто:
Вычесть (сложить, если мы переезжаем через кольцо) два указанных времени, для простых маршрутов без пересадок
Сложить два числа на станциях отправления и прибытия, а так же прибавить разность двух пересадок на кольце, если мы едем по пути радиус - кольцо - радиус.
В заключении
Надеюсь, что эта статья была кому-то полезна. Использование таких неочевидных источников данных как мобильное приложение, работающее в режиме оффлайн, может сильно помочь исследователям из стран не развивающих open data активно. Весь исходный код вы сможете найти в гугл колабе, но там довольно большой беспорядок, но разобраться будет проще чем все писать с нуля. Для его работы нужно загрузить JSON файлы с метрополитеном города.
Комментарии (15)
thesame
00.00.0000 00:00Для поездок по относительно старым веткам, введенным до 2000 (2010) года, я использую эмпирическую формулу 3-3-1.5, где 3 минуты - время между станциями, 3 минуты - время на вход/выход в метро или переход, 1.5 минуты - время ожидания поезда (в часы пик обычно 1 минута, но там может увеличиться время на переход). Формула дает хорошую оценку сверху времени в пути с превышением на 5-10 минут на длинных маршрутах.
Для новых веток и станций за МКАДом можно добавить 5 минут и еще 3-5 минут ожидания для Ольховки и Бутовской ветки. Солнцевскую я пока толком не исследовал.
МЦК/МЦД - время перехода 10 минут, время ожидания - 5-10 минут.
lair
А не через кольцо пересадок не бывает, да? А если пересадок больше одной, и обе не через кольцо (я так одно время ездил с Савеловской в Митино)?
Так что я не вижу смысла зашумлять карту цифрами, которыми все равно неудобно пользоваться для (чем дальше, тем большего) числа случаев.
FF_hunter
В чем проблема? Зная время до кольцевой от начала текущего отрезка пути и от станции пересадки, считаем отдельно время в пути по каждой ветке. Складываем результаты, и к полученной сумме добавляем среднее время пересадки для задействованных пар станций. Получаем итоговое время пути. Я не москвич, но думаю, что редкий маршрут включает в себя более двух подземных пересадок. А уж 3 двузначных числа сложить в уме, дай Б-г, сможет каждый. Поэтому в целом способ рабочий.
P.S. Совсем не обязательно привязываться к времени именно до кольцевой. Это может быть и условная середина ветки, чтобы всем было считать примерно одинаково просто. Или даже конечная станция, при условии, что она гарантированно останется конечной в будущем. Например, в случае наличия естественных преград к ведению дальнейшего строительства, типа крупных водоёмов, гор, и т.д.
lair
В том, что слишком много всего надо в уме держать. Особенно если хочется выбрать маршрут по времени. А еще некоторые ветки не имеют пересечения с кольцевой.
Вам надо сначала вычислить три двухзначных числа, а потом их сложить. Проблема (лично у меня) возникает там, где надо за время вычисления второй пары не забыть результат первой.
А и двух достаточно. От Савеловской до Митино есть как минимум четыре маршрута - попробуйте по схеме понять, какой из них короче.
В целом, способ "просто посмотри в телефоне" - тоже рабочий (и более эффективный). Вопрос же о том, какая схеме удобнее.
FF_hunter
Так и оптимизацию никто не отменял. Очевидно, что время в пути прямо пропорционально количеству станций. И ровно то же самое про кол-во пересадок. Видел я маршрут Савеловская - Митино. Нашлось 2 пути с двумя пересадками и 1 с 4. Выбор однозначен, лучше потратить на целых 3-4 минуты больше времени в дороге, зато сэкономить силы перед активным трудовым днем или после такового. Да и на кольцевой свет клином не сошелся, многие города до сих пор без нее прекрасно обходятся.
И да, вариант с телефоном далеко не всегда так хорош, как кажется. Москва город специфический, многие приезжают туда на недельку-другую из разных стран. Проводя аналогии, это как оказаться в каком-нибудь условном Нью-Йорке или Сеуле с телефоном, в котором нет ничего, кроме сервисов Яндекса. И вот тогда уже удобность такой бумажной схемы перестает вызывать сомнения.
lair
Не всегда. От Сокола до Белорусской - три станции, восемь минут. От Мякинино до Крылатского - две станция, но одиннадцать минут.
Маршрута с одной пересадкой вы не нашли, да? А их два.
Но при это я предпочту поехать по Д-2, пусть это и с двумя пересадками, но зато (а) я большую часть времени буду ехать поверху, и (б) это на семь минут быстрее (а не на 3-4).
Для этих людей работают (раньше работали) Гугл-карты. А если и этого нет - информационные табло прекрасно справляются.
Я как-то раз был в Токио, в котором тогда не работали гугл-карты нормально. Так вот, первое, что я сделал - это нашел сервис, который позволял строить маршруты по тамошней схеме метро и ЖД, потому что сделать это самому без опыта - между "сложно" и "нереально", а когда ты еще и в стрессе от поездки - тем более.
Неа, не перестает. Почему вы думаете, что приезжие смогут вообще пользоваться этой схемой, если в их родных городах ее нет?
Это как раз как я в Токио, Нью-Йорке, Лондоне или Мадриде - чем пытаться разобраться в нескольких видах транспорта (и том, как они рисуются на конкретной схеме), проще попросить приложение построить маршрут.
FF_hunter
Рискну предположить, что первый маршрут будет скорее ближе к центру города, тогда как второй ближе к периферии. Тогда всё логично. Но я говорил о статистической вероятности корреляции длины маршрута с его, условно, скоростью. Исключения есть всегда, но их немного.
Видимо, подразумевается маршрут через Кунцевскую? Видел я его, но склонен таки записать в вариант с двумя пересадками, потому что иначе это бы выглядело натягиванием хода расчетов на заранее известный результат. Поэтому и брал время пути от самой дальней Савеловской, чтобы уж наверняка не промахнуться, раз уж их всё равно несколько.
Ну и да, 7 минут экономии времени в сутки - это серьезный результат, тут не поспорить) Берем случайный пример, маршрут Парнас - Девяткино. Есть как минимум 4 варианта пути, 1 из них с одной пересадкой и 3 с двумя. И да, один из этих трех вариантов выходит даже на целых 2 минуты быстрее. В реальности, конечно, мало кто поедет по северу города через центр, проще выбрать трамвай, маршрутку или даже такси. Но если бы случилось так, что мне почему-то пришлось ехать именно на метро, я бы абсолютно точно выбрал вариант с одной пересадкой, хоть он и дольше.
Про какие табло идет речь? Те, что я видел, можно назвать полезными с очень большой натяжкой. Возможно, в последние годы что-то и поменялось.
Токио вообще отдельная тема. Там местные-то в этих схемах путаются, когда нужно отклониться от маршрута дом - работа. И кажется даже есть официальная услуга от перевозчиков по платному составлению маршрутов прямо в билетных кассах. К счастью, существует не так уж и много стран с большим населением, малой площадью и настолько широко развитой ЖД логистикой, чтобы опыт Японии был массово востребован. Тут скорее из разряда "так звезды сошлись", слишком много факторов совпало.
lair
Было бы логично, если бы следующие перегоны за Строгино не были опять короткими.
Вопрос в том, как мерять "длину".
Их достаточно, чтобы портить маршруты.
Через Боровицкую, очевидно.
Это почему вдруг?
В сутки - пятнадцать (потому что туда и обратно). И это уже прилично. Например, это время на чашку кофе.
...или МЦД, или МЦК, или БКЛ... Именно поэтому приложение удобнее.
Которые стоят на станциях и в новых поездах, где можно просто выбрать откуда куда едешь.
Вот именно поэтому есть сервис, который это прекрасно считает. То же самое и в Москве.
Ну вот в Москве и МО он уже востребован, учитывая как минимум три разных системы только рельсового транспорта.
freQuensy23 Автор
Разумеется такой способ сильно менее удобный чем построить через навигатор. Но дать быструю оценку времени в пути он может. Условно я регулярно еду с севера мск в центр, и часто мне звонят и спрашивают когда я буду. Я знаю что на данный момент я на условной "Владыкино", но вот сколько еще ехать 0 представления. С использованием такой карты, примерно сложив 2 числа я смогу дать точный ответ - через 15 30 или 40 минут.
lair
Вопрос в том, достаточно ли таких случаев, чтобы оправдать дополнительную информацию на и без того загруженной карте.