GraphStream Users

Archives de la liste Aide

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

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

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>
Hi Guilhelm,

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

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

Archives gérées par MHonArc 2.6.16.

Top of page