Re: [igraph] searching by node index: runtime analysis

[Ahmed Abdeen Hamed]

I found some info related to the dictionary lookup: ["https://wiki.python.org/moin/TimeComplexity"]

The worst case scenario is O(n). Does this sound right?

Thanks very much for the help,

-Ahmed

On Mon, Jan 5, 2015 at 4:25 PM, Ahmed Abdeen Hamed <address@hidden> wrote:

Thanks you, Dr. Nepusz!

I did mean the Python implementation yes. If this is the case, what the runtime complexity for 2 vertices if we use g.vs.find("name")? I am asking because I have designed a new algorithm that uses this feature. The runtime analysis is needed for a publication and I am trying to be as accurate as possible.

Thanks again!

-Ahmed

On Mon, Jan 5, 2015 at 4:16 PM, Tamas Nepusz <address@hidden> wrote:

Hi,

> What the runtime analysis for retrieving the index of a node by its name?

It depends. If you are using the C core directly, you are on your own --
looking up a vertex by name would involve scanning the vertices and comparing
their name attribute with the name you are looking for. Or you can implement
your own data structure (e.g., a hash table) to speed up the lookups. If you
are using the Python interface, the situation is a bit better because the
"name" attribute is indexed behind the scenes so looking up a vertex by name
should be as fast as a Python dictionary lookup. (But watch out for a caveat:
g.vs.find("name") is fast but g.vs.find(name="name") is slow; this is a bug
that will be rectified soon). I cannot tell anything about the R interface,
though, because I'm not familiar with its internals.

--
T.

_______________________________________________
igraph-help mailing list
address@hidden
https://lists.nongnu.org/mailman/listinfo/igraph-help