1 /* mkDSTree.c */
2
3 #include "../GPart.h"
4 #include "../../DSTree.h"
5 #include "../../MSMD.h"
6 #include "../../BKL.h"
7 #include "../../ETree.h"
8 #include "../../Perm.h"
9 #include "../../IV.h"
10 #include "../../timings.h"
11
12 /*--------------------------------------------------------------------*/
13 int
main(int argc,char * argv[])14 main ( int argc, char *argv[] )
15 /*
16 ---------------------------------------------------------------
17 test the recursive bisection algorithm that uses
18 (1) fishnet to get the domain decomposition
19 (2) domain/segment BKL to get the two set partition
20 (3) Dulmadge-Mendelsohn decomposition to smooth the bisector
21 the output is a DSTree object to hold the domain/separator tree
22
23 created -- 96mar09, cca
24 ---------------------------------------------------------------
25 */
26 {
27 char *inGraphFileName, *msgFileName, *outDSTreeFileName ;
28 DSTree *dstree ;
29 DDsepInfo *info ;
30 double alpha, freeze, msCPU, t1, t2 ;
31 FILE *msgFile ;
32 GPart *gpart ;
33 Graph *gf ;
34 int DDoption, maxdomweight, maxweight, minweight, msglvl,
35 nlayer, nvtx, rc, seed ;
36
37 if ( argc != 13 ) {
38 fprintf(stdout,
39 "\n\n usage : %s msglvl msgFile inGraphFile seed"
40 "\n minweight maxweight freeze alpha maxdomwght "
41 "\n DDoption nlayer outDSTreeFileName"
42 "\n msglvl -- message level"
43 "\n msgFile -- message file"
44 "\n inGraphFile -- input file, must be *.graphf or *.graphb"
45 "\n seed -- random number seed"
46 "\n minweight -- minimum domain weight"
47 "\n maxweight -- maximum domain weight"
48 "\n freeze -- cutoff multiplier for nodes of high degree"
49 "\n alpha -- cost function parameter"
50 "\n maxdomweight -- maximum subgraph weight"
51 "\n DDoption -- option for domain decomposition"
52 "\n 1 --> fishnet for each subgraph"
53 "\n 2 --> fishnet for graph, projection for each subgraph"
54 "\n nlayer -- number of layers for max flow improvement"
55 "\n outDSTreeFileName -- output file, must be *.dstreef"
56 "\n or *.dstreeb"
57 "\n", argv[0]) ;
58 return(0) ;
59 }
60 msglvl = atoi(argv[1]) ;
61 msgFileName = argv[2] ;
62 if ( strcmp(msgFileName, "stdout") == 0 ) {
63 msgFile = stdout ;
64 } else if ( (msgFile = fopen(msgFileName, "a")) == NULL ) {
65 fprintf(stderr, "\n fatal error in %s"
66 "\n unable to open file %s\n",
67 argv[0], msgFileName) ;
68 return(-1) ;
69 }
70 inGraphFileName = argv[3] ;
71 seed = atoi(argv[4]) ;
72 minweight = atoi(argv[5]) ;
73 maxweight = atoi(argv[6]) ;
74 freeze = atof(argv[7]) ;
75 alpha = atof(argv[8]) ;
76 maxdomweight = atoi(argv[9]) ;
77 DDoption = atoi(argv[10]) ;
78 nlayer = atoi(argv[11]) ;
79 outDSTreeFileName = argv[12] ;
80 fprintf(msgFile,
81 "\n %s : "
82 "\n msglvl -- %d"
83 "\n msgFile -- %s"
84 "\n inGraphFile -- %s"
85 "\n seed -- %d"
86 "\n minweight -- %d"
87 "\n maxweight -- %d"
88 "\n freeze -- %f"
89 "\n alpha -- %f"
90 "\n maxdomweight -- %d"
91 "\n DDoption -- %d"
92 "\n nlayer -- %d"
93 "\n outDSTreeFile -- %s"
94 "\n", argv[0], msglvl, msgFileName, inGraphFileName, seed,
95 minweight, maxweight, freeze, alpha, maxdomweight, DDoption,
96 nlayer, outDSTreeFileName) ;
97 fflush(msgFile) ;
98 /*
99 ---------------------------------------
100 initialize the DDsep information object
101 ---------------------------------------
102 */
103 info = DDsepInfo_new() ;
104 info->seed = seed ;
105 info->minweight = minweight ;
106 info->maxweight = maxweight ;
107 info->freeze = freeze ;
108 info->alpha = alpha ;
109 info->DDoption = DDoption ;
110 info->maxcompweight = maxdomweight ;
111 info->nlayer = nlayer ;
112 info->msglvl = msglvl ;
113 info->msgFile = msgFile ;
114 /*
115 ------------------------
116 read in the Graph object
117 ------------------------
118 */
119 if ( strcmp(inGraphFileName, "none") == 0 ) {
120 fprintf(msgFile, "\n no file to read from") ;
121 exit(0) ;
122 }
123 MARKTIME(t1) ;
124 gf = Graph_new() ;
125 Graph_setDefaultFields(gf) ;
126 if ( (rc = Graph_readFromFile(gf, inGraphFileName)) != 1 ) {
127 fprintf(msgFile, "\n return value %d from Graph_readFromFile(%p,%s)",
128 rc, gf, inGraphFileName) ;
129 exit(-1) ;
130 }
131 MARKTIME(t2) ;
132 fprintf(msgFile, "\n CPU %9.5f : read in graph from file %s",
133 t2 - t1, inGraphFileName) ;
134 nvtx = gf->nvtx ;
135 if ( msglvl < 4 ) {
136 Graph_writeStats(gf, msgFile) ;
137 fflush(msgFile) ;
138 } else {
139 Graph_writeForHumanEye(gf, msgFile) ;
140 fflush(msgFile) ;
141 }
142 /*
143 -----------------------
144 create the GPart object
145 -----------------------
146 */
147 MARKTIME(t1) ;
148 gpart = GPart_new() ;
149 GPart_init(gpart, gf) ;
150 GPart_setMessageInfo(gpart, msglvl, msgFile) ;
151 MARKTIME(t2) ;
152 /*
153 ------------------------------------------
154 get the DSTree object that represents the
155 domain/separator partition of the vertices
156 ------------------------------------------
157 */
158 MARKTIME(t1) ;
159 dstree = GPart_RBviaDDsep(gpart, info) ;
160 MARKTIME(t2) ;
161 msCPU = t2 - t1 ;
162 fprintf(msgFile, "\n\n CPU %9.5f : find subgraph tree ", msCPU) ;
163 DDsepInfo_writeCpuTimes(info, msgFile) ;
164
165 if ( msglvl > 0 ) {
166 fprintf(msgFile, "\n # subgraphs = %d", dstree->tree->n) ;
167 fflush(msgFile) ;
168 }
169 if ( msglvl > 2 ) {
170 fprintf(msgFile, "\n DSTree subgraph tree") ;
171 DSTree_writeForHumanEye(dstree, msgFile) ;
172 fflush(msgFile) ;
173 }
174 if ( msglvl > 2 ) {
175 fprintf(msgFile, "\n map from vertices to subgraphs") ;
176 IV_writeForHumanEye(dstree->mapIV, msgFile) ;
177 fflush(msgFile) ;
178 }
179 DDsepInfo_free(info) ;
180 /*
181 --------------------------------------------
182 renumber the tree via a post-order traversal
183 --------------------------------------------
184 */
185 DSTree_renumberViaPostOT(dstree) ;
186 if ( msglvl > 2 ) {
187 fprintf(msgFile, "\n renumbered DSTree subgraph tree") ;
188 DSTree_writeForHumanEye(dstree, msgFile) ;
189 fflush(msgFile) ;
190 }
191 /*
192 --------------------------------------------
193 optionally write the DSTree object to a file
194 --------------------------------------------
195 */
196 if ( strcmp(outDSTreeFileName, "none") != 0 ) {
197 DSTree_writeToFile(dstree, outDSTreeFileName) ;
198 }
199 /*
200 ----------------------------
201 free all the working storage
202 ----------------------------
203 */
204 Graph_free(gpart->g) ;
205 GPart_free(gpart) ;
206 DSTree_free(dstree) ;
207
208 fprintf(msgFile, "\n") ;
209 fclose(msgFile) ;
210
211 return(1) ; }
212
213 /*--------------------------------------------------------------------*/
214