GraphStream Users

Archives de la liste Aide

Re: 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: Re: Complexity of method Graph::getNode(String id)
  • Date: Wed, 4 Dec 2013 12:15:44 +0100

You can easily manipulate a big graph of about 1 million nodes in such that the access time will not be significant. But it depends of your needs of course : nodes count, and access count.
I make some benchmark on my laptop (2.60GHz CPU) over a 1million nodes graph, and the average access time, for one node, is about 1µs, vs. 3ns with indexes.

2013/12/4 <simone.davico AT>
You're right, it's a stupid idea.

My problem is that the graph is static, but when I have to retrieve a node I
don't know what the index of the node is, I only know what is its ID in the
case that the node is present.

The graph could be very huge, as I am performing instrumentation of Java
bytecode, and the nodes are representing methods. For reasons I'm not
explaining because it would take too long, it could be possible that some
methods I encounter are not in the graph, so before taking action I have to
ensure that they are by calling getNode(methodID), where ID is a unique String
based on the method signature.

Honestly I can't think of a way of knowing in advance what the corresponding
index for my ID would be, so I'm probably forced to keep complexity O(n).

Guilhelm Savin
PhD Student of Computer Science

Archives gérées par MHonArc 2.6.16.

Top of page