Quick and hacky tree isomorphism testing

For twinql's test suite, I needed a way to compare two Lisp trees. equal does this just fine if this trees only contain things that actually are equal; symbols, say. It doesn't work so well if the trees contain bnodes, because I want those bnodes to be compared in a special way*.

Two minutes of quick hackery later…

 (defun graph-isomorphic (g1 g2 bnode-equivs)
  "Returns true if the graphs are identical, 
   barring bnode identities."
  (declare (type list g1 g2)
           (type hash-table bnode-equivs))
  (let ((head-1 (first g1))
        (head-2 (first g2)))
    (and (or (eq head-1 head-2)
             ;; If we come across a bnode...
             (cond ((and (typep head-1 'wilbur::node)
                         (null (node-uri head-1)))
                    ;; If it's the same as the first one
                    ;; it was compared to...
                    (if (gethash head-1 bnode-equivs)
                      (eq (gethash head-1 bnode-equivs) 
                          head-2)
                      ;; Otherwise, record for next time.
                      (setf (gethash head-1 bnode-equivs) 
                            head-2)))
                   ((consp head-1)
                    (graph-isomorphic 
                      head-1 head-2 bnode-equivs))))
         ;; End the recursion.
         (if (null head-1)
           (null head-2)
           (graph-isomorphic 
             (cdr g1) (cdr g2) bnode-equivs)))))

Another nasty parser test case, too:

(parse-sparql 
  "ASK 
  { ?b ?c ?d .
    { ?e ?f ?g . } 
    UNION 
    { { ?h ?i ?j }
      UNION 
      { { ?k ?l ?m ; ?n ?o .  } 
        UNION 
        { ?p ?q ?r } 
      } 
    }
  }")
'(sparql
   :ask :where
   '(graph-pattern
      (triple |b| |c| |d|)
      (union
        (graph-pattern
          (triple |e| |f| |g|))
        (graph-pattern
          (union
            (graph-pattern
              (triple |h| |i| |j|))
            (graph-pattern
              (union
                (graph-pattern
                  (triple |k| |l| |m|)
                  (triple |k| |n| |o|))
                (graph-pattern
                  (triple |p| |q| |r|)))))))))

* Two bnodes should successfully compare if all of the bnodes in one tree have a corresponding node in the other; they don't need to be the same node, just consistent.

Posted at 2006-02-24 14:04:32 by Richard • Link to Quick and hacky tr…
Comments, trackbacks.

Inexplicable failures to carry ideas to their conclusions

“If everybody would agree that their current reality is A reality, and that what we essentially share is our capacity for constructing a reality, then perhaps we could all agree on a meta-agreement for computing a reality that would mean survival and dignity for everyone on the planet, rather than each group being sold on a particular way of doing things.”

Francisco J. Varela, Centre for Research in Applied Epistemology, École Polytechnique, Paris

Does anyone else see the fundamental flaw in this statement? (From Moleskinerie.)

Posted at 2006-02-24 11:02:38 by Richard • Link to Inexplicable failu…
Comments, trackbacks.