teoria profundidad kosaraju grafos grafo fuertemente ejemplos debilmente conexos conexo componentes busqueda algoritmo scala clojure functional-programming graph-algorithm tarjans-algorithm

scala - profundidad - Implementación funcional del algoritmo de componentes fuertemente conectados de Tarjan



grafo debilmente conexo (3)

Echa un vistazo a https://github.com/jordanlewis/data.union-find , una implementación Clojure del algoritmo. Es un poco disfrazado de una estructura de datos, pero el algoritmo está todo allí. Y es puramente funcional, por supuesto.

Seguí adelante e implemented la versión de libro de texto del algoritmo SCC de Tarjan en Scala. Sin embargo, no me gusta el código, es muy imperativo / procesal con muchos estados mutantes e índices de contabilidad. ¿Hay una versión más "funcional" del algoritmo? Creo que las versiones imperativas de los algoritmos ocultan las ideas centrales detrás del algoritmo a diferencia de las versiones funcionales. Encontré a alguien más con el mismo problema con este algoritmo en particular, pero no he podido traducir su código de Clojure a Scala idomático.

Nota: si alguien quiere experimentar, tengo una buena configuración que genera gráficos aleatorios y prueba su algoritmo SCC frente a la ejecución de Floyd-Warshall

El siguiente código funcional de Scala genera un mapa que asigna un representante a cada nodo de un gráfico. Cada representante identifica un componente fuertemente conectado. El código se basa en el algoritmo de Tarjan para componentes fuertemente conectados.

Para comprender el algoritmo puede ser suficiente comprender el pliegue y el contrato de la función 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) } }

He probado el código solo en el gráfico de ejemplo que se encuentra en la página de Wikipedia.

Diferencia a versión imperativa.

En contraste con la implementación original, mi versión evita el desenrollado explícito de la pila y simplemente usa una función recursiva adecuada (sin cola). La pila está representada por un mapa persistente llamado path lugar. En mi primera versión utilicé una List como pila; pero esto fue menos eficiente ya que tuvo que buscarse para contener elementos.

Eficiencia

El código es bastante eficiente. Para cada borde, debe actualizar y / o acceder a la path mapa inmutable, que cuesta O(log|N|) , para un total de O(|E| log|N|) . Esto contrasta con O(|E|) alcanzado por la versión imperativa.

Implementación de tiempo lineal

El artículo en la respuesta de Chris Okasaki ofrece una solución de tiempo lineal en Haskell para encontrar componentes fuertemente conectados. Su implementación se basa en el algoritmo de Kosaraju para encontrar SCC, que básicamente requiere dos recorridos de profundidad primero. La principal contribución del artículo parece ser una implementación DFS de tiempo lineal y perezosa en Haskell.

Lo que requieren para lograr una solución de tiempo lineal es tener un conjunto con O(1) singleton add y membresía de prueba. Este es básicamente el mismo problema que hace que la solución dada en esta respuesta tenga una mayor complejidad que la solución imperativa. Lo resuelven con subprocesos de estado en Haskell, que también se puede hacer en Scala (ver Scalaz). Entonces, si uno está dispuesto a hacer que el código sea bastante complicado, es posible implementar el algoritmo SCC de Tarjan en una versión funcional O(|E|) .