Вот взял я и попробовал раскрасить схему трамвайных линий Москвы:


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

Непонятно только с голубой линией. А так: жёлтые линии имеют возможность альтернативного проезда только с одной стороны, зелёные с двух (справа и слева), а красные - безальтернативны.

Цитата (karelalex)
Непонятно только с голубой линией. А так: жёлтые линии имеют возможность альтернативного проезда только с одной стороны, зелёные с двух (справа и слева), а красные - безальтернативны.

Вот да, с голубой мне и самому непонятно, почему она голубая, и правильно ли она так окрашена или нет :)
Насчёт альтернативных проездов - да, конечно, изначальная идея с этим как-то связана, но вот с одной стороны или с двух - это как-то по барабану. Мне так кажется (повторяю - только кажется, я не математик, да и со строгими критериями раскраски не очень понятно), что такой расклад насчёт проездов с двух сторон получился совершенно случайно. И ещё в силу определённых допущений (в частности - что линии, ведущие в депо, на заводы и к конечным станциям, за отдельные линии не считаются и на схеме не отображаются, и не участвуют в раскраске). Из депо у нас, впрочем, 3 расположены, так или иначе, на концах линий, а одно - на середине "красной" линии, так что оно тоже красноты линии никак не изменит. Но вот Русаковское подсоединено к линии, которая на картинке зелёная. Так вот, если бы я решил линию по Матросской Тишине посчитать за самостоятельную линию и нарисовать в схеме - то соответствующая зелёная линия была бы вынуждена пожелтеть. Поскольку красный тупик по правилам никак не может подсоединяться к зелёной линии, а в лучшем случае только к жёлтой. То есть, вернее, это линия, от которой ответвляется тупик, не может быть более чем жёлтой.
И наоборот, если бы не хвостик у Курского вокзала и если бы соответственно там был прямой проезд, а не вилка около Сыромятнического сплетения, то участок от Андроньевской пл. до Бауманской ул. был зелёным. То же касается и ещё двух несущих на себе тупики участков "большого кольца", точнее, "большой петли", имеющих "зелёные" обходы.

Т.е. похоже, да, эта закономерность по наличию обходов справа и слева - действительно случайное совпадение.

На самом деле я пытался рассуждать примерно так. Красные линии - это такие линии, разрыв которых (например, из-за ремонта или временного перерыва движения при аварии) разрывает до того единую сеть на два не связанных фрагмента. Ну, тут всё понятно. Действительно, безальтернативные. Дальше жёлтые - это значит, что для того, чтобы сеть разорвалась на 2 не связанных фрагмента, нужно кроме самого этого участка сделать ещё по крайней мере один разрыв на его обходе. Зелёная - это значит, что ещё одного разрыва всё равно мало, надо два разрыва на обходах, чтобы разорвать сеть.

А синий - соответственно, что даже двух разрывов на обходах не хватает для разрыва сети. Но, если формулировать так вот примитивно, то для синего участка на картинке это, разумеется, не так. Ибо понятно, что если его обход по факту проходит по "жёлтой" линии, то двух разрывов на оной хватит для разрыва сети. Но с другой стороны, это как бы не считается, поскольку тот же разрыв произойдёт и без участия синей линии, т.е. за него ответственная исключительно жёлтая. Т.е. появляется необходимость дополнительных условий. Скорее всего - что тот набор дополнительных разрывов не должен разрывать сеть сам по себе, но только в комплексе с разрывом рассматриваемой линии.

Т.е. грубо говоря, вводится некий целочисленный параметр. Минимальное количество единичных разрывов линий, в сочетании (но только в сочетании, а не сами по себе) с разрывом данной линии вызывающих разрыв всей сети в целом.
0 - красный, 1 - жёлтый, 2 - зелёный, и >2 - синий. Но вот в правильности окраски синего кусочка в московской схеме я не уверен, т.к. проверять вручную как-то трудновато, по крайней мере, пока процесс подсчёта этого параметра не алгоритмизирован каким-то удобным способом.

По-хорошему, надо бы ещё расширить это кроме линий на узлы (которые также могут быть подвержены "точечным разрывам" по каким-то причинам, накрывая тем самым все сходящиеся там линии), и соответственно раскрашивать отдельно и узлы как таковые.

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

И, естественно, для того, чтобы на основе этих картинок можно было доказательно демонстрировать собеседникам, что многие декларируемые якобы неустранимые и органически присущие недостатки трамвая на самом деле не являются недостатками самого трамвая, а являются сугубо недостатками топологии (а даже не только общего численного развития в километрах) имеющейся в данной системе сети. Опять же, проследить, как менялась "окрашенность" сети в истории той или иной системы, или как она могла бы измениться, если восстановить/вновь построить какие-либо соединительные участки (а значит, и иметь возможность оценивать сравнительную полезность их постройки с точки зрения надёжности сети). Например, есть идея по историческим данным сделать какую-нибудь такую цветную анимацию по истории сети Москвы и/или Питера, чтобы зритель мог наблюдать не только изменения абсолютной длины сети и некой общеориентировочной разветвлённости, но и соотношения длин и вид общей картинки по цветам.

Теорема: Аффтар ошибся: синяя линия на самом деле зелёная.

Доказательство: разорвем сеть по следующим точкам: МЭИ, Преображенское кладбище, Москва товарная курская.
Проверяем условия: сеть разорвана - да, рассматриваемый кусок в разрыве участвует - да, удаление разрыва на рассматриваемом участке восстановит сеть в единую - да, число прочих разрывов соответствует критерию синий линии - нет, зелёной - да.

Ура, товарищи, синих линий в Москве нет.



Редактировано 1 раз(а). Последний раз 08.04.11 00:52 пользователем karelalex.

