// File graph.cpp    Graph<V,W> class template implementation file
// shinnerl@ucla.edu   

#ifndef GRAPH_CPP
#define GRAPH_CPP

/*
template <class V, class W>   
void Graph<V,W>::getComponent(const V& v0, set<V>& myPiece)
{
  // Find all vertices connected to v0, put them in myPiece with v0.

  cerr << "\nYou must implement function Graph<V,W>::getComponent()."
       << std::endl;
  assert(0);
}
*/


template <class V, class W>   // Verify "undirectedness" of graph data
bool Graph<V,W>::isSymmetric( pair<V,V>& badEdge ) 
{  
   // The weight for edge {u,v} must be stored twice, for both (u,v) and (v,u). 
   // This function stops as soon as it finds one bad edge and 
   // passes it back, returning false.  If *all* edges are ok, it returns true.
   // There is no efficient way to avoid visiting every stored edge *twice*.
   //
   // Recall, edge (u,v) with weight w is stored in u's Adjacency map as 
   //   the pair (v,w).  

   bool symmetric = true;
   std::map<V, map<V,W> >::iterator p;
   for (p = map< V, map<V,W> >::begin(); 
        p !=map< V, map<V,W> >::end(); 
        ++p)
   {
      const V& v_i      = p->first;          // shorthand
      map<V,W>& v_i_map = p->second;         // shorthand
      if (!v_i_map.empty())
      {
        std::map<V,W>::iterator q;
	for ( q = v_i_map.begin();
	       symmetric && q != v_i_map.end();
	       ++q )
	 {
            const V& neighbor   = q->first;
            W edgeWeight        = q->second;
            W* counterWeightPtr = findEdge(neighbor, v_i);
            if (!counterWeightPtr || (*counterWeightPtr != edgeWeight))
            {
               symmetric = false;
               badEdge.first  = v_i;
               badEdge.second = neighbor;
            }
	 }
      }
   } 
   return symmetric;  
}

template <class V, class W>          
void Graph<V,W>::insertVertex( const V& v )
{
   operator[](v) = map<V,W>();  // Initially, v has no neighbors. 
}


template <class V, class W>          
void Graph<V,W>::removeVertex( const V& v )
{ 
   // Before removing v, we must remove all edges incident upon it.
   // To do this, we visit every neighbor of v and remove v from
   //  that neighbor's adjacency map.  Then we remove v.

   map<V,W> *Aptr = findVertex( v );
   if (Aptr) {
      std::map<V,W>::iterator p; 
      for ( p = Aptr->map<V,W>::begin(); 
	    p != Aptr->map<V,W>::end(); 
	    ++p ) {
         map<V,W> *tAptr = findVertex(p->first);
         tAptr->erase( v );   // tAptr nonzero if the Graph is symmetric.
      }                        
   }                        
   map<V, map<V,W> >::erase(v);
}

template <class V, class W>          // Symmetry preserving.
void Graph<V,W>::removeEdge( const V& v1, const V& v2 )
{
   map<V,W> *A1ptr = findVertex(v1), 
            *A2ptr = findVertex(v2);
   if (A1ptr && A2ptr)
   {
      if (findEdge(v1, v2))
         A1ptr->erase( v2 );
      if (findEdge(v2, v1))
         A2ptr->erase( v1 );
   }
}

template <class V, class W>           // Symmetry preserving.        
void Graph<V,W>::setEdge(const V& v1, const V& v2, const W& w)
{
   map<V,W> *A1ptr = findVertex(v1), 
	    *A2ptr = findVertex(v2);
   if (A1ptr && A2ptr)
   {
       A1ptr->operator[](v2) = w; 
       A2ptr->operator[](v1) = w; 
   }
}

template <class V, class W>         
map<V,W>*  Graph<V,W>::findVertex(const V& v) const
{ 
  map<V,W>* nhbdPtr = 0;
  std::map< V, map<V,W> >::const_iterator p1 
     = map< V, map<V,W> >::find(v);
  if (p1 != map< V, map<V,W> >::end())
     nhbdPtr = const_cast<map<V,W>*>(&(p1->second));    // cast
  return nhbdPtr;
}

