私は、できればvalsと不変のデータ型を使用して、グラフScalaスタイルをトラバースするための適切な方法を見つけようとしています。
次のグラフを考えると、
val graph = Map(0 -> Set(1),
1 -> Set(2),
2 -> Set(0, 3, 4),
3 -> Set(),
4 -> Set(3))
出力を、特定のノードで開始する深さ優先走査にします。たとえば、1から始めて、たとえばを生成する必要があります1 2 3 0 4。
可変コレクションまたは変数なしでこれを行うための良い方法を理解できないようです。どんな助けでもいただければ幸いです。
テール再帰ソリューション:
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
}
これは私が推測する1つのバリアントです：
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
これが再帰的な解決策です（あなたの要件を正しく理解していることを願っています）：
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)
また、この関数は末尾再帰ではないことに注意してください。
この質問は、私が当初考えていたよりも複雑なようです。別の再帰的なソリューションを作成しました。それはまだ末尾再帰ではありません。また、ワンライナーにするように努力しましたが、この場合、読みやすさが大幅に低下するため、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))
}
以前の回答では、有向グラフで特定のノードからのすべてのパスを見つけようとしました。しかし、それは要件に従って間違っていました。この回答は有向エッジをたどろうとしますが、それができない場合は、未訪問のノードを取得してそこから続行します。
天使、
私はあなたの解決策を完全には理解していませんが、間違っていなければ、次の行の複雑さは O(|V|) であるため、時間の複雑さは少なくとも O(|V|^2) です。
val newResult = result :+ node
つまり、リストの右側に要素を追加します。
さらに、コードは末尾再帰ではありません。これは、たとえば、使用している環境によって再帰の深さが制限されている場合に問題になる可能性があります。
次のコードは、有向グラフに関するいくつかの DFS 関連のグラフの問題を解決します。これは最も洗練されたコードではありませんが、私が間違っていなければ、次のようになります。
コード：
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)))
}
Marimuthu Madasamyの答えは確かに機能しています。
これがその一般的なバージョンです。
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)
注: のインスタンスがTequals と hashcode を正しく実装していることを確認する必要があります。プリミティブ値を持つケース クラスを使用することは、そこにたどり着くための簡単な方法です。