00001
00002
00003
00004
00005
00006
00007
00008
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
00068 Edge originalEdge( edge.originalSource(),
00069 edge.originalTarget(),
00070 edge.weight() );
00071
00072
00073 add( originalEdge );
00074 }
00075
00076
00082 inline void MST::add(const RelabeledEdgeWithoutSource &edge)
00083 {
00084
00085 Edge originalEdge( edge.originalSource(),
00086 edge.originalTarget(),
00087 edge.weight() );
00088
00089
00090 add( originalEdge );
00091 }
00092
00093
00095 inline void MST::add(const Edge &edge)
00096 {
00097
00098 _mst.push_back( edge );
00099
00100
00101 _totalWeight += edge.weight();
00102 }
00103
00104
00105 #endif // MST_H