libspooles-dev 2.2-10build1 / usr / include / spooles / BKL / BKL.h

/*  BKL.h  */

#include "../BPG.h"
#include "../cfiles.h"

/*--------------------------------------------------------------------*/
/*
   -------------------------------------------------------------------
   the BKL object handles the block kernihan-lin family 
   of algorithms defined on bipartite graphs.

   bpg       -- bipartite graph to work with, 
                not free'd when BKL object is free'd
   ndom      -- number of domains
   nseg      -- number of segments
   nreg      -- number of regions, nreg = ndom + nseg
   totweight -- total weight of the bipartite graph
   npass     -- # of passes made
   npatch    -- # of patches evaluated
   nflips    -- # of domain flips that were executed
   nimprove  -- # of improvement steps
   ngaineval -- # of gain evaluations
   colors    -- map from regions to colors, size nreg
   cweights  -- array to store color weights,
      cweights[0] -- separator weight
      cweights[1] -- black component weight
      cweights[2] -- white component weight
   regwghts  -- vector of region weights. 
      if the Graph g has vertex weights then
         regwght points to its vertex weights
         and is not free'd when the BKL object is free'd
      else
         regwghts is allocated and set to unit weights
         and free'd when the BKL object is free'd
      endif
   alpha -- cost function parameter
      cost = |S|(1 + alpha*max(|B|,|W|)/min(|B|,|W|))

   created  -- 95oct07, cca
   modified -- 95dec07, cca
      directory cleaned up, added some efficiency,
      inserted exhaustive search into fidmat procedure.
   -------------------------------------------------------------------
*/
typedef struct _BKL   BKL ;
struct _BKL {
   BPG     *bpg        ;
   int     ndom        ;
   int     nseg        ;
   int     nreg        ;
   int     totweight   ;
   int     npass       ;
   int     npatch      ;
   int     nflips      ;
   int     nimprove    ;
   int     ngaineval   ;
   int     *colors     ;
   int     cweights[3] ;
   int     *regwghts   ;
   float   alpha       ;
} ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in basics.c ----------------------------------------
------------------------------------------------------------------------
*/
/*
   -----------------------
   constructor

   created -- 95oct07, cca
   -----------------------
*/
BKL *
BKL_new (
   void
) ;
/*
   -----------------------
   set the default fields

   created -- 95oct07, cca
   -----------------------
*/
void
BKL_setDefaultFields (
   BKL   *bkl
) ;
/*
   -----------------------
   clear the data fields

   created -- 95oct07, cca
   -----------------------
*/
void
BKL_clearData (
   BKL   *bkl
) ;
/*
   -----------------------
   destructor

   created -- 95oct07, cca
   -----------------------
*/
void
BKL_free (
   BKL   *bkl
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in init.c ------------------------------------------
------------------------------------------------------------------------
*/
/*
   -----------------------
   initialize the object
 
   created -- 95oct07, cca
   -----------------------
*/
void
BKL_init (
   BKL     *bkl,
   BPG     *bpg,
   float   alpha
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in util.c ------------------------------------------
------------------------------------------------------------------------
*/
/*
   ------------------------------------------------
   set the colors of the domains and segments 
   by coloring the domains black or white randomly.
 
   created -- 95oct07, cca
   ------------------------------------------------
*/
void
BKL_setRandomColors (
   BKL   *bkl,
   int   seed
) ;
/*
   -----------------------------------------
   set the component weights.
   note, we assume the domain colors are set
 
   created -- 95oct07, cca
   -----------------------------------------
*/
void
BKL_setColorWeights (
   BKL   *bkl
) ;
/*
   ---------------------------------------
   return the segment color, a function of
   the colors of its neighboring domains.
  
   created -- 95oct07, cca
   ---------------------------------------
*/
int
BKL_segColor (
   BKL   *bkl,
   int   iseg
) ;
/*
   -----------------------
   flip the domain
 
   created -- 95oct07, cca
   -----------------------
*/
void
BKL_flipDomain (
   BKL   *bkl,
   int   idom
) ;
/*
   ------------------------------
   return the next domain to flip
   in a grey code sequence
 
   created -- 95oct07, cca
   ------------------------------
*/
int
BKL_greyCodeDomain (
   BKL   *bkl,
   int   count
) ;
/*
   ----------------------------------------------------------------
  set the initial partition.
 
   flag -- specifies initial partition type
      flag == 1 --> random coloring of domains
      flag == 2 --> one black domain, (seed % ndom), rest are white
      flag == 3 --> one black pseudoperipheral domain, found using
                    domain (seed % ndom) as root, rest are white
      flag == 4 --> roughly half-half split, breadth first search
                    of domains, (seed % ndom) as root
      flag == 5 --> roughly half-half split, breadth first search
                    of domains, (seed % ndom) as root to find
                    a pseudoperipheral domain as root
      flag == 6 --> use domcolors[] to seed the colors[] array
   seed      -- random number seed, for flag == 1, if seed > 0 then
               we call srand48(seed) to set the random number
                generator.
   domcolors -- vector of domain colors, used when flag == 6
 
   created -- 95oct11, cca
   ----------------------------------------------------------------
*/
float
BKL_setInitPart (
   BKL   *bkl,
   int   flag,
   int   seed,
   int   domcolors[]
) ;
/*
   ---------------------------------------------------
   return 1 if the domain is adjacent to the separator
 
   created -- 95oct11, cca
   ---------------------------------------------------
*/
int
BKL_domAdjToSep ( 
   BKL   *bkl, 
   int   dom
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in exhSearch.c -------------------------------------
------------------------------------------------------------------------
*/
/*
   --------------------------------------------------------------------
   perform an exhaustive search over a subspace of domains
   
   mdom    -- number of domains in the subspace
   domids  -- vector of domain ids, size mdom
   tcolors -- temporary vector to hold active domain colors, size mdom
 
   note : region colors and component weights of the best
          partition are left in bkl->colors[] and bkl->cweights[].
 
   return value -- cost of best partition
 
   created -- 95oct07, cca
   --------------------------------------------------------------------
*/
float
BKL_exhSearch (
   BKL   *bkl,
   int   mdom,
   int   domids[],
   int   tcolors[]
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in evalfcn.c ---------------------------------------
------------------------------------------------------------------------
*/
/*
   -----------------------
   evaluate the partition
 
   created -- 95oct07, cca
   -----------------------
*/
float
BKL_evalfcn (
   BKL   *bkl
) ;
/*
   -----------------------
   evaluate the partition
 
   created -- 95oct07, cca
   -----------------------
*/
float
BKL_eval (
   BKL   *bkl,
   int   Sweight,
   int   Bweight,
   int   Wweight
) ;
/*
   ---------------------------------------------------------
   evaluate the (deltaS, deltaB and deltaW) of a domain flip
 
   created -- 950ct11, cca
   ---------------------------------------------------------
*/
void
BKL_evalgain (
   BKL   *bkl,
   int   dom,
   int   *pdeltaS,
   int   *pdeltaB,
   int   *pdeltaW
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in fidmat.c ----------------------------------------
------------------------------------------------------------------------
*/
/*
   ------------------------------------------------
   improve the partition using the FidMat algorithm
 
   created -- 95oct11, cca
   ------------------------------------------------
*/
float
BKL_fidmat ( 
   BKL   *bkl
) ;
/*--------------------------------------------------------------------*/