スカラのトポロジカルソート

Question

スカラーのtopological sortingの素晴らしい実装を探しています。

溶液は安定でなければならない：

• 入力が既にソートされている場合、出力は、アルゴリズムは決定論的であるべきである

• 不変でなければならない（ハッシュコードは影響を及ぼさない）

私はこれを行うことができるライブラリがあると思うが、私はこれに起因する重要な依存関係を追加したくない。

例問題：

case class Node(name: String)(val referenced: Node*) 

val a = Node("a")() 
val b = Node("b")(a) 
val c = Node("c")(a) 
val d = Node("d")(b, c) 
val e = Node("e")(d) 
val f = Node("f")() 

assertEquals("Previous order is kept", 
    Vector(f, a, b, c, d, e), 
    topoSort(Vector(f, a, b, c, d, e))) 

assertEquals(Vector(a, b, c, d, f, e), 
    topoSort(Vector(d, c, b, f, a, e))) 

ここ

順序は、ノードは、プログラミング言語の宣言は、他の宣言を参照すると言った場合、結果の順序は それが有する前まで宣言が使用されないようになるように定義されます宣言されました。

Answer 1

ここは私自身の解決策です。さらに、入力で検出された可能なループを返します。

呼び出し元が訪問者に がノードとコールバックを取得し、参照ノードごとにコールバックを呼び出すため、ノードの形式は固定されていません。

ループのレポート作成が不要な場合は、簡単に削除できます。

import TopologicalSort._ 

def visitor(node: BaseNode, callback: (Node) => Unit): Unit = { 
    node.referenced.foreach(callback) 
} 

assertEquals("Previous order is kept", 
    Vector(f, a, b, c, d, e), 
    topoSort(Vector(f, a, b, c, d, e), visitor).result) 

assertEquals(Vector(a, b, c, d, f, e), 
    topoSort(Vector(d, c, b, f, a, e), visitor).result) 

複雑さにいくつかの考え：これは次のように適用される質問の例では

import scala.collection.mutable 

// Based on https://en.wikipedia.org/wiki/Topological_sorting?oldformat=true#Depth-first_search 
object TopologicalSort { 

    case class Result[T](result: IndexedSeq[T], loops: IndexedSeq[IndexedSeq[T]]) 

    type Visit[T] = (T) => Unit 

    // A visitor is a function that takes a node and a callback. 
    // The visitor calls the callback for each node referenced by the given node. 
    type Visitor[T] = (T, Visit[T]) => Unit 

    def topoSort[T <: AnyRef](input: Iterable[T], visitor: Visitor[T]): Result[T] = { 

    // Buffer, because it is operated in a stack like fashion 
    val temporarilyMarked = mutable.Buffer[T]() 

    val permanentlyMarked = mutable.HashSet[T]() 

    val loopsBuilder = IndexedSeq.newBuilder[IndexedSeq[T]] 

    val resultBuilder = IndexedSeq.newBuilder[T] 

    def visit(node: T): Unit = { 
     if (temporarilyMarked.contains(node)) { 

     val loopStartIndex = temporarilyMarked.indexOf(node) 
     val loop = temporarilyMarked.slice(loopStartIndex, temporarilyMarked.size) 
      .toIndexedSeq 
     loopsBuilder += loop 

     } else if (!permanentlyMarked.contains(node)) { 

     temporarilyMarked += node 

     visitor(node, visit) 

     permanentlyMarked += node 
     temporarilyMarked.remove(temporarilyMarked.size - 1, 1) 
     resultBuilder += node 
     } 
    } 

    for (i <- input) { 
     if (!permanentlyMarked.contains(i)) { 
     visit(i) 
     } 
    } 

    Result(resultBuilder.result(), loopsBuilder.result()) 
    } 
} 

このソリューションの最悪の場合の複雑さは、実際にOを超えています（ n + m）。ノードごとにtemporarilyMarkedアレイがスキャンされるためです。

temporarilyMarkedをたとえばHashSetに置き換えると、漸近的な複雑さが改善されます。

ノード内にマークを直接格納すると真のO（n + m）が達成されますが、それらを外部に格納すると汎用ソリューションの作成が容易になります。

私はパフォーマンステストを実行していませんが、それは非常に深くない限り、大きなグラフであってもtemporarilyMarkedアレイのスキャンは問題ではないと思われます。

Answer 2

グラフが非周期的である場合にのみトポロジカルな順序を返す純粋に機能的な実装です。

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

    def topologicalSort: Option[List[Node]] = dfs match { 
    case (topologicalOrder, false) => Some(topologicalOrder) 
    case _ => None 
    } 
}