using unordered_map to implement adjacency list for graph representation

1
votes

I want to implement adjacency list for graph using unordered_map. Selecting unordered_map because it can give me O(1) time to access neighboring vertices by a given vertex. So my idea is to define the unordered_map as below:

using namespace std;

class node {};
class edge {};  
typedef vector<edge*> edges_t;
typedef unordered_map<node*, edges_t*> graph_t;

I use the pointer of class node as the key of unordered_map because using node object directly would require a customized std::hash implementation. The major issue of using pointer is memory management. I need to free the allocated memory explicitly.

Can unique_ptr be used here to ease the memory managment? or any better solution to suggest ?

Thanks !

2
c++c++11unordered-mapadjacency-list
Why not have node contain an edges_t thingy? – n. 1.8e9-where's-my-share m.
@n.m.: you would still need an adjacency map (probably) because edges link two vertices (unless you accept duplication, but it has its own issues). – Matthieu M.
why not using unordered_multimap and ditch the edges_t thingsy entirly – Valerij
@MatthieuM. Does adjacency map let you get rid of duplication? How? – n. 1.8e9-where's-my-share m.
@Valerij Because an edge is not a pair of vertices. – n. 1.8e9-where's-my-share m.

2 Answers

1
votes

Ownership policy is indeed an issue, you have a few possibilities:

  • if a clear owner exists, std::unique_ptr is the best choice (see this example)
  • if there are multiple possible owners, you can either break the symmetry and introduce one or defer to std::shared_ptr (beware of cycles)

Breaking the symmetry can be as simple as introducing a std::deque<node> that will contain the nodes and take pointers inside that container. Likewise, a std::deque<edge> would solve the ownership issue for the edges.

0
votes

In a recent program, in my Graph class,I created a new data type called Map which I defined as:

typedef unordered_map, VertexHash, VertexEquals> Map

where Vertex objects are nodes; Edges objects are an origin Vertex, destination Vertex and double distance; VertexHash is a class or struct with an overloaded ( ) to hash Vertex objects ; and VertexEquals is a class or stuct which determines if two Verrte. Objects are equal used the overloaded ==. Each Graph object has a vector which holds a list of Vertex objects and and a Map variable which holds the graph data.