I am using an adjacency list to store a graph. Since I am using adjacency list, I cannot access edge weight of a graph in constant time. So, I wonder which EXTRA data structure to use only to story edges indexed by the two nodes u and v?
Currently, I am trying with map<pair<int, int>, int> but it has log (N) complexity and unordered_map does not have a policy for pairs. I know that, an edge weight is independent of the order of {u,v}, but I am not able to use this feature anyhow.
Use an adjacency matrix; a 2D array where each element in the array[x][y] is the weight of the edge between nodes x and y.
A quite simple solution would be to create an array that stores the outgoing edges for each node plus the weight. You'd simply jump to one node, search the other node in it's outgoing edges and take the weight. Complexity is maximal degree, which I usually assume to be capped.
Only thing to make sure is that all the redundant information is kept consistent.
Like
class AdjacentWeightedEdges {
struct OutgoingWeightedEdge {
size_t target_node;
int weight;
}
vector<OutgoingWeightedEdge> edges;
int edge_weight(const size_t index) const {
iterate through edges
if an edge with index found, return it's weight
raise an error if not
}
}
class Graph {
//your stuff as it is right inserted here
vector<AdjacentWeightedEdges> adjacencies;
int edge_weight(const size_t index_1, const size_t index_2){
return adjacencies[index_1].edge_weight(index_2);
}
}
If even a 1d approach like this creates memory problems, consider only storing the edges for index_1 < index_2.
Another similar method:
Store an array of pointers to the nodes, have the edge weights in the adjacency list and do what I did directly. If you don't go with indices anyhow if memory is a problem.
Another answer here talks about the adjacency matrix - this one could even work if a certain structure for a sparse matrix class is used that stores first non-zero in row/column pointers and then pointers to every following non-zero entry. Although this essentially collapses to my approach. Might be worthwhile if you need a sparse matrix class anyway.
