A* search and Greedy search

[crimsonzero2]

Hello, I was to make a program that can do either A* search or greedy search. I got it mostly done, but the output I get is weird and I can't seem to find a way to correct it. Here is my code:

State.hpp

#ifndef STATE_HPP_INCLUDED
#define STATE_HPP_INCLUDED

#include <string>
#include <vector>
#include <fstream>

using namespace std;

class State
{
    //fields
    private:
        string city;
    public:
        //constructor
        State(const string &city_name);
        bool operator ==(const State &s) const;
        vector<State> getNeighbors();
        double getPathCost(State s);
        double getPathHeuristic(State s);
        string getName();

};
State::State(const string &city_name) : city(city_name)
{

}
//equals
bool State::operator ==(const State &s) const
{
    if(this->city == s.city)
    {
        return true;
    }
    else
    {
        return false;
    }
    //return this->city == s.city;
}
//neighbors
//ArrayList<State> getNeighbors()
vector<State> State::getNeighbors()
{
    //use lookup table to get neighbors
    vector<State> neighbors;// = new list<State>;
    string s1, s2;
    ifstream infile("romania_path_cost.txt");
    while(!infile.eof())
    {
        infile >> s1 >> s2;
        if(this->city == s1)
        {
            State neighbor(s2);
            neighbors.push_back(neighbor);
        }
    }
    infile.close();
    return neighbors;
}
//path cost
double State::getPathCost(State s)
{
    // Again, use lookup table
    // Read in lookup table from text file and create a matrix
    // Matrix should have initial city, final city, and cost in the respected columns
    // Look for city that matches this.city in first column, then look for city that matches
    string s1, s2;
    int cost;
    ifstream infile("romania_path_cost.txt");
    while(!infile.eof())
    {
        infile >> s1 >> s2 >> cost;
        if(this->city == s1 && s.city == s2)
        {
            infile.close();
            return cost;
        }
    }
}
//get heuristic
double State::getPathHeuristic(State s)
{
    //again, use lookup table
    string s1;
    int heuristic;
    ifstream infile("romania_heuristic.txt");
    while(!infile.eof())
    {
        infile >> s1 >> heuristic;

        if(s.city == s1)
        {
            infile.close();
            return heuristic;
        }
    }
}
string State::getName()
{
    return city;
}

#endif // STATE_HPP_INCLUDED

Node.hpp

#ifndef NODE_HPP_INCLUDED
#define NODE_HPP_INCLUDED

#include <iostream>
#include <vector>
#include "State.hpp"

using namespace std;

class Node
{
    private:
        vector<State> states;
        //total path cost of this node so far
        double cost;
        //heuristic - estimate of how close you are to goal state
        double heuristic;
    public:
        //make a node from a state
        Node(State state);
        Node(const Node&);
        Node(const Node* const);
        vector<State> getStates() const;
        double getCost() const;
        double getHeuristic() const;
        State getLastState() const;
        vector<Node> expand() const;
        void print_states();
};
Node::Node(State state)
{
    //states = new list<State>;
    states.push_back(state);
}
//make a node from a node
Node::Node(Node const &node)
{
    states = node.getStates();
    cost = node.getCost();
    heuristic = node.getHeuristic();
}

vector<State> Node::getStates() const
{
    /* use the operator= to copy the states from
    one list to another.
    ex: list1 = list2 //list2 is copied to list1*/
    vector<State> new_states;// = new list<State>;
    new_states = this->states;
    return new_states;
}
double Node::getCost() const
{
    return cost;
}
double Node::getHeuristic() const
{
    return heuristic;
}
State Node::getLastState() const
{
    //list<State>::iterator ending;
    //ending = states.size() - 1;
    int last = states.size() - 1;
    State lastState = states[last];
    return lastState;
}
//expand
vector<Node> Node::expand() const
{
    //get last state in node
    State lastState = getLastState();
    //get neighbors of last state
    vector<State> neighbors = lastState.getNeighbors();
    //create new nodes from neighbors
    int nNeighbors = neighbors.size();
    vector<Node> newNodes; // = new List<Node>;
    for(int i = 0; i < nNeighbors; i++)
    {
        bool same = false;
        // Check for repeated states and don't make
        // new nodes for those cases
        // For each of new nodes that we create from
        // neighbors we'll need to calculate
        // heuristics & path costs, etc.
        // Copy parent node
        for(int j = 0; j < states.size(); j++)
        {
            if(neighbors[i] == this->states[j])
            {
                same = true;
                break;
            }
        }
        if(same)
        {
            continue;
        }
        Node newNode(*this);// = new Node(this);

        // Add one of the neighbors to the list of states in newNode
        newNode.states.push_back(neighbors[i]);

        // Calculate new cost
        // TODO fill in
        newNode.cost = newNode.cost + lastState.getPathCost(neighbors[i]); // Some function that calculates the cost of going from lastState to this neighbor state
        // Calculate new heuristic
        newNode.heuristic = lastState.getPathHeuristic(neighbors[i]);//neighbors[i].heuristic;
        newNodes.push_back(newNode);
    }
    return newNodes;
}
void Node::print_states()
{
    string current_city;
    int states_size = this->states.size();
    for(int i = 0; i < states_size; i++)
    {
        current_city = this->states[i].getName();
        cout << current_city << " ";
    }
}

