GraphStream Users

Archives de la liste Aide

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

Chronologique Discussions 
  • From: guilhelm savin <guilhelm.savin AT>
  • To: "graphstream-users AT" <graphstream-users AT>, simone.davico AT
  • Subject: Re: Complexity of method Graph::getNode(String id)
  • Date: Wed, 4 Dec 2013 11:10:08 +0100

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++)

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



2013/12/4 <simone.davico AT>
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

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!


Guilhelm Savin
PhD Student of Computer Science

Archives gérées par MHonArc 2.6.16.

Top of page