graph_vat.h

这是一个用于数据挖掘的常用算法的模板库（数据挖掘的C++模板库for UNIX)

        }
      }

      if(back_idx==-1) {
        cerr<<"vat.intersect: back_idx not found for edge_vid="<<edge_vid<<" in rmp.size="<<cand_rmp.size()<<endl;
        tt_vat.stop();
        return 0;
      }
    }

    // now determine which of v1's evats need to be copied into cand_vat: 
    // if is_fwd, only evats till edge_vid need be copied
    // else all evats need to be copied

    if(is_fwd)
      rmp_index=cand_pats[0]->rmp_size()-2;
    else
      rmp_index=cand_pats[0]->rmp_size()-1;

    if(cand_pats[0]->label(edge_vid)==cand_pats[0]->label(rvid))
      new_edge_state=0;
    else
      if(is_fwd)
        new_edge_state=(cand_pats[0]->label(edge_vid)>cand_pats[0]->label(rvid))+1;
      else
        new_edge_state=(cand_pats[0]->label(rvid)>cand_pats[0]->label(edge_vid))+1;
      
    CONST_IT it_v1=v1->begin();
    CONST_IT it_v2=v2->begin();
      
    // find a common TID
    while(it_v1!=v1->end() && it_v2!=v2->end()) {
      if(it_v1->first<it_v2->first) {
        it_v1++;
        continue;
      }
  
      if(it_v1->first>it_v2->first) {
        it_v2++;
        continue;
      }
  
      // execution reaches here only if both TIDs are equal
      const EVAT* v1_evat;
      const EVAT* v2_evat=&(it_v2->second[0]);
  
      if(!is_fwd)    
        v1_evat=&(it_v1->second[rmp_index-1]);
      else {
        if(is_fwd_chain)
          v1_evat=&((it_v1->second)[rmp_index-1]);
        else
          v1_evat=&((it_v1->second)[0]);
      }
  
      /// we now have both evats, intersect them ///
      // the intersection routines are expected to fill in the new evat in 
      // cand_vat
      if(is_fwd) {
        tt_fwd_isect.start();
        evat<ALLOC>::template fwd_intersect<ST, VAT, ALLOC>(*v1, *v1_evat, *v2_evat, *cand_vat, 
                                         is_fwd_chain, rmp_index, new_edge_state, 
                                         it_v1-v1->begin(), l2_eq);
        tt_fwd_isect.stop();
        fwd_isect_cnt++;
      }
      else {
        tt_back_isect.start();
        evat<ALLOC>::template back_intersect<ST, VAT, ALLOC>(*v1, *v1_evat, *v2_evat, *cand_vat, back_idx, new_edge_state, it_v1-v1->begin());
        tt_back_isect.stop();
        back_isect_cnt++;
      }

      it_v1++;
      it_v2++;
    }//end while

    cand_sups[0]->set_sup(make_pair(cand_vat->size(), 0));

    VAT** cand_vats=new VAT*;
    cand_vats[0]=cand_vat;
    tt_vat.stop();
    return cand_vats;
  }//end intersect()


    unsigned long int byte_size() const{
      unsigned long int  b_size=0;
      CONST_IT it;
      CONST_EIT eit;
      b_size += sizeof(int);
      for (it = begin(); it!=end();++it){
        b_size += 2*sizeof(int); //tid, number of evats

        for (eit = it->second.begin(); eit != it->second.end(); eit++){
          b_size+=(1*sizeof(int))+eit->byte_size(); // n, e[0], e[1] .. e[n]
        }
      }
      // (VIDS GOES HERE)
      typename VSETS::const_iterator vit;
      b_size += sizeof(int);
      for (vit = begin_v(); vit != end_v(); vit++){
        b_size += sizeof(int);
        typename vector<VSET>::const_iterator vvsetit;
        for (vvsetit=vit->begin(); vvsetit!=vit->end(); vvsetit++){
          b_size += (vvsetit->size()+1) * sizeof(int);
        }//vvsetit
      } //vit
      return b_size;
    }

    void print(){
      int ITSZ=sizeof(int);
      CONST_IT it;
      CONST_EIT eit;
      int tid,evat_n,evat_sz;
      int gvat_sz=_vat.size();
      cout << "size:" <<gvat_sz << endl;
      for (it=begin();it!=end();++it){
        tid=it->first;
        evat_n=it->second.size();
        cout << tid << " " << evat_n << endl;
        for (eit=it->second.begin(); eit!=it->second.end(); ++eit){
          evat_sz = eit->size();
          cout << evat_sz << endl;
          eit->print();
        } //for eit
      }//it
      // Writing _vids goes here.
      typename VSETS::iterator vit;
      int vvsetn = _vids.size();
      cout << "Vids size: " << vvsetn << endl;
      for (vit=begin_v(); vit!=end_v(); vit++){
        typename vector<VSET>::iterator vvsetit;
        int vsetn = vit->size();
        cout << vsetn << endl;
        for (vvsetit=vit->begin(); vvsetit!=vit->end(); vvsetit++){
          typename VSET::iterator vsetit;
          int n = vvsetit->size();
          cout << "- " << n << endl;
          for (vsetit=vvsetit->begin(); vsetit!=vvsetit->end(); vsetit++){
            int v=*vsetit;
            cout << "-- " << v << endl;
          }//vsetit
        }//vvsetit
      }//vit

    }

    //writing a VAT to a binary file
    void write_file(ostream & output) const{
      //ostringstream output;
      int ITSZ=sizeof(int);
      CONST_IT it;
      CONST_EIT eit;
      int tid,evat_n,evat_sz;
      int gvat_sz=_vat.size();
      output.write(reinterpret_cast<const char *>(&gvat_sz), ITSZ);
      for (it=begin();it!=end();++it){
        tid=it->first;
        evat_n=it->second.size();
        output.write(reinterpret_cast<const char *>(&tid), ITSZ);
        output.write(reinterpret_cast<const char *>(&evat_n), ITSZ);
        for (eit=it->second.begin(); eit!=it->second.end(); ++eit){
          evat_sz = eit->size();
          output.write(reinterpret_cast<const char *>(&evat_sz), ITSZ);
          eit->write_file(output);
        } //for eit
      }//it
      // Writing _vids goes here.
      typename VSETS::const_iterator vit;
      int vvsetn = _vids.size();
      output.write(reinterpret_cast<const char *>(&vvsetn), ITSZ);
      for (vit=begin_v(); vit!=end_v(); vit++){
        typename vector<VSET>::const_iterator vvsetit;
        int vsetn = vit->size();
        output.write(reinterpret_cast<const char *>(&vsetn), ITSZ);
        for (vvsetit=vit->begin(); vvsetit!=vit->end(); vvsetit++){
          typename VSET::iterator vsetit;
          int n = vvsetit->size();
          output.write(reinterpret_cast<const char *>(&n), ITSZ);
          for (vsetit=vvsetit->begin(); vsetit!=vvsetit->end(); vsetit++){
            int v=*vsetit;
            output.write(reinterpret_cast<const char *>(&v), ITSZ);
          }//vsetit
        }//vvsetit
      }//vit
      //output_file.write(output.str().c_str(), output.str().size());
    } //end write_file
    
    void read_file (istream & input, unsigned long int size) {
      int ITSZ=sizeof(int);
      int buf_size=size/ITSZ;   
      int *buf = new int[buf_size];
      input.read((char *)buf, (size)); 
      int current=0;
      int vats_size=buf[current++], vats_seen=0;
      while(vats_seen++ < vats_size){
        int tid=buf[current++];
        int evat_n=buf[current++];
        int evats_seen=0;
        RMP_VATS edges;
        while(evats_seen++ < evat_n){
          evat<ALLOC> new_evat;
          int evat_sz=buf[current++];
          while(evat_sz-- > 0){
            int f1, f2;
            f1 = buf[current++];
            f2 = buf[current++];
            new_evat.push_back(make_pair(f1, f2));
          }
          edges.push_back(new_evat);
        }
        _vat.push_back(make_pair(tid, edges));
      }
      //Reading _vids goes here.

      int vids_size=buf[current++], vids_seen=0;
      while(vids_seen++ < vids_size){
        vector <VSET> new_vsetv;
        int vsetv_n=buf[current++];
        int vsets_seen=0;
        while(vsets_seen++ < vsetv_n){
          VSET new_vset;
          int vset_sz=buf[current++];
          while(vset_sz-- > 0){
            int i = buf[current++];
            new_vset.insert(i);
          } // evat_sz
          new_vsetv.push_back(new_vset);
        }//vsets_seen
        _vids.push_back(new_vsetv);
      }//vids_seen

      //this->print();
      input.clear();
      delete [] buf;
    } //read_file

  /** Returns true if vid occurs in any of the offset-th vids in tid-th vat */
  bool is_new_vertex(const int& vid, const int& tid, const int& offset) const {
    if(_vids[tid][offset].find(vid)==_vids[tid][offset].end()) {
      return true;
    }
    return false;
  }//end is_new_vertex()


  friend class evat<ALLOC>; // required for intersect functions in evat to work
  
 private:
  GVAT _vat;
  VSETS _vids;

}; //end class vat for graphs