#endif // NODE_HPP_INCLUDED

main.cpp

#include <iostream>
#include <list>
#include <vector>
#include <string>
#include <algorithm>
#include "State.hpp"
#include "Node.hpp"

using namespace std;

bool compare_cost(const Node& n1, const Node& n2)
    {
            return(n1.getCost() <= n2.getCost());
    }
bool compare_heuristic(const Node& n1, const Node& n2)
{
    return(n1.getHeuristic() <= n2.getHeuristic());
}
bool compare_total_cost(const Node& n1, const Node& n2)
{
    return((n1.getCost()+n1.getHeuristic()) <= (n2.getCost()+n2.getHeuristic()));
}
bool goalTest(const State& s1, const State& s2)
{
    if(s1 == s2)
    {
        return true;
    }
    else
    {
        return false;
    }
}

int main()
{
    string beginning, finish;
    cout << "Enter the starting city and the ending city: " << endl;
    cout << "Starting: ";
    getline(cin, beginning);// cin >> beginning;
    cout << "Ending: ";
    getline(cin, finish);// cin >> finish;
    State initialState(beginning);// = new State(beginning);
    State goalState(finish);// = new State(finish);
    //list<Node>::iterator start;
    char a;
    cout << "which method of sort do you want? c for cost, h for heuristic: ";
    a = getchar();

    // Open nodes - a list of nodes currently available to expand
    // TODO determine structure of open nodes list
    vector<Node> openNodes;
    // Initialize the problem
    // Add a node representing the initial state
    Node start_Node(initialState);
    // openNodes.add(new Node(initialState))
    openNodes.push_back(start_Node);
    while (openNodes.size() > 0)
    {
        //start = openNodes.begin();
        Node bestNode(openNodes[0]);
        bestNode.print_states();
        cout << endl;
        //int last = bestNode.states.size() - 1;
        bool goalReached = goalTest(bestNode.getLastState(), goalState);
        if(goalReached)
        {
            cout << "Successful" << endl;
            return 0;
        }
        else
        {
            openNodes.erase(openNodes.begin());
            vector<Node> children = bestNode.expand();

            int children_size = children.size() -1;
            //add children to openNodes
            for(int i = 0; i < children_size; i++)
            {
                openNodes.push_back(children[i]);
            }
        }

        //sort openNodes by whatever criteria we're using
        //openNodes.sort(compare);
        if(a == 'C' || a == 'c')
        {
            sort (openNodes.begin(), openNodes.end(), compare_total_cost);
        }
        else
        {
            sort (openNodes.begin(), openNodes.end(), compare_heuristic);
        }
    }
}

[crimsonzero2]

Here is the following output:

Enter the starting city and the ending city:
Starting: arad
Ending: bucharest
which method of sort do you want? c for cost, h for heuristic: c
arad
arad 118
arad 140
arad sibiu
arad sibiu 99
arad sibiu rimnicu
arad sibiu rimnicu 97
arad sibiu fagaras
arad sibiu rimnicu pitesti
arad sibiu rimnicu pitesti bucharest

The problem with this output is that I get numbers in it which I shouldn't be getting. If anyone here knows anything about these search algorithms would be willing to look at the code and help me fix it, it would be appreciated. If anyone wants the files that are being read in, I will supply if asked.