//-------------------------------GRAPH.H-----------------------------------
#ifndef Graph_H
#define Graph_H

#include <vector>
#include <map>
#include "Vertex.h"

using namespace std;

class Graph
{
public:
    //store vertices in graph
    map<int, Vertex*> vertice;

    //load vertex into graph
    void load(Vertex* v);

    //mark two vertices to be adjacent, and record the distance between them
    void makeAdjacency(int v1, int v2, double distance);

    //print adjacency matrix
    void printAdjacencyMatrix();

    //print adjacency list
    void printAdjacencyList();

    //bread first search
    void breadFirstSearch(int v);

    //depth first search
    void depthFirstSearch(int v);

    //Dijkstras
    void Dijkstra(int v);

    //reset the flag
    void restoreVisitedFlag();
};

#endif

//------------------------------- GRAPH.CPP---------------------------------
//#include "stdafx.h"
#include "Graph.h"
#include <iostream>
#include <algorithm>
#include <queue> // std::priority queue

#include <stack>
#include<fstream>
void Graph::load(Vertex* v)
{
    map<int, Vertex*>::iterator iter = vertice.find((*v).id);

    if (iter == vertice.end())
    {
        vertice.insert(pair<int, Vertex*> ((*v).id, v));
    }
    else
    {
        cout<<"Fail: the vertex has been inserted into the network!";
    }
}

void Graph::makeAdjacency(int v1, int v2, double distance)
{
    map<int, Vertex*>::iterator iter1 = vertice.find(v1);
    map<int, Vertex*>::iterator iter2 = vertice.find(v2);

    if (iter1 == vertice.end())
    {
        cout<<"Fail: v1 does not exist in the network!";
        return;
    }

    if (iter2 == vertice.end())
    {
        cout<<"Fail: v2 does not exist in the network!";
        return;
    }

    Vertex* vertex1 = vertice.at(v1);
    Vertex* vertex2 = vertice.at(v2);

    vertex1->addAdjacentVertex(vertex2,distance);
    vertex2->addAdjacentVertex(vertex1,distance);
}

void Graph::printAdjacencyMatrix()
{
    cout <<"Adjacency Matrix:"<<endl;

    for( map<int, Vertex*>::const_iterator it1 = vertice.begin(); it1 != vertice.end(); ++it1 )
    {
      int key1 = it1->first;
      Vertex* vertex1 = it1->second;

        for( map<int, Vertex*>::const_iterator it2 = vertice.begin(); it2 != vertice.end(); ++it2 )
        {
          int key2 = it2->first;
          Vertex* vertex2 = it2->second;

          if (vertex1->isAdjacentTo(vertex2))
              cout << "1" << '\t';
          else
              cout << "0" << '\t';

        }
        cout <<endl;
    }

    cout<<'\n';
}

void Graph::printAdjacencyList()
{
    cout <<"Adjacency List:"<<endl;

    for( map<int, Vertex*>::const_iterator it1 = vertice.begin(); it1 != vertice.end(); ++it1 )
    {
      int key1 = it1->first;
      Vertex* vertex1 = it1->second;
      cout<<key1<<'\t'<<":"<<'\t';

        for( map<int, Vertex*>::const_iterator it2 = vertice.begin(); it2 != vertice.end(); ++it2 )
        {
          int key2 = it2->first;
          Vertex* vertex2 = it2->second;

          if (vertex1->isAdjacentTo(vertex2))
              cout << key2 << '\t';
        }
        cout << endl;
    }
    cout << endl;
}


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::restoreVisitedFlag()
{
    for( map<int, Vertex*>::const_iterator it = vertice.begin(); it != vertice.end(); ++it )
    {
        int key = it->first;
        Vertex* vertex = it->second;

        vertex->isVisited = false;

    }

}
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;

}

//---------------------------VERTEX.CPP-----------------------------
/*Vertex: Corner Point Where lines meet*/




//#include "stdafx.h"
#include "Vertex.h"
#include <cmath>

Vertex::Vertex(int id)
{
    this->id = id;
    this->isVisited = false;
}

Vertex::Vertex(int id, double x, double y)
{
    this->id = id;
    this->x = x;
    this->y = y;

    this->isVisited = false;
}

