Как реализовать DFS с неизменяемыми типами данных - PullRequest
Новая
       26

Как реализовать DFS с неизменяемыми типами данных

8 голосов
/ 29 марта 2011

Я пытаюсь найти изящный способ обхода графа в стиле Scala, желательно с использованием vals и неизменяемых типов данных.

Учитывая следующий график, 

val graph = Map(0 -> Set(1),
                1 -> Set(2),
                2 -> Set(0, 3, 4),
                3 -> Set(),
                4 -> Set(3))

IХотелось бы, чтобы вывод был первым проходом глубины, начинающимся в данном узле.Например, начиная с 1, должно получиться, например, 1 2 3 0 4.

Я не могу найти хороший способ сделать это без изменяемых коллекций или переменных.Любая помощь будет оценена.

Ответы [ 7 ]

8 голосов
/ 30 марта 2011

Хвост Рекурсивное решение: 

  def traverse(graph: Map[Int, Set[Int]], start: Int): List[Int] = {
    def childrenNotVisited(parent: Int, visited: List[Int]) =
      graph(parent) filter (x => !visited.contains(x))

    @annotation.tailrec
    def loop(stack: Set[Int], visited: List[Int]): List[Int] = {
      if (stack isEmpty) visited
      else loop(childrenNotVisited(stack.head, visited) ++ stack.tail, 
        stack.head :: visited)
    }
    loop(Set(start), Nil) reverse
  }
4 голосов
/ 29 марта 2011

Мне кажется, это один из вариантов: 

graph.foldLeft((List[Int](), 1)){
  (s, e) => if (e._2.size == 0) (0 :: s._1, s._2) else (s._2 :: s._1, (s._2 + 1))
}._1.reverse

Обновлено : это расширенная версия.Здесь я сворачиваю влево элементы карты, начиная с кортежа из пустого списка и числа 1. Для каждого элемента я проверяю размер графика и соответственно создаю новый кортеж.Полученный список выходит в обратном порядке. 

val init = (List[Int](), 1)
val (result, _) = graph.foldLeft(init) {
  (s, elem) => 
    val (stack, count) = s
    if (elem._2.size == 0) 
      (0 :: stack, count) 
    else 
      (count :: stack, count + 1)
}
result.reverse
2 голосов
/ 29 марта 2011

Вот рекурсивное решение (надеюсь, я правильно понял ваши требования): 

def traverse(graph: Map[Int, Set[Int]], node: Int, visited: Set[Int] = Set()): List[Int] = 
    List(node) ++ (graph(node) -- visited flatMap(traverse(graph, _, visited + node)))

traverse(graph, 1)

Также обратите внимание, что эта функция НЕ с хвостовой рекурсией.

1 голос
/ 19 августа 2017

Не знаю, ищете ли вы ответ через 6 лет, но вот он:)

Он также возвращает топологический порядок и цикличность графика: - 

case class Node(label: Int)
    case class Graph(adj: Map[Node, Set[Node]]) {
      case class DfsState(discovered: Set[Node] = Set(), activeNodes: Set[Node] = Set(), tsOrder: List[Node] = List(),
                          isCylic: Boolean = false)

      def dfs: (List[Node], Boolean) = {
        def dfsVisit(currState: DfsState, src: Node): DfsState = {
          val newState = currState.copy(discovered = currState.discovered + src, activeNodes = currState.activeNodes + src,
            isCylic = currState.isCylic || adj(src).exists(currState.activeNodes))

          val finalState = adj(src).filterNot(newState.discovered).foldLeft(newState)(dfsVisit(_, _))
          finalState.copy(tsOrder = src :: finalState.tsOrder, activeNodes = finalState.activeNodes - src)
        }

        val stateAfterSearch = adj.keys.foldLeft(DfsState()) {(state, n) => if (state.discovered(n)) state else dfsVisit(state, n)}
        (stateAfterSearch.tsOrder, stateAfterSearch.isCylic)
      }}
0 голосов
/ 27 апреля 2016

Ответ Маримуту Мадасами действительно работает.

Вот его общая версия: 

val graph = Map(0 -> Set(1),
  1 -> Set(2),
  2 -> Set(0, 3, 4),
  3 -> Set[Int](),
  4 -> Set(3))

def traverse[T](graph: Map[T, Set[T]], start: T): List[T] = {
  def childrenNotVisited(parent: T, visited: List[T]) =
    graph(parent) filter (x => !visited.contains(x))

  @annotation.tailrec
  def loop(stack: Set[T], visited: List[T]): List[T] = {
    if (stack.isEmpty) visited
    else loop(childrenNotVisited(stack.head, visited) ++ stack.tail,
      stack.head :: visited)
  }
  loop(Set(start), Nil).reverse
}

