Краткое описание методики анализа доступности элементов сложной структуры 3
Результаты анализа графов, построенных на основе существующих схем метрополитена. 5
Санкт-Петербург. 5
Последовательность выполнения анализа 11
Запуск модулей Common LISP для выполнения анализа. 14
Амстердам. 15
Москва. 21
Париж. 25
Сводная таблица результатов анализа схем метрополитена различных городов мира. 32
Приложение 1. Модуль Common Lisp для построения матрицы всех кратчайших путей между всеми парами вершин. 33
Приложение 2. Модуль Common Lisp для построения матрицы смежностей графа в виде массива строк бит. 35
Приложение 3. Санкт-Петербург 36
Приложение 4. Москва. 37
Приложение 5. Киев. 38
Приложение 6. Рим. 39
Приложение 7. Париж. 40
Приложение 8. Лондон. 41
Приложение 9. Хельсинки. 42
Приложение 10. Берлин. 43
Приложение 11. Амстердам. 44
Приложение 12. Модуль 'ss.lisp' 45
Приложение 13. Модуль 'ws.lisp'. 46
Введение
В стандартных наборах методов анализа топологии, реализованных в геоинформационных системах отсутствуют средства оценки и сравнения топологических структур в целом, отсутствуют функции анализа структурной сложности топологии, сравнения различных структур между собой, отсутствует механизм отслеживания изменений в структурной сложности при внесении изменений в топологию изучаемого объекта.
Настоящая работа посвящена задаче реализации методики оценки доступности элементов структуры сложных объектов для сравнения различных объектов и моделирования изменений в них для целенаправленного достижения нужного уровня сложности.
Практическое применение этих дополнений к геоинформационным системам довольно велико, например - при изучении структуры транспортных схем, в частности метрополитена, реализованных в различных городах мира, что позволит выявить качественные различия между различными схемами и найти общие закономерности их построения, определить худшие и лучшие варианты для дальнейшего использования в практике проектирования.
Несмотря на то, что формирование сети станций метрополитена - задача намного более сложная и многогранная, зависящая от множества иных, не только топологических проблем, эта задача очень хорошо и наглядно иллюстрирует возможности разработанной методики и дает инструмент для решения подобных задач в других областях, для которых топологические проблемы являются наиболее важными.
Краткое описание методики анализа доступности элементов сложной структуры
Для изучения доступности элементов объектов сложной структуры применяется аппарат теории графов и сетей, в частности, метод нахождения всех кратчайших путей матрицы смежностей графа при помощи алгоритма Флойда, реализованный в модуле 'kp.lisp' (Приложение 1). Для подготовки исходных данных используется модуль 'ms.lisp' (Приложение 2), который формирует матрицу смежностей объекта в виде массива строк бит.
Для анализа объекта строится его граф на основе растрового изображения. Перечень использованных в работе изображений - в Приложениях 3 - 11.
Структурная сложность объекта определяется при помощи индекса Винера (WIENER, 1947) W - полусуммы элементов матрицы расстояний (кратчайших путей между всеми парами вершин):
где di,j - элемент матрицы расстояний.
Определение топологического центра сложного объекта и его внутренней структуры может быть выполнено при помощи индекса суммы расстояний (BONCHEV, 1980):
Для оценки и сравнения топологических структур с резко отличающимся количеством узлов можно применять относительные значения индексов:
где
или
где
или
Расчет индексов Винера и суммы расстояний реализован в модуле 'ws.lisp' (Приложение 13).
Для выполнения анализа запускается модуль 'TAN.lisp', который последовательно вызывает модули 'ss.lisp', 'ms.lisp', 'kp.lisp', 'ws.lisp'. Исходные данные для модуля 'TAN.lisp' должны находиться в файле 'a.txt' - выгруженная из Autodesk MAP совокупность таблиц TPMLINK_имя-топологии.
Результаты анализа графов, построенных на основе существующих схем метрополитена.
Санкт-Петербург.
Существующая топологическая структура метрополитена Санкт-Петербурга дает следующий перечень 'топологических слоев' в отображающем ее графе (результат работы модуля 'kp.lisp'):
747 (ДЕВЯТКИНО)
690 (ГРАЖДАНСКИЙ)
678 (КУПЧИНО)
660 (ПРОСВЕЩЕНИЯ)
640 (ВЕТЕРАНОВ)
635 (АКАДЕМИЧЕСКАЯ)
621 (ЗВЕЗДНАЯ)
603 (ОЗЕРКИ)
601 (РЫБАЦКОЕ)
583 (ЛЕНИНСКИЙ)
582 (ПОЛИТЕХНИЧЕСКАЯ)
574 (КОМЕНДАНТСКИЙ)
567 (ДЫБЕНКО)
566 (МОСКОВСКАЯ)
548 (УДЕЛЬНАЯ)
544 (ОБУХОВО)
531 (МУЖЕСТВА)
528 (АВТОВО)
517 (СТАРАЯ_ДЕРЕВНЯ)
513 (ПАРКПОБЕДЫ)
510 (БОЛЬШЕВИКОВ)
495 (ПИОНЕРСКАЯ)
489 (ПРОЛЕТАРСКАЯ)
482 (ЛЕСНАЯ)
475 (КИРОВСКИЙ)
462 (ЭЛЕКТРОСИЛА КРЕСТОВСКИЙ)
455 (ЛАДОЖСКАЯ)
444 (ЧЕРНАЯ_РЕЧКА)
436 (ЛОМОНОСОВСКАЯ)
435 (ВЫБОРГСКАЯ)
424 (НАРВСКАЯ)
420 (ПРИМОРСКАЯ)
413 (МОСКОВСКИЕВОРОТА)
409 (ЧКАЛОВСКАЯ)
402 (НОВОЧЕРКАССКАЯ)
395 (ПЕТРОГРАДСКАЯ)
390 (ПЛ_ЛЕНИНА)
385 (ЕЛИЗАРОВСКАЯ)
375 (БАЛТИЙСКАЯ)
366 (ФРУНЗЕНСКАЯ)
363 (ВАСИЛЕОСТРОВСКАЯ)
358 (СПОРТИВНАЯ)
351 (АЛ_НЕВСКОГО_2)
348 (ГОРЬКОВСКАЯ)
347 (ЧЕРНЫШЕВСКАЯ)
340 (ЛИГОВСКАЯ)
336 (АЛ_НЕВСКОГО_1)
328 (ТЕХНОЛ1)
326 (ПУШКИНСКАЯ)
321 (ТЕХНОЛ2)
309 (ДОСТОЕВСКАЯ САДОВАЯ)
308 (ВЛАДИМИРСКАЯ МАЯКОВСКАЯ ГОСТИННЫЙ_ДВОР)
306 (ВОССТАНИЯ)
305 (СЕННАЯ)
303 (НЕВСКИЙПРОСПЕКТ)
Выявлено 55 слоев топологической структуры (по величине индекса суммы расстояний, станции ранжированы по величине этого индекса). 'Невский проспект' является топологическим центром метрополитена (равноудаленным от всех остальных станций), его индекс S = 303.
Вверху списка находятся станции, имеющие максимальные значения S и имеющие худшие параметры 'достижимости' до всех остальных станций 'ДЕВЯТКИНО', 'ГРАЖДАНСКИЙ', 'КУПЧИНО', 'ПРОСВЕЩЕНИЯ', 'ВЕТЕРАНОВ', 'АКАДЕМИЧЕСКАЯ', 'ЗВЕЗДНАЯ' и т.д.
Структурированность топологической схемы оценивается количеством и мощностью ее топологических слоев. В данном случае имеется 55 слоев при 59 станциях, т.е. схема практически не структурирована.
Посмотрим, как меняется топологическая структура схемы метрополитена при внесении в нее некоторых изменений.
Посмотрим, как изменится топологическая структура метрополитена при соединении станций Василеостровская - Старая Деревня - Пионерская - Площадь Мужества - Ладожская - Пролетарская - Московская - Ленинский проспект - Василеостровская, т.е. при создании кольца.
Исходные списки станций в этом случае будут выглядеть так: