void Graph::breadFirstSearch(int vid)
{
    cout <<"The sequence of breadth first search starts from vertex " << vid << " is :" << endl;

    queue<Vertex* > search_queue;
    //place starting nodes on the queue
    Vertex* v = vertice.at(vid);
    search_queue.push(v);

    //make sure queue isnt empty before beginning
    while (search_queue.size() != 0)
    {
        Vertex* current_vertex = search_queue.front();
        search_queue.pop();

        if (current_vertex->isVisited == true)
            continue;

        current_vertex->isVisited = true;

        cout<< current_vertex->id << endl;

        for( vector<Vertex*>::const_iterator it = current_vertex->adj_v.begin(); it != current_vertex->adj_v.end(); ++it )
        {
            Vertex* neighbor_vertex = *it;

            if (neighbor_vertex->isVisited == true)
            {
                continue;
            }

            search_queue.push(neighbor_vertex);
        }
    }

    cout<<endl;

}

void Graph::depthFirstSearch(int vid)
{
    cout << "The sequence of depth first search starts from vertex " << vid << " is :" << endl;

    stack<Vertex* > search_stack; //

    //create vertex to search
    Vertex* v = vertice.at(vid); // pointer to vertex
    search_stack.push(v);       //

    while (search_stack.size() != 0)
    {
        Vertex* current_vertex = search_stack.top();
        search_stack.pop();

        if (current_vertex->isVisited == true)
            continue;

        current_vertex->isVisited = true;

        cout << current_vertex->id << endl;

        for (vector<Vertex*>::const_iterator it = current_vertex->adj_v.begin(); it != current_vertex->adj_v.end(); ++it)
        {
            Vertex* neighbor_vertex = *it;

            if (neighbor_vertex->isVisited == true)
            {
                continue;
            }

            search_stack.push(neighbor_vertex);
        }
    }

    cout << endl;

}

void Graph::Dijkstra(int vid)
{
    // input
    //
    Graph g; //define the graph
    ifstream vertex_file;
    vertex_file.open("vertex.txt", ios::in);
    int id;
    double x, y;
    while (vertex_file >> id >> x >> y)
    {
        Vertex* v = new Vertex(id);
        v->x = x;
        v->y = y;
        g.load(v); //load the vertex into the graph
    }
    vertex_file.close();
    //read adjacency relationship among vertices
    ifstream adjacency_file;
    adjacency_file.open("adjacency.txt", ios::in);
    int adj_1, adj_2;
    while (adjacency_file >> adj_1 >> adj_2)
    {
        Vertex* v_1 = g.vertice.at(adj_1);
        Vertex* v_2 = g.vertice.at(adj_2);
        //calculate the distance between the two vertices
        double distance= v_1->distanceTo(*v_2);
        v_1->addAdjacentVertex(v_2, distance);
        v_2->addAdjacentVertex(v_1, distance);
    }
    adjacency_file.close();
    //start vertex:
    // end vertex:
    cout << "The sequence of Dijkstra search starts from vertex " << 28776 << " is :" << endl;

    priority_queue<Vertex* > search_queue;
    //place starting nodes on the queue
    Vertex* v = vertice.at(28776);
    search_queue.push(v);

    //make sure queue isnt empty before beginning
    while (search_queue.size() != 0)
    {
        Vertex* current_vertex = search_queue.top();
        search_queue.pop();

        if (current_vertex->isVisited == true)
            continue;

        current_vertex->isVisited = true;

        cout << current_vertex->id << endl;

        for (vector<Vertex*>::const_iterator it = current_vertex->adj_v.begin(); it != current_vertex->adj_v.end(); ++it)
        {
            Vertex* neighbor_vertex = *it;

            if (neighbor_vertex->isVisited == true)
            {
                continue;
            }

            search_queue.push(neighbor_vertex);
        }
    }

    cout << endl;

}