double Vertex::distanceTo(Vertex v)
{
    double dx = this->x - v.x;
    double dy = this->y - v.y;
    double distance = sqrt(dx * dx + dy * dy );

    return distance;
}

void Vertex::addAdjacentVertex(Vertex* v, double dis)
{
    if (v->id == id)
    {
        return;
    }

    if (adj_v.end() == find (adj_v.begin(), adj_v.end(), v))
    {
        adj_v.push_back(v);
        adj_distance.push_back(dis);
    }
    else
    {
        return;
    }
}

bool Vertex::isAdjacentTo(Vertex* v)
{
    vector<Vertex*>::iterator iter = find (adj_v.begin(), adj_v.end(), v);

    if (adj_v.end() == iter)
        return false;
    else
        return true;
}

void Vertex::deleteAdjacentVertex(Vertex* v)
{
    vector<Vertex*>::iterator iter = find (adj_v.begin(), adj_v.end(), v);


    if (adj_v.end() == iter)
    {
        return;
    }
    else
    {
        size_t pos = iter - adj_v.begin();
        vector<double>::iterator iter_dis = adj_distance.begin() + pos;

        adj_v.erase(iter);
        adj_distance.erase(iter_dis);
    }
}

bool Vertex::operator== (const Vertex& v1)
{
        if (id == v1.id)
        {
            return true;
        }
        else
        {
            return false;
        }
}
//---------------------------------- VERTEX.H ------------------------------------

#ifndef Vertex_H
#define Vertex_H

#include <vector>
#include <algorithm>
using namespace std;

class Vertex
{
public:

    int id; //vertex id
    double x; //coordinate x
    double y; //coordinate y


    bool isVisited; //visited flag

    //store adjacent vertices
    vector<Vertex*> adj_v;

    //store the distances to its adjacent vertices
    vector<double> adj_distance;

    //constructor function
    Vertex(int id);
    Vertex(int id, double x, double y);

    //distance to another vertex
    double distanceTo(Vertex v);

    //add its adjacent vertices
    void addAdjacentVertex(Vertex* v, double dis);

    //check vertex v is adjacent
    bool isAdjacentTo(Vertex* v);

    //delete its adjacent vertex
    void deleteAdjacentVertex(Vertex* v);

    //check if two vertices are the same one
    bool operator == (const Vertex& v1);

};


//----------------------- main.cpp ------------------------------

#endif

#include <iostream>
#include<fstream>
#include "Graph.h"
#include "Vertex.h"

using namespace std;



int main()
{

    Vertex v1(1), v2(2), v3(3), v4(4), v5(5), v6(6), v7(7), v8(8);
    Graph g;

    //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();

    g.load(&v1);
    g.load(&v2);
    g.load(&v3);
    g.load(&v4);
    g.load(&v5);
    g.load(&v6);
    g.load(&v7);
    g.load(&v8);
    v1.addAdjacentVertex(&v2, 0);
    v1.addAdjacentVertex(&v7, 0);
    v2.addAdjacentVertex(&v1, 0);
    v2.addAdjacentVertex(&v3, 0);
    v2.addAdjacentVertex(&v4, 0);
    v3.addAdjacentVertex(&v2, 0);
    v3.addAdjacentVertex(&v4, 0);
    v3.addAdjacentVertex(&v5, 0);
    v3.addAdjacentVertex(&v8, 0);
    v4.addAdjacentVertex(&v2, 0);
    v4.addAdjacentVertex(&v3, 0);
    v4.addAdjacentVertex(&v5, 0);
    v5.addAdjacentVertex(&v3, 0);
    v5.addAdjacentVertex(&v4, 0);
    v5.addAdjacentVertex(&v6, 0);
    v5.addAdjacentVertex(&v7, 0);
    v6.addAdjacentVertex(&v5, 0);
    v7.addAdjacentVertex(&v1, 0);
    v7.addAdjacentVertex(&v5, 0);
    v8.addAdjacentVertex(&v3, 0);
    g.printAdjacencyMatrix();
    g.printAdjacencyList();
    g.breadFirstSearch(2);
    g.restoreVisitedFlag();
    g.depthFirstSearch(2);
    g.restoreVisitedFlag();
    getchar();
    //--------------------------------------

    g.Dijkstra(28776);




    return 0;
}