Цитата (karelalex)
Теорема: Аффтар ошибся: синяя линия на самом деле зелёная.

Ура, товарищи, синих линий в Москве нет.

Большое спасибо! Я так и думал, что в таком в общем-то небогатом "огрызке" как Москва не получится четверного дублирования, впрочем, на момент рисования правила и не были сформулированы, рисовалось всё немножко по другому принципу, а конкретно осмысленные правила появились только вот в момент написания предыдущего поста. Да, значит, теперь, по правилам, будет зелёной.

Кстати, точно так же работает и ещё один вариант, где вместо Преображенского кладбища будет Бауманская-Ольховская-Красносельская. Теперь как бы это алгоритмизировать... В данных случаях мы имеем "линию разреза", пересекающую 3 линии. В этом случае автоматически никакая из этих линий не может иметь статус больше чем зелёный.

Алгоритм предлагается такой:
1) пробуем разрыв испытуемой линии, если сеть разорвана - красный
2) пробуем разрыв всех по очереди (по одному) сегментов, составляющих (вернее, составлявших бы, если бы испытуемая была цела) теснейшие циклы слева и/или справа от испытуемой линии, включающие её, если получилось - жёлтый
3) пробуем комбинировать всеми возможными парами разрывы в теснейших циклах справа и слева, или разрыв с одной стороны и второй разрыв с той же стороны в том цикле, который стал (бы) теснейшим после одного разрыва. Если в каком-то из сочетаний получилось - зелёный.
4) Иначе - синий.

Цитата (Toman)
Но было бы интересно получить формальное описание

Формально красные линии принято называть дендритами, жёлтые - границой остова, зелёные - границами циклов.

Цитата (Geoalex)
Формально красные линии принято называть дендритами, жёлтые - границой остова, зелёные - границами циклов.

Автор терминологии - основоположник эволюционной морфологии транспортных сетей С.А. Тархов.

Цитата (Geoalex)

Цитата (Toman)
Но было бы интересно получить формальное описание

Формально красные линии принято называть дендритами, жёлтые - границой остова, зелёные - границами циклов.

Ну, это не описание, а именно терминология. Причём как бы не факт что она соответствует декларированному выше принципу раскраски. Да, в данном конкретном случае так случайно получилось, что все жёлтые линии оказались на внешних замкнутых контурах, а все зелёные - внутри замкнутых контуров. Но, как я уже упоминал, любая из зелёных линий могла бы стать жёлтой, оставаясь внутри контура, если в середину присоединить какой-то объект, скажем тупиковую ветку. Что, в этом случае эта линия внутри контура переименуется в границу остова?

И, наоборот, некоторые из жёлтых линий по внешнему контуру могли бы стать зелёными, если бы к ним не были подсоединены тупиковые ветки. Они от этого перестали бы считаться границей остова, и стали "границами циклов"? Всё-таки, мне кажется, это немножко другого плана терминология.

Цитата (Toman)
Русаковское подсоединено к линии, которая на картинке зелёная. Так вот, если бы я решил линию по Матросской Тишине посчитать за самостоятельную линию и нарисовать в схеме - то соответствующая зелёная линия была бы вынуждена пожелтеть. Поскольку красный тупик по правилам никак не может подсоединяться к зелёной линии, а в лучшем случае только к жёлтой. То есть, вернее, это линия, от которой ответвляется тупик, не может быть более чем жёлтой.

Так и надо рисовать депо и линию по Стромынке жёлтым! Ведь с точки зрения декларированной задачи показа надёжности - как раз таки Стромынка должна быть жёлтой, т.к. двумя разрывами (с разных сторон от выезда с Матросской Тишины) от сети отсекается целое депо.

Касательно алгоритма начало его мне представляется таким:
1) Находим узлы и линии.
2) Находим красные линии, ибо они очевидны.
3) Мысленно стираем красные линии, ну и заодно узлы, к которым подходят только красные линии.
4) Смотрим, что осталось. Если из какого-то узла выходит только 2 линии, смело присваиваем желтый цвет. Это легко доказать, ибо разрыв обеих линий приведет к отрыву узла от остальной сети, а разрыв любой из линий не приведет к этому, иначе одни были бы красными.
Дальше я ещё не придумал.

Цитата (Алексей Черников)
Так и надо рисовать депо и линию по Стромынке жёлтым! Ведь с точки зрения декларированной задачи показа надёжности - как раз таки Стромынка должна быть жёлтой, т.к. двумя разрывами (с разных сторон от выезда с Матросской Тишины) от сети отсекается целое депо.

Если бы я рисовал ветки, ведущие в депо, и вообще рассматривал, скажем, те же депо конечные станции как отдельные сегменты сети, изображаемые на схеме - то конечно, так и было бы сделано. Но ведь, с другой стороны, если мы будем рисовать схему автомобильной улично-дорожной сети города или региона, то мы не будем, наверное, включать в схему каждый автобусный парк. Потому что тогда придётся, для справедливости, включать туда и каждый двор и каждый гараж, и тогда почти что ни одна улица не сможет быть более чем жёлтой, ибо перекрыв её в двух местах, мы, разумеется, отсечём часть сети в лице этих дворов. В то же время на возможность проезда какого-нибудь апаковского или октябрьского вагона (например, служебного какого-нибудь) в Медведково или на Открытое шоссе недоступность русаковского депо никак не повлияет.

