Main Page   Class Hierarchy   Compound List   File List   Compound Members  

mst.h

00001 /****************************************************
00002  *  Bachelor Project:                               *
00003  *  External Memory Minimum Spanning Trees          *
00004  *  by Dominik Schultes <mail@dominik-schultes.de>  *
00005  *                                                  *
00006  *                mst.h                             *
00007  *                                                  *
00008  *  April 13, 2003                                  *
00009  ****************************************************/
00010 
00011 
00012 #ifndef MST_H
00013 #define MST_H
00014 
00015 #include <iostream>
00016 
00017 #include "edgeVector.h"
00018 #include "relabeledEdge.h"
00019 
00023 class MST
00024 {
00026     friend std::ostream& operator<<( std::ostream& os, MST &mst ) {
00027         os << mst.noOfEdges() << std::endl;
00028         for (EdgeCount i=0; i<mst.noOfEdges(); i++)
00029             os << mst._mst[i] << std::endl;
00030         return os;
00031     }
00032     
00033  public:
00035     MST()
00036         : _mst( 0, 0 ), _totalWeight( 0 )
00037         {}
00038     
00040     EdgeCount noOfEdges() const {return _mst.noOfEdges();}
00041 
00043     EdgeWeightBig totalWeight() const {return _totalWeight;}
00044 
00046     void add(const RelabeledEdge &edge);
00047     
00049     void add(const RelabeledEdgeWithoutSource &edge);
00050 
00052     void add(const Edge &edge);
00053     
00054  private:
00055     EdgeVector<Edge,
00056                DS_MST_BLOCK_SIZE,
00057                DS_MST_NO_OF_PAGES,
00058                DS_MST_PAGE_SIZE> _mst;
00059 
00060     EdgeWeightBig _totalWeight;
00061 };
00062 
00063 
00065 inline void MST::add(const RelabeledEdge &edge)
00066 {
00067     // The original source and target indices are restored ...
00068     Edge originalEdge( edge.originalSource(),
00069                        edge.originalTarget(),
00070                        edge.weight() );
00071     
00072     // ... and the original edge is added to the MST.
00073     add( originalEdge );
00074 }
00075 
00076 
00082 inline void MST::add(const RelabeledEdgeWithoutSource &edge)
00083 {
00084     // The original source and target indices are restored ...
00085     Edge originalEdge( edge.originalSource(),
00086                        edge.originalTarget(),
00087                        edge.weight() );
00088     
00089     // ... and the original edge is added to the MST.
00090     add( originalEdge );
00091 }
00092 
00093 
00095 inline void MST::add(const Edge &edge)
00096 {
00097     // add the given edge to the MST
00098     _mst.push_back( edge );
00099     
00100     // update total weight
00101     _totalWeight += edge.weight();
00102 }
00103 
00104 
00105 #endif // MST_H

Generated on Thu Aug 14 15:13:27 2003 for External Memory Minimum Spanning Trees by doxygen1.2.17