Trayectoria de gráfico en Scala

Question

Implementaciones de cruce de gráfico (DFS y BFS) Sé usar mutable conjunto de vértices "visitados". ¿Cómo los implementaría con solo estructuras de datos inmutables?

Vi this question. Ahora me pregunto si también hay otras soluciones

Answer 1

Aquí es una manera de hacerlo:

def traverse[A](graph : Map[A,Set[A]], toVisit : Seq[A], visited : Set[A]) : Seq[A] = { 
    if(toVisit.isEmpty) { 
    Seq.empty 
    } else { 
    val next = toVisit.head 
    val succ = (graph(next) -- visited -- toVisit).toSeq 
    // DFS : 
    // next +: traverse(graph, sucC++ toVisit.tail, visited + next) 
    // BFS : 
    next +: traverse(graph, toVisit.tail ++ succ, visited + next) 
    } 
} 

def traverseFrom[A](graph : Map[A,Set[A]], initial : A) = 
    traverse(graph, Seq(initial), Set.empty) 

El truco es simplemente para pasar alrededor de la lista de nodos a visitar (lo que correspondería a su pila o cola en un algoritmo imperativo) y el conjunto de estados visitados.

Si usted está preocupado acerca de la pila de llamadas cada vez mayor con cada llamada recursiva, que hacen que sea recursiva de cola mediante el uso de un argumento extra:

@annotation.tailrec 
def traverseTR[A](graph : Map[A,Set[A]], toVisit : Seq[A], visited : Set[A], accumulator : Seq[A]) : Seq[A] = { 
    if(toVisit.isEmpty) { 
    accumulator 
    } else { 
    val next = toVisit.head 
    val succ = (graph(next) -- visited -- toVisit).toSeq 
    // DFS : 
    //traverseTR(graph, sucC++ toVisit.tail, visited + next, accumulator :+ next) 
    // BFS : 
    traverseTR(graph, toVisit.tail ++ succ, visited + next, accumulator :+ next) 
    } 
} 

def traverseFrom[A](graph : Map[A,Set[A]], initial : A) = 
    traverseTR(graph, Seq(initial), Set.empty, Seq.empty) 

esto le dará una versión tan eficiente como si escribió usando un loop while.

Answer 2

La solución anterior tiene un par de problemas:

Es ineficiente: (gráfico (al lado) - visitados - tovisit) .toSeq podría ser lineal en el tamaño del gráfico.

La versión DFS es incorrecta, ya que no visitar de acuerdo al orden de DFS: Por ejemplo, si usted tiene la siguiente gráfica:

mapa ("A" -> Set ("B", "D ")," B "-> Set (" C "," D ")," C "-> Set()," D "-> Set (" E ")," E "-> Set())

Entonces si ejecuta DFS a partir de a, el DFS legal órdenes de visita son:

a, B, C, D, E a, B, D, E, C a, D, E, B , C

El algoritmo anterior puede visitar los vértices en el siguiente orden ilegal: A, D, B, C, E

Dado que en la primera iteración se añaden tanto D y B para la secuencia tovisit.

Answer 3

El siguiente código hace algunos cruces de gráficos dirigidos. Se utiliza estructuras de datos inmutables y solamente es recursiva cola, pero con un cierto coste:

La Lista tovisit podría contener muchos duplicados, ya que contiene todos los vértices que planea visitar en el futuro. En el peor de los casos, podríamos agregar un vértice a la lista para casi todos los bordes del gráfico. Por lo tanto, la complejidad de espacio de la recursividad de cola es O (| E | + | V |).

Para gráficos densos, la solución recursiva estándar sin cola cuya complejidad de espacio es O (| V |) es más eficiente, incluso, aunque requiere guardar una pila de llamadas de longitud O (| V |).

Dado que el almacenamiento del gráfico de entrada en sí requiere espacio O (| V | + | E |), el costo anterior puede ser aceptable. Una posible forma de mejorar la complejidad del espacio de lo anterior es reemplazar a Visitar con una Lista [Iterador [Vértice]].Dado que los Iteradores se evalúan perezosamente, esto reducirá la complejidad del espacio a O (| V |).

object DirectedGraphTraversals { 

    type Graph[Vertex] = Map[Vertex, Set[Vertex]] 

    def dfs[Vertex](graph: Graph[Vertex], initialVertex: Vertex) = 
    dfsRec(DfsNeighbours)(graph, List(initialVertex), Set(), Set(), List()) 

    def topologicalSort[Vertex](graph: Graph[Vertex]) = 
    graphDfsRec(TopologicalSortNeighbours)(graph, graph.keySet, Set(), List()) 

