CODEWITHSUNDEEP
c++hashmap
TheAnonyMoose1234512
TheAnonyMoose1234512

Reputation: 169

Unordered map containing a graph node as the key

I am working on implementing dijsktra's algorithm for traversing a graph and I have hit a small roadblock. 

class Node{

private:
int id = -1;
unordered_map<Node*, int> edges;

};

As you can see each node in the graph contains an int for an id as well as an unordered map containing a node* as the key value and the edge length as the underlying data. The issue i'm having is I do not know what the best way to hash these id's.

Id's will be read in from a file and numbered in order. What is the best way to hash these id's without having many collisions?

EDIT: I currently am just hashing in such a way that returns the id mod edges.size() but I don't believe this to be the best way.

Upvotes: 1

Views: 553

Answers (1)

MSalters
MSalters

Reputation: 179991

Don't even bother with the % edges.size(). The unordered_map itself will already perform a % this -> _Table.size().

Note that for sparsely connected graphs (say < 8 edges/node) a simple std::vector<std::pair<Node*,int>> is probably more efficient.

Upvotes: 1

Related Questions