This is very good news. Thanks so much!!! -Ahmed
On Tue, Jan 6, 2015 at 7:33 AM, Tamas Nepusz <[email protected]> wrote: > 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 <[email protected]> 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 > > > [email protected] > > > https://lists.nongnu.org/mailman/listinfo/igraph-help > > > > > > _______________________________________________ > > igraph-help mailing list > > [email protected] > > https://lists.nongnu.org/mailman/listinfo/igraph-help > > > -- > T. >
_______________________________________________ igraph-help mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/igraph-help
