;;; ---------------------------------------------------------------------------
-(defgeneric make-filtered-graph (old-graph test-fn &optional graph-completion-method depth)
+(defgeneric make-filtered-graph (old-graph test-fn &key
+ graph-completion-method depth
+ new-graph)
(:documentation "Takes a GRAPH and a TEST-FN (a single argument function
returning NIL or non-NIL), and filters the graph nodes according to
the test-fn (those that return non-NIL are accepted), returning
(defgeneric complete-links (new-graph old-graph)
(:documentation "Add edges between vertexes in the new-graph for which the matching vertexes in the old-graph have edges. The vertex matching is done using `find-vertex`."))
-(defgeneric subgraph-containing (graph vertex &optional depth)
+(defgeneric subgraph-containing (graph vertex &key)
(:documentation "Returns a new graph that is a subset of `graph` that contains `vertex` and all of the other vertexes that can be reached from vertex by paths of less than or equal of length `depth`. If depth is not specified, then the entire sub-graph reachable from vertex will be returned. [?? Edge weights are always assumed to be one.]"))
;;; ---------------------------------------------------------------------------
(defmethod make-filtered-graph ((old-graph basic-graph)
test-fn
- &optional
+ &key
(graph-completion-method nil)
- (depth nil))
- (let ((new-graph
- (copy-template old-graph)))
- (ecase graph-completion-method
- ((nil
- :complete-links)
- (iterate-vertexes old-graph
- (lambda (vertex)
- (when (funcall test-fn vertex)
- (add-vertex new-graph (value vertex))))))
- ((:complete-closure-nodes-only
- :complete-closure-with-links)
- (let* ((old-graph-vertexes (collect-items old-graph :filter test-fn))
- (closure-vertexes
- (get-transitive-closure old-graph-vertexes depth)))
- (dolist (vertex closure-vertexes)
- (add-vertex new-graph (copy-template vertex))))))
-
- (ecase graph-completion-method
+ (depth nil)
+ (new-graph
+ (copy-template old-graph)))
+ (ecase graph-completion-method
+ ((nil
+ :complete-links)
+ (iterate-vertexes old-graph
+ (lambda (vertex)
+ (when (funcall test-fn vertex)
+ (add-vertex new-graph (value vertex))))))
+ ((:complete-closure-nodes-only
+ :complete-closure-with-links)
+ (let* ((old-graph-vertexes (collect-items old-graph :filter test-fn))
+ (closure-vertexes
+ (get-transitive-closure old-graph-vertexes depth)))
+ (dolist (vertex closure-vertexes)
+ (add-vertex new-graph (copy-template vertex))))))
+ (ecase graph-completion-method
((nil :complete-closure-nodes-only) nil)
((:complete-links
:complete-closure-with-links)
(complete-links new-graph old-graph)))
-
- new-graph))
+ new-graph)
;;; ---------------------------------------------------------------------------
(defmethod subgraph-containing ((graph basic-graph) (vertex basic-vertex)
- &optional (depth nil))
- (make-filtered-graph graph
- #'(lambda (v)
- (equal v vertex))
- :complete-closure-with-links
- depth))
+ &rest args &key (depth nil) (new-graph nil))
+ (declare (ignore depth new-graph))
+ (apply #'make-filtered-graph
+ graph
+ #'(lambda (v)
+ (equal v vertex))
+ :graph-completion-method :complete-closure-with-links
+ args))
;;; ---------------------------------------------------------------------------