functor PATHSEARCH(
structure G : 
      sig eqtype Vertex type Graph 
             val adj : Graph -> Vertex -> Vertex list 
      end
and S:sig type Item type Set
           val empty   : Set
           val member  : Set -> Item -> bool
           val insert  : Item * Set  -> Set
      end
and Q:sig type Item type Queue
           val empty   : Queue
           val isEmpty : Queue -> bool
           val enq     : Item list * Queue -> Queue
           val deq     : Queue -> Item list * Queue
           val menq    : Item list list * Queue -> Queue
      end
   sharing type G.Vertex = S.Item = Q.Item
): sig type Graph and Vertex and VSet
   val path : Graph -> Vertex -> Vertex -> Vertex list
   end
= struct
   type Graph  = G.Graph
   type Vertex = G.Vertex
   type VSet   = S.Set
   exception NoPath

   fun path (g:Graph) (s:Vertex) (f:Vertex) : Vertex list =
   let fun search todo visited = 
        if Q.isEmpty todo then raise NoPath else
            let val ((h::t), xs) = Q.deq todo
             in
                 if h = f then h :: t else
                 if S.member visited h then search xs visited
                 else search 
                        (Q.menq (map (fn y => y::h::t) (G.adj g h), xs))
                        (S.insert (h, visited))
            end
    in 
       search (Q.enq([s], Q.empty)) S.empty
    end
end;