Re: [Seqan-dev] Inverse of _getId for ESA vertexes?

["Weese, David" <weese@campus.fu-berlin.de>]

Hi John,

_getId is a function from the set of nodes to the smallest possible interval - in the ESA case to [0..2n) for the total number of text characters n. For the ESA that function is more or less one interval boundary of the node's SA interval, so that function is not reversible as you cannot determine the other boundary directly. It would be possible in O(n) time with a scan over the lcp to the left or right for lcp values strictly less the the one at the boundary, but then parentRight is still missing.

However, instead you could store the whole VertexDescriptor in your property map. With that VertexDescriptor you can resume at the corresponding node with a TopDown iterator.

Cheers,
Dave

--
David Weese, Ph.D.              david.weese@fu-berlin.de
Freie Universität Berlin        http://www.inf.fu-berlin.de/
Institut für Informatik         Phone: +49 30 838 75137
Takustraße 9                    Algorithmic Bioinformatics
14195 Berlin                    Room 020

Am 13.11.2013 um 11:03 schrieb John Reid <j.reid@mail.cryst.bbk.ac.uk>:

> I find property maps for ESAs very useful. I can index into a sparse
> data structure using the ID of a vertex in an ESA. However I couldn't
> find any way to reconstruct the vertex from the ID. Is this possible? At
> the moment I have to iterate over the whole ESA again looking to see if
> I have an entry for the ID for each vertex. It would be much more
> efficient for me to iterate over my sparse data structure and be able to
> map IDs back to vertexes/iterators.
> 
> Thanks,
> John.
> 
> _______________________________________________
> seqan-dev mailing list
> seqan-dev@lists.fu-berlin.de
> https://lists.fu-berlin.de/listinfo/seqan-dev

Attachment: smime.p7s
Description: S/MIME cryptographic signature