template <class V, class W>         
W* Graph<V,W>::findEdge( const V& v1, const V& v2 ) const
{
   W* Wptr = 0;
   map<V,W>* AmapPtr = findVertex(v1);
   if (AmapPtr)
   {
      std::map<V,W>::iterator p2 = AmapPtr->find(v2);
      if (p2 != AmapPtr->end())
        Wptr = &(p2->second);
   }
   return Wptr;
}


template <class V, class W>         // Vertex adjacency map output
void Graph<V,W>::print( ostream& os )
{
  std::map< V, map<V, W> >::iterator p;
  for (p = map< V, map<V,W> >::begin(); 
       p !=map< V, map<V,W> >::end(); 
       ++p){
     os << p->first; 
     os << "  { ";
     std::map<V, W>::iterator q;
     for (q = p->second.begin(); 
	  q !=p->second.end(); 
	  ++q)
        os << " ( " << q->first 
	   << " , " << q->second << " ) ";
     os << " } " << std::endl;
  }
  os << std::endl;
}


template <class V, class W>         // Vertex adjacency map input
void Graph<V,W>::read( istream& is )
{
   erase();
   V v;
   map<V,W> A;
   while (is){
     is >> v;
     if (is){
        getAdjacencyMap(is, A);
	operator[](v) = A;
     }
   }

   pair<V,V> badPair;
   if (!isSymmetric( badPair ))
   {
      stringstream info;
      info << "\nError in graph input at edge ("
           << badPair.first << " , " << badPair.second << "). \n"
	   << "The graph must be undirected. Graph discarded. \n\n" 
	   << "See sample file \"g1.dat\" for format conventions; note spacing."
	   << std::endl;
      erase();
      throw Error(info.str());
   }
}

template <class V, class W>         // Vertex adjacency map input
void Graph<V,W>::getAdjacencyMap( istream& is,  map<V,W>& A )
{
   A.map<V,W>::clear();            
   char ch = ' ';
   while ( is && ch != '{')
     is >> ch;

   bool done = false;
   V neighbor;
   W weight;
   while (is && !done)
   {
      is >> ch;
      done = (!is || ch =='}');
      if (!done && ch == '(')
      {
      	is >> neighbor;
	is >> ch;       // Separating comma.
      	is >> weight;
	is >> ch;       // Closing paren.
      	A[neighbor] = weight;
      }
   }
}


// --- Begin leastCostPath code ---

template <class V, class W>   
struct PathVertex            // wrapper used by leastCostPath().
{
   V vertex;
   V predecessor;
   W pathWeight;

   PathVertex() {}                           
   PathVertex( const V& v, const W& pw )    // For searching.
     : vertex(v), pathWeight(pw) {}           
   PathVertex( const V& v, const V& p, const W& pw ) 
     : vertex(v), predecessor(p), pathWeight(pw) {}

   bool operator<( const PathVertex& w ) const
    {return     (pathWeight < w.pathWeight && vertex != w.vertex)
             || (pathWeight == w.pathWeight && vertex < w.vertex);}
   bool operator<=( const PathVertex& w ) const
    {return    (*this < w )
            || (pathWeight <= w.pathWeight && vertex == w.vertex);}
   bool operator>( const PathVertex& w ) const
    {return !operator<=(w);}
   bool operator>=( const PathVertex& w ) const
    {return !operator<(w); }
   bool operator==( const PathVertex& w ) const
    {return  (vertex == w.vertex);}
   bool operator!=( const PathVertex& w ) const
    {return !operator==(w); }
};

template <class V, class W>
ostream& operator<<( ostream& os, const PathVertex<V,W>& pv )
{os << pv.vertex; return os;}

template <class V, class W>
istream& operator>>( istream& is, PathVertex<V,W>& pv )
{is >> pv.vertex >> pv.predecessor >> pv.pathWeight; return is;}


template <class T>
T popLeast ( std::set<T>&  theSet )
{
   assert (!theSet.empty());      // Precondition: theSet must be nonempty.
   std::set<T>::iterator p = theSet.begin();
   T answer = *p;
   theSet.erase(answer);          
   return answer;
}