Впрочем, можно попробовать нарисовать и другую схему, уже с функциональным уклоном, где депо будут рассматриваться как обязательные элементы (равно как и конечные, и узлы будут тоже рассматриваться либо как сегменты, либо рисоваться вообще как совокупность соединительных линий), а то и вообще раскрашивать детальную путевую схему. Но в последнем случае смотреть такую схему в целом будет малореально, а хочется сделать именно предельно наглядную картинку эволюции сети в городе - чтобы наглядно показать, скажем так, степень катастрофичности тех или иных закрытий советского времени (30-х-80-х годов) для связности сети.

Цитата (karelalex)
Касательно алгоритма начало его мне представляется таким:
1) Находим узлы и линии.

В компьютерной реализации это не требуется, т.к. эту стадию в любом случае выполнил предварительно человек. Единственное что - если наша задача, допустим, раскрашивать "полную историческую схему" для каждого периода, после каждого открытия/закрытия, то, конечно, программа должна будет из полного исторического набора исключать те узлы, которые больше не узлы, и соответствующим образом объединять линии.

Цитата
2) Находим красные линии, ибо они очевидны.

Для нас-то очевидны, а как это будет делать программа в автоматическом режиме? Впрочем, вот на этот пункт у меня, кажется, сегодня появился конкретный алгоритм (именно машинный по своему характеру - для человека он хоть и возможен, но требует работы в письменно-табличном виде с перечислением всех линий и, возможно, узлов, или прямо с раскрашивающим карандашом в руках, но не в устном виде).

(Для краткости назовём вышеупомянутый численный параметр "рейтингом").
В начальный момент всем линиями присваивается нечисловой рейтинг "неопределённо". Далее:
1) Находим все тупиковые линии (хотя бы в одном из ограничивающих узлов нет никаких других линий), и тут же присваиваем им рейтинг=0 ("красные линии").
2) Находим все линии с пока неопределённым рейтингом, у которых хотя бы в одном из ограничивающих узлов все остальные линии имеют рейтинг=0, и присваиваем им самим рейтинг=0. Продолжаем поиск и "раскрашивание" по данному пункту 2) до тех пор, пока не перестали находиться линии, удовлетворяющие условию.

В принципе, можно (и даже нужно, пожалуй) сформулировать в виде единственного цикла:
найти линию, у которой хотя бы в одном из концов(узлов) число других линий с ненулевым рейтингом (неопределённый считается также ненулевым!) равно нулю, присвоить ей рейтинг=0, повторять до тех пор, пока такие линии не перестанут находиться.

После выполнения этой стадии можно считать, что все линии, которые пока помечены "неопределённым" рейтингом, имеют рейтинг>0.

Цитата
3) Мысленно стираем красные линии, ну и заодно узлы, к которым подходят только красные линии.
4) Смотрим, что осталось. Если из какого-то узла выходит только 2 линии, смело присваиваем желтый цвет. Это легко доказать, ибо разрыв обеих линий приведет к отрыву узла от остальной сети, а разрыв любой из линий не приведет к этому, иначе одни были бы красными.

Более коротко и близко к уже программной реализации формулируем то же самое так: находим линии, у которых хотя бы в одном конце число других линий с ненулевым рейтингом равно 1, и присваиваем этим линиям рейтинг=1 ("жёлтые"). Это то же самое, просто в другой формулировке. То, что этим линиям надо присвоить рейтинг=1, понятно. Но есть проблема, что таким образом мы не исчерпаем все "жёлтые" линии, т.е. в общем случае останутся ещё, как мне кажется. И с этим надо что-то делать, если мы хотим продолжать работать путём последовательного исчерпывания линий с рейтингом=1, потом 2, 3 и т.д.

...Ещё один факт, который как-то выпал из виду, когда доказывалось отсутствие "синих" линий в Москве, но теперь представляется очевидным: линия просто никак не может иметь рейтинг>2 (условие для "синей" линии), если оба её конца не являются узлами четверными или имеющими большее число сходящихся линий. Если хотя бы один из концов - простой треугольный узел (угловой и вообще неполные в данном случае пока приравниваем к полным, благодаря хотя бы теоретической возможности проезда задним ходом по неправильному пути), то разрыв обеих других линий от одного из концов, плюс рассматриваемой линии, разумеется, оторвёт от сети сам данный узел и прилегающие, вплоть до разрывов, участки трёх линий. Даже только по этой причине та линия между двумя тройными узлами не может быть более чем зелёной.
А четверных узлов у нас в Москве только 2, кажется. Ну или, с некоторой натяжкой, можно посчитать за единый четверной узел место присоединения линии по Палиха-Лесной (в том смысле, что в принципе, при желании и необходимости, это место можно было бы оформить в виде настоящего неполного четверного узла, ну или просто волюнтаристски объявить это единым узлом). Но в любом случае, все эти узлы друг с другом не соседствуют, и в современной сети просто нет линий, которые бы соединяли два как минимум четверных узла - для которых имело бы смысл делать какие-то более сложные проверки величин рейтинга>2.

Цитата (Toman)
После выполнения этой стадии можно считать, что все линии, которые пока помечены "неопределённым" рейтингом, имеют рейтинг>0.

И в этот момент совершаем историческую ошибку. Главный недостаток предложенного алгоритма заключается в том, что он работает от тупиков, однако красные линии могут находится и между узлами, к которым никакие тупиковые ветки и не подходят.
Посмотрим на карту Москвы, линию от площади Борьбы до Красносельской указанный алгоритм красной не посчитает. (Т.к. для присваивания красноты требуется, чтобы один из концов линии был тупиком или становился таким после мысленного стирания всех красных линий, с указанной линией это, очевидно, не произойдет).
Так что похоже, что рассматривая только локальные свойства линий, что Вы делаете в своих рассуждениях здесь и далее, рейтинг линии можно оценить только сверху т.е. если наш алгоритм показал, что линия жёлтая, то она никак не может быть зелёной.

