Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

DCGraph< T > Class Template Reference

#include <DCGraph.h>

List of all members.

Public Member Functions

 DCGraph ()
virtual ~DCGraph ()
DCVertex< T > * Find (T *)
bool AddVertex (T *)
bool AddEdge (T *, T *)
int GetNVerts () const
int GetNEdges () const
float GetSummedMetric () const
float GetXSummedMetric () const
float GetYSummedMetric () const
float GetMaxMetric () const
float GetSummedZ () const
DCVertex< T > * GetFirst ()
vector< float > GetAllWeights ()
vector< float > GetAllZ ()
void NewFirst (DCVertex< T > *nf)
virtual void Print (Option_t *t="") const
virtual void Draw (Option_t *t="")
vector< DCGraph< T > * > FindAllMinSpan (float maxmetric=0., float minz=0., float maxlowzmetric=0.)
DCGraph< T > * FindMinSpan (float maxmetric=0., float minz=0., float maxlowzmetric=0.)
bool AddClosestNode (vector< T > &out, float maxmetric=0., float minz=0., float maxlowzmetric=0.)
vector< T > Complement (DCGraph< T > *)
DCGraph< T > * GraphMaxHits (int nhits)

Private Attributes

DCVertex< T > * first
int nverts
int nedges
float summetric
float sumxmetric
float sumymetric
float maxmetric

template<class T>
class DCGraph< T >

Constructor & Destructor Documentation

template<class T>
DCGraph< T >::DCGraph (   )  [inline]
 

Definition at line 22 of file DCGraph.h.

References DCGraph< T >::first, DCGraph< T >::maxmetric, DCGraph< T >::nedges, DCGraph< T >::nverts, DCGraph< T >::summetric, DCGraph< T >::sumxmetric, and DCGraph< T >::sumymetric.

00022             {first=0;nverts=0;nedges=0;
00023              summetric=0.;sumxmetric=0.;sumymetric=0.;maxmetric=0.;}

template<class T>
virtual DCGraph< T >::~DCGraph (   )  [inline, virtual]
 

Definition at line 25 of file DCGraph.h.

References DCGraph< T >::first.

00025 { if(first!=0) {delete first; first=0;}}

Member Function Documentation

template<class T>
bool DCGraph< T >::AddClosestNode (  vector< T > &  out,
float  maxmetric = 0.,
float  minz = 0.,
float  maxlowzmetric = 0.
) 
 

Definition at line 206 of file DCGraph.h.

References DCGraph< T >::AddEdge(), DCGraph< T >::AddVertex(), DCGraph< T >::Find(), DCVertex< T >::GetData(), DCVertex< T >::GetNextVertex(), and vout.

Referenced by DCGraph< T >::FindMinSpan().

00210 {
00211 //   cout<<"In DCGraph::AddClosestNode"<<endl;
00212    float minmetric=-1.;
00213    //   DCVertex<T> *closestin=0;
00214    //   DCVertex<T> *closestout=0;
00215    T *closestin=0;
00216    T *closestout=0;
00217    int closestoutindex=0;
00218    DCVertex<T> *vin=first;
00219    while(vin!=0){      
00220      //      DCVertex<T> *vout=out->GetFirst();
00221      for(unsigned int c=0;c<out.size();c++){
00222        T *vout = &out[c];
00223        if(Find(vout)!=0){
00224          continue;
00225        }
00226        float m = ((*vin->GetData())-(*vout)).abs();
00227        float x,y,z;
00228        vout->GetData(x,y,z);
00229        if(minmetric<0){
00230          if(z<minz&&m>maxlowzmetric&&maxlowzmetric!=0){     
00231          }
00232          else if(m>maxmetric&&maxmetric!=0){
00233          }
00234          else{   
00235            minmetric = m;
00236            closestout = vout;
00237            closestin = vin->GetData();
00238            closestoutindex=c;
00239          }
00240        }
00241        if(m<minmetric){
00242          if(z<minz&&m>maxlowzmetric&&maxlowzmetric!=0){     
00243          }
00244          else if(m>maxmetric&&maxmetric!=0){
00245          }
00246          else{
00247            minmetric = m;
00248            closestout = vout;
00249            closestin = vin->GetData();
00250            closestoutindex=c;
00251          }
00252        }
00253      }
00254      if(vin->GetNextVertex()){
00255        vin=vin->GetNextVertex();
00256      }
00257      else{
00258        vin=0;
00259      }
00260    }
00261    
00262    if(closestin==0||closestout==0){
00263      //      cout<<"couldnt find a closest node returning false"<<endl;
00264      return false;
00265    }
00266 
00267    else{
00268      //      cout<<"Adding ";
00269      //      closestout->Print();
00270      //      cout<<"with metric "<<minmetric<<endl;
00271      AddVertex(closestout);
00272      AddEdge(closestin,closestout);
00273      //     vector<T>::iterator vi(&(out[closestoutindex]));
00274      out.erase(out.begin()+closestoutindex);
00275      return true;
00276    }
00277 
00278    return false;
00279 }

