graph_vat.h

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

/*
 *  Copyright (C) 2005 M.J. Zaki <[e-mail]> Rensselaer Polytechnic Institute
 *  Written by [e-mail]
 *  Updated by [e-mail], [e-mail], [e-mail]
 *
 *  This program is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU General Public License
 *  as published by the Free Software Foundation; either version 2
 *  of the License, or (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License along
 *  with this program; if not, write to the Free Software Foundation, Inc.,
 *  59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
 */
#ifndef _GRAPH_VAT_H
#define _GRAPH_VAT_H

#include <ext/hash_set>
#include "graph_evat.h"
#include "pattern.h"
#include "generic_classes.h"
#include "typedefs.h"

//#include "pat_support.h"


time_tracker tt_vat, tt_fwd_isect, tt_back_isect;
int fwd_isect_cnt=0;
int back_isect_cnt=0;


template<typename PP, typename MP, template <typename> class ALLOC, 
         template<typename, typename> class ST>
class vat<GRAPH_PROP, V_Fk1_MINE_PROP, ALLOC, ST>;

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);

/** Graph vat class */
// NOTE: ST should model a vector, else this class shall not compile
// vectors are used to make the design efficient

/**
 * \brief Graph VAT class by partial specialization of the generic VAT class.
 *
 * In this partial specialization, PP is fixed to undirected (undirected graph property),
 * MP is fixed to Fk X F1 and vert_mine (vertical mining with FK X F1),
 * ST is the VAT storage type. For graph, ST should model a vector, else this
 * shall not compile.
 */

template<typename PP, typename MP, template <typename> class ALLOC, template<typename, typename> class ST>
class vat<GRAPH_PROP, V_Fk1_MINE_PROP, ALLOC, ST>
{
 public:

  typedef evat<ALLOC> EVAT;
  typedef vat<GRAPH_PROP, V_Fk1_MINE_PROP, ALLOC, ST> VAT;
  typedef ST<EVAT, ALLOC<EVAT> > RMP_VATS;
  typedef ST<pair<int, RMP_VATS>, ALLOC<pair<int, RMP_VATS> > > GVAT;
  /**< a graph-vat is a collection of evats for each vertex, where each evat 
     must have same size. This collection of evats is organized itself as 
     ST<EVAT> evats, and it holds evats of all edges on right most path 
     of cand_pat */
  typedef HASHNS::hash_set<int, HASHNS::hash<int>, std::equal_to<int>, ALLOC<int> > VSET; /**< Set of vertex ids denoting exactly 
                                                                                               one of this graph's occurence in 
                                                                                               the dataset */
  typedef vector<vector<VSET, ALLOC<VSET> >, ALLOC<vector<VSET, ALLOC<VSET> > > > VSETS; /**< This graph can occur several times 
                                                                                              in one graph in the dataset, and in 
                                                                                              several graphs (tids) as well */
  typedef typename GVAT::const_iterator CONST_IT;
  typedef typename GVAT::iterator IT;
  typedef typename ST<EVAT, ALLOC<EVAT> >::const_iterator CONST_EIT;
  typedef typename VSETS::iterator VS_IT;
  typedef typename VSETS::const_iterator CONST_VS_IT;

  void* operator new(size_t size) {
    ALLOC<VAT> v;
    return v.allocate(size);
  }

  void  operator delete(void *p, size_t size) {
    if (p) {
      ALLOC<VAT> v;
      v.deallocate(static_cast<VAT*> (p), size);
    }
  }

  IT begin() { 
    return _vat.begin();
  }
  CONST_IT begin() const { 
    return _vat.begin();
  }
  IT end() { 
    return _vat.end();
  }
  CONST_IT end() const { 
    return _vat.end();
  }

  VS_IT begin_v() { 
    return _vids.begin();
  }
  CONST_VS_IT begin_v() const { 
    return _vids.begin();
  }
  VS_IT end_v() { 
    return _vids.end();
  }
  CONST_VS_IT end_v() const { 
    return _vids.end();
  }

  friend ostream& operator<< <>(ostream&, const VAT*);

  int size() const { 
    return _vat.size();
  }

  bool empty() const { 
    return _vat.empty();
  }

  const pair<int, ST<EVAT, ALLOC<EVAT> > >& back() const { 
    return _vat.back();
  }

  void insert_occurrence_tid(const int& tid, const pair<int, int>& new_occurrence) {
    ST<EVAT, ALLOC<EVAT> > new_evats;
    evat<ALLOC> new_evat;
    new_evat.push_back(new_occurrence);
    new_evats.push_back(new_evat);
    _vat.push_back(make_pair(tid, new_evats));
  }//insert_new_occurrence()


  void insert_occurrence_evat(const pair<int, int>& new_occurrence) {
    evat<ALLOC> new_evat;
    new_evat.push_back(new_occurrence);
    _vat.back().second.push_back(new_evat);
  }//insert_occurrence_evat()

  void insert_occurrence(const pair<int, int>& new_occurrence) {
    _vat.back().second.back().push_back(new_occurrence);
  }


  void insert_vid_hs(const int& vid) { 
    VSET vs;
    vs.insert(vid);
    _vids.back().push_back(vs);
  }