Цитата (Toman)
Но есть проблема, что таким образом мы не исчерпаем все "жёлтые" линии, т.е. в общем случае останутся ещё, как мне кажется.

Разумеется. Однако в Москве, похоже, таких случаев нету. Но его не сложно представить: уберём мысленно линию на 16-парковую от Семёновской. От этого линия Семёновская - Преображенская площадь не станет зелёной, однако указанному критерию удовлетворять перестанет.

Цитата (Toman)
...Ещё один факт, который как-то выпал из виду, когда доказывалось отсутствие "синих" линий в Москве, но теперь представляется очевидным: линия просто никак не может иметь рейтинг>2 (условие для "синей" линии), если оба её конца не являются узлами четверными или имеющими большее число сходящихся линий.

Ну да, это же очевидно: если к узлу примыкает эн линий, то, чтобы оторвать узел от сети, достаточно не более эн разрывов. Следовательно примыкающие к узлу линии не могут иметь рейтинг больший, чем тот, что соответствует эн разрывам.
Пока больше ничего не придумывается.



Редактировано 3 раз(а). Последний раз 06.05.12 13:56 пользователем karelalex.

Цитата (karelalex)
И в этот момент совершаем историческую ошибку. Главный недостаток предложенного алгоритма заключается в том, что он работает от тупиков, однако красные линии могут находится и между узлами, к которым никакие тупиковые ветки и не подходят.

Да, тут та же самая история, что и с жёлтыми. Почему-то про красные я не подумал - наверное, потому, что смотрел не на современную схему Москвы (глядя на современную, я бы, конечно, не забыл про не тупиковые красные, а вот в схеме начала 40-х годов все красные были, кажется, действительно только тупиковыми).
Однако сам этот этап имеет смысл оставить, по крайней мере, для случая больших и сложных сетей, поскольку это самый простой способ отделить тупиковые линии и кусты, чтобы, возможно, даже в разы облегчить дальнейшую работу. Для проверки остальных линий можно попробовать метод поиска неповторяющихся маршрутов, соединяющих концы линии, кроме собственно самой этой линии. Если такой маршрут не находится, линия красная и исключается. Можно использовать это как единственную операцию, если поиск маршрутов происходит пошагово с каждого конца, и одновременно для всех линий, по принципу, у какой линии и с какого конца раньше обнаружится невозможность. В этом случае тупиковые линии выявляются и исключются на первом же шаге, и начало работы автоматически сводится к предыдущему алгоритму.

Цитата
Так что похоже, что рассматривая только локальные свойства линий, что Вы делаете в своих рассуждениях здесь и далее, рейтинг линии можно оценить только сверху т.е. если наш алгоритм показал, что линия жёлтая, то она никак не может быть зелёной.

Значит, придётся использовать те же самые уже найденные неповторяющиеся (сами поверх себя, т.е. не закольцованные) маршруты. В простейшем (но вычислительно тяжёлом) случае можно искать все такие маршруты. Далее ищем наиболее популярную линию (или несколько таковых, при равной популярности), и смотрим, входит ли она во все маршруты без исключения. Если да - то линия жёлтая. Если нет - пробуем все попарные сочетания линий, чтобы вырубить все обходы, далее тройные и т.д.

Но если сеть большая, то все маршруты заранее проложить и потом анализировать физически невозможно. Отчасти тут пригодится то самое локальное верхнее ограничение: как только оно достигнуто, дальше прибавлять маршруты уже нет смысла. Но вот что делать с теми случаями, когда оно не будет достигнуто никогда? Значит, надо делать ограничение не только строго локальное по концам самой линии, но и по каким-то более далёким "границам", скорее всего, целенаправленно выбранным.

Цитата (Toman)
Для проверки остальных линий можно попробовать метод поиска неповторяющихся маршрутов, соединяющих концы линии, кроме собственно самой этой линии. Если такой маршрут не находится, линия красная и исключается.

Вот ещё мысли:
Пусть мы умеем строить маршруты от точки к точке или находить, что такого маршрута нет, как, это можно обсудить потом.
Строго я сейчас этого доказать не могу, но на интуитивном уровне мне кажется, что стирание любой красной линии не влияет на цвет остальных, если мы не трогаем узлы (за исключение узлов, к которым подходят только красные линии, их можно тоже смело удалять).
Алгоритм строим так:
1) Присваиваем красный цвет всем тупиковым линиям
2) Удаляем их
3) Повторяем до тех пор, пока они не перестанут находится.
4) Проводим проверку на красноту всех линий, методом построения альтернативного маршрута. Если он есть, помечаем линию как некрасную, чтобы потом не рассматривать. При нахождении стираем линию и возвращаемся к первому пункту. (Это для экономии вычислительного ресурса).
5) То, что осталось считаем как минимум жёлтым.
6) Линии, выходящие из двойных узлов считаем жёлтыми сразу.
7) Проверку на желтизну остальных линий делаем следующим образом: мысленно удаляем проверяемую линию и на оставшейся сети ищем красные линии. Если они появились, значит проверяемая линия жёлтая, и те самые теперь уже красные тоже жёлтые.
8) Остальные линии, очевидно, оказываются как минимум зелёными.
Как отличать зелёную от синей только методом проверки существования маршрута - пока не очень понятно.



Редактировано 1 раз(а). Последний раз 06.05.12 23:25 пользователем karelalex.

Обычная "теория графов" вам в помощь.

Только рассматривать надо не тупики, а все возможные варианты проезда "от узла до узла".
Ну а метод рейтингования - получается простым: он равен числу альтернативных маршрутов (т.е. красный - это 1, желтый - 2 и т.п.).
Кстати, в сети есть не только голубые, но и белые участки (в схеме есть кусочек с числом альтернативных маршрутов = 5, хотя, конечно, объезд маршрутом на порядок длиннее основного - это из области фантастики. Но возможность-то есть!)

