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

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

Hi Simone,

You have several ways to access a node :

1. by it's id, Graph::getNode(String). Its complexity depends of the Graph implementation but with AdjacencyListGraph, it's linked to the complexity of HashMap::get(String). So the worst case is O(n), and the better one is O(1) ;

2. you can access nodes by their index. Indexes may vary over time, so it should be used locally. In this case, access is done through an array, so you have a constant complexity of O(1) to access one node. This allows to do something like that :

for (int i=0; i<g.getNodeCount(); i++)
  g.getNode(i);

We are opened to any suggestion that may improve this behavior !

Regards

Guilhelm

2013/12/4 <simone.davico AT usi.ch>

Hello everyone,

I was wondering what is the complexity of the method Graph::getNode(String id).
What is used to retrieve the node in the graph? Is it implemented as linear
search? Binary Search? Or maybe it uses a Map and allows constant time
retrieval?

This is very critical for the project I'm working on, as I could find myself in
the situation of handling a huge quantity of nodes and I have to know if calls
to this method are computationally expensive.

Thank you for your help!

Simone

--
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
/\/\/\/\/\/\