prim.c
Go to the documentation of this file.
00001 /*------------------------------------------------------------------------
00002  *---------------------           RT-WMP              --------------------
00003  *------------------------------------------------------------------------
00004  *                                                         V7.0B  11/05/10
00005  *
00006  *
00007  *  File: ./src/core/prim.c
00008  *  Authors: Danilo Tardioli
00009  *  ----------------------------------------------------------------------
00010  *  Copyright (C) 2000-2010, Universidad de Zaragoza, SPAIN
00011  *
00012  *  Contact Addresses: Danilo Tardioli                   dantard@unizar.es
00013  *
00014  *  RT-WMP is free software; you can  redistribute it and/or  modify it
00015  *  under the terms of the GNU General Public License  as published by the
00016  *  Free Software Foundation;  either  version 2, or (at  your option) any
00017  *  later version.
00018  *
00019  *  RT-WMP  is distributed  in the  hope  that  it will be   useful, but
00020  *  WITHOUT  ANY  WARRANTY;     without  even the   implied   warranty  of
00021  *  MERCHANTABILITY  or  FITNESS FOR A  PARTICULAR PURPOSE.    See the GNU
00022  *  General Public License for more details.
00023  *
00024  *  You should have received  a  copy of  the  GNU General Public  License
00025  *  distributed with RT-WMP;  see file COPYING.   If not,  write to the
00026  *  Free Software  Foundation,  59 Temple Place  -  Suite 330,  Boston, MA
00027  *  02111-1307, USA.
00028  *
00029  *  As a  special exception, if you  link this  unit  with other  files to
00030  *  produce an   executable,   this unit  does  not  by  itself cause  the
00031  *  resulting executable to be covered by the  GNU General Public License.
00032  *  This exception does  not however invalidate  any other reasons why the
00033  *  executable file might be covered by the GNU Public License.
00034  *
00035  *----------------------------------------------------------------------*/
00036 
00037 #include "config/compiler.h"
00038 #include "include/wmp_utils.h"
00039 
00040 #define DBL_MAX 2^31
00041 
00042 static char **tree;
00043 static int **graph;
00044 static char *vertexOnTree,N_ROBOTS;
00045 
00046 void init_prim(int nnodes){
00047         int i;
00048         N_ROBOTS=nnodes;
00049         graph=(int **) MALLOC(N_ROBOTS*sizeof(int*));
00050         tree=(char **) MALLOC(N_ROBOTS*sizeof(char*));
00051         // ??? vertexOnTree=(int *) MALLOC(N_ROBOTS*N_ROBOTS*sizeof(char));
00052         vertexOnTree=(char *) MALLOC(N_ROBOTS*N_ROBOTS*sizeof(char));
00053         for (i=0;i<N_ROBOTS;i++){
00054                 graph[i]=(int *) MALLOC(N_ROBOTS*sizeof(int));
00055                 tree[i]=(char *) MALLOC(N_ROBOTS*sizeof(char));
00056         }
00057 }
00058 
00059 void free_prim(void){
00060    int i;
00061 
00062    for (i=0;i<N_ROBOTS;i++){
00063       FREE(graph[i]);
00064       FREE(tree[i]);
00065    }
00066    FREE(vertexOnTree);
00067    FREE(tree);
00068    FREE(graph);
00069 }
00070 
00071 
00072 char ** prim(char **lqm){
00073         int i,j, numVertexOnTree;
00074    char val;
00075         int fail = 0;
00076         for (i=0;i<N_ROBOTS;i++){
00077                 for (j=0;j<N_ROBOTS;j++){
00078                         tree[i][j]=0;
00079                         val = lqm[i][j] < lqm[j][i] ? lqm[i][j]:lqm[j][i];
00080                         /* DEC09 simetrification matrix (less value) */
00081                         if (val > 0){
00082                                 graph[i][j]=100 - val;
00083                                 graph[j][i]=100 - val;
00084                         } else{
00085                                 graph[i][j]=DBL_MAX;
00086                                 graph[j][i]=DBL_MAX;
00087                         }
00088                         WMP_DBG(PRIM,"lqm: %d :%d :%d %f\n",lqm[i][j],i,j,graph[i][j]);
00089                 }
00090         }
00091 
00092         numVertexOnTree=1;    // ,vertexOnTree[N_ROBOTS];
00093         vertexOnTree[0]=0;
00094         while (numVertexOnTree < N_ROBOTS){
00095                 int minWeight=DBL_MAX, v;
00096 
00097                 int minWeightIdxi=-1;
00098                 int minWeightIdxj=-1;
00099                 int i,j;
00100                 for (i=0;i<numVertexOnTree;i++){
00101                         int vertex=vertexOnTree[i];
00102                         for (j=0;j<N_ROBOTS;j++){
00103                                 if (vertex==j) {
00104                                         continue;
00105                                 }
00106 
00107                                 if (graph[vertex][j] <= minWeight){
00108                                         minWeight=graph[vertex][j];
00109                                         minWeightIdxi=vertex;
00110                                         minWeightIdxj=j;
00111                                 }
00112                         }
00113                 }
00114                 /* XXX: Hay un caso en el que minWeightIdxi y minWeightIdxj = -1 */
00115                 if (minWeightIdxi < 0 || minWeightIdxj < 0){
00116                         static char txt[1000];
00117                         lqmToString(lqm,txt, N_ROBOTS);
00118                         WMP_DBG(PRIM,"PRIM Failed, LQM:\n %s\n",txt);
00119                         fail = 1;
00120                         break;
00121                 }
00122                 v=lqm[minWeightIdxi][minWeightIdxj];
00123                 if (v>0) {
00124                         v=99;
00125                 } else {
00126                         v=0;
00127                 }
00128                 tree[minWeightIdxi][minWeightIdxj]=v;
00129                 tree[minWeightIdxj][minWeightIdxi]=v;
00130                 for (i=0;i<numVertexOnTree;i++){
00131                         graph[(int)vertexOnTree[i]][minWeightIdxj]=DBL_MAX;
00132                         graph[minWeightIdxj][(int)vertexOnTree[i]]=DBL_MAX;
00133                 }
00134                 vertexOnTree[numVertexOnTree]=minWeightIdxj;
00135                 numVertexOnTree++;
00136         }
00137         if (!fail){
00138                 return tree;
00139         } else {
00140                 return lqm;
00141         }
00142 }
00143 
00144 
00145 
00146 
00147 
00148 


ros_rt_wmp
Author(s): Danilo Tardioli, dantard@unizar.es
autogenerated on Fri Jan 3 2014 12:07:55