template<class T>
bool DCGraph< T >::AddEdge (  T *  ,
T * 
) 
 

Definition at line 114 of file DCGraph.h.

References DCVertex< T >::ConnectTo(), DCGraph< T >::Find(), DCVertex< T >::GetFirstEdge(), DCGraph< T >::maxmetric, DCGraph< T >::nedges, DCGraph< T >::summetric, DCGraph< T >::sumxmetric, and DCGraph< T >::sumymetric.

Referenced by DCGraph< T >::AddClosestNode().

00114                                                            {
00115   //   cout<<"In DCGraph::AddEdge"<<endl;
00116   // find the pointer to the end vertex
00117    DCVertex<T> *vEnd = Find(End);
00118 
00119   // if the vertex is not in the graph, cannot add the edge
00120   if (vEnd == 0) return false;
00121 
00122   // find the pointer to the start vertex
00123   DCVertex<T> *vBegin = Find(Begin);
00124 
00125   // if the vertex is not in the graph, cannot add the edge
00126   if (vBegin == 0) return false;
00127 
00128   // connect the start vertex to the end one
00129   summetric+=vBegin->ConnectTo(vEnd);
00130   if(vBegin->GetFirstEdge()->GetMetric()>maxmetric){
00131      maxmetric=vBegin->GetFirstEdge()->GetMetric();
00132   }
00133   sumxmetric+=vBegin->GetFirstEdge()->GetXMetric();
00134   sumymetric+=vBegin->GetFirstEdge()->GetYMetric();
00135 
00136   nedges++;
00137   return true;
00138 }

template<class T>
bool DCGraph< T >::AddVertex (  T *   ) 
 

Definition at line 95 of file DCGraph.h.

References DCGraph< T >::Find(), DCGraph< T >::first, and DCGraph< T >::nverts.

Referenced by DCGraph< T >::AddClosestNode(), MSTCalcAna::FindAllGraphs(), DCGraph< T >::FindAllMinSpan(), DCGraph< T >::FindMinSpan(), and DCGraph< T >::GraphMaxHits().

00095                                                        { 
00096   // checking if the vertex is already in the graph
00097   // if it is, it cannot be added again 
00098   //   cout<<"In DCGraph::AddVertex"<<endl;
00099   if (Find(theData) != 0 )
00100     return false;
00101 
00102   // allocate memory for new vertex with data theData,
00103   // make it point to the previous first vertex
00104   DCVertex<T> *newVertex = new DCVertex<T>(theData, first);
00105   // make the new vertex the first one in the list of vertexes
00106   first = newVertex;
00107   nverts++;
00108   return true;
00109 }

template<class T>
vector< T > DCGraph< T >::Complement (  DCGraph< T > *   ) 
 

Definition at line 300 of file DCGraph.h.

References DCGraph< T >::Find(), DCVertex< T >::GetData(), DCGraph< T >::GetFirst(), DCVertex< T >::GetNextVertex(), and vout.

Referenced by DCGraph< T >::FindAllMinSpan(), and DCGraph< T >::FindMinSpan().

00301 {
00302 //   cout<<"In DCGraph::Complement"<<endl;
00303    vector<T> vout;
00304    DCVertex<T> *v = g->GetFirst();
00305    while(v!=0){
00306       if(Find(v->GetData())==0){
00307          vout.push_back(*(v->GetData()));
00308       }
00309       v=v->GetNextVertex();
00310    }
00311    return vout;
00312 }

template<class T>
void DCGraph< T >::Draw (  Option_t *  t = ""  )  [virtual]
 

Definition at line 154 of file DCGraph.h.

References DCVertex< T >::DrawGraph(), DCGraph< T >::first, DCVertex< T >::GetData(), and DCVertex< T >::GetNextVertex().

