Support arbitrary node & edge ID ?

[sidml]

In the current codebase, we are making an implicit assumption that the user supplied id will be unsigned long. However, this mayn't be always true because the user may want to use strings as user-ids for convenience.
@ZigRazor What do you think about extending support to arbitrary ids ?
One possible way to accomplish this can be to map the user given ids to an internal unsigned long representation & do the processing. While returning the result, we can again translate it to the user id.

[ZigRazor]

Is a good idea, but how do you think to generalize this?

Maybe is more useful to provide an interface where the Graph class decide the id of the node and of the edge map with the original one, but how we can manage the duplicate?

I think the name of a node can be an attribute of the data contained in the node.

Another idea is to let the user the possibilibily to get a free id for the node, with only the graph that will contains it.

I think we should do more brainstorming on this!

[sidml]

BTW the reason I proposed supporting this is because I noticed that people are using string names on this dataset. Many other datasets are available here.
I felt that our current csv/tsv reader wouldn't work with these datasets mostly because of the unsigned long assumption. (feel free to correct me)

[ZigRazor]

ok, i think we can add this features for this kind of graph, can you develop this?
I think the mapping between the string and node id can be good, as said by you.
Or you think add a string field in the node can be more useful?
Are you able to define a costrctor for the node that create a unique id from a string? And all the interface needed by this features?
I think an hash function with a 512 bit ( 64 byte) result can be a good choice, obviously it has to have a good collision rate! ( SHA-2 can be the right choice )

If you are OK with these things I set a milestone for this, and we can start open the first issue for the implementation.
Let me know!

[ZigRazor]

No, i suggest a sha512 as hash algorithm for this reason, the only implementation that i know is the openSSL one, you know another tested implementation or standard library function?

[sidml]

ok, let's go with openSSL sha512. I will start the implementation.

[sidml]

@ZigRazor
I implemented this and ran into few problems while running tests.
Now, I think just using string as id maybe simpler (if user provides integer we cast it to string). It has two advantages:

• Reduced storage requirement (as we don't have to store useId & id separately)
• No need to re-translate our internal id to the user provided id which will save some computation.
• We also save compute time since we wouldn't be calcualating sha512.

What do you think ?

[ZigRazor]

@sidml
I Think this analysis is not fully corrected!

Reduced storage requirement (as we don't have to store useId & id separately)

it's ok for storage requirements, but i think are not 8 byte, over a string that can take also more than 100 byte, are important.

• No need to re-translate our internal id to the user provided id which will save some computation.

The re-translation of the internal id to the user provide id is done in time log(n) if stored in a map, but in the case we store in the node the userId string, when you retrive a node you already have the userId string

• We also save compute time since we wouldn't be calcualating sha512.

This is true, but think about an operation of equality over a string, or a find over a string, how much cost?, i think 1 time per node sha512 is not so much in term of computation, and anyway, in the major case it has done one time at the load of the graph!

[sidml]

ok! just wanted you to be aware.
Let me create PR.

[ZigRazor]

I open the Issue for this discussion

[sidml]

@ZigRazor
Now we are supporting string based node & edge id. I was thinking about getId function.

• When the node id provided by user is a unsigned long, output of getId is unsigned long and is equal to the user-provided node id.
• When the node id provided by user is a string, output of getId is still unsigned long obtained by using sha512. So, in this case the output mayn't make sense from the user's perspective (i.e. he willn't recognize the hash value)

So, I was thinking whenever we output the result to the user (when algorithm result contains node id) we should use string type for node Id to take care of both cases. Further in this case we should use getUserId function instead of getId.
What do you think ?

[ZigRazor]

I think we should disable the constructor of node with unsigned long long nodeId, and let the use create the node only with string nodeId. So also the setNodeId should be private. The getNodeId can remain public for other purposes.
If we let the user can set the NodeId we can't guarantee the uniqueness of the nodeId , and this should never happens.

When an output result is returned obviosly should be returned userId. This grant that the nodeId will be the same if the string is the same, this is guaranteed by the SHA512 Algorithm.

So the aswer is yes, when working with user the library should ever work with userId (String) , when working internally should work with nodeId (unsigned long long ) also for performance reasons.

I open an issue #147 for this!