union-find.h

聚类分析程序 k-means 编译环境 gcc/stl

/*
  
  Text Clustering  Copyright (C) 2004 Debora "Barbara" Donato, Antonio Gulli

  This library is free software; you can redistribute it and/or modify it 
  under the terms of the GNU Lesser General Public License as published by 
  the Free Software Foundation; either version 2.1 of the License, or 
  (at your option) any later version.

  This library 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 Lesser General Public 
  License for more details.

  You should have received a copy of the GNU Lesser General Public License 
  along with this library; if not, write to the Free Software Foundation, Inc., 
  59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 
*/
#ifndef UNION_FIND
#define UNION_FIND 1

#include <iostream>
#include "types.h"

using namespace std;

 
class UnionFind{

 private:
  documentID *id;
  int *sz;
  int size; // Debo

  documentID find(documentID x){
    
    while( x != id[x])
      x = id[x]; 
    return x;
  }
  
 public:

  /**
   * UnionFind: on a certain numer of docs;
   *
   *    @ documentID_t number of nodes
   */
  UnionFind(int N){

    size = N; // Debo
    id = new documentID[N];
    sz = new int[N];
    for (int i = 0; i < N; i++){
      id[i] = i; sz[i] = 1;
    }
  }
  
  ~UnionFind(){ delete id; delete sz;}

  /**
   * Find: a common anchestor
   *
   * @ documentID_t (first doc_id), documentID_t (second doc_id)
   */
  documentID find(documentID doc1, documentID doc2);  
  
  /**
   * Union: create the common anchestor.
   *
   * @ documentID_t (first doc_id), documentID_t (second doc_id)
   */
  
  void unite(documentID doc1, documentID doc2);

  /*
   * Connectivity
   *
   */

  bool connect(documentID doc1, documentID doc2);

  void print(){

    cout << "IDs = ";
    for(int i=0; i< size; i++){
      cout << id[i] << " ";
    }
    cout << endl << " Sz =  ";
    for(int i=0; i< size; i++){
      cout << sz[i] << " ";
    }
    cout << endl;
  }
  
  void printCluster(){
    int c=0;
    for (int i=0; i< size; i++){
      //first figure out whether i is a cluster id
      if (sz[i]<=1)
	continue;
      // else
      c++;
      cout << "Cluster " << c << " = " ;
      for (int j=0; j< size; j++){
	// cluster id is represented by i
	// find all elements with parent i
	if(id[j]==i)
	  cout << j << " ";
      }
      cout << endl;
    }

  }

};
#endif