Ответ 1
Следующий функциональный код Scala генерирует карту, которая назначает представителя каждому node графика. Каждый представитель идентифицирует один сильно связанный компонент. Код основан на алгоритме Тарьяна для сильно связанных компонентов.
Чтобы понять алгоритм, достаточно было бы понять сгиб и контракт функции dfs.
def scc[T](graph:Map[T,Set[T]]): Map[T,T] = {
//`dfs` finds all strongly connected components below `node`
//`path` holds the the depth for all nodes above the current one
//'sccs' holds the representatives found so far; the accumulator
def dfs(node: T, path: Map[T,Int], sccs: Map[T,T]): Map[T,T] = {
//returns the earliest encountered node of both arguments
//for the case both aren't on the path, `old` is returned
def shallowerNode(old: T,candidate: T): T =
(path.get(old),path.get(candidate)) match {
case (_,None) => old
case (None,_) => candidate
case (Some(dOld),Some(dCand)) => if(dCand < dOld) candidate else old
}
//handle the child nodes
val children: Set[T] = graph(node)
//the initially known shallowest back-link is `node` itself
val (newState,shallowestBackNode) = children.foldLeft((sccs,node)){
case ((foldedSCCs,shallowest),child) =>
if(path.contains(child))
(foldedSCCs, shallowerNode(shallowest,child))
else {
val sccWithChildData = dfs(child,path + (node -> path.size),foldedSCCs)
val shallowestForChild = sccWithChildData(child)
(sccWithChildData, shallowerNode(shallowest, shallowestForChild))
}
}
newState + (node -> shallowestBackNode)
}
//run the above function, so every node gets visited
graph.keys.foldLeft(Map[T,T]()){ case (sccs,nextNode) =>
if(sccs.contains(nextNode))
sccs
else
dfs(nextNode,Map(),sccs)
}
}
Я тестировал код только на графике примера, найденном на странице Википедии.
Разница с императивной версией
В отличие от исходной реализации, моя версия позволяет явно разматывать стек и просто использует правильную (не хвостовую) рекурсивную функцию. Стек представляет собой постоянную карту, называемую path. В моей первой версии я использовал List как стек; но это было менее эффективно, так как нужно было искать элементы, содержащие элементы.
Эффективность
Код довольно эффективен. Для каждого ребра вам необходимо обновить и/или получить доступ к неизменяемой карте path, которая стоит O(log|N|), в общей сложности O(|E| log|N|). Это контрастирует с O(|E|), достигнутым императивной версией.
Выполнение линейного времени
В докладе Криса Окасаки в линейке Haskell для решения задачи нахождения сильносвязанных компонент дается линейное временное решение. Их реализация основана на алгоритме Косараджу для поиска ГТК, что в основном требует двух первых пересечений по глубине. Основной вклад в документ представляет собой ленивую, линейную временную реализацию DFS в Haskell.
Для достижения линейного решения времени требуется набор с тестом t1 и singleton add и membership. Это в основном та же проблема, что и решение, данное в этом ответе, имеет более высокую сложность, чем императивное решение. Они решают его с помощью потоков состояний в Haskell, что также можно сделать в Scala (см. Scalaz). Поэтому, если кто-то хочет сделать код довольно сложным, можно реализовать алгоритм Tarjan SCC для функциональной версии O(|E|).