Commits

Anonymous committed e568b05

BREADTH-FIRST-SEARCH method for GRAPH class implemented.

TODO: Make DEPTH-FIRST-SEARCH return sequence.

  • Participants
  • Parent commits 039fbc0
  • Branches dev

Comments (0)

Files changed (2)

        ))
      (:module
       "graph"
-      :depends-on ("edge")
+      :depends-on ("utility" "edge")
       :components
       ((:file "graph")
        (:file "standard-graph"

File source/graph/graph.lisp

 					predicate)
   (:documentation "Returns a path (if there is one) from SOURCE to
   TARGET in GRAPH and NIL of there is none. The path is found via
-  breadth first search."))
+  breadth first search.")
+  (:method ((graph graph)
+	    source target &optional (predicate (constantly t)))
+    (when (and (contains-node? graph source)
+	       (contains-node? graph target))
+      (let ((paths (sort (image (lambda (n)
+				  (seq n))
+				(neighbours graph source))
+			 predicate))
+	    (visited (set source)))
+	(if (equal? source target)
+	    (seq source)
+	    (loop do
+		 (if (empty? paths)
+		     (return-from breadth-first-search
+		       nil)
+		     (let* ((path (lookup paths 0))
+			    (end (last path)))
+		       (if (equal? end target)
+			   (return-from breadth-first-search
+			     (concat (seq source)
+				     path))
+			   (setf
+			    paths
+			    (concat (subseq paths 1)
+				    (image
+				     (lambda (n)
+				       (concat path (seq n)))
+				     (sort (set-difference (neighbours
+							    graph
+							    end)
+							   visited)
+					   predicate)))
+			    visited (with visited end)))))))))))
 
 (defgeneric normal-spanning-tree (graph root &optional predicate)
   (:documentation "Returns a normal spanning tree of GRAPH with root