amdb_clustering.cc

Libgist is an implementation of the Generalized Search Tree, a template index structure that makes i

	// in itemNo order), filling up gaps (caused by non-retrieved items);
	// assign clusterNo 0
	int nextItemNo = 0; // items start at 0
	ClusterInfo info;
	for (mit = retrievedMap.begin(); mit != retrievedMap.end(); mit++) {
	    int itemNo = (*mit).first;
	    while (nextItemNo < itemNo) {
		// fill up gaps
		info.itemNo = nextItemNo;
		info.clusterNo = invalidNo;
		clustering.info.push_back(info);
		nextItemNo++;
	    }
	    info.itemNo = itemNo;
	    info.clusterNo = 0;
	    clustering.info.push_back(info);
	    nextItemNo = itemNo + 1;
	}
	// fill up with remaining non-retrieved items
	int i;
	for (i = nextItemNo; i < tmap.itemMap.size(); i++) {
	    info.itemNo = i;
	    info.clusterNo = invalidNo;
	    clustering.info.push_back(info);
	}

	return (RCOK);
    }

    char hmetiscmd[1024];
    sprintf(hmetiscmd, "hmetis %s %d %d %d 3 3 1 1 0", filename, numClustersCreated,
        ubfactor, runs);
    printf("%s\n", hmetiscmd);
    int res = system(hmetiscmd);
    if (res == -1) {
	// hmetis crashed
	return eCLUSTERERROR;
    }

    // First, load the clustering information into clusterMap, then copy the contents of 
    // this map to an array. We must do it in two steps, because the 
    // clustering info reflects the condensed item numbering we obtained from 
    // retrievedMap. In order to convert the condensed item numbers into the original 
    // item numbers, we need to invert retrievedMap (into invertedMap).
    Map invertedMap; // map<itemno, itemno, less<itemno>>: condensed to orig. item no
    for (mit = retrievedMap.begin(); mit != retrievedMap.end(); mit++) {
        invertedMap[(unsigned int) (*mit).second] = (void *) (*mit).first;
    }

// VCPORT_B
#ifndef WIN32
    (void) sprintf(filename, "%x.hgr.part.%-d", getpid(), numClustersCreated);
#else
    (void) sprintf(filename, "%x.hgr.part.%-d", _getpid(), numClustersCreated);
#endif
// VCPORT_E

    printf("reading clustering: %s\n", filename);
    ifstream clustfile(filename);
    if (!clustfile.good()) {
        return eFILEERROR;
    }
    const int BUFLEN = 16;
    char buf[BUFLEN];
    // map<shpid_t, int, less<shpid_t> > clusterMap: translate from the
    // (original, non-condensed) item number to the cluster number
    Map clusterMap;
    for (i = 1; i <= numRetrieved; i++) {
        clustfile.getline(buf, BUFLEN);
	unsigned int clust;
	sscanf(buf, "%u", &clust);
	unsigned int itemNo = (unsigned int) invertedMap[i]; // 1-based
	clusterMap[itemNo] = (void *) clust;
    }


    // reset clustering
    clustering.info.erase(clustering.info.begin(), clustering.info.end());
    clustering.info.reserve(tmap.itemMap.size());

    // copy 'clusterMap' to 'clustering' (iterator will walk through clusterMap
    // in itemNo order), filling up gaps (caused by non-retrieved items)
    int nextItemNo = 0; // items start at 0
    ClusterInfo info;
    for (mit = clusterMap.begin(); mit != clusterMap.end(); mit++) {
	int itemNo = (*mit).first;
	while (nextItemNo < itemNo) {
	    // fill up gaps
	    info.itemNo = nextItemNo;
	    info.clusterNo = invalidNo;
	    clustering.info.push_back(info);
	    nextItemNo++;
	}
	info.itemNo = itemNo;
	info.clusterNo = (int) (*mit).second;
	clustering.info.push_back(info);
	nextItemNo = itemNo + 1;
    }
    // fill up with remaining non-retrieved items
    for (i = nextItemNo; i < tmap.itemMap.size(); i++) {
	info.itemNo = i;
	info.clusterNo = invalidNo;
	clustering.info.push_back(info);
    }

    // XXX debug: find entries with itemno = 0
    amdb_clustering::ClusterInfoVect::iterator cit;
    int cnt = 0;
    int cntInv = 0;
    for (cit = clustering.info.begin(); cit != clustering.info.end(); cit++) {
        if (cit->itemNo == 0) cnt++;
        if (cit->clusterNo == invalidNo) {
	    cntInv++;
	}
	assert(cnt <= 1);
    }
    cout << "non-retrieved: " << cntInv << endl;

    return RCOK;
}