template<typename PP, typename MP, template <typename> class ALLOC, template<typename, typename> class ST>
  ostream& operator<< (ostream& ostr, const vat<PP, MP, ALLOC, ST>* v) {
  typename vat<PP, MP, ALLOC, ST>::CONST_IT it;
  typename vat<PP, MP, ALLOC, ST>::RMP_VATS::const_iterator rit;

  ostr<<"VAT:"<<endl;
  for(it=v->begin(); it!=v->end(); it++) {
    ostr<<"tid="<<it->first<<endl;
    for(rit=it->second.begin(); rit!=it->second.end(); rit++)
      ostr<<*rit<<endl;
  }

  // These lines print out the vid-sets
  typename vat<PP, MP, ALLOC, ST>::VSETS::const_iterator vit1;
  // typename vector<typename vat<PP, MP, ALLOC, ST>::VSET, ALLOC<typename vat<PP, MP, ALLOC, ST>::VSET> >::const_iterator vit2;
  typename vector<typename vat<PP, MP, ALLOC, ST>::VSET >::const_iterator vit2;
  typename vat<PP, MP, ALLOC, ST>::VSET::const_iterator vit3;

  ostr<<"Vertices are"<<endl;
  for(vit1=v->begin_v(), it=v->begin(); vit1!=v->end_v(); vit1++, it++) {
    ostr<<"tid="<<it->first<<endl;
    for(vit2=vit1->begin(); vit2!=vit1->end(); vit2++) {
      for(vit3=vit2->begin(); vit3!=vit2->end(); vit3++)
        ostr<<*vit3<<" ";
        ostr<<endl;
    }
  }
      
  return ostr;
}//operator<< for vat*

#endif