/* 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
) ;
/*--------------------------------------------------------------------*/
syntax highlighted by Code2HTML, v. 0.9.1