* This function takes a graph and produces a bisection of it **************************************************************************/
| 101 | * This function takes a graph and produces a bisection of it |
| 102 | **************************************************************************/ |
| 103 | int MlevelRecursiveBisection(CtrlType *ctrl, GraphType *graph, int nparts, idxtype *part, float *tpwgts, float ubfactor, int fpart) |
| 104 | { |
| 105 | int i, j, nvtxs, cut, tvwgt, tpwgts2[2]; |
| 106 | idxtype *label, *where; |
| 107 | GraphType lgraph, rgraph; |
| 108 | float wsum; |
| 109 | |
| 110 | nvtxs = graph->nvtxs; |
| 111 | if (nvtxs == 0) { |
| 112 | printf("\t***Cannot bisect a graph with 0 vertices!\n\t***You are trying to partition a graph into too many parts!\n"); |
| 113 | return 0; |
| 114 | } |
| 115 | |
| 116 | /* Determine the weights of the partitions */ |
| 117 | tvwgt = idxsum(nvtxs, graph->vwgt); |
| 118 | tpwgts2[0] = tvwgt*ssum(nparts/2, tpwgts); |
| 119 | tpwgts2[1] = tvwgt-tpwgts2[0]; |
| 120 | |
| 121 | MlevelEdgeBisection(ctrl, graph, tpwgts2, ubfactor); |
| 122 | cut = graph->mincut; |
| 123 | |
| 124 | /* printf("%5d %5d %5d [%5d %f]\n", tpwgts2[0], tpwgts2[1], cut, tvwgt, ssum(nparts/2, tpwgts));*/ |
| 125 | |
| 126 | label = graph->label; |
| 127 | where = graph->where; |
| 128 | for (i=0; i<nvtxs; i++) |
| 129 | part[label[i]] = where[i] + fpart; |
| 130 | |
| 131 | if (nparts > 2) { |
| 132 | SplitGraphPart(ctrl, graph, &lgraph, &rgraph); |
| 133 | /* printf("%d %d\n", lgraph.nvtxs, rgraph.nvtxs); */ |
| 134 | } |
| 135 | |
| 136 | |
| 137 | /* Free the memory of the top level graph */ |
| 138 | /*GKfree(&graph->gdata, &graph->rdata, &graph->label, LTERM);*/ |
| 139 | GKfree3((void **)&graph->gdata, (void **)&graph->rdata, (void **)&graph->label); |
| 140 | |
| 141 | /* Scale the fractions in the tpwgts according to the true weight */ |
| 142 | wsum = ssum(nparts/2, tpwgts); |
| 143 | sscale(nparts/2, 1.0/wsum, tpwgts); |
| 144 | sscale(nparts-nparts/2, 1.0/(1.0-wsum), tpwgts+nparts/2); |
| 145 | /* |
| 146 | for (i=0; i<nparts; i++) |
| 147 | printf("%5.3f ", tpwgts[i]); |
| 148 | printf("[%5.3f]\n", wsum); |
| 149 | */ |
| 150 | |
| 151 | /* Do the recursive call */ |
| 152 | if (nparts > 3) { |
| 153 | cut += MlevelRecursiveBisection(ctrl, &lgraph, nparts/2, part, tpwgts, ubfactor, fpart); |
| 154 | cut += MlevelRecursiveBisection(ctrl, &rgraph, nparts-nparts/2, part, tpwgts+nparts/2, ubfactor, fpart+nparts/2); |
| 155 | } |
| 156 | else if (nparts == 3) { |
| 157 | cut += MlevelRecursiveBisection(ctrl, &rgraph, nparts-nparts/2, part, tpwgts+nparts/2, ubfactor, fpart+nparts/2); |
| 158 | /*GKfree(&lgraph.gdata, &lgraph.label, LTERM);*/ |
| 159 | GKfree2((void **)&lgraph.gdata, (void **)&lgraph.label); |
| 160 | } |
no test coverage detected