BFS implementation

[Ana Developer]

I havent been using C++ in 4 years and therefore I have some difficulties implementing my BFS algorithm.

I keep getting errors like
Error 12 error C2784: 'bool std::operator <(const std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt2> &)' : could not deduce template argument for 'const std::reverse_iterator<_RanIt> &' from 'const Node' c:\program files\microsoft visual studio 8\vc\include\functional 143


Could anyone please help me what could be the prob?
Thanks a lot!

[jsmith]

You have to post the code that is causing the compile error. The error by itself isn't
helpful.

[Ana Developer]

Thank you for helping me!



#include "stdafx.h"
#include <deque>
#include <list>
#include <queue>
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <set>
using namespace std;

char file_name[15];
char links_file[15];
char alg[15];
char with_list[15];
char new_name[15];
int depth;
long idstart,idgoal;

class Action
{
public:

long start_node;
long end_node;
int distance;
int one_way;
string road;

Action();
Action(long sn, long en, int dist, int ow, string r)
{
start_node=sn;
end_node=en;
distance=dist;
one_way=ow;
road=r;
}
};

class Node
{
public:
long state;
int path_cost;
Node();
Node(long s,int p_c)
{
state=s;
path_cost=p_c;
}
};

class Problem
{
public:
long initial_node;
long final_node;
int path_cost;

bool GoalTest(Node node)
{
if(node.state==final_node)
return true;
else return false;
}
Problem();
Problem(long in, long fn)
{
initial_node=in;
final_node=fn;
path_cost=0;

}
bool bfs(Problem pbm);


};


Node ChildNode(Problem pbm, Node n, Action a)
{

}

void assign_value(Node n1,Node n2)
{
n1.path_cost=n2.path_cost;
n1.state=n2.state;
}

bool cmpNodes(Node n1, Node n2)
{
if((n1.path_cost==n2.path_cost) && (n1.state==n2.state))
return true;
else return false;
}


int _tmain(int argc, _TCHAR* argv[])
{
list<Action> actions;
list<Action>::iterator j;
int frontier_no=0;

queue<Node> frontier;
set<Node> explored;
char command_line[150];
int acts=0;

if(argc==8)
{
printf("Enter: file name, links file, algorithm name(bfs/dfs/astar), closed list(Y/N), depth to search, id of the starting node, id of the goal node, name of new file: ");
scanf("%s",command_line); //read the name of the file
sscanf(command_line,"%s %s %s %s %d %l %l %s",file_name,links_file,alg,with_list,depth,idstart,idgoal,new_name);

string start_node;
string end_node;
string distance;
string one_way;
string road;
string line;
int no_links;
int line_no;
ifstream fp(links_file);

if (fp.is_open())
{
while (!fp.eof())
{
getline (fp,line);
line_no++;
}
fp.close();
}


if (fp.is_open())
{
while (!fp.eof())
{
getline(fp,line);
istringstream iss(line);
iss >> start_node;
iss>>end_node;
iss>>distance;
iss>>one_way;
iss>>road;
iss>>line;
Action a;
a.distance=atoi(distance.c_str());
a.end_node=atol(end_node.c_str());
a.one_way=atoi(one_way.c_str());
a.road=road;
a.start_node=atol(start_node.c_str());
//=new Action(atol(start_node.c_str()),atol(end_node.c_str()),atoi(distance.c_str()),atoi(one_way.c_str()),road);
actions.push_back(a);
acts++;

}
fp.close();
}
else cout << "Unable to open file";


Problem problem;
problem.final_node=idgoal;
problem.initial_node=idstart;
//=new Problem(idstart,idgoal);
Node child;
Node node;
node.path_cost=problem.path_cost;
node.state=problem.initial_node;
//=new Node((*problem).initial_node,(*problem).path_cost);
if(problem.GoalTest(node)) return (1);


bool in_queue=false;

while(1)
{
if(frontier.empty()) return -1;
assign_value(node,frontier.front());
explored.insert(node);


for(j=actions.begin();j!=actions.end();j++)
{
assign_value(child,ChildNode(problem,node,actions.front()));
int i;
for( i=0;i<acts;i++)
{
in_queue=cmpNodes(child,frontier.front());
Node n;
assign_value(n,frontier.front());
frontier.push(n);
frontier.pop();
if(in_queue)
break;

}
set<Node>::iterator it;
it=explored.find(child);
if(it!=explored.end()&&!in_queue)
{

if(problem.GoalTest(child))
return (1);
frontier.push(child);
}
in_queue=false;
}
}


}
return 0;
}

[Silvermaul]

Please enclose your code with <> from the button in the right cause it is hard to read this way.

[Denis]

Please implement operator< for Node class. It's used by std::set to do insert

[Ana Developer]

Thanks a lot!