longest path through digraph

graph.clj

(ns fun.graph)

(defn unvisited-neighbors [graph node path-so-far]
  (clojure.set/difference
           (get graph node)
           (set path-so-far)))

(defn path-with-node [path new-node]
  (conj path new-node))

(defn longest [sequences]
  (let [nonempty-collection-of-sequences (conj sequences '())]
    (apply max-key count nonempty-collection-of-sequences)))

(defn longest-starting-at
  ([node graph] (longest-starting-at node graph '()))
  ([node graph path-so-far]
   (let [unvisited-neighbors
         (unvisited-neighbors graph node path-so-far)
         best-paths-from-neighbors
         (map
           #(longest-starting-at
              %
              graph
              (path-with-node path-so-far %))
           unvisited-neighbors)
         best-path (longest best-paths-from-neighbors)]
     (path-with-node best-path node))))

(defn longest-path-in [graph]
  (let [longest-paths-from-nodes
        (map #(longest-starting-at % graph) (keys graph))]
    (longest longest-paths-from-nodes)))

graph_spec.clj

(ns fun.graph-spec
  (:require [speclj.core :refer :all]
            [fun.graph :refer :all]))

(describe
  "longest-path"
  (it "finds the longest path starting at a given node"
      (let [graph {:a #{:b :c}
                   :b #{:c :d}
                   :c #{:f :g}
                   :d #{:g :x}
                   :x #{:y}}]
        (should= [:a :b :d :x :y] (longest-starting-at :a graph))))

  (it "finds the longest path in the whole graph"
      (let [graph {:a #{:b :c}
                   :b #{:c :d}
                   :c #{:f :g}
                   :d #{:g :x}
                   :x #{:y}}]
        (should= [:a :b :d :x :y] (longest-path-in graph))
        )
      )
  )