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

[Tamas Nepusz]

igraph_get_shortest_paths() runs in O(|V|+|E|) time where |V| is the number of
vertices and |E| is the number of edges. FWIW, the time complexities of the
functions in igraph's C core are included in the documentation:

http://igraph.org/c/doc/igraph-Structural.html#igraph_get_shortest_path

Since the wrapper functions in the Python layer usually do nothing else but
a straightforward conversion between Python data types and C data types, it is
safe to assume that in most cases the time complexity of the Python wrapper is
the same as the time complexity of the underlying C function.

T.

On 01/05, Ahmed Abdeen Hamed wrote:
> Great to receive this clarification, thank you!
> 
> If I now call the get_shortest_paths(id_a, id_b), from within the
> algorithm, to find all shortest paths. What is the runtime analysis for
> this one? I found in this 2 years old publication that it can be done in
> O(n^2.4) vs O(n^3) ["http://www.utdallas.edu/~edsha/papers/bin/ISCA03.pdf";].
> Have you guys done this with better runtime? or I should report O(n^2.4) as
> the official runtime?
> 
> Thanks again :-)
> 
> 
> -Ahmed
> 
> 
> 
> 
> On Mon, Jan 5, 2015 at 4:43 PM, Tamas Nepusz <address@hidden> wrote:
> 
> > > 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")?
> > Same as a lookup in a Python dictionary. According to the Python wiki,
> > lookups
> > are O(1) on average in a Python dictionary, although it could be O(n)
> > amortized
> > worst case (but you shouldn't need to worry about this):
> >
> > https://wiki.python.org/moin/TimeComplexity
> >
> > However, I wouldn't fret about that too much if you are just describing
> > a generic algorithm -- the point is that you _could_ do a name-to-index
> > lookup
> > in O(1) on average if you use a hash table, even if the particular Python
> > dictionary implementation does not use a hash table. So, in your
> > publication,
> > you could simply say that name-to-index lookups can be done in O(1) without
> > mentioning that igraph _happens_ to use a Python dict for this. If I were
> > lazy
> > and did not implement this in the Python interface, it would not make your
> > algorithm any worse, although it would make the _implementation_ of your
> > algorithm worse of course.
> >
> > All the best,
> > Tamas
> >
> > _______________________________________________
> > igraph-help mailing list
> > address@hidden
> > https://lists.nongnu.org/mailman/listinfo/igraph-help
> >

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


-- 
T.