Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save Hendekagon/3d582703fbe50c1435b1c95cbf3aac05 to your computer and use it in GitHub Desktop.
Save Hendekagon/3d582703fbe50c1435b1c95cbf3aac05 to your computer and use it in GitHub Desktop.
Slow LCA
(defn lca
"Last common ancestor"
[db name1 name2]
(d/q '[
:find [(pull ?anc [:db/id :name]) ...]
:in $ % ?name1 ?name2
:where
(?node1 :name ?name1)
(?node2 :name ?name2)
(anc ?anc1 ?node1)
(anc ?anc2 ?node2)
[(not= ?anc1 ?anc2)]
(parent ?anc ?anc1)
(parent ?anc ?anc2)
(?anc :type :variable)
]
@db
'[
[ (parent ?par ?child)
(?par :children ?child)]
[ (anc ?par ?child)
(?par :children ?child)]
[ (anc ?anc ?child)
(?par :children ?child)
(anc ?anc ?par)]
]
name1
name2))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment