1. thomas_bartscher
  2. cl-fgraph

Commits

Thomas Bartscher  committed c82ffb4

Documentation strings and some generic functions added.
SPANNING-TREE renamed to NORMAL-SPANNING-TREE.
BREADTH-SPANNING-TREE and TREE? generic functions added.

  • Participants
  • Parent commits 82a0d4e
  • Branches dev

Comments (0)

Files changed (1)

File source/graph/graph.lisp

View file
  • Ignore whitespace
 (defclass graph ()
   ())
 
-(defgeneric nodes (graph))
+(defgeneric nodes (graph)
+  (:documentation "Returns the set of all nodes in GRAPH."))
 
-(defgeneric edges (graph))
+(defgeneric edges (graph)
+  (:documentation "Returns the set of all edges in GRAPH."))
 
-(defgeneric connected? (graph))
+(defgeneric connected? (graph)
+  (:documentation "Returns T if there is a path from any node in GRAPH
+  to any other node. Returns NIL otherwise."))
 
 (defgeneric complete? (graph)
+  (:documentation "Returns T if there is an edge for any two nodes in
+  GRAPH. Returns NIL otherwise.")
   (:method ((graph graph))
     (= (size (edges graph))
        (let ((n (size (nodes graph))))
 	 (* n (1- n)
 	    1/2)))))
 
+(defgeneric tree? (graph)
+  (:documentation "Returns T if GRAPH is connected and contains no
+  cycles."))
+
 (defgeneric make-graph-edge (graph source target &rest options &key
-				   &allow-other-keys))
+				   &allow-other-keys)
+  (:documentation "Returns an edge between nodes SOURCE and TARGET of
+  the edge type used by GRAPH with specified options. SOURCE and
+  TARGET need not be in GRAPH."))
 
 (defgeneric add-node (graph node))
 
 
 (defgeneric find-edges (graph &rest options &key source target
 			      &allow-other-keys)
+  (:documentation "Returns the set of all edges in GRAPH that
+  satisifies OPTIONS.")
   (:method ((graph graph)
 	    &rest options &key source target &allow-other-keys)
     (declare (ignore source target))
 	graph)))
 
 (defgeneric incident? (graph node1 node2)
+  (:documentation "Returns T if NODE1 and NODE2 are connected by an
+  edge in GRAPH. Returns NIL otherwise.")
   (:method ((graph graph)
 	    node1 node2)
     (not (and (empty? (find-edges graph
 
 (defgeneric neighbours (graph node &rest options &key
 			      &allow-other-keys)
+  (:documentation "Returns the set of all nodes N for which there is
+  an edge from NODE to N in GRAPH satisfying OPTIONS.")
   (:method ((graph graph)
 	    node &rest options &key &allow-other-keys)
     (image (lambda (edge)
 		  :source node
 		  options))))
 
-(defgeneric graph-union (graph1 graph2))
+(defgeneric graph-union (graph1 graph2)
+  (:documentation "Returns the union of GRAPH1 and GRAPH2."))
 
 (defmethod union ((set-or-bag1 graph)
 		  (set-or-bag2 graph)
   (declare (ignore test test-not))
   (graph-union set-or-bag1 set-or-bag2))
 
-(defgeneric graph-intersection (graph1 graph2))
+(defgeneric graph-intersection (graph1 graph2)
+  (:documentation "Returns the intersection of GRAPH1 and GRAPH2."))
 
 (defmethod intersection ((set-or-bag1 graph)
 			 (set-or-bag2 graph)
 
 (defgeneric graph-cross-product (graph1 graph2))
 
-(defgeneric spanning-tree (graph root))
+(defgeneric normal-spanning-tree (graph root &optional predicate)
+  (:documentation "Returns a normal spanning tree of GRAPH with root
+  ROOT."))
 
-(defgeneric graph-complement (graph))
+(defgeneric breadth-spanning-tree (graph root &optional predicate)
+  (:documentation "Returns a spanning tree of GRAPH obtained by doing
+  a breadth first traversal of GRAPH starting at ROOT."))
 
-;;; LEAF-ORDER should be a function of 4 arguments (NODE1 EDGE1 NODE2
-;;; EDGE2) and should return a boolean. This function is used to sort
-;;; the neighbours of root
+#|
+;;; Problem: How to combine edges? When using a priority queue to do
+;;; dijkstra we need to know how far a certain node is from the root
+;;; and not only from its parent.
+(defgeneric dijkstra-spanning-tree (graph root predicate)
+  (:documentation "Returns a spanning tree of GRAPH obtained by doing
+  a traversal as in dijkstras algorithm starting at ROOT. PREDICATE
+  should be a function from two edges to a boolean and should return T
+  if the first edge is 'shorter' than the second edge and NIL
+  otherwise."))|#
+
+(defgeneric graph-complement (graph)
+  (:documentation "Returns the graph with all nodes of GRAPH so that
+  for any nodes N1 and N2 there is an edge from N1 to N2 in the
+  resulting graph if there is no edge from N1 to N2 in GRAPH."))
+
 (defgeneric contract-graph (graph op root &key start leaf
 				  child-order)
+  ;; CHILD-ORDER should be a function of 4 arguments (NODE1 EDGE1
+  ;; NODE2 EDGE2) and should return a boolean. This function is used
+  ;; to sort the neighbours of root
   (:method ((graph graph)
 	    (op function)
 	    root &key start leaf (child-order (constantly t)))