r11162: support for map/smap and ucon ancestors

[umlisp.git] / class-support.lisp

diff --git a/class-support.lisp b/class-support.lisp
index 92b39aab617f3a7549c0ed5f587cc1eff0078377..7948dec091732de7c0337687ef34d0f2ca2aa400 100644 (file)
--- a/class-support.lisp
+++ b/class-support.lisp
@@ -336,27 +336,88 @@
          "Other"))))
 
 
-(defun ucon-parents (con &key sab include-rb)
-  (ucon-ancestors con :sab sab :include-rb include-rb 
-                  :single-level t))
-
-(defun ucon-ancestors (ucon &key sab single-level include-rb)
+(defun ucon-parents (ucon &key sab include-rb)
+  (ucon-ancestors ucon :sab sab :include-rb include-rb
+                  :ancestors nil))
+
+(defun is-ucon-in-ancestors (ucon ancestors)
+  (cond
+   ((null ancestors) nil)
+   ((atom ancestors) (eql (cui ucon) (cui ancestors)))
+   ((listp (car ancestors))
+    (or (is-ucon-in-ancestors ucon (car ancestors))
+        (is-ucon-in-ancestors ucon (cdr ancestors))))
+   (t
+    (or (eql (cui ucon) (cui (car ancestors)))
+        (is-ucon-in-ancestors ucon (cdr ancestors))))))
+
+
+(defun ucon-ancestors (ucon &key sab include-rb ancestors)
   "Returns a list of ancestor lists for a concept"
   (let* ((parent-rels (append (filter-urels-by-rel (s#rel ucon) "par")
-                              (when include-rb 
+                              (when include-rb
                                 (filter-urels-by-rel (s#rel ucon) "rb"))))
-        (anc nil))
+         (parents nil))
     (when sab
       (setq parent-rels (delete-if-not
                         (lambda (rel) (string-equal sab (sab rel)))
                         parent-rels)))
-    (dolist (rel parent-rels (nreverse anc))
+    (dolist (rel parent-rels)
       (let ((parent (find-ucon-cui (cui2 rel))))
-       (push
-        (if single-level
-            (list parent)
-          (list* parent (car (ucon-ancestors parent (sab rel) nil))))
-        anc)))))
+        ;; (format t "~S ~S ~S ~S~%" rel ucon parent ancestors)
+        (unless (is-ucon-in-ancestors parent ancestors)
+          (push
+           (list*
+            parent
+            (ucon-ancestors parent :sab (sab rel) :ancestors (append (list parent) ancestors)))
+           parents))))
+    (nreverse parents)))
+
+
+(defun find-minimum-distance (anc1 anc2 &key (distance 0) (minimum 0) path)
+  (cond
+    ((or (null anc1) (null anc2) nil)
+    ((and (atom (car anc1)) (atom (car anc2)))
+     (when (eql (cui ucon1) (cui ucon2))
+       (return-from find-minimum-distance (values distance path)))
+     (incf distance)
+     (when (> distance minimum)
+       (return-from find-minimum-distance nil))
+     (multiple-value-bind (dist1 path1)
+         (find-minimum-distance anc1 (cdr anc2)
+                                :distance distance :minimum minimum
+                                :path (list* anc1 path))
+       (when (and dist1 (< dist1 minimum))
+         (setf minimum dist1
+               path path1)))
+     (multiple-value-bind (dist2 path2)
+         (find-minimum-distance (cdr anc1) anc2
+                                :distance distance :minimum minimum
+                                :path (list* anc2 path))
+       (when (and dist2 (< dist2 minimum))
+         (setf minimum dist2
+               path path2)))
+       (return-from find-minimum-distance (values distance path))
+
+
+           (min2 (find-minimum-distance
+                  (cdr anc1) anc2
+                  :distance distance :minimum minimum
+                  :path (list* anc2 path))))
+
+       (when (and min2 (< min2 minimum))
+         (setf minimum min2
+               path (list* anc2 path)))))
+
+
+  )
+
+(defun ucon-cdist (ucon1 ucon2 &key include-rb sab)
+  "Compute James Cimino's CDist metric"
+  (let ((anc1 (ucon-ancestors ucon1 :include-rb include-rb :sab sab))
+        (anc2 (ucon-ancestors ucon2 :include-rb include-rb :sab sab)))
+    (find-minimum-distance (list ucon1 anc1) (list ucon2 anc2))))
+
 
 (defgeneric cxt-ancestors (obj))
 (defmethod cxt-ancestors ((con ucon))
@@ -395,7 +456,7 @@
 (defun ucon-has-sab (ucon sab)
   (and (find-if (lambda (uso) (string-equal sab (sab uso))) (s#so ucon)) t))
 
-    
+
 #+scl
 (dolist (c '(urank udef usat uso ucxt ustr ulo uterm usty urel ucoc uatx ucon uxw uxnw uxns lexterm labr lagr lcmp lmod lnom lprn lprp lspl ltrm ltyp lwd sdef sstr sstre1 sstre2 usrl))
     (let ((cl (find-class c)))