www.pudn.com > AdaBoost_weaklearner_1.rar > graph.h


/* File graph.h    Graph class template header file 
   shinnerl@ucla.edu 
*/ 
 
#ifndef GRAPH_H 
#define GRAPH_H 
 
#pragma warning(disable : 4786)    // Prevents 500 spurious warnings  
#pragma warning(disable : 4503)    //  in MS Visual C++ 6.0. 
 
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
 
using std::map; 
using std::set; 
using std::deque; 
using std::pair; 
using std::ostream; 
using std::istream; 
using std::string; 
using std::stringstream; 
 
template  
class Graph : public map > 
{ 
   /*  Undirected, weighted graph representation. 
 
       A graph as implemented here "is a" map of adjacency maps. 
       That is, each vertex v_i is associated with a collection of  
       (vertex,weight) pairs,  
              { (v_j, w_ij) : j = i_1, i_2, ..., i_k }, 
       where v_i1, v_i2, ..., v_ik are the neighboring vertices of v_i. 
       Pair (v_j, w_ij) represents an edge of weight w_ij joining  
       v_i and v_j. 
 
       Notice the symmetry in the graph's representation.  
       If (v_j, w_ij) is stored in v_i's adjacency map, then  
       (v_i, w_ji) is stored in v_j's adjacency map, and w_ij == w_ji. 
 
       For input/output format, see sample file "g1.dat."  Note 
       the delimiting spaces. 
 
       The automatically generated essential member functions  
       ( default constructor, copy constructor, destructor, operator= )  
       are sufficient. 
   */ 
 
  public: 
    bool isSymmetric( pair& );           // Verify "undirectedness" 
                                              //  Pass back offending edge 
    W*   findEdge(const V&, const V&) const;  // returns 0 if not found. 
    void setEdge(const V&, const V&, const W&); 
    void removeEdge(const V&, const V&); 
 
    std::map*  findVertex( const V& ) const; // returns 0 if not found. 
    void insertVertex(const V&);                  
    void removeVertex(const V&); 
 
    W leastCostPath(const V&, const V&, deque&) const;    
      // For efficiency, the path is put in a reference argument. 
 
    void erase() {clear();}            
    bool empty() const { return std::map >::empty(); } 
 
    friend std::istream& operator>>( std::istream& is, Graph& G)  
      { G.read(is);  return is; }      // Includes symmetry check. 
    friend std::ostream& operator<<( std::ostream& os, Graph& G ) 
      { G.print(os); return os; } 
 
  // Optional exercises: 
  //  int maxDegree() const; // Number of neighbors of the most connected vertex 
  //  void getComponent(const V&, set&);      
 
  struct Error{                    // For exception handling. 
     string message; 
     Error( const string& m0 ) : message(m0) {} 
     operator string() const { return message; }  // conversion operator. 
  }; 
 
  protected: 
     void  read ( std::istream& );     
     void  getAdjacencyMap( std::istream&,  std::map& ); 
     void  print( std::ostream& ); 
 
}; 
#include "graph.cpp" 
#endif