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