/////////////////////////////////////////////////////////////////////////
// amdb_clustering::extractRetrieved - extract item numbers for result sets
//
// Description:
//	- creates a map from original item numbers (those give in the 
//	  result sets) to condensed item numbers (which are a contiguous
//	  numbering of the items)
//
/////////////////////////////////////////////////////////////////////////

void
amdb_clustering::extractRetrieved(
    ResultSet resultSets[],	// hypergraph 
    int numResultSets,		// number of edges in hypergraph
    Map& retrievedMap,		// out: map of orig. itemno to condensed itemno
    int& numNonEmpty)		// out: number of non-empty result sets
{
    ItemId itemCounter = 1; // start at 1, otherwise can't distinguish from NULL
    int i;
    numNonEmpty = 0;
    for (i = 0; i < numResultSets; i++) {
	ResultSet *rs = &resultSets[i];
	int j;
	if (rs->itemCnt > 0) {
	    numNonEmpty++;
	}
	for (j = 0; j < rs->itemCnt; j++) {
	    ItemId item = rs->items[j];
	    if (retrievedMap[item] == NULL) {
		// This item hasn't been retrieved yet. Assign it the next number.
		retrievedMap[item] = (void *) itemCounter;
		itemCounter++;
	    }
	}
    }
    assert(retrievedMap.size() == itemCounter -1);
}


///////////////////////////////////////////////////////////////////////////////
// amdb_clustering::freeResultSets - dealloc array of ResultSet
//
// Description:
//	- also deallocates sets[].items
///////////////////////////////////////////////////////////////////////////////

void
amdb_clustering::freeResultSets(
    ResultSet* sets,
    int numResultSets)
{
    int i;
    for (i = 0; i < numResultSets; i++) {
        delete [] sets[i].items;
    }
    delete [] sets;
}


///////////////////////////////////////////////////////////////////////////////
// amdb_clustering::Clustering::sortClusterNo - sort on clusterNo
//
// Description:
//
///////////////////////////////////////////////////////////////////////////////

void
amdb_clustering::Clustering::sortClusterNo()
{
    _less_clusterNo comp;
    sort(info.begin(), info.end(), comp);
}


///////////////////////////////////////////////////////////////////////////////
// amdb_clustering::Clustering::sortItemNo - sort on itemNo
//
// Description:
//
///////////////////////////////////////////////////////////////////////////////

void
amdb_clustering::Clustering::sortItemNo()
{
    _less_itemNo comp;
    sort(info.begin(), info.end(), comp);
}


///////////////////////////////////////////////////////////////////////////////
// amdb_clustering::Clustering::read - read from input stream
//
// Description:
//
///////////////////////////////////////////////////////////////////////////////

rc_t
amdb_clustering::Clustering::read(
    istream& s)
{
    ClusterInfoVect::size_type size;
    s.read((char *) &size, sizeof(size));
    info.reserve(size);
    int i;
    for (i = 0; i < size; i++) {
	ClusterInfo cinfo;
        s.read((char *) &cinfo, sizeof(cinfo));
	info.push_back(cinfo);
    }
    return(RCOK);
}

///////////////////////////////////////////////////////////////////////////////
// amdb_clustering::Clustering::write - write to output stream
//
// Description:
//
///////////////////////////////////////////////////////////////////////////////

rc_t
amdb_clustering::Clustering::write(
    ostream& s,
    bool ascii)
{
    
  if (!ascii) {
    ClusterInfoVect::size_type size = info.size();
    s.write((char *) &size, sizeof(size));
    ClusterInfoVect::iterator cit;
    for (cit = info.begin(); cit != info.end(); cit++) {
#if (__GNUG__==3)
      s.write((char *) &(*cit), sizeof(*cit));
#else
      s.write((char *) cit, sizeof(*cit));
#endif
    }
    return(RCOK);
  }
  else {
    ClusterInfoVect::size_type size = info.size();
    s << size << "\n";
    ClusterInfoVect::iterator cit;
    for (cit = info.begin(); cit != info.end(); cit++) {
#if (__GNUG__==3)
	  s << &(*cit) << "\n";
#else
      s << cit << "\n"; 
#endif
    }
    return(RCOK);
  }
}

void
amdb_clustering::Clustering::copy(
    const Clustering& cl)
{
    info.erase(info.begin(), info.end());
    info.insert(info.end(), cl.info.begin(), cl.info.end());
}