00155 {
00156 //   TCanvas *pad = (TCanvas *)gROOT->GetSelectedPad();
00157    TCanvas *pad = (TCanvas *)(gPad);
00158    if(pad==0){
00159 //      cout<<"no pad selected, making new"<<endl;
00160       pad = new TCanvas();
00161    }
00162 //   cout<<"Drawing to canvas "<<pad->GetName()<<endl;
00163    pad->Clear();
00164    
00165    float x0=0.;
00166    float y0=0.;
00167    float z0=0.;
00168    first->GetData()->GetData(x0,y0,z0);
00169    DCVertex<T> *v=first;
00170    while(v!=0){
00171       float x=0;
00172       float y=0;
00173       float z=0;
00174       v->GetData()->GetData(x,y,z);
00175       if(x<x0){
00176         x0=x;
00177         y0=y;
00178       }
00179       v=v->GetNextVertex();
00180    }
00181 
00182 
00183    //   eventvertex->GetData()->GetData(x0,y0,z0);
00184    pad->DrawFrame(x0-140,y0-164,x0+700,y0+164);
00185    if (first == 0) 
00186       cout << "Graph has no vertexes " << endl;
00187    else{
00188       first->DrawGraph();
00189    }
00190 }

template<class T>
DCVertex<T>* DCGraph< T >::Find (  T *   ) 
 

Referenced by DCGraph< T >::AddClosestNode(), DCGraph< T >::AddEdge(), DCGraph< T >::AddVertex(), DCGraph< T >::Complement(), and DCGraph< T >::FindAllMinSpan().

template<class T>
vector< DCGraph< T > * > DCGraph< T >::FindAllMinSpan (  float  maxmetric = 0.,
float  minz = 0.,
float  maxlowzmetric = 0.
) 
 

Definition at line 314 of file DCGraph.h.

References DCGraph< T >::AddVertex(), DCGraph< T >::Complement(), DCGraph< T >::Find(), and DCGraph< T >::FindMinSpan().

Referenced by MSTCalcAna::FindAllGraphs().

00315 {
00316 //   cout<<"In DCGraph::FindAllMinSpan"<<endl;
00317    vector<DCGraph<T> *> trees;
00318    DCGraph<T> *msg = FindMinSpan(maxmetric,minz,maxlowzmetric);
00319    trees.push_back(msg);
00320    vector<T> out=msg->Complement(this);
00321    while(out.size()>0){
00322 //      cout<<"DCGraph::FindAllMinSpan() found "<<out.size()
00323 //        <<" vertices out"<<endl;
00324       DCGraph<T> ng;
00325       for(unsigned int i=0;i<out.size();i++){
00326 //       cout<<"adding vertices to ng"<<endl;
00327          ng.AddVertex(&out[i]);
00328       }
00329       DCGraph<T> *msg2 = ng.FindMinSpan(maxmetric,minz,maxlowzmetric);
00330 //      cout<<"Printing new msg2"<<endl;
00331 //      msg2->Print();
00332 //      cout<<"***"<<endl;
00333       //make newout vector
00334       vector<T> newout=out;
00335       out.clear();
00336 //      cout<<"size of out now is "<<out.size()<<endl;
00337       for(unsigned int i=0;i<newout.size();i++){
00338          if(msg2->Find(&newout[i])==0){
00339 //          cout<<"found a vertex in out that wasn't in the new tree"<<endl;
00340 //          newout[i].Print();
00341             out.push_back(newout[i]);
00342          }
00343       }
00344 
00345       trees.push_back(msg2);
00346 //      cout<<"Found a new minspan, starting loop again."<<endl;
00347 //      cout<<"Size of trees now: "<<trees.size()<<endl;
00348    }
00349 //   cout<<"all done with AllMinSpan"<<endl;
00350    return trees;
00351 }

template<class T>
DCGraph< T > * DCGraph< T >::FindMinSpan (  float  maxmetric = 0.,
float  minz = 0.,
float  maxlowzmetric = 0.
) 
 

Definition at line 192 of file DCGraph.h.

References DCGraph< T >::AddClosestNode(), DCGraph< T >::AddVertex(), DCGraph< T >::Complement(), and DCVertex< T >::GetData().

Referenced by DCGraph< T >::FindAllMinSpan(), and DCGraph< T >::GraphMaxHits().

00195 {
00196 //   cout<<"In DCGraph::FindMinSpan"<<endl;
00197    DCGraph<T> *msg = new DCGraph<T>();
00198    
00199    DCVertex<T> *v=first;
00200    msg->AddVertex(v->GetData());
00201    vector<T> out = msg->Complement(this);
00202    while(msg->AddClosestNode(out, maxmetric, minz, maxlowzmetric));
00203    return msg;
00204 }

template<class T>
vector< float > DCGraph< T >::GetAllWeights (   ) 
 

Definition at line 402 of file DCGraph.h.

References DCVertex< T >::GetFirstEdge(), DCEdge< T >::GetMetric(), DCEdge< T >::GetNext(), and DCVertex< T >::GetNextVertex().

