Commits

Anonymous committed 4859b22

Some convenience functions and stuff.

Comments (0)

Files changed (3)

 	   #:dijkstra-spanning-tree #:map-graph #:edge #:graph
 	   #:standard-graph #:contract-edge #:subdivide-edge
 	   #:make-standard-graph #:add-nodes #:rem-nodes
-	   #:replace-ends #:make-edge))
+	   #:replace-ends #:make-edge #:add-edges))

source/graph/graph.lisp

 (defgeneric edges (graph)
   (:documentation "Returns the set of all edges in GRAPH."))
 
+(defmethod empty? ((collection graph))
+  (empty? (nodes collection)))
+
 (defgeneric connected? (graph)
   (:documentation "Returns T if there is a path from any node in GRAPH
   to any other node. Returns NIL otherwise."))
 (defgeneric add-edge (graph node1 node2 &rest options &key
 			    &allow-other-keys))
 
+(defgeneric add-edges (graph source targets &rest options &key
+			     &allow-other-keys)
+  (:method ((graph graph)
+	    source (targets null)
+	    &rest options &key &allow-other-keys)
+    (declare (ignore source targets options))
+    graph)
+  (:method ((graph graph)
+	    source (targets cons)
+	    &rest options &key &allow-other-keys)
+    (apply #'add-edges
+	   (apply #'add-edge
+		  graph source (car targets)
+		  options)
+	   source (cdr targets)
+	   options)))
+
 (defgeneric find-edges (graph &rest options &key source target
 			      &allow-other-keys)
   (:documentation "Returns the set of all edges in GRAPH that
 
 (defgeneric graph-cross-product (graph1 graph2))
 
+(defgeneric depth-first-search (graph source target &optional
+				      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
+  depth first search."))
+
+(defgeneric breadth-first-search (graph source target &optional
+					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."))
+
 (defgeneric normal-spanning-tree (graph root &optional predicate)
   (:documentation "Returns a normal spanning tree of GRAPH with root
   ROOT."))

source/graph/standard-graph.lisp

+
 (in-package #:fgraph)
 
 (defclass standard-graph (graph)