00001
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00037
00044
00045
00046
00047 #include <avl.h>
00048 #include <configuration.h>
00049 #include "graph.h"
00050 #include "partition.h"
00051 #include "ksection.h"
00052
00053
00054 static int __dist_compare_asc_edges(const void *p1, const void *p2)
00055 {
00056 Edge *u = * (Edge **) p1;
00057 Edge *v = * (Edge **) p2;
00058
00059 if (u->dist > v->dist)
00060 return 1;
00061 else if (u->dist < v->dist)
00062 return -1;
00063 else
00064 return 0;
00065 }
00066
00067
00068 static void __sort_edges(Graph *g, Edge *sorted_edges[])
00069 {
00070 unsigned int i;
00071 Edge *edge = g->edges;
00072 for (i = 0; edge != 0 && i < g->E; edge = edge->next, i++) {
00073 sorted_edges[i] = edge;
00074 edge->removed = 0;
00075 edge->depth = edge->u->depth + edge->v->depth;
00076 }
00077
00078 qsort(&sorted_edges[0], g->E, sizeof(Edge *),
00079 __dist_compare_asc_edges);
00080 }
00081
00082
00083 static int __complete(unsigned int array[], int size)
00084 {
00085 int i;
00086 for (i = 0; i < size; i++) {
00087 if (array[i] == 0)
00088 return 0;
00089 }
00090 return 1;
00091 }
00092
00093
00094 static int __size(Partition_Element *p) {
00095 int size = 0;
00096 Partition_Node *node = p->head;
00097 while (node != 0) {
00098 size++;
00099 node = node->next;
00100 }
00101 return size;
00102 }
00103
00104
00105 static unsigned int __p_length(Partition *p, int k)
00106 {
00107 int i, size = 0;
00108 for (i = 0; i < k; i++) {
00109 if (p->array(i)->head != 0)
00110 size++;
00111 }
00112 return size;
00113 }
00114
00115
00116 static int __empty(Partition_Element *p) {
00117 return (p->head == 0);
00118 }
00119
00120
00121 static int __vertex_in_partition(Partition *p, int size, int v)
00122 {
00123 int i;
00124 for (i = 0; i < size; i++) {
00125 Partition_Node *vertex = p->array(i)->head;
00126
00127 if (vertex == 0)
00128 return i;
00129
00130 while (vertex != 0) {
00131 if (vertex->id == v)
00132 return i;
00133 vertex = vertex->next;
00134 }
00135 }
00136 return -1;
00137 }
00138
00139
00140
00141 Ksection::Ksection(Graph *g, unsigned int k) : Partition(k)
00142 {
00143 unsigned int i, v_done[g->V];
00144 unsigned int restart = 0;
00145 int target_size = g->V / k;
00146 Edge *sorted[g->E];
00147 Partition *l = new Partition(g->V);
00148
00149 for (i = 0; i < g->V; i++)
00150 v_done[i] = 0;
00151
00152 __sort_edges(g, sorted);
00153
00154 while (!__complete(v_done, g->V) || __p_length(l, g->V) != k) {
00155 if (__complete(v_done, g->V)) {
00156 restart = 0;
00157 target_size++;
00158 }
00159 int first = 1;
00160
00161 for (i = restart; i < g->E; i++) {
00162 unsigned int u_id = sorted[i]->u->id;
00163 unsigned int v_id = sorted[i]->v->id;
00164 int q = __vertex_in_partition(l, g->V, u_id);
00165 int r = __vertex_in_partition(l, g->V, v_id);
00166
00167 if (__empty(l->array(q)) && __empty(l->array(r))) {
00168 int z = -1;
00169 Partition_Node *u = new Partition_Node();
00170 u->id = u_id;
00171 u->next = 0;
00172
00173 Partition_Node *v = new Partition_Node();
00174 v->id = v_id;
00175 v->next = 0;
00176
00177 if (target_size < 2) {
00178 if (q == r)
00179 z = q + 1;
00180 else
00181 z = r;
00182 l->array(q)->head =
00183 l->array(q)->tail = u;
00184 l->array(z)->head =
00185 l->array(z)->tail = v;
00186 } else {
00187 if (q < 0)
00188 z = r;
00189 else
00190 z = q;
00191
00192 u->next = v;
00193 if (l->array(z)->tail != 0)
00194 l->array(z)->tail->next = u;
00195 else
00196 l->array(z)->head = u;
00197 l->array(z)->tail = v;
00198 }
00199
00200 v_done[u_id] = 1;
00201 v_done[v_id] = 1;
00202 break;
00203 } else if (__empty(l->array(q)) &&
00204 __size(l->array(r)) < target_size) {
00205 l->array(r)->tail->next = new Partition_Node();
00206 l->array(r)->tail = l->array(r)->tail->next;
00207 l->array(r)->tail->id = u_id;
00208 l->array(r)->tail->next = 0;
00209
00210 if (q < r) {
00211 l->array(q)->head = l->array(r)->head;
00212 l->array(q)->tail = l->array(r)->tail;
00213 l->array(r)->head = 0;
00214 l->array(r)->tail = 0;
00215 }
00216 v_done[u_id] = 1;
00217 break;
00218 } else if (__empty(l->array(r)) &&
00219 __size(l->array(q)) < target_size) {
00220 l->array(q)->tail->next = new Partition_Node();
00221 l->array(q)->tail = l->array(q)->tail->next;
00222 l->array(q)->tail->id = v_id;
00223 l->array(q)->tail->next = 0;
00224
00225 if (r < q) {
00226 l->array(r)->head = l->array(q)->head;
00227 l->array(r)->tail = l->array(q)->tail;
00228 l->array(q)->head = 0;
00229 l->array(q)->tail = 0;
00230 }
00231 v_done[v_id] = 1;
00232 break;
00233 } else if (!__empty(l->array(q)) &&
00234 !__empty(l->array(r)) &&
00235 (__size(l->array(q)) +
00236 __size(l->array(r))) <= target_size) {
00237 if (r < q) {
00238 l->array(r)->tail->next =
00239 l->array(q)->head;
00240 l->array(r)->tail = l->array(q)->tail;
00241 l->array(q)->head = 0;
00242 l->array(q)->tail = 0;
00243 } else if (q < r) {
00244 l->array(q)->tail->next =
00245 l->array(r)->head;
00246 l->array(q)->tail = l->array(r)->tail;
00247 l->array(r)->head = 0;
00248 l->array(r)->tail = 0;
00249 }
00250
00251 if (q != r) {
00252 unsigned int x;
00253 for (x = 0; x < g->V - 1; x++) {
00254 if (l->array(x)->head == 0 &&
00255 l->array(x+1)->head != 0) {
00256 l->array(x)->head =
00257 l->array(x+1)->head;
00258 l->array(x)->tail =
00259 l->array(x+1)->tail;
00260 l->array(x+1)->head = 0;
00261 l->array(x+1)->tail = 0;
00262 }
00263 }
00264 } else {
00265 if (first == 1) {
00266 first = 0;
00267 restart = i;
00268 }
00269 }
00270 } else {
00271 if (first == 1) {
00272 first = 0;
00273 restart = i;
00274 }
00275 }
00276 }
00277 }
00278
00279 for (i = 0; i < k; i++) {
00280 _arr[i].head = l->array(i)->head;
00281 _arr[i].tail = l->array(i)->tail;
00282 }
00283 }