Referenced by MSTCalcAna::ComputeGraphQuantities().

00403 {
00404    multiset<float> w;
00405    DCVertex<T> *v = first;
00406    DCEdge<T> *e;
00407    while(v!=0){
00408 //      cout<<"on vertex "<<endl;
00409 //     v->Print();
00410       e = v->GetFirstEdge();
00411       while(e!=0){
00412          w.insert(e->GetMetric());
00413 //       cout<<"current edge metric is "<<e->GetMetric()<<endl;
00414          e = e->GetNext();
00415 //       if(e!=0){
00416 //          e->Print();
00417 //       }
00418 //       else{
00419 //          cout<<"edge zero, going on to next vertex"<<endl;
00420 //       }
00421       }
00422       v=v->GetNextVertex();
00423    }
00424 
00425    multiset<float>::iterator it(w.begin());
00426    vector<float> vw;
00427    while(it!=w.end()){
00428 //      cout<<*it<<endl;
00429       vw.push_back(*it);
00430       it++;
00431    }
00432 
00433    return vw;
00434 
00435 }

template<class T>
vector< float > DCGraph< T >::GetAllZ (   ) 
 

Definition at line 438 of file DCGraph.h.

References DCVertex< T >::GetData(), and DCVertex< T >::GetNextVertex().

Referenced by MSTCalcAna::ComputeGraphQuantities().

00439 {
00440    multiset<float> w;
00441    DCVertex<T> *v = first;
00442    while(v!=0){
00443       float x,y,z;
00444       v->GetData()->GetData(x,y,z);
00445       w.insert(z);
00446       v=v->GetNextVertex();
00447    }
00448 
00449    multiset<float>::iterator it(w.begin());
00450    vector<float> vw;
00451    while(it!=w.end()){
00452 //      cout<<*it<<endl;
00453       vw.push_back(*it);
00454       it++;
00455    }
00456 
00457    return vw;
00458 
00459 }

template<class T>
DCVertex<T>* DCGraph< T >::GetFirst (   )  [inline]
 

Definition at line 37 of file DCGraph.h.

Referenced by DCGraph< T >::Complement(), and MSTCalcAna::GraphLoop().

00037 {return first;}

template<class T>
float DCGraph< T >::GetMaxMetric (   )  const [inline]
 

Definition at line 35 of file DCGraph.h.

00035 {return maxmetric;}

template<class T>
int DCGraph< T >::GetNEdges (   )  const [inline]
 

Definition at line 31 of file DCGraph.h.

00031 {return nedges;}

template<class T>
int DCGraph< T >::GetNVerts (   )  const [inline]
 

Definition at line 30 of file DCGraph.h.

Referenced by MSTCalcAna::ComputeGraphQuantities(), and MSTCalcAna::FindAllGraphs().

00030 {return nverts;}

template<class T>
float DCGraph< T >::GetSummedMetric (   )  const [inline]
 

Definition at line 32 of file DCGraph.h.

Referenced by MSTCalcAna::ComputeGraphQuantities().

00032 {return summetric;}

template<class T>
float DCGraph< T >::GetSummedZ (   )  const
 

Definition at line 281 of file DCGraph.h.

References DCVertex< T >::GetData(), and DCVertex< T >::GetNextVertex().

Referenced by MSTCalcAna::ComputeGraphQuantities(), and DCGraph< T >::Print().

00282 {
00283 //   cout<<"In DCGraph::GetSummedZ"<<endl;
00284    float sumz=0;
00285    if(this==0){
00286       return sumz;
00287    }
00288    DCVertex<T> *vert = first;
00289    while(vert){
00290       float x=0;
00291       float y=0;
00292       float z=0;
00293       vert->GetData()->GetData(x,y,z);
00294       sumz+=z;
00295       vert=vert->GetNextVertex();
00296    }
00297    return sumz;
00298 }

template<class T>
float DCGraph< T >::GetXSummedMetric (   )  const [inline]
 

Definition at line 33 of file DCGraph.h.

00033 {return sumxmetric;}

template<class T>
float DCGraph< T >::GetYSummedMetric (   )  const [inline]
 

Definition at line 34 of file DCGraph.h.

00034 {return sumymetric;}

template<class T>
DCGraph< T > * DCGraph< T >::GraphMaxHits (  int  nhits  ) 
 

Definition at line 353 of file DCGraph.h.

References DCGraph< T >::AddVertex(), DCGraph< T >::FindMinSpan(), DCVertex< T >::GetData(), DCVertex< T >::GetNextVertex(), max, and DCGraph< T >::nverts.

Referenced by MSTCalcAna::ComputeGraphQuantities().