Цитата (ailcat)
Обычная "теория графов" вам в помощь.

Это понятно, но для конкретной задачи вся теория явно не нужна, в главное: у нас её преподавали почему-то только параллельной группе.

Цитата
Только рассматривать надо не тупики, а все возможные варианты проезда "от узла до узла".

А Вам не кажется, что это метод потребует заметно больше вычислительных ресурсов?

Цитата
Ну а метод рейтингования - получается простым: он равен числу альтернативных маршрутов (т.е. красный - это 1, желтый - 2 и т.п.).

Тут есть один момент: число маршрутов в объезд напрямую не связано с предложенным тов. Томаном рейтингом. Так, например, от Семёновской до Преображенской площади можно доехать (кроме прямого) ещё минимум 4-мя способами, однако прямая линия между ними желтая.

Цитата
Кстати, в сети есть не только голубые, но и белые участки (в схеме есть кусочек с числом альтернативных маршрутов = 5, хотя, конечно, объезд маршрутом на порядок длиннее основного - это из области фантастики. Но возможность-то есть!)

Вы заменили исходное условие задачи, да в вашей задаче цветов сильно больше, но они отвечают совсем другому критерию. И это даже понятно почему: критерий тов. Томана отвечает не общему количеству альтернативных маршрутов, а количеству альтернативных маршрутов, не имеющих общих участков.

Цитата (karelalex)
Как отличать зелёную от синей только методом проверки существования маршрута - пока не очень понятно.

Да аналогично - т.е. рекурсивно. Закрытие зелёной линии превращает в жёлтые хотя бы в каких-то точках два её обхода. Т.е., если у нас синий - это верхний предел, и выше этого мы ничего не хотим различать, то после закрытия любой линии мы ищем не только сразу красные (проверка на жёлтый), но и, если линия оказалась не жёлтой - ищем ещё раз новые жёлтые. К сожалению, однако, такой порядок вычислений обещает быть чудовищно вычислительно сложным (по крайней мере, если не кэшировать найденные маршруты, потом просто исключая те, которые оказались недоступны, а искать их каждый раз заново), если только сеть не совсем маленькая, и о повышении предельного определяемого рейтинга выше 3 (синего) нечего и думать (хотя это и очень редкие случаи, видимо: как минимум, линия должна лежать между двумя пятерными узлами). Но и кэшировать все найденные маршруты в большой сети накладно.

...А вообще, сейчас я вот подумал перейти к рассмотрению с немножко другой точки зрения - когда основными объектами будут считаться целевые станции и подъездные пути, а также узлы (особенно учитывая нечёткость грани между узлами и конечными станциями с функциональной точки зрения). Т.е. уже когда рассматривается не только закрытие линии, но и узла, а также рассматривается разница между полными/неполными узлами, с разворотом или без, двухпутными и однопутными линиями, местами возможного перехода на неправильный путь или обратно и т.д. Общий принцип-то может быть тот же - поиск обходных маршрутов и дальнейший анализ. Только разница в том, что эти обходные маршруты должны быть корректными - т.е. начинаться и заканчиваться именно на тех направлениях, на которых надо, а также, в зависимости от установленнх правил: можно ли разворачиваться в узлах/станциях задним ходом, можно ли проезжать по линии задним ходом. При игнорировании внутреннего устройства узлов/конечных и числа путей на линиях на оба эти вопроса вынужденно приходилось отвечать "да" - т.к. иначе, например, отключение вроде бы красной (ибо тупиковой) линии от Курского вокзала до развилки привело бы к изменению расклада на остальной сети (т.к. накрылся бы объезд Волочаевской ул. через Сыромятники, если только не проезжать целую линию задним ходом). С современной московской схемой путевого развития, конечно, любой компьютер справится и без какой-либо хитрой оптимизации, по-простому. А так, рассмотрение внутреннего устройства узлов (т.е. "запрета поворотов") только снижает вычислительную сложность поиска маршрутов, пожалуй, т.к. вариантов ветвления меньше.

Цитата (Toman)

Цитата (karelalex)
Как отличать зелёную от синей только методом проверки существования маршрута - пока не очень понятно.

Да аналогично - т.е. рекурсивно. Закрытие зелёной линии превращает в жёлтые хотя бы в каких-то точках два её обхода.

Есть вариант, когда закрытие зелёной линии вообще не влияет на цвета других. Представим на секунду, что линию у Бауманской опять закрыли. И посмотрим на линию по Краснобогатырской. Она так и останется зелёной, однако линия между Сокольниками и Преображенкой пожелтеет.
А теперь уберём линию на Краснобогатырской, ни одна не поменяет цвет. Вот поэтому у меня и случился затык в придумывании дальнейшего алгоритма.

Цитата (karelalex)
А теперь уберём линию на Краснобогатырской, ни одна не поменяет цвет. Вот поэтому у меня и случился затык в придумывании дальнейшего алгоритма.

Если сравнивать с состоянием, когда убраны не только красные линии, но и узлы, где они присоединяются, всё бы поменяло как надо. Теоретически, можно и так считать - вначале убрать красные вместе с узлами, посчитать только для замкнутых остовов сети, а потом вернуть красные вместе с узлами, и перекрасить что положено в жёлтый. Но, пожалуй, это всё - слишком сильное усложнение. В т.ч. по выч. ресурсам - поскольку схема сети по ходу дела меняется, и кэшировать маршруты между разными этапами уже не получится.
Тем более, что на практике же алгоритм поиска маршрута не ищет только один маршрут, он всё равно так или иначе найдёт несколько маршрутов (возможно, даже все), т.е. уже будет сделана бОльшая работа, чем бинарная информация о существовании или несуществовании маршрута, т.е. мы уже сразу имеем какую-то кучку маршрутов, и можем сразу найти среди них не имеющие общих участков, если таковые есть.

