r11167: added cdist fn

[umlisp.git] / class-support.lisp

diff --git a/class-support.lisp b/class-support.lisp
index 92b39aab617f3a7549c0ed5f587cc1eff0078377..1d3f96d0902ba0a5f909812b154af04f8d9948c8 100644 (file)
--- a/class-support.lisp
+++ b/class-support.lisp
@@ -336,27 +336,105 @@
          "Other"))))
 
 
-(defun ucon-parents (con &key sab include-rb)
-  (ucon-ancestors con :sab sab :include-rb include-rb 
-                  :single-level t))
+(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 sorted-ancestor-cuis (anc)
+  (sort (remove-duplicates (map 'list 'cui (flatten anc))) #'<))
+
+(defun shared-cuis (a1 a2)
+  (let ((cl1 (sorted-ancestor-cuis a1))
+        (cl2 (sorted-ancestor-cuis a2))
+        (shared nil))
+    (dolist (c1 cl1 (nreverse shared))
+      (dolist (c2 cl2)
+        (cond
+         ((eql c1 c2)
+          (push c1 shared))
+         ((> c2 c1)
+          (return)))))))
+
+(defun cdist-ancestors (anc1 anc2)
+  (let ((shareds (shared-cuis anc1 anc2)))
+    (let ((min most-positive-fixnum)
+          (cui-min nil))
+      (declare (fixnum min))
+      (dolist (shared shareds)
+        (let* ((d1 (ancestor-distance shared anc1))
+               (d2 (ancestor-distance shared anc2))
+               (dtotal (+ d1 d2)))
+          (declare (fixnum d1 d2 dtotal))
+          (when (< dtotal min)
+            (setq min dtotal
+                  cui-min shared))))
+      (values min cui-min))))
+
+(defun cdist (c1 c2 &key sab include-rb)
+  (let* ((anc1 (ucon-ancestors c1 :sab sab :include-rb include-rb))
+         (anc2 (ucon-ancestors c2 :sab sab :include-rb include-rb)))
+    (multiple-value-bind (min cui)
+        (cdist-ancestors anc1 anc2)
+      (if cui
+          (values min cui)
+        (values nil nil)))))
+               
+
+(defun ancestor-distance (cui ancestors &key (distance 0))
+  (cond
+   ((null ancestors)
+    nil)
+   ((atom ancestors)
+    (when (eql cui (cui ancestors))
+      distance))
+   ((atom (car ancestors))
+    (if (eql cui (cui (car ancestors)))
+        distance
+      (ancestor-distance cui (cdr ancestors) :distance distance)))
+   (t
+    (let ((min most-positive-fixnum))
+      (dolist (a ancestors)
+        (let ((d (ancestor-distance cui a :distance (1+ distance))))
+          (when (and d (< d min))
+            (setq min d))))
+      (when (< min most-positive-fixnum)
+        min)))))
 
-(defun ucon-ancestors (ucon &key sab single-level include-rb)
+    
+        
+(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)))
+
 
 (defgeneric cxt-ancestors (obj))
 (defmethod cxt-ancestors ((con ucon))
@@ -395,7 +473,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)))