I have written code (reference below) to count number of moves from a start Vertex to an end vertex.
Sparing the validation of logic of the code, I'm a little overwhelmed by the compile errors I'm getting for this code. I think I can understand why the errors are happening, but I'm unsure about the best way to fix them. So I could really use some help there.
The lines that give me compile errors, the reasons I think why they're there, and what I have gleaned so far are listed below.
Number 1
map<Vertex,int> distanceMap; // distance is the minimum distance required to reach this current visited vertex.
unordered_map<Vertex,Vertex> pathMap; // pathMap is to trace the path until current visited Vertex.
unordered_set<Vertex> Q;
The error I get above is
no matching function for call to ‘std::unordered_map, std::pair
>::unordered_map()
no matching function for call to ‘std::unordered_set >::unordered_set()’
I've already declared the type Vertex like so
typedef pair<int,int> Vertex;
So what's the mistake here?
Number 2
for(int i = 0; i < rows; ++i)
{
for(int j = 0; j < cols; ++j)
{
Q.insert(make_pair(i,j));
}
}
The error occurs when I insert the pair into the unordered_set.
no matching function for call to ‘std::unordered_set >::insert(std::pair)’
Number 3
for ( auto it = Q.begin(); it != Q.end(); ++it )
{
distanceMap[it++] = INT_MAX;
}
Error:
‘class std::unordered_set >’ has no member named ‘begin’
!‘class std::unordered_set >’ has no member named ‘end’
How do I properly declare the iterator for this, if auto doesn't apply?
Number 4
Q.erase(Q.find(currVertex));
Error:
‘class std::unordered_set >’ has no member named ‘erase’
!‘class std::unordered_set >’ has no member named ‘find’
Number 5
distanceMap[*it] = updateDist;
pathMap[*it] = currVertex;
Error :
no match for ‘operator[]’ (operand types are ‘std::unordered_map, std::pair >’ and ‘std::pair’)
I understand there needs to be some sort of an operator overloading here? How would I implement this?
Number 6
while(pmap[curr])
// COMPILE ERROR : no match for ‘operator[]’ (operand types are ‘std::unordered_map, std::pair >’ and ‘Vertex {aka std::pair}’)
{
moves+=1;
curr = pmap[curr];
// COMPILE ERROR : no match for ‘operator[]’ (operand types are ‘std::unordered_map, std::pair >’ and ‘Vertex {aka std::pair}’)
}
For this, again, I'm not sure why the error exists when I'de already declared that pmap is of type unordered_map<Vertex,Vertex> pmap
and typedef pair<int,int> Vertex;
Full code for reference
// ------ UTIL -------
/* all required structures for Graph */
typedef pair<int,int> Vertex;
/* all criteria required to get a vertex */
typedef pair<Vertex, int> MyPairType;
struct CompareSecond
{
bool operator()(const MyPairType& left, const MyPairType& right) const
{
return left.second < right.second;
}
};
Vertex get_min_distance_vertex(map<Vertex,int> distMap)
{
pair<Vertex, int> min = *min_element(distMap.begin(), distMap.end(), CompareSecond());
return min.first; // compare (int) distances to get min dist, return vertex.
}
/* count moves */
int countMoves(Vertex target, unordered_map<Vertex,Vertex> pmap)
{
int moves = 0;
Vertex curr = target;
while(pmap[curr])
// COMPILE ERROR : no match for ‘operator[]’ (operand types are ‘std::unordered_map, std::pair >’ and ‘Vertex {aka std::pair}’)
{
moves+=1;
curr = pmap[curr];
// COMPILE ERROR : no match for ‘operator[]’ (operand types are ‘std::unordered_map, std::pair >’ and ‘Vertex {aka std::pair}’)
}
return moves;
}
/* get neighbours */
vector<Vertex> get_neighbours(Vertex curr, int rows, int cols)
{
vector<Vertex> n;
if (curr.first <rows && curr.second <cols)
{
if( curr.first+1 < cols && curr.second+2 < rows)
n.push_back(make_pair(curr.first+1,curr.second+2));
if( curr.first+2 < cols && curr.second+1 < rows)
n.push_back(make_pair(curr.first+2,curr.second+1));
if( curr.first+2 < cols && curr.second-1 < rows)
n.push_back(make_pair(curr.first+2,curr.second-1));
if( curr.first+1 < cols && curr.second-2 < rows)
n.push_back(make_pair(curr.first+1,curr.second-2));
if( curr.first-1 < cols && curr.second+2 < rows)
n.push_back(make_pair(curr.first-1,curr.second+2));
if( curr.first-2 < cols && curr.second+1 < rows)
n.push_back(make_pair(curr.first-2,curr.second+1));
if( curr.first-2 < cols && curr.second-1 < rows)
n.push_back(make_pair(curr.first-2,curr.second-1));
if( curr.first-1 < cols && curr.second-2 < rows)
n.push_back(make_pair(curr.first-1,curr.second-2));
}
return n;
}
/* get distance */
int distance_between_vertices(Vertex source, Vertex target)
{
float x = (source.first - target.first)*(source.first - target.first);
float y = (source.second - target.second)*(source.second - target.second);
return (int) sqrt(x+y);
}
// ---------------
int minimumMoves(int rows, int cols, int startx, int starty, int endx, int endy) {
Vertex source = make_pair(startx,starty);
Vertex target = make_pair(endx,endy);
map<Vertex,int> distanceMap; // distance is the minimum distance required to reach this current visited vertex.
unordered_map<Vertex,Vertex> pathMap; // pathMap is to trace the path until current visited Vertex.
unordered_set<Vertex> Q; // Q is a set of vertices in chessboard graph.
// initialize Graph ===> O(N^2) assuming rows = cols = n in a chessboard.
for(int i = 0; i < rows; ++i)
{
for(int j = 0; j < cols; ++j)
{
Q.insert(make_pair(i,j));
}
}
// Iterate over set, and then assign distanceMap and pathMap values.
auto it = Q.begin();
for ( auto it = Q.begin(); it != Q.end(); ++it )
{
distanceMap[it++] = INT_MAX;
}
// Make distanceMap[source] = 0;
distanceMap[source] = 0;
// Dijkstra's.
// Ref 1 : finding minimum in map -- http://stackoverflow.com/questions/2659248/finding-minimum-value-in-a-map
while(!Q.empty())
{
Vertex currVertex = get_min_distance_vertex(distanceMap);
if(currVertex.first==target.first && currVertex.second==target.second){
return countMoves(currVertex, pathMap);
}
Q.erase(Q.find(currVertex));
vector<Vertex>neighbours = get_neighbours(currVertex,rows,cols);
if(neighbours.empty())
break;
for(auto it = neighbours.begin(); it!= neighbours.end();it++)
{
int updateDist = distanceMap[currVertex] + distance_between_vertices(currVertex,*it);
if (updateDist < distanceMap[*it])
{
distanceMap[*it] = updateDist;
pathMap[*it] = currVertex;
}
}
}
// return all valid distances here.
return -1; //no possible move.
}
