union-find.cpp

聚类分析程序 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 
*/

#include "union-find.h"



documentID UnionFind::find(documentID doc1, documentID doc2){
  
  return (find(doc1) == find(doc2));
}


void UnionFind::unite(documentID doc1, documentID doc2){

  documentID i = find(doc1);
  documentID j = find(doc2);
  if (i == j) return;         // already linked
  if (sz[i] < sz[j]){         // balance
    id[i] = j; sz[j] += sz[i];
  } else {
    id[j] = i; sz[i] += sz[j]; // error by authors fixed by Debo
  }
}


bool UnionFind::connect(documentID doc1, documentID doc2){

  if (!find(doc1, doc2)){

    unite(doc1,doc2);
    return true;
  }
  return false;
}