Возможно также применение неких принципиально не маршрутных изначально алгоритмов для поиска узких мест, или для предварительного определения направлений движения - например, "токовые" - рассмотрение сети как электрической цепи или гидравлической сети, с подключением концов к разнообразным парам станций. Кстати, да, как раз вопрос существования или несуществования маршрута логичнее всего решать именно "гидравлическим" численным моделированием - там сразу получается чёткий ответ. Да даже и выявлять конкретные маршруты - и те, пожалуй, начиная с определённой сложности сети, проще тем же гидравлическим моделированием (грубо говоря, симуляция разбегающейся волны) - когда порядок количества разветвляющихся и не обрывающихся маршрутов начинает приближаться/превосходить порядок количества элементов сети для симуляции волны.

На "гидравлике" алгоритм типа вышеобсуждаемого рекурсивного, кажется, получается попроще. А именно: подключаем исток и сток к концам рассматриваемой линии (сама она перекрыта), и видим, есть ли ток. Нет тока - линия красная, есть ток - как минимум жёлтая. Смотрим на величину тока по всем линиям, на предмет, не равен ли он где единице. Если такие нашлись, пробуем по очереди перекрывать их все, чтобы удостовериться, что они все точно жёлтые, вместе с нашей линией. Если нет единиц, пробуем перекрывать самые разные линии, начиная с самых жирных потоков, пока где-нибудь не появится единица. Если появится - перекрываем и её для проверки, и, если действительно перекрылось, назначаем исследуемой (изначальной) линии зелёный цвет. Не нашлось таких - значит, синяя.
Можно ещё попробовать поиграться с нелинейной вязкостью. Причём в обе стороны - там могут быть некие полезные для вычислений эффекты, ведущие к разного типа алгоритмам.

Для проверки наличия маршурта можно использовать вот такой примитивный (в общем-то) алгоритм. Вычислительная сложность его не больше, чем у простой сортировки.
1) Строим матрицу связывания.
2) Берём массив, соответствующий узлам, в котором помечаем элемент связанным с конечной точкой, начальной точкой или не определенным.
3) Одной и той же функцией идём с разных концов. Соответственно помечаем связанные узлы. А также вновь добавленные точки кладём в стек или очередь, чтобы потом с них продолжать поиск. Как только с одной из сторон мы встречаем точку, связанную с другим узлом, говорим "Да маршрут существует".
4) Если же очередь (стек) кончается с обеих сторон, говорим, что "Маршрута нет".
Всё на уровне школьных знаний.

Цитата (karelalex)
3) Одной и той же функцией идём с разных концов. Соответственно помечаем связанные узлы. А также вновь добавленные точки кладём в стек или очередь, чтобы потом с них продолжать поиск. Как только с одной из сторон мы встречаем точку, связанную с другим узлом, говорим "Да маршрут существует".
4) Если же очередь (стек) кончается с обеих сторон, говорим, что "Маршрута нет".

В общем и целом это и есть аналог распространения волны, в простейшем его виде (в данном случае - без учёта времени, например). Вот только насчёт стека/очереди я что-то не понял, что именно туда кладётся и зачем. И что значит "кончается", если мы туда только что-то кладём, вроде бы. Для оптимизации расширения помеченных областей (чтобы знать, в каком месте расширять, в то время как во всех остальных областях либо ещё ничего не меняется, либо уже всё помечено) достаточно держать список граничных точек помеченного "круга". Можно для каждой из граничных точек записывать кратчайший/лучший (в каком-то из смыслов) маршрут, по которому она была достигнута, либо можно для каждой точки метить не только факт достижения, но и число шагов (или расстояние, или условное время), на котором она была достигнута (что позволит в обоих случаях после установления факта наличия связи найти конкретный кратчайший маршрут - и тут же перекрыть его по всей длине, после чего либо честно начать сначала поиск ещё каких-то альтернативных маршрутов, либо, чтобы сэкономить время, аккуратно "откатить" те точки, которые были достигнуты через закрытые участки, соответствующим образом перерисовав границы, и продолжить поиск маршрутов с такого положения).

Что-то я долго думал, хотя есть абсолютно очевидный алгоритм, который сможет дать точные данные по каждой линии:
1) Мысленно вычёркиваем линию из схемы
2) Ищем альтернативный маршрут между узлами вычеркнутой линии
2а) Если найден, то вычёркиваем его целиком, счётчик найденных маршрутов увеличиваем на один.
2б) Повторяем пункт 2а сколько нужно раз.
3) Как только маршрут оказывается не найден, присваиваем цвет исходной линии. Красный, если счётчик ноль, жёлтый - 1, зелёный - 2, синий - 3 и более.

Правда, в случае синей линии возможна ситуация, когда маршрут будет построен так, что она будет по ошибке принята за жёлтую, но это маловероятно.

Цитата (karelalex)
2) Ищем альтернативный маршрут между узлами вычеркнутой линии
2а) Если найден, то вычёркиваем его целиком, счётчик найденных маршрутов увеличиваем на один.

Собственно, именно это же я и предложил в предыдущем посте. Но, видимо, всё не так просто, и рановато говорить, что это решение.

Цитата

Правда, в случае синей линии возможна ситуация, когда маршрут будет построен так, что она будет по ошибке принята за жёлтую, но это маловероятно.

