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

[Stefan Balev <stefan.balev AT gmail.com>]

Hi Simone,

An additional mapping is definitely not a good idea. All current graph implementations use internal HashMaps to retrieve nodes/edges by their ids. As you can see here, getNode(id) is implemented as a call to get(id) of the corresponding map.

The performance of a HashMap depends on many factors, including its capacity and load factor (more details here). We use the default load factor of 0.75. Default settings do a good job most of the time. However, If you are unhappy with node retrieving speed, I suggest you to play with the initialNodeCapacity parameter of this constructor. It affects the initial capacity of the HashMap. If you set it let's say twice as big as the expected number of nodes, you will have almost no key collisions, but the trade-off is more memory consumption.

Regards,

--

Stefan

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