void Graph::unweighted( const string & startName )
{
    clearAll( );

    vmap::iterator itr = vertexMap.find( startName );

    if( itr == vertexMap.end( ) )
    {
        cout << startName << " is not a vertex in this graph" << endl;
        return;
    }

    Vertex *start = (*itr).second;
    list<Vertex *> q;
    q.push_back( start ); start->dist = 0;

    while( !q.empty( ) )
    {
        Vertex *v = q.front( );	q.pop_front( );

        for( int i = 0; i < v->adj.size( ); i++ )
        {
            Vertex *w = v->adj[ i ];
            if( w->dist == INFINITY )
            {
                w->dist = v->dist + 1;
                w->path = v;
                q.push_back( w );
            }
        }
    }
}

Vertex* Graph::getVertex (vdata v)
{
	vmap::iterator it = vertexMap.find (v);
	
	if (it == vertexMap.end()) {
		return addVertex (v);
	}
	
	return (*it).second;
}

Vertex* BinaryTree::getVertex (int v)
{
	vmap::iterator it = vertexMap.find (v);
	
	if (it == vertexMap.end()) {
		return addVertex (v);
	}
	
	return (*it).second;
}

Vertex* Graph::getVertex(const string& s){

	vmap::const_iterator it = vertexMap.find(s);
	if(it == vertexMap.end()){
		Vertex* v = new Vertex(s);
		vertexMap[s] = v;
		return v;
	}

	return (*it).second;
}

// If vertexName is not present, add it to vertexMap
// In either case, return the Vertex
Vertex * Graph::getVertex( const string & vertexName )
{
    vmap::iterator itr = vertexMap.find( vertexName );

    if( itr == vertexMap.end( ) )
    {
        Vertex *newv = new Vertex( vertexName );
        allVertices.push_back( newv );
        vertexMap.insert( vpair( vertexName, newv ) );
        return newv;
    }
    return (*itr).second;
}

void graph::addvertex(const string &name)
{
	vmap::iterator itr=work.begin();
	itr=work.find(name);
	if(itr==work.end())
	{
		vertex *v;
		v= new vertex(name);
		work[name]=v;
		return;
	}
	cout<<"\nVertex already exists!";
}

void Graph::printPath( const string & destName ) const
{
    vmap::const_iterator itr = vertexMap.find( destName );

    if( itr == vertexMap.end( ) )
    {
        cout << "Destination vertex not found" << endl;
        return;
    }

    const Vertex & w = *(*itr).second;
    if( w.dist == INFINITY )
        cout << destName << " is unreachable";
    else
        printPath( w );
    cout << endl;
}

map<mmddyyyy, UI> construct_hits_map(const vmap &r)
{
	map<mmddyyyy, UI> k;

	// construct map of dates and number of visits in each date
	for(vmap::const_iterator i = r.begin(); i!=r.end(); i++)
	{
		for(dvec::const_iterator j = i->second.begin(); j!=i->second.end(); j++)
		{
			if(k.find(*j)==k.end())
				k[*j] = 1;
			else
				k[*j]++;
		}
	}

	// erase unwanted elements
	mmddyyyy td = k.rbegin()->first;
	td.yyyy--; // this serves as the upper bound for erasure
	k.erase(k.begin(), k.upper_bound(td));

	return k;
}

long long Graph::prim(const string& s){
	vmap::const_iterator itr = vertexMap.find(s);
	if(itr == vertexMap.end())
		cerr<<"Source vertex not found"<<endl;

	clearAll();
	int n = vertexMap.size() - 1;
	Vertex *p = itr->second;
	vector<Vertex*> Q;
//	priority_queue<Vertex*, vector<Vertex*>, Compare> Q;
	p->dist = 0;
	for(vmap::const_iterator it = vertexMap.begin(); it != vertexMap.end(); it++)
	Q.push_back(it->second);
	long long cost = 0;

	while(!Q.empty()){

		make_heap(Q.begin(), Q.end(), Compare());
		Vertex *u = Q.front();
		u->done = true;
		pop_heap(Q.begin(), Q.end(), Compare());
		Q.pop_back();
		for(vector<Edge>::const_iterator it = u->adj.begin(); it != u->adj.end(); it++){
			Vertex *v = it->dest;
			if(!v->done && v->dist > it->cost){
				v->dist = it->cost;
				v->prev = u;
//				cout<<"cost of "<<v->name<<" is updated to "<<v->dist<<endl;
			}
		}

	}

	for(vmap::const_iterator it = vertexMap.begin(); it != vertexMap.end(); it++){
	 	cost+=it->second->dist;
	}

	return cost;
}

bool Graph::isVertex(const string& s) const {

	vmap::const_iterator it = vertexMap.find(s);
	if(it == vertexMap.end()) return false;
	return true;
}

void graph::addedge(const string& from, const string& to, double cost)
{
	vertex *f=(work.find(from)->second);
	vertex *t=(work.find(to)->second);
	pair<int,vertex *> edge = make_pair(cost,t);
	f->adj.push_back(edge);
}

Vertex* WGraph::getVertex (vdata v) {
  it = vertexMap.find (v);

  if (it == vertexMap.end())
    return addVertex (v);

  return it->second;
}

Vertex* Graph::addVertex (vdata v, bool waken = false) {
	Vertex* newv = new Vertex (v);
  newv->waken = waken;
	allVertexes.push_back (newv);
	vertexMap.insert (vpair (v, newv));
	return newv;
}

Vertex* Graph::addVertex (vdata v) {
	Vertex* newv = new Vertex (v);
	allVertexes.push_back (newv);
	vertexMap.insert (vpair (v, newv));
	return newv;
}

Vertex* BinaryTree::addVertex (int v) {
	Vertex* newv = new Vertex (v);
	allVertexes.push_back (newv);
	vertexMap.insert (vpair (v, newv));
	return newv;
}