А как это? Найденный "кратчайший" маршрут проходит так, что перерезает все остальные возможные маршруты (при том, что на их месте можно было бы проложить несколько полностью независимых)? "Маловероятно" в данном случае не годится, увы - это детерминированный дискретный алгоритм, в нём либо ошибка исключена (а это надо доказывать), либо сам алгоритм надо считать ошибочным. Я даже не могу сказать, что ситуация маловероятна - в развитой сети она как раз очень вероятна, и нетрудно специально сконструировать такую сеть, где ошибка такого рода будет происходить. И не только между синей и жёлтой, а на любом уровне в сторону понижения (не ниже жёлтого, конечно: если уж маршрут есть, он будет найден). А именно: рисуем первый обход исследуемой линии - тот, который станет кратчайшим и потому первым найденным и перекрытым. Потом рисуем два частичных обхода этой линии, с некоторым перекрытием в середине (по типу как ж.д. разъезд полупродольного типа), но оба насколько-то удлиняющих путь в том смысле, который используется алгоритмом - хоть по числу узлов, хоть в километрах, хоть ещё как (хотя достаточно и того, чтобы они были равны по длине, т.к. в этом случае выбор "главного" маршрута произойдёт по каким-то случайным и не имеющим отношения к делу факторам, и с большой вероятностью попадёт так, как нам надо для получения ошибки). Кусок схемы такого вида настолько тривиально выглядит, что игнорировать такое нельзя даже под предлогом маловероятности.

С другой стороны, есть такое предположение, что, возможно, такого "запоганивания" маршрутов можно избежать, если закрывать сегменты только для прохождения в том же направлении, которое пройдено "первым" маршрутом, но не для обратного направления (и, аналогично, для узлов - закрывается только то направление из существующих для узла, в котором оно проходилось маршрутом, не задевая других направлений). Пока это только предположение, однако - основанное только на том, что это так для данного частного случая. Но может быть, это и реальная закономерность хотя бы для какой-то разновидности графов (вот это-то наверняка можно откопать где-то на самой поверхности теории графов...), в таком случае это может быть выходом - хотя и несколько искусственным с физической точки зрения, и не менее рискованным в смысле, наоборот, завышения рейтинга (если узлы у нас имеют ограничения направлений движения, то мы можем воспринять как независимые два маршрута, которые реально исчерпывают всё множество возможных обходов, но используют один сегмент, только в противоположных направлениях, или один узел в разных направлениях (если мы определяем рейтинг и для узлов) ).

Можно попробовать в случае обнаружения такого "встречного самопересечения" очередным найденным маршрутом одного из предыдущих делать шаг назад, и, "забыв" оба маршрута, и откатив счётчик, закрыть (но уже в обоих направлениях) один из тех сегментов, которые использовались в разных направлениях в двух законфликтовавших маршрутах (постольку, поскольку, НЯП, если только не действуют ограничения на направления по узлам, о таковой линии можно однозначно утверждать, что она является фактически лишь "перемычкой" между некими отдельными маршрутами), после чего заново повторить поиск-исключение маршрутов. Если ещё маршруты без самопересечений находятся, то засчитываем их. Если опять происходят пересечения - то откатываем пересекшиеся, закрываем очередную перемычку, и так до тех пор, пока самопересечения не прекратятся. Если же после перекрытия очередного "встречного" сегмента маршруты вообще перестали находиться (что возможно при наличии ограничений по узлам), то засчитываем в счётчик единицу, т.к. данная линия оказалась по смыслу единственным оставшимся обходом, хотя и использовалась какими-то двумя маршрутами в разных направлениях.

...Но всё это опять основано на предположениях, в которых я совершенно не уверен, по крайней мере, пока...

Цитата (Toman)

Цитата (karelalex)
Правда, в случае синей линии возможна ситуация, когда маршрут будет построен так, что она будет по ошибке принята за жёлтую, но это маловероятно.

А как это? Найденный "кратчайший" маршрут проходит так, что перерезает все остальные возможные маршруты (при том, что на их месте можно было бы проложить несколько полностью независимых)?

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

Вот в таком графе, если мы рассматриваем синюю линию, то несложно заметить, что разрыв её и розовых линий приведут к разрыву всего графа, однако кратчайший маршрут по графу в обход синей линии (голубые и розовые линии) проходит как раз через них. Для удобства я пометил "расстояния" до рассматриваемых узловых точек, от различных узлов графа. Т.о. хотя бы теоретически, но для синих линий возможно занижение их статуса до жёлтых при использовании ранее мною предложенного метода.

Цитата
И не только между синей и жёлтой, а на любом уровне в сторону понижения (не ниже жёлтого, конечно: если уж маршрут есть, он будет найден).

Про жёлтую я высказался ранее, а вот теперь я покажу, что для зелёной в любом случае такой ситуации не возникнет. Рассмотрим зелёную линию, а также любые 2 линии, который собственно и делают эту линию зелёной. Тогда граф можно изобразить вот в таком виде:

Большие области - это две половинки графа, связи в внутри которых нас не интересуют, главное, что эти половинки внутри себя полностью связаны, а между ними есть только 3 связи (зелёная и серые линии).
Будем доказывать утверждение от противного: пусть кратчайший маршрут в обход зелёный ветки проходит по обеим серым веткам. Без ограничения общности можно считать, что начальная точка находится в голубой половине, а конечная в оранжевой, тогда маршрут либо уходит в оранжевую область по одной из веток, затем возвращается по ней в эту же область и снова выходит из неё по другой, либо сначала выходит по одной, возвращается по другой и снова выходит по первой. В обоих случаях маршрут проходит дважды через одни граничные узлы первой серой линии, а следовательно никак не может быть кратчайшим. ЧТД.
В общем мне пока очевидно только то, что предложенный мной алгоритм с некой долей вероятности может ошибаться при определении статуса синей линии.

