Комментарии 17
for toIndex in graph.adjacencyList[fromIndex].flatMap { $0.toIndices } where !visited.contains(toIndex) {
stack.insert(toIndex, at: 0)
}
Дело вкуса. Я не люблю использовать forEach для подобных ситуаций. И чуть медленней работает нежели for in. Но разница настолько не значительная, что за аргумент не подходит.
P.S. У меня есть четкое деление когда for in а когда forEach, но это объяснить тянет на статью, чтобы понять почему я так делю.
www.swiftbysundell.com/tips/picking-between-for-and-for-each
Хорошая статья. Да, я пожалуй с ней соглашусь во многом. Но я бы сказал так что for in ещё стоит использовать в алгоритмических задач — из-за аргумента, который написан в статье, возможность управления циклом continue break.
Ведь пока я писал алгоритм, тело цикла менялось раз 20 и там были варианты и с continue и с break.
В прочем forEach мне нравится использовать только в случаях когда он целиком означает некое законченное действие. Например, с removeFromSuperview() — тогда весь целиком forEach означает "удалить все subviews".
For in же сложнее воспринимать как единую операцию, но зато проще как Безымянную.
Да так красивее, но where по моим измерениям годичной давности работает сильно медленнее. Поэтому я его не использую. Возможно мои данные устаревшие.
а чем вас не устроила "ссылка1"? Там же приведен работающий алгоритм, осталось только переписать его с C++ на Swift
Исходный вопрос задавался про неориентированный граф, а в тексте вроде как речь идет об ориентированных.
Вообще, по тексту я не совсем понял, зачем в изложенной ситуации перечислять циклы, когда достаточно, казалось бы, найти и отрапортовать сами сильные компоненты связности.
В любом случае, мне представляется, что плясать нужно от алгоритмов Тарьяна — первого для неориентированных графов, второго — для ориентированных. Далее следует более или менее комбинаторный перебор с выкидыванием отработанных частей.
Спасибо. Почитаю. Теорию графов я помню только от универа где она была около месяца. Поэтому научные труды не искал — мне бы понадобилось много времени на поиск и почтение.
Скорей всего есть более оптимальные алгоритмы подходящие под мою задачу. Где-то читал, что можно через Остовное дерево находить.
Для моей задачи меня устроил достигнутый результат, который должен быть понятен большому кругу людей.
Я надеялся на комментарий от человека знакомого с этой темой — чтобы была возможность почитать как подобные задачи решаются на больших данных.
А циклы мне нужно найти все (не обязательно сохранять), чтобы проверить что они верные в рамках прикладной области. Для этого там есть различные проверки на данных которые хранятся в вершинах и рёбрах. И некоторые проверки требуют полную информацию — нельзя сказать по части цикла верный он или нет.
Я старался не вдаваться в подробности этих проверок, но возможно отдельной статьей напишу о всех проверках. Тем более мне кажется, что можно проверить ещё что-нибудь, а сообщество может предложить интересные идеи.
Оно там даже больше чем экспонента растёт от количества вершин. Вопрос лишь сколько лишних операций надо сделать чтобы их найти. Одно дело 10к циклов и на них 100к операций, другое 10к циклов и на них как у меня было бы, в обычном обходе в глубину, 10^13 операций где-то.
Если рассматривать сложность не от количества вершин, а от количества циклов то идеально О(N). Боюсь правда такого нет, но возможно приближенно что-то подобное есть.
Спасибо, классная статья, интересный стиль повествования.
Не могли бы поделиться своим супер-пупер графом? Хочется поиграться самому.
Проект рабочий. Я не в праве давать код, по которому строиться граф.
Но я сейчас занимаюсь визуализацией — сохраняю граф весь в dot формате. Это не полная информация, но этот файлик я могу дать, перед этим переименовав все названия вершин.
Если информации о наличии вершин, рёбрах, пакетах достаточно без конкретных данных то в течении сегодняшнего дня приложу отдельно к статье.
Для построения графа с целью поискать циклы этого должно быть достаточно.
en.wikipedia.org/wiki/Johnson%27s_algorithm
и его реализацию на Swift
github.com/hectr/swift-elementary-cycles
Как я простые циклы искал