Go API code to find closest common predecessor


#1

This is resurrecting a necro thread from the old list that petered out before an answer for the question was posted.

The original question:

I’m interested in using cayley to find closest common predecessor in
trees or DAGs - this is for evolutionary analysis, so the concrete
entities being queried are biological taxa and the sought entities are
most recent common ancestors.

Illustrative graphs with expected results are here:

A is_parent_of B . 
B is_parent_of C . 
B is_parent_of D . 
D is_parent_of E . 

most recent ancestor of (E, C) -> B

O is_parent_of A . 
A is_parent_of B . 
A is_parent_of C . 
O is_parent_of X . 
X is_parent_of Y . 
Y is_parent_of Z . 
Y is_parent_of C . 
B is_parent_of Z . 

most recent ancestor of (Z, C) -> A and X

O is_parent_of A . 
A is_parent_of C . 
A is_parent_of Z . 
O is_parent_of X . 
X is_parent_of Y . 
Y is_parent_of Z . 
Y is_parent_of C . 

most recent ancestor of (Z, C) -> A

Can someone suggest a reasonable way to achieve this?

And my last query/position:

This is what I have as a basis for thinking about how this would be
implemented, but I have a strong feeling (unfounded in any actual
evidence) that there must be a more efficient way to do it (avoiding the
loop in ancestorsOf).

The DAG case would be essentially the same except that instead of
ancestorsOf and a []string, we’d do a BFT (but I’m thinking there that
calling out to cayley for each step of the BFT is not the most efficient
way of doing things).

http://play.golang.org/p/ZKBnWOsgdT

package main

import (
“fmt”
“log”

    "github.com/google/cayley"
    "github.com/google/cayley/graph"
    "github.com/google/cayley/graph/path"
    "github.com/google/cayley/quad"

)

func main() {
store, err := cayley.NewMemoryGraph()
if err != nil {
log.Fatalln(err)
}

    for _, q := range []quad.Quad{
            {Subject: "A", Predicate: "is_parent_of", Object: "B"},
            {Subject: "B", Predicate: "is_parent_of", Object: "C"},
            {Subject: "B", Predicate: "is_parent_of", Object: "D"},
            {Subject: "D", Predicate: "is_parent_of", Object: "E"},
    } {
            store.AddQuad(q)
    }
    fmt.Println(lca("C", "E", store))

}

func lca(a, b string, store *cayley.Handle) (common string, depth int) {
paths := make(map[string]int)
for d, t := range ancestorsOf(a, store) {
paths[t] = d
}
var (
min = int(^uint(0) >> 1)
lca string
)
for d, t := range ancestorsOf(b, store) {
p, found := paths[t]
p += d
if found && p < min {
min = p
lca = t
}
}
return lca, min
}

func ancestorsOf(a string, store *cayley.Handle) []string {
line := []string{a}
for {
p := path.StartPath(store, a).In(“is_parent_of”)
it := p.BuildIterator()
found := false
for graph.Next(it) {
a = store.NameOf(it.Result())
line = append(line, a)
found = true
break
}
if !found {
return line
}
}
}

What would be the cayley-idiomatic way to do this?


Building a Cayley Cookbook
#2

These seems like a fun one – I will play with it tomorrow, right now on a ticket moving spree!


#3

The pairwise case can be used to build the n-ary case, but it would be nice to be able to find ways to cache work between the searches to improve the performance there.


#4

@kortschak Interesting. Are you asking about general approach or possible optimizations?

Looks a bit similar to a way transitive closure works in @barakmich’s branch.

Regarding optimizations, you should avoid using store.NameOf if possible and compare values returned by iterators directly. Value lookup is not always free (or almost always it is not).

In any case, I think loop will be there. The best way will be to implement a special iterator type for this (in-depth transition via some predicate), but again, I think transitive closure branch does exactly that.


#5

@dennwc I think both. A general approach is worth knowing about, but optimisations are going to be necessary in the long term.

What you’re describing is certainly what I had in mind conceptually. Can you point to Barak’s branch? I don’t see it.


#6

https://github.com/barakmich/cayley/tree/transitive_closure – hidden in his own little toybox of Cayley insanity!


#7

Yes, that does look like a way to walk the path.