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

grafo debilmente conexo

Question

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

Answer 1

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.

Answer 2

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|) .

Answer 3

Ver Lazy Depth-First Search y los algoritmos de gráficos lineales en Haskell por David King y John Launchbury. Describe muchos algoritmos de grafos en un estilo funcional, incluyendo SCC.