template <class V, class W>                 
W Graph<V,W>::leastCostPath( const V& vStart, const V& vEnd, 
                             deque<V>& pathDeque ) const
{ 
 //  Dijkstra's algorithm.  The tree of least cost paths is stored in
 //  an STL map<V,V> called "pathMap."  Each vertex in the pathMap
 //  is paired with a unique predecessor (vStart is paired with itself).
 //
 //  The boundary or "edge" of this tree of least cost paths is 
 //  stored twice to support two different modes of access: by
 //  pathWeight and by vertex.
 //  The "boundarySet" is also an STL set< PathVertex<V,W> >. 
 //  Its elements are ordered first by pathWeight and second by 
 //  vertex name, as defined by PathVertex::operator<(...).   Its 
 //  least-weight element is efficiently removed and added to 
 //  the pathMap at each step of the algorithm. 
 //  The "boundaryMap" is an STL map<V, W> that supports simple 
 //  pathWeight look-up by vertex key.  It facilitates the 
 //  boundary-weight updating that must be applied to all neighbors 
 //  of each newly added element of the pathMap.
 //
 //  Precondition: Vertex vStart must be in the graph.

   map<V,V> pathMap;
   std::set< PathVertex<V,W> > boundarySet;      
   map<V, W> boundaryMap;            
   bool done = false;
   W pathCost(0);                    // Assuming  W=0 makes sense.
   if (vStart == vEnd)
      done = true;
   else // Initialize. Put vStart's neighbors in the boundarySet as triples.
   {
     pathMap[vStart] = vStart;
     map<V,W>* neighbors = findVertex( vStart );
     assert(neighbors);
     std::map<V,W>::iterator p;
     for ( p = neighbors->begin(); p != neighbors->end(); ++p )
     {
       const V& terminus   = p->first;
       W& edgeWeight       = p->second;
       boundarySet.insert( PathVertex<V,W>(terminus, vStart, edgeWeight) );
       boundaryMap[terminus]  = edgeWeight;        
     }
   }

   while (!done && !boundarySet.empty())    
   {                
     // Main loop.  Get boundary vertex of least pathWeight
     //             and add it to the table, updating any other 
     //             boundary vertices as appropriate.

     PathVertex<V,W> pvNearest = popLeast( boundarySet );
     V& vNew  = pvNearest.vertex;
     W& pwNew = pvNearest.pathWeight;
     boundaryMap.erase( vNew );        
     pathMap[vNew] = pvNearest.predecessor;
     if (vNew != vEnd)
     {
	map<V,W>* vNewNeighbors = findVertex( vNew );
	std::map<V,W>::iterator p;
	for ( p = vNewNeighbors->begin(); p != vNewNeighbors->end(); ++p )
	{
           const V& terminus   = p->first;
           if( pathMap.find(terminus) == pathMap.end() ) // if terminus is not 
           {                                             //   in the pathMap...
              W& edgeWeight = p->second;
      	      W oldWeight;             // old weight of terminus in boundaryMap
   	      W npwt = edgeWeight + pwNew;   // npwt = new weight of terminus
		  std::map<V,W>::iterator pbm = boundaryMap.find(terminus);
   	      if ( pbm != boundaryMap.end() )
   	      { 
		oldWeight = pbm->second;
      	        if (npwt < oldWeight) 
   	        {
   	          boundarySet.erase(PathVertex<V,W>( terminus, oldWeight ));
   	          boundarySet.insert( PathVertex<V,W>(terminus, vNew, npwt) );
   	          boundaryMap[terminus] = npwt;
   	        }
   	      }
   	      else 
	      {
   	         boundarySet.insert( PathVertex<V,W>( terminus, vNew, npwt) );
   	         boundaryMap[terminus] = npwt;
	      }
           }
	}
     }
     else
     {
       pathCost = pwNew;
       done = true;
     }
   }
   if (done && vStart != vEnd) // Get the path from the table as a deque.
   {                           
      pathDeque.push_front(vEnd);
      V curr = vEnd;
      do{
	   std::map<V,V>::iterator pps = pathMap.find( curr );
	   assert( pps != pathMap.end() );
	   curr = pps->second;
	   pathDeque.push_front(curr);
      }while( curr != vStart );
   }
   else if (!done)
      cout << "\nNo path between those vertices exists." << endl;
   else
      ;                // vStart == vEnd
   return pathCost;
}

// --- End leastCostPath code ---


#endif