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

[guilhelm savin <guilhelm.savin AT gmail.com>]

Well, MultiGraph extends AdjacencyListGraph, so nodes are also stored in a map.

About your first solution, this will not improve your complexity since ID -> INDEX -> NODE will be the same complexity (and maybe worst) than ID -> NODE. Problem is the mapping, no matter if it is between id and index or between id and node.

How huge is your graph ? Is it a static graph ? In this case index of nodes will be constant.

2013/12/4 <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?

--
Guilhelm Savin
PhD Student of Computer Science

LITIS, University of Le Havre
\/\/\/\/\/\/

http://gsavin.lewub.org

http://d3-project.org
http://iscn.univ-lehavre.fr
http://graphstream-project.org
/\/\/\/\/\/\