Цитата (karelalex)
Большие области - это две половинки графа, связи в внутри которых нас не интересуют, главное, что эти половинки внутри себя полностью связаны, а между ними есть только 3 связи (зелёная и серые линии).

А зря не интересуют. Потому что именно как минимум в какой-то одной из них проблема и возникнет. Непонятно, почему выбрано именно это "узкое место". Оно ведь, вполне возможно, не единственное. Кто сказал, что дальше, внутри синей или оранжевой областей, по дороге к нашим концевым узлам, нет ещё другого узкого места шириной тоже в 2 линии, не считая проверяемой зелёной?

Цитата
Будем доказывать утверждение от противного: пусть кратчайший маршрут в обход зелёный ветки проходит по обеим серым веткам.

Вот непонятно, зачем ему так проходить, когда вполне достаточно мирно пройти по одной, после чего уже в оранжевой области "подрезать" второй?

Цитата
тогда маршрут либо уходит в оранжевую область по одной из веток, затем возвращается по ней в эту же область и снова выходит из неё по другой, либо сначала выходит по одной, возвращается по другой и снова выходит по первой.

Такие варианты даже рассматривать не имеет смысла (по крайней мере, в простом варианте без ограничений направлений по узлам, где заезд туда-обратно может быть необходим технически для разворота/поворота в нужном направлении - но при таком подходе мы уже отдельно рассматриваем разные пути, так что граф там получается уже другой, и с направленными линиями). Поскольку мы изначально ищем только не повторяющие себя маршруты: алгоритм просто не пойдёт метить уже помеченные ранее узлы или линии, и уже только поэтому ни прямо, ни обратно два раза по одной линии найденный маршрут пройти не может.

Цитата
В обоих случаях маршрут проходит дважды через одни граничные узлы первой серой линии, а следовательно никак не может быть кратчайшим. ЧТД.

Нет, это не ЧТД. Просто в примере с синей линией можно было провести линию раздела между "голубой" и "оранжевой" областями так, что кратчайший маршрут запоганил все три независимых маршрута именно на этой линии раздела. Конечно, для того, чтобы один маршрут мог запоганить все независимые маршруты именно на одном и том же "узком месте", и при этом быть несамоповторяющимся, этих независимых маршрутов должно быть нечётное число. Но такое строгое оформление не обязательно - на самом деле, когда я писал предыдущий пост, я не имел в виду в первую очередь именно такой проход "зигзагом", с обязательным реверсом на одном из независимых маршрутов. Узких мест может быть несколько последовательно, с одной или несколькими перемычками между независимыми маршрутами. Достаточно кратчайшему маршруту даже без всякого реверса, в "правильном направлении", перебрать все независимые маршруты, чтобы заткнуть их все (а обход по перемычкам тоже станет невозможен, т.к. они тоже заткнуты, да и к узлам подход может быть разный). При этом на любом узком сечении, где две части сети соединяет ровно определяющее число линий, кратчайший маршрут честно использует только одну из них (или, в общем случае, удовлетворяет условию выше: в "правильном" направлении проходит на на один раз больше, чем в неправильном, итого использует нечётное количество ниток).

Вот фактически простейший вариант схемы-ловушки с зелёной линией:

Тонкие линии показывают возможные узкие места, по которым можно поделить сеть на две части ("голубая" и "оранжевая"), видно, что в любом из них кратчайший маршрут проходит, как и положено, только по одной нитке. Что, однако, не мешает ему уже к другому узкому месту перепрыгнуть на другую нитку, закрыв и её саму, и перемычку. После закрытия только розовых линий, даже обеих одновременно (если не трогать узлы при этом) альтернативный маршрут бы остался (через перемычку в противоположном направлении) - но при закрытии всего кратчайшего маршрута (как это предполагалось делать в обсуждаемом сейчас алгоритме) оставшиеся чёрные звенья уже не смыкаются. В результате ошибочно принимаем зелёную линию за жёлтую. Причём, как видно, схема настолько скромненькая и нехитрая (4 тройных узла, 4, допустим, конечных или узла-подсоединения тупиковых линий или какой-нибудь обходной петли, которая тут ничего не поменяет, 10 неразветвлённых участков линий, да и геометрия не какая-то особо вывернутая), что встречаться такой фрагмент в реальности может ну очень часто и непринуждённо, так что даже о малой вероятности/частоте таких ошибок я бы говорить не стал.

Аналогично можно и для трёх обходных нарисовать - так, что на каждом отдельно взятом узком месте, соединённом ровно тремя обходами помимо проверяемой линии, кратчайший маршрут пройдёт только по одной нитке, но суммарно подрежет всё оставшееся.

Нехорошо получилось, значит в общем случае метод последовательного вычёркивания маршрутов целиком не работает. Тогда вспомним, что мы имеем. В принципе мы можем легко определять красные, жёлтые линии, а также статус "более чем жёлтая". Впрочем, как уже выше было замечено, такое определение не требует даже собственно построения маршрута, достаточно проверки его существования. И ещё: метод затирания маршрута только в использованном направлении в случае синей линии тоже даст неправильный результат, т.к. средняя линия первыми двумя маршрутами будет использована в оба направления.
Таким образом видимо нужно делать того, чего не хотелось бы: искать все возможные маршруты и выделять из них максимум не имеющих общих участков. Что пока не очевидно как. Хотя есть ещё один способ методом тупого перебора:
1) разрываем интересующую нас линию, затем разрываем 2 другие: проверяем связанность.
2) Повторяем до тех пора, пока не обнаружим разрыв или не кончатся отрезки сети
3) Делаем выводы из результатов второго пункта.