I haven't learned operators in c++ yet so I do not understand what does compiler want from me. Here is a full code and error pops up in AStar class. I understand that the problem (maybe) is because I want to get size of vector<Node> and have to do something extra, but do not understand what.
Could anybody help me and tell what should I do?
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <set>
#include <cmath>
using namespace std;
struct Node {
int i;
int j;
double g;
double h;
double f;
};
class AStar {
public:
double getG(int i, int j) { // dist from starting node
return pow(i, 2) + pow(j, 2);
}
double getH(int i, int j) { // dist from ending node
double a = pow(goal_i - i, 2);
double b = pow(goal_j - j, 2);
return a + b;
}
double getF(double g, double h) {
return g + h;
}
vector<vector<int>> g; // graph
stack<Node> path;
set<Node> setVisited;
double goal_i;
double goal_j;
AStar(vector<vector<int>> graph, int goalI, int goalJ) {
// set goal i, j
goal_i = goalI;
goal_j = goalJ;
// set graph as class variable
g = graph;
// create first node
Node firstNode;
firstNode.i = 0;
firstNode.j = 0;
firstNode.g = getG(0, 0);
firstNode.h = getH(0, 0);
firstNode.f = getF(firstNode.g, firstNode.h);
// set first node to path as a begining
path.push(firstNode);
// set first node as visited
setVisited.insert(firstNode);
}
stack<Node> start() {
// choose the current node
Node currentNode = path.top();
while (currentNode.i != goal_i && currentNode.j != goal_j) {
//if no path exist
if (path.size() == 0) {
stack<Node> noPathStack;
return noPathStack;
}
// get all its available neighbours
Node neighbour = getBestNeighbour(currentNode);;
// check if neighbour is chosen:
if (neighbour.i == currentNode.i && neighbour.j == currentNode.j) { // if no unvisited neighbours left
path.pop();
setVisited.insert(neighbour);
}
else { // if neighbour has been chosen
path.push(neighbour);
}
Node currentNode = path.top();
}
return path;
}
private:
vector<Node> getNeighbours(Node node) {
vector<Node> neighbours;
// check if this neighbour is not out of bounds of the graph
// if not add it to neighbours vector
int numberOfNeighbours = 0;
if (node.i < goal_i && node.j < goal_j) {
if (node.i != goal_j) { // if bottom of the graph is not reached
Node checkNeighbourNode1;
checkNeighbourNode1.i = node.i + 1;
checkNeighbourNode1.j = node.j;
checkNeighbourNode1.g = getG(checkNeighbourNode1.i, checkNeighbourNode1.j);
checkNeighbourNode1.h = getH(checkNeighbourNode1.i, checkNeighbourNode1.j);
checkNeighbourNode1.f = getF(checkNeighbourNode1.g, checkNeighbourNode1.h);
neighbours.push_back(checkNeighbourNode1);
}
if (node.j != goal_j) { // if right bound of the graph is not reached
Node checkNeighbourNode2;
checkNeighbourNode2.i = node.i;
checkNeighbourNode2.j = node.j + 1;
checkNeighbourNode2.g = getG(checkNeighbourNode2.i, checkNeighbourNode2.j);
checkNeighbourNode2.h = getH(checkNeighbourNode2.i, checkNeighbourNode2.j);
checkNeighbourNode2.f = getF(checkNeighbourNode2.g, checkNeighbourNode2.h);
neighbours.push_back(checkNeighbourNode2);
}
// if diagonal right down node == 14 add it as neighbour otherwise don't
if (g[node.i + 1][node.j + 1] == 14) {
Node checkNeighbourNode3;
checkNeighbourNode3.i = node.i + 1;
checkNeighbourNode3.j = node.j + 1;
checkNeighbourNode3.g = getG(checkNeighbourNode3.i, checkNeighbourNode3.j);
checkNeighbourNode3.h = getH(checkNeighbourNode3.i, checkNeighbourNode3.j);
checkNeighbourNode3.f = getF(checkNeighbourNode3.g, checkNeighbourNode3.h);
neighbours.push_back(checkNeighbourNode3);
}
}
return neighbours;
}
bool neighbourVisited(Node node) {
return (setVisited.count(node)) ? true : false;
}
Node getBestNeighbour(Node node) {
vector<Node> neighbours = getNeighbours(node);
// for all neighbours
for (unsigned int i = 0; i < neighbours.size(); i++) {
// if neighbour is not visited
if (neighbours[i].i == goal_i && neighbours[i].j == goal_j) {
return neighbours[i];
}
if (!neighbourVisited(neighbours[i])) {
return neighbours[i];
}
}
// if all neighbours visited
return node; // returning input node means there is no unvisited neighbours left
}
};
class MillerMyers {
public:
string seq_1; // rows
string seq_2; // cols
vector<vector<int>> graph;
int row_size;
int col_size;
MillerMyers(string Sseq_1, string Sseq_2) {
row_size = Sseq_1.length();
col_size = Sseq_2.length();
seq_1 = Sseq_1;
seq_2 = Sseq_2;
setWeights();
};
vector<vector<int>> getGraph() {
return graph;
}
void printGraph() {
cout << " ";
for (int i = 0; i < row_size; i++) {
cout << seq_2[i] << " "; // cols
}
cout << "\n";
for (int i = 0; i < row_size; i++) { // rows
cout << seq_1[i] << " ";
for (int j = 0; j < col_size; j++) {
cout << graph[i][j] << " ";
}
cout << "\n";
}
}
private:
int getWeight(int i, int j) {
if (seq_1[i] == seq_2[j]) {
return 14;
}
else {
return 20;
}
}
void setWeights() {
// for each node we set weight
// 2 if it is simple node that chains UP, LEFT nodes
// 1.41 if it is node that chain UP, LEFT and UPPER-LEFT node.
for (int i = 0; i < row_size; i++) {
graph.push_back(vector<int>());
for (int j = 0; j < col_size; j++) {
int weight = getWeight(i, j);
graph[i].push_back(weight);
}
}
}
};
vector<pair<int, int>> getstack(stack <Node> s) {
vector<pair<int, int>> path;
while (!s.empty()) {
path.push_back(make_pair(s.top().i, s.top().j));
s.pop();
}
return path;
}
int main() {
string seq_1 = "AGTCCTT";
string seq_2 = "AGTTTCT";
MillerMyers mm(seq_1, seq_2);
vector<vector<int>> graph = mm.getGraph();
AStar astar(graph, seq_1.length(), seq_2.length());
stack<Node> path = astar.start();
// show the stack
vector<pair<int, int>> vecPath = getstack(path);
for (unsigned int i = 0; i < vecPath.size(); i++) {
cout << vecPath[i].first << " " << vecPath[i].second << endl;
}
return 0;
}
Error :
1>------ Build started: Project: MillerMayers, Configuration: Debug Win32 ------
1>MillerMayers.cpp
1>c:\program files (x86)\microsoft visual studio\2017\community\vc\tools\msvc\14.16.27023\include\xstddef(141): error C2678: binary '<': no operator found which takes a left-hand operand of type 'const _Ty' (or there is no acceptable conversion)
1> with
1> [
1> _Ty=Node
1> ]
1>c:\program files (x86)\microsoft visual studio\2017\community\vc\tools\msvc\14.16.27023\include\system_error(319): note: could be 'bool std::operator <(const std::error_condition &,const std::error_condition &) noexcept'
1>c:\program files (x86)\microsoft visual studio\2017\community\vc\tools\msvc\14.16.27023\include\system_error(312): note: or 'bool std::operator <(const std::error_code &,const std::error_code &) noexcept'
1>c:\program files (x86)\microsoft visual studio\2017\community\vc\tools\msvc\14.16.27023\include\xstddef(141): note: while trying to match the argument list '(const _Ty, const _Ty)'
1> with
1> [
1> _Ty=Node
1> ]
1>c:\program files (x86)\microsoft visual studio\2017\community\vc\tools\msvc\14.16.27023\include\xstddef(140): note: while compiling class template member function 'bool std::less<_Kty>::operator ()(const _Ty &,const _Ty &) const'
1> with
1> [
1> _Kty=Node,
1> _Ty=Node
1> ]
1>c:\program files (x86)\microsoft visual studio\2017\community\vc\tools\msvc\14.16.27023\include\xutility(1110): note: see reference to function template instantiation 'bool std::less<_Kty>::operator ()(const _Ty &,const _Ty &) const' being compiled
1> with
1> [
1> _Kty=Node,
1> _Ty=Node
1> ]
1>c:\program files (x86)\microsoft visual studio\2017\community\vc\tools\msvc\14.16.27023\include\xutility(264): note: see reference to class template instantiation 'std::less<_Kty>' being compiled
1> with
1> [
1> _Kty=Node
1> ]
1>c:\program files (x86)\microsoft visual studio\2017\community\vc\tools\msvc\14.16.27023\include\xutility(264): note: see reference to variable template 'const bool is_empty_v<std::less<Node> >' being compiled
1>c:\program files (x86)\microsoft visual studio\2017\community\vc\tools\msvc\14.16.27023\include\xtree(1032): note: see reference to class template instantiation 'std::_Tree_comp_alloc<_Traits>' being compiled
1> with
1> [
1> _Traits=std::_Tset_traits<Node,std::less<Node>,std::allocator<Node>,false>
1> ]
1>c:\program files (x86)\microsoft visual studio\2017\community\vc\tools\msvc\14.16.27023\include\set(55): note: see reference to class template instantiation 'std::_Tree<std::_Tset_traits<_Kty,_Pr,_Alloc,false>>' being compiled
1> with
1> [
1> _Kty=Node,
1> _Pr=std::less<Node>,
1> _Alloc=std::allocator<Node>
1> ]
1>c:\users\horseman.mini\source\repos\millermayers\millermayers\millermayers.cpp(41): note: see reference to class template instantiation 'std::set<Node,std::less<_Kty>,std::allocator<_Ty>>' being compiled
1> with
1> [
1> _Kty=Node,
1> _Ty=Node
1> ]
1>Done building project "MillerMayers.vcxproj" -- FAILED.
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========
P.S. I added here Miller class for checking AStar class, beacuse AStar takes graph from Miller
EDIT 1
I added
// overloading operator
Node operator<(const Node& n) {
Node n;
return n;
}
under the AStar constructor and above start function, but now error is
1>...ers\millermayers.cpp(65): error C2082: redefinition of formal parameter 'n'
SOLUTION FOR THOSE WHO GOOGLE SUCH A PROBLEM
I needed to specify how set should sort Node objects, so I added go global space this function:
bool operator< (const Node& node1, const Node& node2) {
return node1.f < node2.f;
}
Instead of node1.f < node2.f here could be any method how you can compare 2 objects.