  void insert_vid(const int& vid) { 
    _vids.back().back().insert(vid);
  }


  void insert_vid_tid(const int& vid) {
    VSET vset;
    vset.insert(vid);
    vector<VSET, ALLOC<VSET> > vsets;
    vsets.push_back(vset);
    _vids.push_back(vsets);      
  }//insert_vid_tid()


  void copy_vats(const pair<int, ST<evat<ALLOC>, ALLOC<evat<ALLOC> > > >& v1, const int& offset, const int& sz, bool swap=0) {
    int i;
    for(i=0; i<sz; i++)
      if(swap)
        _vat.back().second[i].push_back(make_pair(v1.second[i][offset].second, v1.second[i][offset].first));
      else
        _vat.back().second[i].push_back(v1.second[i][offset]);
  }//copy_vats()
  

  void copy_vats_tid(const pair<int, ST<evat<ALLOC>, ALLOC<evat<ALLOC> > > >& v1, const int& offset, const int& sz, bool swap=0) {
    int i;
    ST<EVAT, ALLOC<EVAT> > new_entry;
  
    for(i=0; i<sz; i++) {
      evat<ALLOC> tmp_evat;
      if(swap)
        tmp_evat.push_back(make_pair(v1.second[i][offset].second, v1.second[i][offset].first));
      else
        tmp_evat.push_back(v1.second[i][offset]);
        new_entry.push_back(tmp_evat);
    }
    _vat.push_back(make_pair(v1.first, new_entry));
  }//copy_vats_tid()


  void copy_vids_hs(const VSET& v1_vids) {
    
    VSET vs;
    typename VSET::const_iterator it;
    for(it=v1_vids.begin(); it!=v1_vids.end(); it++)
      vs.insert(*it);
    _vids.back().push_back(vs);
  }//copy_vids()


  void copy_vids_tid(const VSET& v1_vids) {
    VSET vset;
    typename VSET::const_iterator it;
    for(it=v1_vids.begin(); it!=v1_vids.end(); it++)
      vset.insert(*it);
    vector<VSET, ALLOC<VSET> > vsets;
    vsets.push_back(vset);
    _vids.push_back(vsets);
  }//copy_vids_tid()


  /** Main vat intersection function;
      It also populates support argument passed */
  // NOTE: only one candidate is generated in a FkxF1 join of graphs, 
  // hence only the first value in cand_pats should be inspected
  template<typename PATTERN, typename PAT_SUP>
  static VAT** intersection(const VAT* v1, const VAT* v2, PAT_SUP** cand_sups, PATTERN** cand_pats, bool) {
#ifdef PRINT
    cout<<"VAT intersection entered with v1="<<v1<<endl;
    cout<<"v2="<<v2<<endl;
#endif

    tt_vat.start();

    // How it works
    // 1. determine which edge of v1 is being extended and get its evat1
    // 2. determine right-most-path of candidate (rmp)
    // 3. find common occurrences in v2 and evat1
    // 4. copy these common occurrences to new_vat, and also copy evats in 
    // rmp corresponding to these common occurrences

    VAT* cand_vat=new VAT;
    bool is_fwd;
    bool is_fwd_chain=false; // flag to denote whether edge appended by 
    // intersection is at the root (which is when flag=0)
    bool l2_eq=(cand_pats[0]->size()==3) && (cand_pats[0]->label(0)==cand_pats[0]->label(1)); // special case in evat intersection for L-2 with first edge 
    // with equal vertex labels

    int rmp_index; // index of last vid on rmp common to cand_pat and its 
    // parent's rmp
    int new_edge_state=-1; // flag to denote if the new edge to be added has 
    // same labeled vertices, of the form A-A (flag=0); or is of the form 
    // A-B (flag=1); or is not canonical at all, of the form B-A (flag=2).
    // evat intersection needs to take this into account

    int rvid=cand_pats[0]->rmost_vid();
    int edge_vid=-1; // vid of the other vertex (other than rvid) connected 
    // to rvid as to form the new edge

    typename PATTERN::CONST_EIT_PAIR eit_p=cand_pats[0]->out_edges(rvid);
    int back_idx=-1; // this is used only for back extensions. It holds the 
    // index of edge_vid in rmp of cand_pats[0]

    if(eit_p.second-eit_p.first>1)
      is_fwd=false; // last edge was fwd edge only if outdegree of last vid=1
    else
      is_fwd=true;

    // get other vertex's vid
    if(is_fwd) {
      edge_vid=eit_p.first->first;
      if(!edge_vid) // rvid is attached to the root
        is_fwd_chain=0;
      else
        is_fwd_chain=1;
    }
    else {
      //prev_vid=eit_p.first->first;
      eit_p.second--;
      edge_vid=eit_p.second->first;

      /// now determine the index of edge_vid on rmp of candidate. This is 
      /// used by back_intersect.
      // TO DO: this is currently a linear search through rmp, is there a 
      // more efficient way??
      const typename PATTERN::RMP_T& cand_rmp=cand_pats[0]->rmost_path();
      for(unsigned int i=0; i<cand_rmp.size(); i++) {
        if(cand_rmp[i]==edge_vid) {
          back_idx=i;
          break;