graclus.c_bak

多层权核k均值算法

/*
 * Copyright 2005
 *
 * mlkkm.c
 *
 * This file contains the driving routine for multi-level kernel k-means
 *
 * Started 12/2004
 * Yuqiang Guan
 *
 * 
 *
 */

#include <metis.h>



int cutType; //cut type, default is normalized cut
char mlwkkm_fname[256]; //used to store coarsest file

/*************************************************************************
* multi-level weighted kernel k-means main function
**************************************************************************/
main(int argc, char *argv[])
{
  int i, nparts, options[11];
  idxtype *part;
  float rubvec[MAXNCON], lbvec[MAXNCON];
  float result;
  GraphType graph;
  char filename[256];
  int numflag = 0, wgtflag = 0, edgecut, chain_length;
  timer TOTALTmr, METISTmr, IOTmr;

  cutType = 0;
  chain_length = 0;

  if (argc <3 || argc>5) {
    printf("Usage: %s <GraphFile> <Nparts> [<Cut Type> <chain length>]\n",argv[0
]);
    exit(0);
  }
  else if(argc ==3){
    strcpy(filename, argv[1]);
    nparts = atoi(argv[2]);
  }
  else if(argc==4){
    strcpy(filename, argv[1]);
    nparts = atoi(argv[2]);
    cutType = atoi(argv[3]);
  }
  else{
    strcpy(filename, argv[1]);
    nparts = atoi(argv[2]);
    cutType = atoi(argv[3]);
    chain_length = atoi(argv[4]);
  }

  if (nparts < 2) {
    printf("The number of partitions should be greater than 1!\n");
    exit(0);
  }

  extractfilename(filename, mlwkkm_fname);
  strcat(mlwkkm_fname, argv[2]);
  
  cleartimer(TOTALTmr);
  cleartimer(METISTmr);
  cleartimer(IOTmr);

  starttimer(TOTALTmr);
  starttimer(IOTmr);
  ReadGraph(&graph, filename, &wgtflag);
  if (graph.nvtxs <= 0) {
    printf("Empty graph. Nothing to do.\n");
    exit(0);
  }
  stoptimer(IOTmr);

  printf("\n----------------------------------------------------------------------\n");
  printf("%s", MLKKMTITLE);
  printf("Graph Information:\n");
  printf("  Name: %s, \n  #Vertices: %d, #Edges: %d, #Parts: %d\n", filename, graph.nvtxs, graph.nedges/2, nparts);
  if (graph.ncon > 1)
    printf("  Balancing Constraints: %d\n", graph.ncon);
  //printf("\nK-way Partitioning... -----------------------------------------------\n");

  part = idxmalloc(graph.nvtxs, "main: part");
  options[0] = 0;
  

  starttimer(METISTmr);
  if (graph.ncon == 1) {
    /* modification 
    METIS_PartGraphKway(&graph.nvtxs, graph.xadj, graph.adjncy, graph.vwgt, graph.adjwgt, 
    &wgtflag, &numflag, &nparts, options, &edgecut, part); */
    
    MLKKM_PartGraphKway(&graph.nvtxs, graph.xadj, graph.adjncy, graph.vwgt, graph.adjwgt, 
    &wgtflag, &numflag, &nparts, &chain_length, options, &edgecut, part);
    
    /* ends */
  }
  else {
    for (i=0; i<graph.ncon; i++)
      rubvec[i] = HORIZONTAL_IMBALANCE;

    METIS_mCPartGraphKway(&graph.nvtxs, &graph.ncon, graph.xadj, graph.adjncy, graph.vwgt, 
          graph.adjwgt, &wgtflag, &numflag, &nparts, rubvec, options, &edgecut, part);
  }
  stoptimer(METISTmr);

  ComputePartitionBalance(&graph, nparts, part, lbvec);
  /*
  for (int i=0; i<graph.nvtxs; i++)
    printf("%d ", part[i]);
  printf("!\n");
  */
  if (cutType == NCUT){
    result = ComputeNCut(&graph, part, nparts);
    printf("\nNormalized-Cut... \n   Cut value: %7f, Balance: ", result);
  }
  else{
    result = ComputeRAsso(&graph, part, nparts);
    printf("\nRatio Association...  \n  Association value: %7f, Balance: ", result);
  }
    
  //printf("  %d-way Edge-Cut: %7d\n", nparts, ComputeCut(&graph, part));
  for (i=0; i<graph.ncon; i++)
    printf("%5.2f ", lbvec[i]);
  printf("\n");

  starttimer(IOTmr);
  WritePartition(filename, part, graph.nvtxs, nparts); 
  stoptimer(IOTmr);
  stoptimer(TOTALTmr);

  printf("\nTiming Information:\n");
  printf("  I/O:          \t\t %7.3f\n", gettimer(IOTmr));
  printf("  Partitioning: \t\t %7.3f   (Graclus time)\n", gettimer(METISTmr));
  printf("  Total:        \t\t %7.3f\n", gettimer(TOTALTmr));
  printf("----------------------------------------------------------------------\n");


  GKfree((void **) &graph.xadj, (void **) &graph.adjncy, (void **) &graph.vwgt, (void **) &graph.adjwgt, (void **) &part, LTERM);
}