    def stronglyConnectedComponents[Vertex](graph: Graph[Vertex]) = { 
    val exitOrder = graphDfsRec(DfsNeighbours)(graph, graph.keySet, Set(), List()) 
    val reversedGraph = reverse(graph) 

    exitOrder.foldLeft((Set[Vertex](), List(Set[Vertex]()))){ 
     case ((visitedAcc, connectedComponentsAcc), vertex) => 
     val connectedComponent = dfsRec(DfsNeighbours)(reversedGraph, List(vertex), visitedAcc, visitedAcc, List()).toSet 
     (visitedAcC++ connectedComponent, connectedComponent :: connectedComponentsAcc) 
    }._2.filterNot(_.isEmpty) 
    } 

    def reverse[Vertex](graph: Graph[Vertex]) = { 
    val reverseList = for { 
     (vertex, neighbours) <- graph.toList 
     neighbour <- neighbours 
    } yield (neighbour, vertex) 

    reverseList.groupBy(_._1).mapValues(_.map(_._2).toSet) 
    } 

    private sealed trait NeighboursFunc { 
    def apply[Vertex](graph: Graph[Vertex], vertex: Vertex, entered: Set[Vertex], exited: Set[Vertex]):Set[Vertex] 
    } 

    private object DfsNeighbours extends NeighboursFunc { 
    def apply[Vertex](graph: Graph[Vertex], vertex: Vertex, entered: Set[Vertex], exited: Set[Vertex]) = 
     graph.getOrElse(vertex, Set()).filterNot(entered) 
    } 

    private object TopologicalSortNeighbours extends NeighboursFunc { 
    def apply[Vertex](graph: Graph[Vertex], vertex: Vertex, entered: Set[Vertex], exited: Set[Vertex]) = { 
     val neighbours = graph.getOrElse(vertex, Set()) 
     if(neighbours.exists(neighbour => entered(neighbour) && !exited(neighbour))) 
     throw new IllegalArgumentException("The graph is not a DAG, it contains cycles: " + graph) 
     else 
     neighbours.filterNot(entered) 
    } 
    } 

    @tailrec 
    private def dfsRec[Vertex](neighboursFunc: NeighboursFunc)(graph: Graph[Vertex], toVisit: List[Vertex], 
                  entered: Set[Vertex], exited: Set[Vertex], 
                  exitStack: List[Vertex]): List[Vertex] = { 
    toVisit match { 
     case List() => exitStack 
     case hd :: tl => 
     if(exited(hd)) 
      dfsRec(neighboursFunc)(graph, tl, entered, exited, exitStack) 
     else if(entered(hd) && !exited(hd)) 
      dfsRec(neighboursFunc)(graph, tl, entered, exited + hd, hd :: exitStack) 
     else { // not entered yet 
      dfsRec(neighboursFunc)(graph, neighboursFunc(graph, hd, entered, exited) ++: toVisit, entered + hd, exited, exitStack) 
     } 
    } 
    } 

    @tailrec 
    private def graphDfsRec[Vertex](neighboursFunc: NeighboursFunc)(graph: Graph[Vertex], notVisited: Set[Vertex], 
                    visited: Set[Vertex], order: List[Vertex]): List[Vertex] = { 
    if(notVisited.isEmpty) 
     order 
    else { 
     val orderSuffix = dfsRec(neighboursFunc)(graph, List(notVisited.head), visited, visited, List()) 
     graphDfsRec(neighboursFunc)(graph, notVisited -- orderSuffix, visited ++ orderSuffix, orderSuffix ::: order) 
    } 
    } 
} 

object DirectedGraphTraversalsExamples extends App { 
    import DirectedGraphTraversals._ 

    val graph = Map(
    "B" -> Set("D", "C"), 
    "A" -> Set("B", "D"), 
    "D" -> Set("E"), 
    "E" -> Set("C")) 

    //println(dfs(graph, "A")) 
    println("dfs A " + dfs(graph, "A")) 
    println("dfs B " + dfs(graph, "B")) 

    println("topologicalSort " + topologicalSort(graph)) 
    println("dfs B " + dfs(graph, "B")) 

    println("reverse " + reverse(graph)) 
    println("stronglyConnectedComponents graph " + stronglyConnectedComponents(graph)) 

    val graph2 = graph + ("C" -> Set("D")) 
    println("stronglyConnectedComponents graph2 " + stronglyConnectedComponents(graph2)) 
    println("topologicalSort graph2 " + Try(topologicalSort(graph2))) 
}