Mysterious infinite loop in Clojure

Question

I'm writing a Clojure function to perform a topological sort via depth-first search on a directed graph, and for some inputs it doesn't terminate. It uses loop-recur, but I don't see any lazy sequences used in arguments to recur, which seems to be the most common culprit for infinite loops. I ran the program on paper for the sample inputs below and they all appeared to work fine.

(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

bmaddy · Accepted Answer · 2013-02-16 11:47:57Z

1

When calling recur you're using the first of the current node's neighbors instead of the first of the unvisited neighbors. For node 1 you're always adding node 2 to the stack.

Try this:

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

edited Feb 16, 2013 at 11:47

answered Feb 16, 2013 at 11:41

bmaddy

89510 silver badges18 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

James Over a year ago

That was exactly the problem. At one point I changed neigh from "just unvisited neighbors" to "all the neighbors", and didn't reflect that everywhere else. Many thanks!

Collectives™ on Stack Overflow

Mysterious infinite loop in Clojure

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related