On 11/05/2015 11:08 AM, Gavin Flower wrote:
> On 06/11/15 04:33, Rob Sargent wrote:
>> On 11/05/2015 04:56 AM, Achilleas Mantzios wrote:
>>> On 04/11/2015 17:53, Rob Sargent wrote:
>>>> On 11/04/2015 03:03 AM, Achilleas Mantzios wrote:
>>>>> Sorry for being kind of late to the party (I was in 2015.PgConf.EU
>>>>> !!), and not having read
>>>>> most of the replies, what we have been successfully doing for this
>>>>> problem for our app
>>>>> is do it this way :
>>>>> parents int[] -- where parents stores the path from the node to
>>>>> the root of the tree
>>>>> and then have those indexes :
>>>>> btree (first(parents))
>>>>> btree (level(parents)) -- length
>>>>> btree (last(parents))
>>>>> gin (parents gin__int_ops) -- the most important
>>>>>
>>>>> This has been described as "genealogical tree" approach, and works
>>>>> very good, IMHO much better
>>>>> than nested sets.
>>>>>
>>>> Is there a more complete description of this approach available?
>>>> By the title one might assume could be applied to populations as
>>>> opposed to phylogeny (the OP's use case). Does it deal with
>>>> consanguinity? Does it perform well going "up" the tree (which is
>>>> of course branched at every level)?
>>>
>>> From here https://en.wikipedia.org/wiki/Phylogenetic_tree I assume
>>> that phylogenetic trees are normal
>>> trees, and I see no reason why not be modeled with the genealogical
>>> approach described. The earliest paper
>>> I based my work on was :
>>> https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&ved=0CCUQFjABahUKEwiR6auUlvnIAhXGvhQKHVyDA-s&url=https%3A%2F%2Fdownload.samba.org%2Fpub%2Funpacked%2Fldb%2Fldb_sqlite3%2Ftrees.ps&usg=AFQjCNEktJsibP435MBki5cdGmO_CzKmwg&sig2=I9yC_tpyeWrEueDJTXbyAA&bvm=bv.106674449,d.d24&cad=rja
>>>
>>>
>>> Finding the root is O(1). Going "up" the tree or finding common
>>> ancestry is reduced to the problem
>>> of finding overlap/intersections/contains/contained between
>>> postgresql arrays.
>>>
>>> The indexes, functions and operators provided by contrib/intarray
>>> were a basic element for the success of this
>>> approach.
>>>
>> Going "up" a genealogy to me means getting two parents, four
>> grandparents, 8 great grandparents etc. On a good day, at least when
>> there are no loops. This isn't, to my understanding, how phylogeny
>> works (but my genetics degree was thirty year ago) so perhaps I'm
>> still confused by the titles used. And certainly not to say that
>> your approach isn't what the OP really needs!
>>
>>
> You're actually going 'DOWN' the tree, in terms of how trees are used
> in computer science & graph theory!
>
> See http://www.mathcove.net/petersen/lessons/get-lesson?les=32
>
>
> Cheers,
> Gavin
>
>
Fine. Be that way :) Still the question of loops/consanguinity?