Клименко Борис Федорович : другие произведения.

Доступность элементов сложной структуры

Самиздат: [Регистрация] [Найти] [Рейтинги] [Обсуждения] [Новинки] [Обзоры] [Помощь|Техвопросы]
Ссылки:
Школа кожевенного мастерства: сумки, ремни своими руками
 Ваша оценка:
  Введение 2
  Краткое описание методики анализа доступности элементов сложной структуры 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 станциях, т.е. схема практически не структурирована.
  
  Посмотрим, как меняется топологическая структура схемы метрополитена при внесении в нее некоторых изменений.
  
  Исходная структура списков смежных станций:
  
  (ВЕТЕРАНОВ ЛЕНИНСКИЙ NIL)
  (ЛЕНИНСКИЙ ВЕТЕРАНОВ АВТОВО)
  (АВТОВО ЛЕНИНСКИЙ КИРОВСКИЙ)
  (КИРОВСКИЙ АВТОВО НАРВСКАЯ)
  (НАРВСКАЯ КИРОВСКИЙ БАЛТИЙСКАЯ)
  (БАЛТИЙСКАЯ НАРВСКАЯ ТЕХНОЛ1)
  (ТЕХНОЛ1 БАЛТИЙСКАЯ ПУШКИНСКАЯ ТЕХНОЛ2)
  (ПУШКИНСКАЯ ТЕХНОЛ1 ВЛАДИМИРСКАЯ)
  (ВЛАДИМИРСКАЯ ПУШКИНСКАЯ ВОССТАНИЯ ДОСТОЕВСКАЯ)
  (ВОССТАНИЯ ВЛАДИМИРСКАЯ ЧЕРНЫШЕВСКАЯ МАЯКОВСКАЯ)
  (ЧЕРНЫШЕВСКАЯ ВОССТАНИЯ ПЛ_ЛЕНИНА)
  (ПЛ_ЛЕНИНА ЧЕРНЫШЕВСКАЯ ВЫБОРГСКАЯ)
  (ВЫБОРГСКАЯ ПЛ_ЛЕНИНА ЛЕСНАЯ)
  (ЛЕСНАЯ ВЫБОРГСКАЯ МУЖЕСТВА)
  (МУЖЕСТВА ЛЕСНАЯ ПОЛИТЕХНИЧЕСКАЯ)
  (ПОЛИТЕХНИЧЕСКАЯ МУЖЕСТВА АКАДЕМИЧЕСКАЯ)
  (АКАДЕМИЧЕСКАЯ ПОЛИТЕХНИЧЕСКАЯ ГРАЖДАНСКИЙ)
  (ГРАЖДАНСКИЙ АКАДЕМИЧЕСКАЯ ДЕВЯТКИНО)
  (ДЕВЯТКИНО ГРАЖДАНСКИЙ NIL)
  (КУПЧИНО ЗВЕЗДНАЯ NIL)
  (ЗВЕЗДНАЯ КУПЧИНО МОСКОВСКАЯ)
  (МОСКОВСКАЯ ЗВЕЗДНАЯ ПАРКПОБЕДЫ)
  (ПАРКПОБЕДЫ МОСКОВСКАЯ ЭЛЕКТРОСИЛА)
  (ЭЛЕКТРОСИЛА ПАРКПОБЕДЫ МОСКОВСКИЕВОРОТА)
  (МОСКОВСКИЕВОРОТА ЭЛЕКТРОСИЛА ФРУНЗЕНСКАЯ)
  (ФРУНЗЕНСКАЯ МОСКОВСКИЕВОРОТА ТЕХНОЛ2)
  (ТЕХНОЛ2 ФРУНЗЕНСКАЯ СЕННАЯ ТЕХНОЛ1)
  (СЕННАЯ ТЕХНОЛ2 НЕВСКИЙПРОСПЕКТ САДОВАЯ)
  (НЕВСКИЙПРОСПЕКТ СЕННАЯ ГОРЬКОВСКАЯ ГОСТИННЫЙ_ДВОР)
  (ГОРЬКОВСКАЯ НЕВСКИЙПРОСПЕКТ ПЕТРОГРАДСКАЯ)
  (ПЕТРОГРАДСКАЯ ГОРЬКОВСКАЯ ЧЕРНАЯ_РЕЧКА)
  (ЧЕРНАЯ_РЕЧКА ПЕТРОГРАДСКАЯ ПИОНЕРСКАЯ)
  (ПИОНЕРСКАЯ ЧЕРНАЯ_РЕЧКА УДЕЛЬНАЯ)
  (УДЕЛЬНАЯ ПИОНЕРСКАЯ ОЗЕРКИ)
  (ОЗЕРКИ УДЕЛЬНАЯ ПРОСВЕЩЕНИЯ)
  (ПРОСВЕЩЕНИЯ ОЗЕРКИ NIL)
  (РЫБАЦКОЕ ОБУХОВО NIL)
  (ОБУХОВО РЫБАЦКОЕ ПРОЛЕТАРСКАЯ)
  (ПРОЛЕТАРСКАЯ ОБУХОВО ЛОМОНОСОВСКАЯ)
  (ЛОМОНОСОВСКАЯ ПРОЛЕТАРСКАЯ ЕЛИЗАРОВСКАЯ)
  (ЕЛИЗАРОВСКАЯ ЛОМОНОСОВСКАЯ АЛ_НЕВСКОГО_1)
  (АЛ_НЕВСКОГО_1 ЕЛИЗАРОВСКАЯ МАЯКОВСКАЯ АЛ_НЕВСКОГО_2)
  (МАЯКОВСКАЯ АЛ_НЕВСКОГО_1 ГОСТИННЫЙ_ДВОР ВОССТАНИЯ)
  (ГОСТИННЫЙ_ДВОР МАЯКОВСКАЯ ВАСИЛЕОСТРОВСКАЯ НЕВСКИЙПРОСПЕКТ)
  (ВАСИЛЕОСТРОВСКАЯ ГОСТИННЫЙ_ДВОР ПРИМОРСКАЯ)
  (ПРИМОРСКАЯ ВАСИЛЕОСТРОВСКАЯ NIL)
  (ДЫБЕНКО БОЛЬШЕВИКОВ NIL)
  (БОЛЬШЕВИКОВ ДЫБЕНКО ЛАДОЖСКАЯ)
  (ЛАДОЖСКАЯ БОЛЬШЕВИКОВ НОВОЧЕРКАССКАЯ)
  (НОВОЧЕРКАССКАЯ ЛАДОЖСКАЯ АЛ_НЕВСКОГО_2)
  (АЛ_НЕВСКОГО_2 НОВОЧЕРКАССКАЯ ЛИГОВСКАЯ АЛ_НЕВСКОГО_1)
  (ЛИГОВСКАЯ АЛ_НЕВСКОГО_2 ДОСТОЕВСКАЯ)
  (ДОСТОЕВСКАЯ ЛИГОВСКАЯ САДОВАЯ ВЛАДИМИРСКАЯ)
  (САДОВАЯ ДОСТОЕВСКАЯ СПОРТИВНАЯ СЕННАЯ)
  (СПОРТИВНАЯ САДОВАЯ ЧКАЛОВСКАЯ)
  (ЧКАЛОВСКАЯ СПОРТИВНАЯ КРЕСТОВСКИЙ)
  (КРЕСТОВСКИЙ ЧКАЛОВСКАЯ СТАРАЯ_ДЕРЕВНЯ)
  (СТАРАЯ_ДЕРЕВНЯ КРЕСТОВСКИЙ КОМЕНДАНТСКИЙ)
  (КОМЕНДАНТСКИЙ СТАРАЯ_ДЕРЕВНЯ NIL)
  
  Посмотрим, как изменится топологическая структура метрополитена при соединении станций Василеостровская - Старая Деревня - Пионерская - Площадь Мужества - Ладожская - Пролетарская - Московская - Ленинский проспект - Василеостровская, т.е. при создании кольца.
  
  Исходные списки станций в этом случае будут выглядеть так:
  
  (ВЕТЕРАНОВ ЛЕНИНСКИЙ NIL)
  (ЛЕНИНСКИЙ ВЕТЕРАНОВ АВТОВО МОСКОВСКАЯ ВАСИЛЕОСТРОВСКАЯ)
  (АВТОВО ЛЕНИНСКИЙ КИРОВСКИЙ)
  (КИРОВСКИЙ АВТОВО НАРВСКАЯ)
  (НАРВСКАЯ КИРОВСКИЙ БАЛТИЙСКАЯ)
  (БАЛТИЙСКАЯ НАРВСКАЯ ТЕХНОЛ1)
  (ТЕХНОЛ1 БАЛТИЙСКАЯ ПУШКИНСКАЯ ТЕХНОЛ2)
  (ПУШКИНСКАЯ ТЕХНОЛ1 ВЛАДИМИРСКАЯ)
  (ВЛАДИМИРСКАЯ ПУШКИНСКАЯ ВОССТАНИЯ ДОСТОЕВСКАЯ)
  (ВОССТАНИЯ ВЛАДИМИРСКАЯ ЧЕРНЫШЕВСКАЯ МАЯКОВСКАЯ)
  (ЧЕРНЫШЕВСКАЯ ВОССТАНИЯ ПЛ_ЛЕНИНА)
  (ПЛ_ЛЕНИНА ЧЕРНЫШЕВСКАЯ ВЫБОРГСКАЯ)
  (ВЫБОРГСКАЯ ПЛ_ЛЕНИНА ЛЕСНАЯ)
  (ЛЕСНАЯ ВЫБОРГСКАЯ МУЖЕСТВА)
  (МУЖЕСТВА ЛЕСНАЯ ПОЛИТЕХНИЧЕСКАЯ ПИОНЕРСКАЯ ЛАДОЖСКАЯ)
  (ПОЛИТЕХНИЧЕСКАЯ МУЖЕСТВА АКАДЕМИЧЕСКАЯ)
  (АКАДЕМИЧЕСКАЯ ПОЛИТЕХНИЧЕСКАЯ ГРАЖДАНСКИЙ)
  (ГРАЖДАНСКИЙ АКАДЕМИЧЕСКАЯ ДЕВЯТКИНО)
  (ДЕВЯТКИНО ГРАЖДАНСКИЙ NIL)
  (КУПЧИНО ЗВЕЗДНАЯ NIL)
  (ЗВЕЗДНАЯ КУПЧИНО МОСКОВСКАЯ)
  (МОСКОВСКАЯ ЗВЕЗДНАЯ ПАРКПОБЕДЫ ПРОЛЕТАРСКАЯ ЛЕНИНСКИЙ)
  (ПАРКПОБЕДЫ МОСКОВСКАЯ ЭЛЕКТРОСИЛА)
  (ЭЛЕКТРОСИЛА ПАРКПОБЕДЫ МОСКОВСКИЕВОРОТА)
  (МОСКОВСКИЕВОРОТА ЭЛЕКТРОСИЛА ФРУНЗЕНСКАЯ)
  (ФРУНЗЕНСКАЯ МОСКОВСКИЕВОРОТА ТЕХНОЛ2)
  (ТЕХНОЛ2 ФРУНЗЕНСКАЯ СЕННАЯ ТЕХНОЛ1)
  (СЕННАЯ ТЕХНОЛ2 НЕВСКИЙПРОСПЕКТ САДОВАЯ)
  (НЕВСКИЙПРОСПЕКТ СЕННАЯ ГОРЬКОВСКАЯ ГОСТИННЫЙ_ДВОР)
  (ГОРЬКОВСКАЯ НЕВСКИЙПРОСПЕКТ ПЕТРОГРАДСКАЯ)
  (ПЕТРОГРАДСКАЯ ГОРЬКОВСКАЯ ЧЕРНАЯ_РЕЧКА)
  (ЧЕРНАЯ_РЕЧКА ПЕТРОГРАДСКАЯ ПИОНЕРСКАЯ)
  (ПИОНЕРСКАЯ ЧЕРНАЯ_РЕЧКА УДЕЛЬНАЯ СТАРАЯ_ДЕРЕВНЯ МУЖЕСТВА)
  (УДЕЛЬНАЯ ПИОНЕРСКАЯ ОЗЕРКИ)
  (ОЗЕРКИ УДЕЛЬНАЯ ПРОСВЕЩЕНИЯ)
  (ПРОСВЕЩЕНИЯ ОЗЕРКИ NIL)
  (РЫБАЦКОЕ ОБУХОВО NIL)
  (ОБУХОВО РЫБАЦКОЕ ПРОЛЕТАРСКАЯ)
  (ПРОЛЕТАРСКАЯ ОБУХОВО ЛОМОНОСОВСКАЯ ЛАДОЖСКАЯ МОСКОВСКАЯ)
  (ЛОМОНОСОВСКАЯ ПРОЛЕТАРСКАЯ ЕЛИЗАРОВСКАЯ)
  (ЕЛИЗАРОВСКАЯ ЛОМОНОСОВСКАЯ АЛ_НЕВСКОГО_1)
  (АЛ_НЕВСКОГО_1 ЕЛИЗАРОВСКАЯ МАЯКОВСКАЯ АЛ_НЕВСКОГО_2)
  (МАЯКОВСКАЯ АЛ_НЕВСКОГО_1 ГОСТИННЫЙ_ДВОР ВОССТАНИЯ)
  (ГОСТИННЫЙ_ДВОР МАЯКОВСКАЯ ВАСИЛЕОСТРОВСКАЯ НЕВСКИЙПРОСПЕКТ)
  (ВАСИЛЕОСТРОВСКАЯ ГОСТИННЫЙ_ДВОР ПРИМОРСКАЯ СТАРАЯ_ДЕРЕВНЯ ЛЕНИНСКИЙ)
  (ПРИМОРСКАЯ ВАСИЛЕОСТРОВСКАЯ NIL)
  (ДЫБЕНКО БОЛЬШЕВИКОВ NIL)
  (БОЛЬШЕВИКОВ ДЫБЕНКО ЛАДОЖСКАЯ)
  (ЛАДОЖСКАЯ БОЛЬШЕВИКОВ НОВОЧЕРКАССКАЯ МУЖЕСТВА ПРОЛЕТАРСКАЯ)
  (НОВОЧЕРКАССКАЯ ЛАДОЖСКАЯ АЛ_НЕВСКОГО_2)
  (АЛ_НЕВСКОГО_2 НОВОЧЕРКАССКАЯ ЛИГОВСКАЯ АЛ_НЕВСКОГО_1)
  (ЛИГОВСКАЯ АЛ_НЕВСКОГО_2 ДОСТОЕВСКАЯ)
  (ДОСТОЕВСКАЯ ЛИГОВСКАЯ САДОВАЯ ВЛАДИМИРСКАЯ)
  (САДОВАЯ ДОСТОЕВСКАЯ СПОРТИВНАЯ СЕННАЯ)
  (СПОРТИВНАЯ САДОВАЯ ЧКАЛОВСКАЯ)
  (ЧКАЛОВСКАЯ СПОРТИВНАЯ КРЕСТОВСКИЙ)
  (КРЕСТОВСКИЙ ЧКАЛОВСКАЯ СТАРАЯ_ДЕРЕВНЯ)
  (СТАРАЯ_ДЕРЕВНЯ КРЕСТОВСКИЙ КОМЕНДАНТСКИЙ ВАСИЛЕОСТРОВСКАЯ ПИОНЕРСКАЯ)
  (КОМЕНДАНТСКИЙ СТАРАЯ_ДЕРЕВНЯ NIL)
  
  Топологическая структура метрополитена в этом случае существенно изменится:
  
   447 (ДЕВЯТКИНО)
   397 (ПРОСВЕЩЕНИЯ)
   390 (ГРАЖДАНСКИЙ)
   346 (КУПЧИНО)
   345 (РЫБАЦКОЕ)
   341 (БАЛТИЙСКАЯ)
   340 (ОЗЕРКИ)
   337 (ДЫБЕНКО)
   335 (НАРВСКАЯ АКАДЕМИЧЕСКАЯ)
   326 (МОСКОВСКИЕВОРОТА)
   324 (ФРУНЗЕНСКАЯ)
   323 (ТЕХНОЛ1)
   320 (ПУШКИНСКАЯ)
   313 (КИРОВСКИЙ)
   311 (ПЛ_ЛЕНИНА)
   309 (ЭЛЕКТРОСИЛА)
   302 (СПОРТИВНАЯ)
   301 (ВЫБОРГСКАЯ ТЕХНОЛ2)
   300 (ЧЕРНЫШЕВСКАЯ)
   293 (ЧКАЛОВСКАЯ)
   289 (ЗВЕЗДНАЯ ПЕТРОГРАДСКАЯ)
   288 (ВЛАДИМИРСКАЯ ОБУХОВО)
   286 (ВЕТЕРАНОВ)
   285 (УДЕЛЬНАЯ)
   282 (ПОЛИТЕХНИЧЕСКАЯ ДОСТОЕВСКАЯ САДОВАЯ КОМЕНДАНТСКИЙ)
   281 (ЛИГОВСКАЯ)
   280 (БОЛЬШЕВИКОВ)
   279 (ГОРЬКОВСКАЯ)
   278 (ЕЛИЗАРОВСКАЯ)
   277 (ПАРКПОБЕДЫ)
   275 (АВТОВО)
   274 (СЕННАЯ)
   272 (ЛЕСНАЯ)
   270 (ЧЕРНАЯ_РЕЧКА ПРИМОРСКАЯ)
   267 (ВОССТАНИЯ)
   266 (ЛОМОНОСОВСКАЯ КРЕСТОВСКИЙ)
   260 (АЛ_НЕВСКОГО_1)
   259 (АЛ_НЕВСКОГО_2)
   253 (НЕВСКИЙПРОСПЕКТ)
   249 (НОВОЧЕРКАССКАЯ)
   244 (МАЯКОВСКАЯ)
   234 (МОСКОВСКАЯ)
   233 (ПРОЛЕТАРСКАЯ)
   232 (ПИОНЕРСКАЯ)
   231 (МУЖЕСТВА)
   229 (ЛЕНИНСКИЙ)
   225 (ГОСТИННЫЙ_ДВОР ЛАДОЖСКАЯ СТАРАЯ_ДЕРЕВНЯ)
   213 (ВАСИЛЕОСТРОВСКАЯ)
  
  
  Топологическим центром в данном случае становится станция 'Василеостровская', причем существенно меньшим становится расстояние от топологического центра до всех остальных станций (213 вместо 303 в исходной схеме).
  
  Наиболее удаленными от топологического центра остаются практически те же станции (в немного измененном порядке' 'ДЕВЯТКИНО', 'ПРОСВЕЩЕНИЯ', 'ГРАЖДАНСКИЙ', 'КУПЧИНО', 'РЫБАЦКОЕ', и т.д. Однако, удаленность самой отдаленной станции 'Девяткино' стала в новой схеме равна удаленности 'Черной речки' в прежней конфигурации. При этом число слоев топологической структуры сократилось с 54 до 48.
  
  Кроме введения кольцевых линий, существенно упрощающих топологическую структуру схем метрополитена и параметры 'достижимости' удаленных станций, существует множество иных способов реализации схем, выраженных в существующих конфигурациях взаимосвязи станций в различных городах мира.
  
  Рассмотрим некоторые из них - после разработки технологии подготовки данных средствами Autodesk MAP.
  
  
  
  Последовательность выполнения анализа
  
  
  1. Загружаем растровое изображение объекта при помощи команды imageattach, настраиваем масштаб, точку вставки и угол поворота изображения.
  2. При помощи последовательных вызовов команды line прорисовываем структуру объекта, соединяя отдельные отрезки (line) в точках связи.
  
   []
  
  
  
  3. Вызываем команду MAPTOPOCREATE, устанавливая необходимые параметры.
  
   []
  
  4. Вызываем команду MAPOD2ASE, устанавливаем таблицу исходных данных TPMLINK_имя-топологии и выгружаем данные во внешнюю таблицу (mdb).
  
  5. Экспортируем полученную таблицу в текстовый файл и вызываем модуль 'ss.lisp' (Приложение 12) для построения списков смежности.
  
  6. Запускаем модули 'ms.lisp' и 'kp.lisp', получаем файл 'sisr.txt' с результатами анализа:
  
   747 (U01)
   690 (U03)
   678 (U59)
   660 (U02)
   640 (U58)
   635 (U06)
   621 (U57)
   603 (U05)
   601 (U55)
   583 (U56)
   582 (U08)
   574 (U04)
   567 (U50)
   566 (U54)
   548 (U07)
   544 (U52)
   531 (U10)
   528 (U53)
   517 (U09)
   513 (U51)
   510 (U46)
   495 (U11)
   489 (U48)
   482 (U12)
   475 (U49)
   462 (U15 U47)
   455 (U41)
   444 (U13)
   436 (U43)
   435 (U14)
   424 (U45)
   420 (U22)
   413 (U44)
   409 (U18)
   402 (U37)
   395 (U17)
   390 (U16)
   385 (U39)
   375 (U42)
   366 (U40)
   363 (U23)
   358 (U20)
   351 (U32)
   348 (U19)
   347 (U21)
   340 (U31)
   336 (U28)
   328 (U35)
   326 (U36)
   321 (U38)
   309 (U29 U30)
   308 (U24 U25 U34)
   306 (U27)
   305 (U33)
   303 (U26)
  
  Обращаем внимание, что данные результаты полностью совпадают с результатами предварительного анализа, выполненного с подготовленными вручную списками смежностей на стр. 5-6.
  
  
  
  
  
  Запуск модулей Common LISP для выполнения анализа.
  
  Для выполнения анализа запускается модуль 'TAN.lisp', который последовательно вызывает модули 'ss.lisp', 'ms.lisp', 'kp.lisp', 'ws.lisp'. Исходные данные для модуля 'TAN.lisp' должны находиться в файле 'a.txt' - выгруженная из Autodesk MAP совокупность таблиц TPMLINK_имя-топологии.
  
  
  
  Амстердам.
  
   []
  
  
   1693 (U78)
   1617 (U77)
   1543 (U75)
   1471 (U76)
   1401 (U74)
   1333 (U73)
   1267 (U72)
   1211 (U01)
   1203 (U71)
   1141 (U70)
   1135 (U02)
   1081 (U67)
   1061 (U06)
   1053 (U60)
   1023 (U66)
   1011 (U65)
   1005 (U69)
   989 (U13)
   977 (U54)
   967 (U62)
   961 (U05)
   937 (U64)
   931 (U68)
   919 (U17)
   913 (U59)
   911 (U04)
   907 (U03)
   903 (U50)
   889 (U09)
   867 (U61)
   861 (U56 U63)
   851 (U21)
   839 (U07)
   835 (U08)
   831 (U45)
   823 (U12)
   811 (U55)
   801 (U57)
   795 (U58)
   785 (U25)
   773 (U11)
   769 (U10)
   763 (U16 U51)
   761 (U40)
   739 (U52)
   733 (U53)
   721 (U29)
   717 (U49)
   713 (U15)
   709 (U14 U18)
   693 (U39)
   681 (U47)
   675 (U48)
   673 (U46)
   661 (U23)
   659 (U20 U35)
   655 (U19)
   631 (U44)
   627 (U33 U42)
   621 (U43)
   619 (U27)
   611 (U22)
   607 (U24)
   599 (U36)
   591 (U30)
   581 (U37)
   577 (U34)
   573 (U31)
   571 (U41)
   569 (U28)
   567 (U38)
   565 (U26)
   559 (U32)
  
  Необходимо отметить, что наличие сдвоенных или даже 'строенных' параллельных линий метрополитена не улучшает его топологическую структуру, и при ненамного увеличенном по сравнению с СПб количеством станций, общая схема метро Амстердама значительно хуже из-за чрезмерно длинных несвязанных друг с другом линий.
  
  Результаты анализа топологии метрополитена Амстердама:
  
  Количество узлов N = 78
  Индекс Винера абсолютный W = 31557.5
  Индекс Винера относительный W-отн = 0.37534177
  Вектор индекса суммы расстояний S-i (абсолютный и относительный):
  1693 0.55228984 (U78)
  1617 0.5263158 (U77)
  1543 0.5010253 (U75)
  1471 0.47641832 (U76)
  1401 0.45249486 (U74)
  1333 0.42925495 (U73)
  1267 0.40669855 (U72)
  1211 0.3875598 (U01)
  1203 0.3848257 (U71)
  1141 0.36363637 (U70)
  1135 0.3615858 (U02)
  1081 0.34313056 (U67)
  1061 0.33629528 (U06)
  1053 0.33356118 (U60)
  1023 0.32330826 (U66)
  1011 0.3192071 (U65)
  1005 0.31715652 (U69)
  989 0.3116883 (U13)
  977 0.30758715 (U54)
  967 0.3041695 (U62)
  961 0.30211893 (U05)
  937 0.2939166 (U64)
  931 0.29186603 (U68)
  919 0.28776488 (U17)
  913 0.2857143 (U59)
  911 0.28503075 (U04)
  907 0.2836637 (U03)
  903 0.28229666 (U50)
  889 0.27751195 (U09)
  867 0.26999316 (U61)
  861 0.26794258 (U56 U63)
  851 0.26452494 (U21)
  839 0.26042378 (U07)
  835 0.25905675 (U08)
  831 0.25768968 (U45)
  823 0.25495556 (U12)
  811 0.2508544 (U55)
  801 0.24743678 (U57)
  795 0.2453862 (U58)
  785 0.24196856 (U25)
  773 0.2378674 (U11)
  769 0.23650034 (U10)
  763 0.23444976 (U16 U51)
  761 0.23376623 (U40)
  739 0.22624743 (U52)
  733 0.22419685 (U53)
  721 0.2200957 (U29)
  717 0.21872865 (U49)
  713 0.21736158 (U15)
  709 0.21599454 (U14 U18)
  693 0.21052632 (U39)
  681 0.20642516 (U47)
  675 0.20437457 (U48)
  673 0.20369105 (U46)
  661 0.19958988 (U23)
  659 0.19890636 (U20 U35)
  655 0.1975393 (U19)
  631 0.18933699 (U44)
  627 0.18796992 (U33 U42)
  621 0.18591934 (U43)
  619 0.18523581 (U27)
  611 0.1825017 (U22)
  607 0.18113466 (U24)
  599 0.17840055 (U36)
  591 0.17566644 (U30)
  581 0.17224881 (U37)
  577 0.17088175 (U34)
  573 0.1695147 (U31)
  571 0.16883117 (U41)
  569 0.16814764 (U28)
  567 0.16746412 (U38)
  565 0.16678059 (U26)
  559 0.16473001 (U32)
  
  Для сравнения приведем результаты анализа существующей схемы метро Санкт-Петербурга:
  
  Количество узлов N = 59
  Индекс Винера абсолютный W = 12769.5
  Индекс Винера относительный W-отн = 0.34016734
  Вектор индекса суммы расстояний S-i (абсолютный и относительный):
  747 0.4168179 (U01)
  690 0.38233516 (U03)
  678 0.3750756 (U59)
  660 0.36418632 (U02)
  640 0.3520871 (U58)
  635 0.34906232 (U06)
  621 0.34059286 (U57)
  603 0.32970357 (U05)
  601 0.32849365 (U55)
  583 0.31760436 (U56)
  582 0.3169994 (U08)
  574 0.31215972 (U04)
  567 0.307925 (U50)
  566 0.30732003 (U54)
  548 0.29643074 (U07)
  544 0.29401088 (U52)
  531 0.2861464 (U10)
  528 0.28433153 (U53)
  517 0.27767694 (U09)
  513 0.2752571 (U51)
  510 0.27344224 (U46)
  495 0.26436782 (U11)
  489 0.26073804 (U48)
  482 0.2565033 (U12)
  475 0.2522686 (U49)
  462 0.2444041 (U15 U47)
  455 0.24016939 (U41)
  444 0.23351482 (U13)
  436 0.22867514 (U43)
  435 0.22807017 (U14)
  424 0.22141561 (U45)
  420 0.21899576 (U22)
  413 0.21476103 (U44)
  409 0.2123412 (U18)
  402 0.20810647 (U37)
  395 0.20387174 (U17)
  390 0.20084694 (U16)
  385 0.19782214 (U39)
  375 0.19177254 (U42)
  366 0.18632789 (U40)
  363 0.184513 (U23)
  358 0.1814882 (U20)
  351 0.17725348 (U32)
  348 0.1754386 (U19)
  347 0.17483364 (U21)
  340 0.17059891 (U31)
  336 0.16817906 (U28)
  328 0.16333938 (U35)
  326 0.16212946 (U36)
  321 0.15910466 (U38)
  309 0.15184513 (U29 U30)
  308 0.15124017 (U24 U25 U34)
  306 0.15003026 (U27)
  305 0.14942528 (U33)
  303 0.14821537 (U26)
  
  Результаты анализа схемы метрополитена Санкт-Петербурга после введения кольцевой линии:
  
  Количество узлов N = 59
  Индекс Винера абсолютный W = 7005.5
  Индекс Винера относительный W-отн = 0.1628626
  Вектор индекса суммы расстояний S-i (абсолютный и относительный):
  447 0.2353297 (ДЕВЯТКИНО)
  397 0.20508167 (ПРОСВЕЩЕНИЯ)
  390 0.20084694 (ГРАЖДАНСКИЙ)
  346 0.17422867 (КУПЧИНО)
  345 0.17362371 (РЫБАЦКОЕ)
  341 0.17120387 (БАЛТИЙСКАЯ)
  340 0.17059891 (ОЗЕРКИ)
  337 0.16878402 (ДЫБЕНКО)
  335 0.16757411 (НАРВСКАЯ АКАДЕМИЧЕСКАЯ)
  326 0.16212946 (МОСКОВСКИЕВОРОТА)
  324 0.16091955 (ФРУНЗЕНСКАЯ)
  323 0.16031457 (ТЕХНОЛ1)
  320 0.1584997 (ПУШКИНСКАЯ)
  313 0.15426497 (КИРОВСКИЙ)
  311 0.15305506 (ПЛ_ЛЕНИНА)
  309 0.15184513 (ЭЛЕКТРОСИЛА)
  302 0.14761041 (СПОРТИВНАЯ)
  301 0.14700544 (ВЫБОРГСКАЯ ТЕХНОЛ2)
  300 0.14640048 (ЧЕРНЫШЕВСКАЯ)
  293 0.14216577 (ЧКАЛОВСКАЯ)
  289 0.13974592 (ЗВЕЗДНАЯ ПЕТРОГРАДСКАЯ)
  288 0.13914095 (ВЛАДИМИРСКАЯ ОБУХОВО)
  286 0.13793103 (ВЕТЕРАНОВ)
  285 0.13732608 (УДЕЛЬНАЯ)
  282 0.13551119 (ПОЛИТЕХНИЧЕСКАЯ ДОСТОЕВСКАЯ САДОВАЯ КОМЕНДАНТСКИЙ)
  281 0.13490623 (ЛИГОВСКАЯ)
  280 0.13430128 (БОЛЬШЕВИКОВ)
  279 0.1336963 (ГОРЬКОВСКАЯ)
  278 0.13309135 (ЕЛИЗАРОВСКАЯ)
  277 0.13248639 (ПАРКПОБЕДЫ)
  275 0.13127647 (АВТОВО)
  274 0.1306715 (СЕННАЯ)
  272 0.12946159 (ЛЕСНАЯ)
  270 0.12825166 (ЧЕРНАЯ_РЕЧКА ПРИМОРСКАЯ)
  267 0.12643678 (ВОССТАНИЯ)
  266 0.12583183 (ЛОМОНОСОВСКАЯ КРЕСТОВСКИЙ)
  260 0.12220205 (АЛ_НЕВСКОГО_1)
  259 0.1215971 (АЛ_НЕВСКОГО_2)
  253 0.11796733 (НЕВСКИЙПРОСПЕКТ)
  249 0.11554749 (НОВОЧЕРКАССКАЯ)
  244 0.112522684 (МАЯКОВСКАЯ)
  234 0.10647308 (МОСКОВСКАЯ)
  233 0.105868116 (ПРОЛЕТАРСКАЯ)
  232 0.10526316 (ПИОНЕРСКАЯ)
  231 0.104658194 (МУЖЕСТВА)
  229 0.10344828 (ЛЕНИНСКИЙ)
  225 0.101028435 (ГОСТИННЫЙ_ДВОР ЛАДОЖСКАЯ СТАРАЯ_ДЕРЕВНЯ)
  213 0.0937689 (ВАСИЛЕОСТРОВСКАЯ)
  
  Москва.
  
   []
  
  Количество узлов N = 177
  Количество слоев = 171
  Индекс Винера абсолютный W = 160504.0
  Индекс Винера относительный W-отн = 0.15950693
  Вектор индекса суммы расстояний S-i (абсолютный и относительный):
  3597 0.22214286 (U176)
  3422 0.21077922 (U177)
  3249 0.19954546 (U175)
  3078 0.18844156 (U174)
  2935 0.17915584 (U56)
  2909 0.17746754 (U173)
  2908 0.1774026 (U168)
  2808 0.17090909 (U167)
  2790 0.16974026 (U172)
  2760 0.1677922 (U65)
  2705 0.16422078 (U01)
  2687 0.16305195 (U164)
  2683 0.1627922 (U150)
  2680 0.1625974 (U25)
  2649 0.16058442 (U171)
  2587 0.15655844 (U71)
  2586 0.1564935 (U142)
  2564 0.15506494 (U161)
  2558 0.15467532 (U02)
  2530 0.15285714 (U03)
  2528 0.15272728 (U170)
  2508 0.15142857 (U149 U169)
  2505 0.15123376 (U31)
  2476 0.14935064 (U43)
  2443 0.1472078 (U08)
  2429 0.1462987 (U158)
  2416 0.14545454 (U77)
  2411 0.14512987 (U138)
  2383 0.1433117 (U04)
  2367 0.14227273 (U165)
  2357 0.14162338 (U05)
  2353 0.14136364 (U166)
  2335 0.1401948 (U144)
  2332 0.14 (U39)
  2301 0.13798702 (U50)
  2298 0.13779221 (U18)
  2292 0.1374026 (U151)
  2268 0.13584416 (U11)
  2247 0.13448052 (U81)
  2238 0.1338961 (U134)
  2226 0.13311689 (U162)
  2225 0.13305195 (U125)
  2223 0.13292208 (U14)
  2210 0.13207792 (U06)
  2186 0.13051948 (U07)
  2180 0.13012987 (U163)
  2168 0.12935065 (U15)
  2164 0.1290909 (U140)
  2162 0.12896104 (U86)
  2161 0.1288961 (U46)
  2153 0.12837662 (U148)
  2150 0.12818182 (U13)
  2128 0.12675324 (U54)
  2123 0.12642857 (U21)
  2095 0.12461039 (U23)
  2085 0.12396104 (U157)
  2080 0.123636365 (U90)
  2067 0.12279221 (U128)
  2050 0.121688314 (U126)
  2045 0.12136364 (U20)
  2039 0.12097403 (U09)
  2022 0.119870126 (U16)
  2017 0.11954545 (U10)
  2014 0.11935065 (U152)
  2012 0.11922078 (U143)
  2009 0.119025975 (U160)
  2002 0.11857143 (U12)
  1995 0.118116885 (U137)
  1992 0.117922075 (U49)
  1987 0.1175974 (U92)
  1957 0.11564935 (U59)
  1950 0.115194805 (U27)
  1944 0.11480519 (U155)
  1933 0.11409091 (U153)
  1924 0.113506496 (U28)
  1915 0.11292208 (U94)
  1898 0.11181818 (U120)
  1877 0.110454544 (U127)
  1871 0.11006494 (U141)
  1870 0.11 (U17)
  1850 0.108701296 (U19)
  1840 0.10805195 (U159)
  1829 0.10733766 (U147)
  1828 0.10727273 (U131)
  1825 0.10707792 (U53)
  1814 0.10636364 (U96)
  1805 0.10577922 (U154)
  1788 0.10467532 (U64)
  1779 0.10409091 (U30)
  1755 0.10253247 (U33)
  1752 0.102337666 (U95)
  1731 0.10097402 (U114)
  1730 0.10090909 (U136)
  1728 0.10077922 (U24)
  1709 0.09954546 (U145)
  1708 0.09948052 (U22)
  1706 0.099350646 (U122)
  1673 0.09720779 (U156)
  1663 0.096558444 (U129)
  1660 0.096363634 (U55)
  1643 0.09525974 (U100)
  1621 0.09383117 (U70)
  1610 0.09311688 (U36)
  1607 0.09292208 (U80)
  1591 0.091883115 (U108)
  1589 0.091753244 (U133)
  1588 0.09168831 (U37)
  1587 0.09162337 (U139)
  1583 0.09136364 (U73)
  1581 0.09123377 (U29)
  1566 0.09025974 (U110)
  1564 0.09012987 (U74)
  1561 0.089935064 (U26)
  1549 0.089155845 (U146)
  1537 0.08837663 (U116)
  1505 0.086298704 (U47)
  1500 0.08597402 (U118)
  1497 0.08577922 (U60)
  1474 0.084285714 (U106)
  1463 0.08357143 (U98)
  1459 0.08331169 (U42)
  1458 0.08324675 (U99 U132)
  1456 0.08311688 (U72)
  1453 0.08292208 (U75)
  1448 0.082597405 (U130)
  1443 0.08227273 (U40)
  1432 0.08155844 (U93)
  1429 0.08136363 (U35)
  1423 0.08097403 (U41 U135)
  1417 0.080584414 (U97)
  1415 0.08045454 (U51)
  1409 0.08006494 (U32)
  1403 0.079675324 (U104)
  1394 0.07909091 (U52)
  1387 0.07863636 (U48)
  1381 0.07824675 (U58)
  1370 0.07753247 (U111)
  1366 0.07727273 (U105)
  1359 0.07681818 (U89)
  1354 0.07649351 (U82)
  1346 0.075974025 (U44)
  1340 0.07558442 (U34)
  1338 0.07545455 (U107)
  1336 0.07532468 (U61)
  1330 0.07493506 (U38)
  1328 0.07480519 (U63)
  1327 0.07474026 (U91)
  1322 0.07441559 (U119)
  1317 0.074090905 (U45)
  1311 0.0737013 (U83)
  1310 0.07363636 (U66)
  1307 0.07344156 (U109 U115)
  1304 0.073246755 (U79)
  1302 0.07311688 (U88)
  1295 0.07266234 (U124)
  1293 0.07253247 (U85)
  1287 0.072142854 (U68)
  1286 0.07207792 (U113)
  1284 0.07194805 (U67)
  1283 0.07188312 (U103)
  1281 0.07175325 (U57)
  1280 0.07168831 (U62)
  1272 0.07116883 (U69)
  1265 0.07071429 (U121)
  1263 0.07058442 (U102)
  1261 0.070454545 (U84 U87)
  1257 0.0701948 (U78 U112)
  1253 0.06993507 (U123)
  1243 0.06928571 (U76)
  1238 0.06896104 (U117)
  1223 0.06798701 (U101)
  
  Топологическим центром Московского метрополитена является станция Таганская, наиболее удаленным от всех остальных станций - Бунинская аллея.
  
  Несмотря на то, что количество станций Московского метрополитена в 3 раза больше числа станций метро в Санкт-Петербурге, его существующая топологическая структура даже лучше той, которая может быть в Санкт-Петербурге после введения кольцевой линии (см. сводную таблицу результатов анализа).
  
  Относительная величина суммы расстояний (кратчайших путей) от топологического центра до всех остальных станций Московского метро равна 0,06; в воображаемом Санкт-Петербурге = 0,09. По величине индекса Винера схемы метро Москвы и Санкт-Петербурга с кольцевой линией равноценны. Существующая топология метрополитена Санкт-Петербурга значительно хуже существующей топологии метро Москвы.
  
  Париж.
  
   []
  
  Количество узлов N = 376
  Количество слоев = 354
  Индекс Винера абсолютный W = 872595.0
  Индекс Винера относительный W-отн = 0.09126124
  Вектор индекса суммы расстояний S-i (абсолютный и относительный):
  8792 0.12002852 (U372)
  8418 0.114695184 (U370)
  8407 0.11453833 (U343)
  8046 0.10939038 (U366)
  8033 0.10920499 (U336)
  7676 0.104114085 (U361)
  7661 0.10390018 (U328)
  7411 0.10033511 (U11)
  7409 0.10030659 (U368)
  7336 0.0992656 (U364)
  7313 0.09893761 (U05)
  7308 0.09886631 (U358)
  7291 0.09862389 (U320)
  7196 0.09726916 (U01)
  7158 0.096727274 (U300)
  7043 0.09508734 (U376)
  7037 0.09500178 (U17)
  7035 0.09497326 (U359)
  6986 0.09427451 (U375)
  6962 0.09393226 (U355)
  6942 0.093647055 (U352)
  6939 0.09360428 (U06)
  6923 0.093376115 (U307)
  6825 0.09197861 (U101)
  6822 0.09193583 (U02)
  6784 0.09139394 (U294)
  6676 0.08985383 (U44)
  6669 0.08975401 (U374)
  6665 0.089696966 (U19)
  6663 0.08966845 (U356)
  6612 0.08894118 (U371)
  6590 0.08862745 (U348)
  6578 0.088456325 (U342)
  6569 0.08832799 (U170)
  6567 0.08829947 (U10)
  6557 0.088156864 (U292)
  6451 0.086645275 (U106)
  6450 0.086631015 (U03)
  6446 0.08657397 (U91)
  6430 0.086345814 (U259)
  6418 0.08617469 (U283)
  6349 0.08519073 (U96)
  6302 0.0845205 (U49)
  6297 0.084449194 (U373)
  6295 0.08442068 (U28)
  6293 0.08439216 (U360)
  6278 0.084178254 (U362)
  6240 0.083636366 (U365)
  6220 0.08335116 (U331)
  6216 0.083294116 (U330)
  6215 0.083279856 (U108)
  6203 0.08310874 (U255)
  6197 0.083023176 (U16)
  6195 0.082994655 (U182)
  6145 0.08228164 (U60)
  6134 0.08212478 (U291)
  6131 0.082081996 (U335)
  6111 0.081796795 (U239)
  6080 0.08135472 (U04)
  6079 0.08134046 (U111)
  6072 0.08124064 (U89)
  6064 0.08112656 (U266)
  6003 0.080256686 (U14)
  5982 0.07995722 (U67)
  5933 0.079258464 (U139)
  5930 0.07921568 (U52)
  5927 0.0791729 (U31 U369)
  5925 0.07914439 (U367)
  5904 0.07884492 (U225 U353)
  5898 0.07875936 (U15)
  5881 0.07851693 (U120)
  5870 0.07836007 (U354)
  5856 0.07816043 (U323)
  5852 0.078103386 (U321)
  5829 0.077775404 (U20)
  5823 0.07768984 (U197)
  5819 0.0776328 (U286)
  5780 0.07707665 (U270)
  5773 0.07697683 (U72)
  5760 0.07679144 (U84)
  5757 0.07674866 (U327)
  5744 0.07656328 (U07)
  5728 0.07633512 (U71)
  5712 0.07610695 (U08)
  5709 0.07606417 (U117)
  5663 0.0754082 (U279)
  5629 0.07492335 (U24)
  5610 0.0746524 (U76)
  5592 0.07439572 (U203)
  5561 0.07395365 (U36)
  5560 0.07393939 (U56)
  5559 0.07392513 (U140 U363)
  5535 0.07358289 (U135)
  5532 0.07354011 (U345)
  5524 0.07342602 (U18)
  5504 0.07314082 (U153)
  5502 0.0731123 (U349)
  5498 0.07305526 (U316)
  5486 0.072884135 (U311)
  5465 0.072584674 (U276)
  5463 0.07255615 (U29)
  5453 0.07241355 (U209)
  5407 0.07175758 (U85)
  5385 0.07144385 (U318)
  5382 0.07140107 (U65)
  5370 0.07122995 (U12)
  5346 0.0708877 (U09)
  5341 0.0708164 (U121)
  5289 0.070074864 (U268)
  5257 0.06961854 (U26 U189)
  5206 0.068891264 (U27)
  5203 0.06884848 (U357)
  5197 0.06876292 (U46)
  5192 0.06869162 (U63)
  5187 0.068620324 (U142)
  5171 0.06839216 (U217)
  5166 0.068320855 (U176)
  5162 0.068263814 (U334)
  5152 0.06812121 (U23)
  5142 0.06797861 (U301)
  5136 0.06789305 (U339)
  5133 0.06785027 (U277)
  5130 0.06780749 (U163)
  5122 0.067693405 (U303)
  5105 0.06745098 (U185)
  5099 0.067365415 (U33)
  5085 0.06716578 (U214)
  5078 0.067065954 (U144)
  5077 0.067051694 (U88)
  5057 0.066766486 (U337)
  5053 0.066709444 (U332)
  5052 0.06669518 (U195)
  5041 0.06653833 (U154 U236)
  5034 0.0664385 (U58)
  5023 0.06628164 (U25)
  5015 0.066167556 (U309)
  4998 0.065925136 (U22)
  4996 0.065896615 (U201)
  4994 0.065868095 (U341)
  4982 0.06569697 (U13)
  4975 0.06559715 (U127)
  4973 0.065568626 (U172)
  4972 0.065554366 (U322)
  4953 0.065283425 (U317)
  4929 0.064941175 (U295)
  4922 0.06484135 (U188)
  4917 0.06477005 (U256)
  4912 0.064698756 (U333)
  4907 0.06462745 (U289)
  4851 0.06382888 (U346)
  4849 0.06380036 (U351)
  4846 0.063757576 (U288)
  4841 0.063686274 (U161)
  4838 0.06364349 (U34)
  4835 0.06360071 (U55)
  4834 0.06358645 (U220 U280)
  4826 0.06347237 (U68)
  4825 0.06345811 (U115)
  4817 0.06334403 (U130)
  4803 0.063144386 (U141)
  4798 0.063073084 (U278)
  4788 0.06293048 (U290)
  4785 0.0628877 (U261)
  4780 0.0628164 (U304)
  4775 0.0627451 (U344)
  4772 0.06270232 (U325)
  4770 0.0626738 (U59 U247)
  4769 0.06265954 (U312)
  4758 0.062502675 (U128)
  4748 0.06236007 (U187)
  4746 0.06233155 (U319)
  4737 0.06220321 (U38)
  4734 0.06216043 (U202)
  4731 0.062117647 (U100)
  4722 0.061989304 (U329)
  4719 0.061946522 (U228)
  4712 0.061846703 (U275)
  4703 0.06171836 (U95)
  4702 0.0617041 (U194)
  4698 0.061647058 (U308)
  4696 0.061618537 (U103)
  4692 0.0615615 (U64)
  4684 0.061447416 (U32)
  4673 0.06129055 (U350)
  4672 0.06127629 (U347)
  4647 0.060919788 (U297)
  4640 0.060819965 (U264)
  4631 0.06069162 (U263)
  4628 0.06064884 (U30)
  4623 0.06057754 (U229)
  4620 0.06053476 (U21 U258)
  4613 0.060434937 (U157)
  4611 0.060406417 (U138)
  4604 0.060306594 (U298)
  4593 0.060149733 (U293)
  4579 0.05995009 (U47)
  4576 0.05990731 (U213)
  4556 0.059622105 (U48)
  4547 0.05949376 (U252)
  4537 0.059351157 (U114)
  4525 0.059180036 (U274)
  4524 0.059165776 (U338)
  4514 0.05902317 (U310)
  4509 0.058951873 (U306)
  4506 0.058909092 (U246)
  4505 0.05889483 (U87)
  4503 0.05886631 (U313 U340)
  4491 0.058695186 (U271)
  4483 0.058581106 (U80)
  4482 0.058566846 (U180)
  4481 0.058552586 (U37)
  4463 0.058295902 (U257)
  4462 0.05828164 (U69)
  4457 0.05821034 (U267)
  4430 0.057825312 (U249)
  4428 0.05779679 (U178)
  4427 0.05778253 (U254)
  4420 0.057682708 (U281)
  4410 0.057540108 (U305)
  4409 0.057525847 (U146)
  4407 0.057497326 (U262)
  4405 0.057468805 (U41 U299)
  4385 0.0571836 (U237)
  4383 0.05715508 (U109)
  4376 0.057055257 (U260)
  4374 0.057026736 (U40)
  4361 0.056841355 (U250)
  4355 0.056755792 (U235)
  4338 0.05651337 (U287)
  4328 0.056370765 (U302)
  4327 0.056356505 (U45)
  4324 0.056313727 (U39 U42)
  4316 0.056199644 (U62)
  4312 0.056142602 (U149)
  4303 0.05601426 (U57)
  4289 0.055814616 (U282)
  4286 0.055771835 (U324)
  4281 0.055700533 (U269)
  4278 0.055657756 (U244)
  4270 0.055543672 (U265)
  4269 0.055529412 (U54)
  4260 0.05540107 (U35)
  4258 0.055372547 (U245)
  4256 0.05534403 (U230)
  4253 0.05530125 (U231)
  4239 0.055101603 (U253)
  4236 0.055058822 (U296)
  4233 0.055016045 (U53)
  4231 0.054987524 (U81 U234)
  4207 0.054645278 (U43 U284)
  4202 0.054573976 (U190)
  4190 0.05440285 (U162)
  4183 0.05430303 (U79)
  4182 0.05428877 (U148)
  4179 0.05424599 (U241)
  4173 0.054160427 (U123)
  4157 0.053932264 (U199)
  4155 0.053903744 (U83)
  4136 0.0536328 (U75)
  4135 0.05361854 (U248)
  4133 0.05359002 (U242)
  4132 0.053575758 (U232)
  4129 0.053532977 (U174 U326)
  4107 0.05321925 (U204)
  4100 0.05311943 (U73)
  4096 0.053062387 (U74)
  4089 0.052962568 (U219)
  4086 0.052919786 (U119 U166)
  4083 0.052877005 (U159)
  4079 0.052819964 (U273)
  4070 0.052691624 (U61 U177)
  4069 0.052677363 (U77)
  4063 0.0525918 (U104)
  4062 0.05257754 (U160)
  4057 0.05250624 (U143)
  4041 0.052278075 (U50 U145)
  4026 0.052064173 (U136)
  4025 0.052049913 (U238)
  4023 0.05202139 (U211)
  4022 0.05200713 (U315)
  3971 0.051279858 (U137)
  3966 0.051208556 (U222)
  3954 0.051037434 (U240)
  3941 0.05085205 (U158)
  3940 0.05083779 (U102)
  3935 0.050766487 (U227)
  3929 0.050680928 (U113)
  3927 0.050652407 (U216)
  3926 0.050638147 (U147)
  3924 0.050609626 (U110)
  3923 0.050595365 (U251)
  3910 0.050409984 (U51)
  3903 0.05031016 (U78)
  3901 0.05028164 (U82)
  3881 0.049996436 (U152)
  3872 0.049868092 (U150)
  3870 0.04983957 (U134)
  3862 0.04972549 (U224)
  3855 0.04962567 (U132 U151)
  3851 0.049568627 (U122)
  3850 0.049554367 (U118 U169)
  3844 0.049468804 (U116)
  3843 0.049454544 (U206)
  3833 0.049311943 (U70)
  3832 0.049297683 (U99)
  3825 0.04919786 (U112)
  3816 0.04906952 (U171)
  3811 0.048998218 (U98)
  3805 0.048912656 (U126)
  3790 0.048698753 (U243)
  3782 0.04858467 (U131)
  3777 0.048513368 (U221)
  3758 0.048242424 (U173)
  3757 0.048228163 (U233 U314)
  3748 0.048099823 (U191)
  3742 0.04801426 (U168)
  3740 0.04798574 (U93 U107)
  3738 0.04795722 (U66 U223)
  3732 0.047871657 (U186)
  3731 0.047857396 (U175)
  3722 0.047729056 (U183)
  3684 0.047187164 (U105)
  3673 0.047030304 (U193)
  3672 0.047016043 (U192)
  3671 0.047001783 (U92)
  3665 0.04691622 (U207)
  3656 0.04678788 (U272)
  3652 0.04673084 (U200)
  3629 0.046402853 (U196)
  3621 0.04628877 (U133)
  3610 0.04613191 (U90)
  3589 0.04583244 (U125)
  3588 0.045818184 (U226)
  3587 0.045803923 (U181)
  3567 0.045518715 (U94)
  3561 0.045433156 (U215)
  3557 0.045376115 (U218)
  3551 0.045290552 (U184)
  3530 0.044991087 (U165)
  3501 0.04457754 (U86)
  3496 0.04450624 (U129)
  3485 0.044349376 (U179)
  3484 0.044335116 (U124)
  3477 0.044235293 (U285)
  3474 0.04419251 (U97)
  3426 0.043508023 (U212)
  3411 0.043294117 (U164)
  3401 0.043151516 (U205)
  3388 0.04296613 (U210)
  3357 0.042524066 (U198)
  3342 0.04231016 (U155)
  3332 0.04216756 (U156)
  3308 0.041825313 (U167)
  3275 0.041354723 (U208)
  
  Сводная таблица результатов анализа схем метрополитена различных городов мира.
  
  Сведем результаты анализа схем метрополитена в таблицу:
  
   []
  
  
  
  
  
  
  
  
  Приложение 1. Модуль Common Lisp для построения матрицы всех кратчайших путей между всеми парами вершин.
  
  ; Строит матрицу всех кратчайших путей
  (setq fbit (open "bbit.txt" :direction :input)) (setq nir (read fbit))
  (setq sb ())
  (loop for i from 0 to (1- nir) do (setq ii (read fbit)) (print ii)
   (set ii (read fbit)) (setq sb (append sb (list ii)))) (close fbit)
  (setq d0 (make-array (list nir nir) :initial-element 9999999999999999))
  (setq d1 (make-array (list nir nir)))
  (print "заполняет матрицы кратчайших путей начальными значениями")
  (loop for i from 0 to (1- nir) do (print i)
   (loop for j from 0 to (1- nir) do
   (cond ((= i j) (setf (aref d0 i j) 0))
   (t (cond ((> (bit (eval (nth i sb)) j) 0) (setf (aref d0 i j) 1)))))
   (setf (aref d1 i j) (aref d0 i j))))
  (print "Строит матрицу кратчайших путей")
  (loop for m from 0 to (1- nir) do (print (list m (nth m sb)))
   (loop for i from 0 to (1- nir) do (print (list m (nth m sb) i))
   (loop for j from 0 to (1- nir) do (print (list m (nth m sb) i j))
   (cond ((= i j) (setf (aref d1 i j) 0))
   (t (setq a1 (+ (aref d0 i m) (aref d0 m j))) (setq a2 (aref d0 i j))
   (setf (aref d1 i j) (min a1 a2))))))
   (setq d0 d1) (setq d1 d0))
  (print "находит суммы строк в матрице")
  (loop for i from 0 to (1- nir) do
   (setq sd 0)
   (loop for j from 0 to (1- nir) do
   (setq sd (+ sd (aref d1 i j)))) (set (nth i sb) sd))
  (defun sorl (l) (setq ls ()) (setq lcop (copy-list l))
   (loop (setq max -1)
   (dolist (i lcop) (cond ((> (eval i) max) (setq xmax i) (setq max (eval i)))))
   (setq ls (cons xmax ls)) (setq lcop (delete xmax lcop))
   (cond ((eq lcop nil) (return)))) (setq ls (reverse ls)))
  (setq fmkp (open "mkp.txt" :direction :output))
  (print "пишет в файл матрицу")
  (loop for i from 0 to (1- nir) do (princ (format nil "~10S" (nth i sb)) fmkp) (princ (format nil "~5D" (eval (nth i sb))) fmkp)
   (loop for j from 0 to (1- nir) do
   (princ (format nil "~4D" (aref d1 i j)) fmkp)) (terpri fmkp))
  (close fmkp) (print "сортирует по величинам сумм строк") (setq sb (sorl sb))
  (setq skp ()) (setq kpi (eval (car sb))) (setq skpi (list (car sb))) (setq nkpi (list (eval (car sb))))
  (print "Формирует списки И с одинаковыми суммами расстояний")
  (dolist (i (cdr sb)) (cond ((= (eval i) kpi) (setq skpi (append skpi (list i))))
   (t (setq skp (append skp (list skpi)))
   (setq kpi (eval i)) (setq skpi (list i))
   (setq nkpi (append nkpi (list (eval i)))))))
  (setq skp (append skp (list skpi)))
  (setq fisr (open "sisr.txt" :direction :output))
  (print "Печатает список")
  (loop for i from 0 to (1- (length skp)) do
   (princ (format nil "~5D" (nth i nkpi)) fisr) (princ " " fisr) (princ (nth i skp) fisr) (terpri fisr))
  (close fisr)
  
  Приложение 2. Модуль Common Lisp для построения матрицы смежностей графа в виде массива строк бит.
  
  ; строим матрицу смежности как массивы бит в свойствах И
  (setq fi (open "bb.txt" :direction :input)) (setq nir (read fi))
  (setq ba (make-array nir :element-type 'bit :initial-element 0))
  (setq si ())
  (loop for i from 0 to (1- nir) do (setq ii (read fi))
   (set (car ii) (list (cdr ii) ba))
   (setq si (append si (list (car ii))))) (close fi)
  (setq fbit (open "bbit.txt" :direction :output))
  (dolist (i si) (princ (list i (car (eval i)) (cadr (eval i))) fbit) (terpri fbit)) (close fbit)
  (setq fbit (open "bbit.txt" :direction :input))
  (setq si ())
  (loop for i from 0 to (1- nir) do
   (setq s (read fbit)) (set (car s) (cdr s))
   (setq si (append si (list (car s)))))
  (dolist (i si) (print i) (setq p0 (position i si)) (print "___")
   (dolist (j (car (eval i))) (setq p (position j si)) (print "+++")
   (print p)
   (cond (p (setf (bit (car (last (eval (nth p si)))) p0) 1)))))
  (close fbit)
  (setq fbit (open "bbit.txt" :direction :output)) (princ nir fbit) (terpri fbit)
  (dolist (i si) (princ (format nil "~10S" i) fbit) (princ " " fbit) (princ (car (last (eval i))) fbit) (terpri fbit))
  (close fbit)
  
  
  
  Приложение 3. Санкт-Петербург
  
   []
  
  
  Приложение 4. Москва.
   []
  
  Приложение 5. Киев.
   []
  
  Приложение 6. Рим.
   []
  
  Приложение 7. Париж.
   []
  
  
  Приложение 8. Лондон.
   []
  
  
  Приложение 9. Хельсинки.
   []
  
  
  Приложение 10. Берлин.
   []
  
  
  Приложение 11. Амстердам.
   []
  
  
  Приложение 12. Модуль 'ss.lisp'
  
  ; формирование списков для исходного файла
  (setq fdb (open "a.txt" :direction :input))
  (setq fsp (open "aa.txt" :direction :output))
  (setq fl (file-length fdb))
  (setq fst (read-line fdb)) (setq lst (length fst)) (setq fst (concatenate 'string "(" fst ")")) (princ fst fsp) (terpri fsp)
  (setq nn 0)
  (loop (cond ((> (- fl (file-position fdb)) lst)
   (setq fst (read-line fdb)) (setq nn (1+ nn))
   (setq fst (concatenate 'string "(" fst ")")) (print fst) (princ fst fsp) (terpri fsp)) (t (return))))
  (close fdb) (close fsp)
  ; формирование списка узлов
  (setq faa (open "aa.txt" :direction :input))
  (setq saa ())
  (loop for i from 0 to nn do (setq saa (append saa (list (read faa))))) (close faa)
  (setq su ())
  (dolist (i saa) (setq su (append su (list (nth 1 i) (nth 2 i)))))
  (setq su (remove-duplicates su)) (setq su (sort su '<)) (setq nu (length su))
  ; формирование списка дуг
  (setq sd ())
  (dolist (i saa) (setq sd (append sd (list (list (nth 1 i) (nth 2 i)))))) (setq nd (length sd))
  ; преобразование списков
  (loop for i from 0 to (1- nu) do (if (< (nth i su) 10) (setf (nth i su) (format nil (concatenate 'string "u" "~2,'0D") (nth i su)))
   (setf (nth i su) (format nil (concatenate 'string "u" "~D") (nth i su)))))
  (dolist (i sd)
   (if (< (nth 0 i) 10) (setf (nth 0 i) (format nil (concatenate 'string "u" "~2,'0D") (nth 0 i)))
   (setf (nth 0 i) (format nil (concatenate 'string "u" "~D") (nth 0 i))))
   (if (< (nth 1 i) 10) (setf (nth 1 i) (format nil (concatenate 'string "u" "~2,'0D") (nth 1 i)))
   (setf (nth 1 i) (format nil (concatenate 'string "u" "~D") (nth 1 i)))))
  (setq lu ())
  (dolist (i su) (setq lu (append lu (list (read-from-string i)))))
  (setq ld ())
  (dolist (i sd) (setq ld (append ld (list (list (read-from-string (nth 0 i)) (read-from-string (nth 1 i)))))))
  
  ; формирование списков смежностей
  (setq ssm ())
  (dolist (i lu) (setq ssmi (list i))
   (dolist (j ld) (cond ((member i j) (setq ssmi (append ssmi (set-difference j (list i)))))))
   (setq ssm (append ssm (list ssmi))))
  
  ; запись списка смежностей в файл
  (setq fbb (open "bb.txt" :direction :output))
  (princ nu fbb) (terpri fbb)
  (dolist (i ssm) (princ i fbb) (terpri fbb))
  (close fbb)
  
  
  
  
  Приложение 13. Модуль 'ws.lisp'.
  
  ; считает индексы - винера и суммы расстояний (абсолютные и относительные).
  (setq fi (open "sisr.txt" :direction :input))
  (setq fo (open "sisrs.txt" :direction :output))
  (setq ni 0)
  (loop when (setq li (read-line fi nil)) do
   (setq st (concatenate 'string "(" li ")")) (setq ni (1+ ni)) (print st) (princ st fo) (terpri fo)
   else do (return))
  (close fi) (close fo)
  (setq fi (open "sisrs.txt" :direction :input))
  (setq si ())
  (loop when (setq li (read fi nil)) do
   (setq si (append si (list li)))
   else do (return))
  (close fi)
  ; определяем минимально и максимально возможные (предельные) значения индексов
  (setq fbb (open "bb.txt" :direction :input)) (setq n (read fbb)) (close fbb)
  (setq smin (1- n)) (setq smax (/ (* n (1- n)) 2.0))
  (setq wmin (/ (* n (1- n)) 2.0))
  (setq wmax 0)
  (loop for i from 1 to n do
   (setq w1 0) (setq w2 0)
   (loop for j from 0 to (1- i) do (setq w1 (+ w1 j)))
   (loop for j from 0 to (- n i) do (setq w2 (+ w2 j)))
   (setq wmax (+ wmax w1 w2)))
  (setq wmax (/ wmax 2.0))
  ; считаем индекс винера - абсолютный и относительный
  (setq win 0.0)
  (dolist (i si) (setq win (+ win (* (car i) (length (cdr i))))))
  (setq win (/ win 2.0))
  (setq wino (/ (- win wmin) (- wmax wmin)))
  ; определяем вектор индекса суммы расстояний
  (setq sio ())
  (dolist (i si) (setq sioi (/ (- (car i) smin) (- smax smin))) (setq sio (append sio (list (list sioi (car (cdr i)))))))
  ; пишем результаты в файл
  (setq fws (open "ws.txt" :direction :output))
  (princ "Количество узлов N = " fws) (princ n fws) (terpri fws)
  (princ "Количество слоев = " fws) (princ (length si) fws) (terpri fws)
  (princ "Индекс Винера абсолютный W = " fws) (princ win fws) (terpri fws)
  (princ "Индекс Винера относительный W-отн = " fws) (princ wino fws) (terpri fws)
  (princ "Вектор индекса суммы расстояний S-i (абсолютный и относительный): " fws) (terpri fws)
  (loop for i from 0 to (1- (length si)) do
   (princ (car (nth i si)) fws) (princ " " fws) (princ (car (nth i sio)) fws) (princ " " fws) (princ (car (cdr (nth i si))) fws) (terpri fws))
  (close fws)
  
 Ваша оценка:
Связаться с программистом сайта.

Новые книги авторов СИ, вышедшие из печати:
О.Болдырева "Крадуш. Чужие души" М.Николаев "Вторжение на Землю"

Как попасть в этoт список

Кожевенное мастерство | Сайт "Художники" | Доска об'явлений "Книги"