Re: Re: Complexity of method Graph::getNode(String id)

[<simone.davico AT usi.ch>]

Hi Guilhelm,

thank you for your quick answer! The actual implementation I'm using is a
Multigraph. 

The fact is that I can't retrieve a node by index, as I can only compute the 
id
of the node I want to retrieve.

The first solution that is coming to my mind right now to ensure constant
retrieval is to keep an additional mapping ID -> INDEX, so that I can first
retrieve the index of the node by its string ID, and then retrieve the node in
the graph by means of its index. 

If I understood well how it is implemented, this would ensure a two steps
retrieval, but both steps would be constant, right? In this way I could avoid
the O(n) worst case for getNode(String id).

What do you think?