graph.h

adaboost code in matlab

/* File graph.h    Graph<V, W=int> class template header file
   [e-mail]
*/

#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 <map>
#include <set>
#include <deque>
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <utility>
#include <sstream>
#include <cassert>

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 V, class W=int>
class Graph : public map<V, map<V, W> >
{
   /*  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<V,V>& );           // 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<V,W>*  findVertex( const V& ) const; // returns 0 if not found.
    void insertVertex(const V&);                 
    void removeVertex(const V&);

    W leastCostPath(const V&, const V&, deque<V>&) const;   
      // For efficiency, the path is put in a reference argument.

    void erase() {clear();}           
    bool empty() const { return std::map<V, std::map<V,W> >::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<V>&);     

  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<V,W>& );
     void  print( std::ostream& );

};
#include "graph.cpp"
#endif