0

有向グラフで深さ優先探索を介してトポロジカルソートを実行するClojure関数を作成していますが、一部の入力では終了しません。loop-recurを使用しますが、recurの引数で使用される遅延シーケンスは見当たりません。これは、無限ループの最も一般的な原因のようです。以下のサンプル入力用にプログラムを紙で実行しましたが、すべて正常に機能しているように見えました。

(require '[clojure.set :as set])

;graph is a hash map, keys are nodes, vals are 
;collections of other nodes that node points to
(defn DFSsort [graph]
  (loop [stack `(~(ffirst graph)),
         visited '()]
    (let [unvisited (set/difference (set (keys graph))
                                    (set visited)),
          node (peek stack), 
          neigh (graph node)]
      (if (empty? stack)
        (if (seq unvisited)
          (recur (conj stack (first unvisited))
                 visited)
          visited) ; return
        (if (seq (set/difference (set neigh) (set visited)))    
          (if (not-any? (partial = (first neigh)) stack)
            (recur (conj stack (first neigh))
                   visited)
            "Cycle detected!") ; abort
          (recur (pop stack)
                 (conj visited node)))))))

(DFSsort {1 [2 3], 2 [3], 3 []})
;=> (1 2 3) 

(DFSsort {1 [2 3], 2 [], 3 []})
;Infinite loop

(DFSsort {1 [2 3], 2 [], 3 [2]})
;Infinite loop
4

1 に答える 1

1

recurを呼び出すときは、訪問されていないネイバーの最初のネイバーではなく、現在のノードのネイバーの最初のネイバーを使用しています。ノード1の場合、常にノード2をスタックに追加します。

これを試して：

(defn DFSsort [graph]
  (loop [stack `(~(ffirst graph)),
         visited '()]
    (println stack visited)
    (let [unvisited (set/difference (set (keys graph))
                                    (set visited)),
          node (peek stack), 
          neigh (graph node)
          unseen-neigh (seq (set/difference (set neigh) (set visited)))]
      (if (empty? stack)
        (if (seq unvisited)
          (recur (conj stack (first unvisited))
                 visited)
          visited) ; return
        (if unseen-neigh
          (if (not-any? (partial = (first unseen-neigh)) stack)
            (recur (conj stack (first unseen-neigh))
                   visited)
            "Cycle detected!") ; abort
          (recur (pop stack)
                 (conj visited node)))))))
于 2013-02-16T11:41:47.900 に答える