/* GPart.h */
#include "../Graph.h"
#include "../BPG.h"
#include "../DSTree.h"
#include "../Tree.h"
#include "../IV.h"
#include "../cfiles.h"
/*--------------------------------------------------------------------*/
/*
----------------------------------------------------------------
The GPart object is used to generate and store information
about a partition of the graph.
id -- id for the object
g -- pointer to Graph object, not free'd by the destructor
nvtx -- # of vertices in the graph, internal vertices only
nvbnd -- # of vertices in the boundary of the graph,
ncomp -- # of components in the graph
compidsIV -- IV object that contains a map from
vertices to components, size nvtx
compids[v] == 0 --> v is on the interface
compids[v] != 0 --> v belongs to domain compids[v]
cweightsIV -- IV object that contains the component weights
par -- pointer to parent GPart object
fch -- pointer to first child GPart object
sib -- pointer to sibling GPart object
vtxMapIV -- IV object that contains a map map from local vertices
to parent's vertices or global vertices
msglvl -- message level, default is zero
msgFile -- message file pointer, default is stdout
created -- 95oct21, cca
----------------------------------------------------------------
*/
typedef struct _GPart GPart ;
struct _GPart {
int id ;
Graph *g ;
int nvtx ;
int nvbnd ;
int ncomp ;
IV compidsIV ;
IV cweightsIV ;
GPart *par ;
GPart *fch ;
GPart *sib ;
IV vtxMapIV ;
int msglvl ;
FILE *msgFile ;
} ;
/*
------------------------------------------
include the DDsepInfo object's header file
------------------------------------------
*/
#include "DDsepInfo.h"
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in basics.c --------------------------------------
------------------------------------------------------------------------
*/
/*
--------------------------------------------
construct a new instance of the GPart object
created -- 95oct05, cca
--------------------------------------------
*/
GPart *
GPart_new (
void
) ;
/*
---------------------------------------------
set the default fields of the GPart object
created -- 95oct05, cca
modified -- 95nov29, cca
par, fch, sib and vtxMap fields included
---------------------------------------------
*/
void
GPart_setDefaultFields (
GPart *gpart
) ;
/*
---------------------------------------------
clear the data fields for a GPart object
created -- 95oct05, cca
modified -- 95nov29, cca
par, fch, sib and vtxMap fields included
---------------------------------------------
*/
void
GPart_clearData (
GPart *gpart
) ;
/*
------------------------
free the GPart object
created -- 95oct05, cca
modified -- 95nov29, cca
gpart now free'd
------------------------
*/
void
GPart_free (
GPart *gpart
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in DDviaFishnet.c --------------------------------
------------------------------------------------------------------------
*/
/*
---------------------------------------------------------------
purpose -- to construct and return a multisector
using the fishnet algorithm
freeze -- parameter used to keep nodes of high degree
in the interface
minweight -- minimum weight for a domain
maxweight -- maximum weight for a domain
seed -- random number seed
created -- 96feb16, cca
---------------------------------------------------------------
*/
void
GPart_DDviaFishnet (
GPart *gpart,
double freeze,
int minweight,
int maxweight,
int seed
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in DDviaProjection.c -----------------------------
------------------------------------------------------------------------
*/
/*
---------------------------------------------------------
set the compids[] vector using a global map from vertices
to domains and interface nodes.
DDmapIV -- IV object that contains the map from vertices
to domains and interface nodes
created -- 96mar17, cca
---------------------------------------------------------
*/
void
GPart_DDviaProjection (
GPart *gpart,
IV *DDmapIV
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in DDsepInfo.c -----------------------------------
------------------------------------------------------------------------
*/
/*
------------------------------------------------
construct a new instance of the DDsepInfo object
created -- 96feb24, cca
------------------------------------------------
*/
DDsepInfo *
DDsepInfo_new (
void
) ;
/*
---------------------------------------------
set the default fields of the DDsepInfo object
created -- 96feb24, cca
---------------------------------------------
*/
void
DDsepInfo_setDefaultFields (
DDsepInfo *info
) ;
/*
---------------------------------------------
clear the data fields for a DDsepInfo object
created -- 96feb24, cca
---------------------------------------------
*/
void
DDsepInfo_clearData (
DDsepInfo *info
) ;
/*
------------------------
free the DDsepInfo object
created -- 96feb24, cca
------------------------
*/
void
DDsepInfo_free (
DDsepInfo *info
) ;
/*
-----------------------
write the CPU times
created -- 97nov06, cca
-----------------------
*/
void
DDsepInfo_writeCpuTimes (
DDsepInfo *info,
FILE *msgFile
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in domSegMap.c -----------------------------------
------------------------------------------------------------------------
*/
/*
--------------------------------------------------------------------
fill *pndom with ndom, the number of domains.
fill *pnseg with nseg, the number of segments.
domains are numbered in [0, ndom), segments in [ndom,ndom+nseg).
return -- an IV object that contains the map
from vertices to segments
created -- 99feb29, cca
--------------------------------------------------------------------
*/
IV *
GPart_domSegMap (
GPart *gpart,
int *pndom,
int *pnseg
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in identifyWideSep.c -----------------------------
------------------------------------------------------------------------
*/
/*
--------------------------------------------------------------
identify the wide separator
return -- IV object that holds the nodes in the wide separator
created -- 96oct21, cca
--------------------------------------------------------------
*/
IV *
GPart_identifyWideSep (
GPart *gpart,
int nlevel1,
int nlevel2
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in init.c ----------------------------------------
------------------------------------------------------------------------
*/
/*
---------------------------
initialize the GPart object
created -- 95oct05, cca
---------------------------
*/
void
GPart_init (
GPart *gpart,
Graph *g
) ;
/*
-----------------------
set the message fields
created -- 96oct21, cca
-----------------------
*/
void
GPart_setMessageInfo (
GPart *gpart,
int msglvl,
FILE *msgFile
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in makeYCmap.c -----------------------------------
------------------------------------------------------------------------
*/
/*
-------------------------------------------------------
make the map from wide separator vertices Y
to components {0, 1, 2, 3}.
YCmap[y] == 0 --> y is not adjacent to either component
YCmap[y] == 1 --> y is adjacent to only component 1
YCmap[y] == 2 --> y is adjacent to only component 2
YCmap[y] == 3 --> y is adjacent to components 1 and 2
created -- 96jun09, cca
-------------------------------------------------------
*/
IV *
GPart_makeYCmap (
GPart *gpart,
IV *YVmapIV
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in RBviaDDsep.c ----------------------------------
------------------------------------------------------------------------
*/
/*
--------------------------------------------------------
this method constructs recursive partition of a graph.
it returns a DSTree object to represent the splitting of
the tree into subgraphs.
the info object contains the information needed by the
DDsep algorithm.
created -- 96feb24, cca
--------------------------------------------------------
*/
DSTree *
GPart_RBviaDDsep (
GPart *gpart,
DDsepInfo *info
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in smoothBisector.c ------------------------------
------------------------------------------------------------------------
*/
/*
---------------------------------------------------------
smooth a wide separator
nlevel -- number of levels one each side of the separator
to include into the separator
alpha -- partition cost function parameter
created -- 96jun02, cca
---------------------------------------------------------
*/
float
GPart_smoothBisector (
GPart *gpart,
int nlevel,
float alpha
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in smoothBy2layers.c -----------------------------
------------------------------------------------------------------------
*/
/*
-----------------------------------------------------------
smooth a bisector using the alternating two-layer algorithm
option -- network flag
1 --> make the network bipartite as for the
Dulmage-Mendelsohn decomposition
otherwise -- use network induced by the wide separator
alpha -- cost function parameter
created -- 96jun08, cca
-----------------------------------------------------------
*/
void
GPart_smoothBy2layers (
GPart *gpart,
int option,
float alpha
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in smoothYSep.c ----------------------------------
------------------------------------------------------------------------
*/
/*
------------------------------------------------------------
smooth the wide separator given by YVmapIV by forming
the associated network, solving the max flow problem,
and examining two min-cuts.
YVmapIV -- map from wide vertices Y to vertices V
YCmapIV -- map from wide vertices Y to {0,1,2,3}
YCmap[y] = 0 --> treat y as an internal node
adjacent to neither component
YCmap[y] = 1 --> treat y as adjacent only to component 1
YCmap[y] = 2 --> treat y as adjacent only to component 2
YCmap[y] = 3 --> treat y as adjacent to components 1 and 2
alpha -- cost function parameter
created -- 96jun08, cca
------------------------------------------------------------
*/
float
GPart_smoothYSep (
GPart *gpart,
IV *YVmapIV,
IV *YCmapIV,
float alpha
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in split.c ---------------------------------------
------------------------------------------------------------------------
*/
/*
--------------------------------------------
split the graph partition object into pieces
created -- 95nov29, cca
--------------------------------------------
*/
void
GPart_split (
GPart *gpart
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in TwoSetViaBKL.c --------------------------------
------------------------------------------------------------------------
*/
/*
-----------------------------------------------------------------
given a domain decomposition, find a bisector
1. construct the domain/segment graph
2. use block kernihan-lin to get an initial bisector
alpha -- cost function parameter for BKL
seed -- random number seed
cpus -- array to store CPU times
cpus[0] -- time to find domain/segment map
cpus[1] -- time to find domain/segment bipartite graph
cpus[2] -- time to find two-set partition
return value -- cost of the partition
created -- 96mar09, cca
-----------------------------------------------------------------
*/
double
GPart_TwoSetViaBKL (
GPart *gpart,
double alpha,
int seed,
double cpus[]
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in util.c ----------------------------------------
------------------------------------------------------------------------
*/
/*
----------------------------------------------------
set the component weights from the compids[] vector
created -- 95oct05, cca
modified -- 95nov29, cca
----------------------------------------------------
*/
void
GPart_setCweights (
GPart *gpart
) ;
/*
----------------------------------------------
return the number of bytes taken by the object
created -- 95oct05, cca
----------------------------------------------
*/
int
GPart_sizeOf (
GPart *gpart
) ;
/*
----------------------------------------------------
return 1 if vertex is adjacent to only one domain
and fill *pdomid with the domain's id
return 0 otherwise
created -- 95oct19, cca
-------------------------------------------------
*/
int
GPart_vtxIsAdjToOneDomain (
GPart *gpart,
int v,
int *pdomid
) ;
/*
------------------------------------------------------
return 1 if the partition has a valid vertex separator
0 otherwise
created -- 95oct18, cca
------------------------------------------------------
*/
int
GPart_validVtxSep (
GPart *gpart
) ;
/*
-------------------------------------
return an IV object filled with the
weights of the component's boundaries
created -- 96oct21, cca
-------------------------------------
*/
IV *
GPart_bndWeightsIV (
GPart *gpart
) ;
/*--------------------------------------------------------------------*/
syntax highlighted by Code2HTML, v. 0.9.1