N-sim
Emulation and simulation of
Wireless Sensor Networks



   Home


   Project Page


   Download


   CVS



   Installation


   Configuration


   Plug-ins




 Hosted by
SourceForge.net Logo

/home/brennan/n-sim/OrbisQuartus/control/ksection.cpp

Go to the documentation of this file.
00001 
00014 /*
00015  * Copyright 2007. Los Alamos National Security, LLC. This material
00016  * was produced under U.S. Government contract DE-AC52-06NA25396 for
00017  * Los Alamos National Laboratory (LANL), which is operated by Los
00018  * Alamos National Security, LLC, for the Department of Energy. The
00019  * U.S. Government has rights to use, reproduce, and distribute this
00020  * software. NEITHER THE GOVERNMENT NOR LOS ALAMOS NATIONAL SECURITY,
00021  * LLC, MAKES ANY WARRANTY, EXPRESS OR IMPLIED, OR ASSUMES ANY LEGAL
00022  * LIABILITY FOR THE USE OF THIS SOFTWARE. If software is modified to
00023  * produce derivative works, such modified software should be clearly
00024  * marked, so as not to confuse it with the version available from LANL.
00025  *
00026  * Additionally, this program is free software; you can redistribute
00027  * it and/or modify it under the terms of the GNU General Public
00028  * License as published by the Free Software Foundation; version 2 of
00029  * the License. Accordingly, this program is distributed in the hope
00030  * it will be useful, but WITHOUT ANY WARRANTY; without even the
00031  * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
00032  * PURPOSE. See the GNU General Public License for more details.
00033  */
00034 
00035 /*-------------------- Documentation block --------------------*/
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);   //  Theta(n logn), n = |E|
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 {   // ignore this edge
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 }


© 2007, Los Alamos National Security, LLC.