traverse(graph,0)

Примечание. Необходимо убедиться, что экземпляры T правильно реализуют equals и hashcode. Использование классов case с примитивными значениями - это простой способ добраться до него.

0 голосов
/ 20 мая 2014

Тенши,

Я не до конца понял ваше решение, но если я не ошибаюсь, сложность по времени составляет не менее O (| V | ^ 2), поскольку сложность следующей строки равна O (| V|): 

val newResult = result :+ node

А именно, добавление элемента справа от списка.

Более того, код не является хвостовой рекурсивной, что может быть проблемой, если, например, рекурсияглубина ограничена используемой средой.

Следующий код решает несколько проблем, связанных с графами в DFS на ориентированных графах.Это не самый элегантный код, но если я не ошибаюсь, это:

  1. Хвост рекурсивный.
  2. Используются только неизменяемые коллекции (и итераторы для них).
  3. Имеет оптимальное время O (| V | + | E |) и сложность пространства (O (| V |).

Код: 

import scala.annotation.tailrec
import scala.util.Try

/**
 * Created with IntelliJ IDEA.
 * User: mishaelr
 * Date: 5/14/14
 * Time: 5:18 PM
 */
object DirectedGraphTraversals {

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

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

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

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

    exitOrder.foldLeft((Set[Vertex](), List(Set[Vertex]()))){
      case (acc @(visitedAcc, connectedComponentsAcc), vertex) =>
        if(visitedAcc(vertex))
          acc
        else {
          val connectedComponent = dfsRec(DfsNeighbours)(reversedGraph, List(DfsNeighbours(reversedGraph, vertex, visitedAcc, visitedAcc)),
            visitedAcc, visitedAcc,List()).toSet
          (visitedAcc ++ connectedComponent, connectedComponent :: connectedComponentsAcc)
        }
    }._2
  }

  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]): (Vertex, Iterator[Vertex])
  }

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

  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
        (vertex, neighbours.iterator)
    }
  }

  @tailrec
  private def dfsRec[Vertex](neighboursFunc: NeighboursFunc)(graph: Graph[Vertex], toVisit: List[(Vertex, Iterator[Vertex])],
                                                             entered: Set[Vertex], exited: Set[Vertex],
                                                             exitStack: List[Vertex]): List[Vertex] = {
    toVisit match {
      case List() => exitStack
      case (currentVertex, neighbours) :: tl =>
        val filtered = neighbours.filterNot(entered)
        if(filtered.hasNext) {
          val nextNeighbour = filtered.next()
          dfsRec(neighboursFunc)(graph, neighboursFunc(graph, nextNeighbour, entered, exited) :: toVisit,
            entered + nextNeighbour, exited, exitStack)
        } else
          dfsRec(neighboursFunc)(graph, tl, entered, exited + currentVertex, currentVertex :: exitStack)
    }
  }

  @tailrec
  private def graphDfsRec[Vertex](neighboursFunc: NeighboursFunc)(graph: Graph[Vertex], notVisited: Set[Vertex],
                                                                  entered: Set[Vertex], exited: Set[Vertex], order: List[Vertex]): List[Vertex] = {
    if(notVisited.isEmpty)
      order
    else {
      val orderSuffix = dfsRec(neighboursFunc)(graph, List(neighboursFunc(graph, notVisited.head, entered, exited)), entered, exited, List())
      graphDfsRec(neighboursFunc)(graph, notVisited -- orderSuffix, entered ++ orderSuffix, exited ++ 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 A " +  dfs(graph, "A"))
  println("dfs B " +  dfs(graph, "B"))

  println("topologicalSort " +  topologicalSort(graph))

  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)))
}
0 голосов
/ 30 марта 2011

Кажется, что этот вопрос более интересен, чем я думал. Я написал другое рекурсивное решение. Это все еще не хвостовая рекурсия. Я также старался сделать его однострочным, но в этом случае читаемость сильно пострадает, поэтому я решил объявить несколько val с: 

def traverse(graph: Map[Int, Set[Int]], node: Int, result: List[Int] = Nil): List[Int] = {
  val newResult = result :+ node
  val currentEdges = graph(node) -- newResult
  val realEdges = if (currentEdges isEmpty) graph.keySet -- newResult else currentEdges

  (newResult /: realEdges) ((r, n) => if (r contains n) r else traverse(graph, n, r))
}

В моем предыдущем ответе я попытался найти все пути от данного узла в ориентированном графе. Но это было неправильно в соответствии с требованиями. Этот ответ пытается следовать за направленными ребрами, но если он не может, тогда он просто берет какой-то не посещенный узел и продолжает оттуда.

...