00354 {
00355 
00356    if(nhits==0){
00357       return 0;
00358    }
00359 
00360    DCVertex<T> *max[100]={0};
00361    float mz[100]={0.};
00362    int N=nhits;
00363    if(nverts<N){
00364       N=nverts;
00365    }
00366    if(N>100){
00367       N=100;
00368    }
00369 //   cout<<"Going to look for "<<N<<" biggest hits"<<endl;
00370 
00371    DCVertex<T> *vin=first;
00372    while(vin!=0){
00373       float x=0.;
00374       float y=0.;
00375       float z=0.;
00376       vin->GetData()->GetData(x,y,z);
00377       for(int i=0;i<N;i++){
00378          if(z>mz[i]){
00379             for(int j=N-1;j>i;j--){
00380                max[j]=max[j-1];
00381                mz[j]=mz[j-1];
00382             }
00383             max[i]=vin;
00384             mz[i]=z;
00385             break;
00386          }
00387       }
00388       vin=vin->GetNextVertex();
00389    }
00390 
00391    DCGraph<T> g;
00392    for(int i=0;i<N;i++){
00393       g.AddVertex(max[i]->GetData());
00394 //      cout<<"Adding vertex to new graph"<<endl;
00395 //      max[i]->GetData()->Print();
00396    }
00397 
00398    return g.FindMinSpan();
00399       
00400 }

template<class T>
void DCGraph< T >::NewFirst (  DCVertex< T > *  nf  )  [inline]
 

Definition at line 41 of file DCGraph.h.

References DCGraph< T >::first.

00041 { first=nf; }

template<class T>
void DCGraph< T >::Print (  Option_t *  t = ""  )  const [virtual]
 

Definition at line 141 of file DCGraph.h.

References DCGraph< T >::first, DCGraph< T >::GetSummedZ(), DCGraph< T >::nedges, DCGraph< T >::nverts, DCVertex< T >::PrintGraph(), DCGraph< T >::summetric, DCGraph< T >::sumxmetric, and DCGraph< T >::sumymetric.

00141                                                               {
00142    cout<<"Tree has "<<nverts<<" Vertices and "<<nedges<<" Edges"<<endl;
00143    cout<<"Summed metric is "<<summetric
00144        <<" and SummedZ is "<<GetSummedZ()<<endl;
00145    cout<<"SummedXmetric is "<<sumxmetric
00146        <<" and SummedYmetric is "<<sumymetric<<endl;
00147 
00148   if (first == 0) 
00149     cout << "Graph has no vertexes " << endl;
00150   else
00151     first->PrintGraph();
00152 }

Member Data Documentation

template<class T>
DCVertex<T>* DCGraph< T >::first [private]
 

Definition at line 60 of file DCGraph.h.

Referenced by DCGraph< T >::AddVertex(), DCGraph< T >::DCGraph(), DCGraph< T >::Draw(), DCGraph< T >::NewFirst(), DCGraph< T >::Print(), and DCGraph< T >::~DCGraph().

template<class T>
float DCGraph< T >::maxmetric [private]
 

Definition at line 69 of file DCGraph.h.

Referenced by DCGraph< T >::AddEdge(), and DCGraph< T >::DCGraph().

template<class T>
int DCGraph< T >::nedges [private]
 

Definition at line 65 of file DCGraph.h.

Referenced by DCGraph< T >::AddEdge(), DCGraph< T >::DCGraph(), and DCGraph< T >::Print().

template<class T>
int DCGraph< T >::nverts [private]
 

Definition at line 64 of file DCGraph.h.

Referenced by DCGraph< T >::AddVertex(), DCGraph< T >::DCGraph(), DCGraph< T >::GraphMaxHits(), and DCGraph< T >::Print().

template<class T>
float DCGraph< T >::summetric [private]
 

Definition at line 66 of file DCGraph.h.

Referenced by DCGraph< T >::AddEdge(), DCGraph< T >::DCGraph(), and DCGraph< T >::Print().

template<class T>
float DCGraph< T >::sumxmetric [private]
 

Definition at line 67 of file DCGraph.h.

Referenced by DCGraph< T >::AddEdge(), DCGraph< T >::DCGraph(), and DCGraph< T >::Print().

template<class T>
float DCGraph< T >::sumymetric [private]
 

Definition at line 68 of file DCGraph.h.

Referenced by DCGraph< T >::AddEdge(), DCGraph< T >::DCGraph(), and DCGraph< T >::Print().

The documentation for this class was generated from the following file:
Generated on Mon Feb 15 11:09:05 2010 for loon by  doxygen 1.3.9.1