eg_dijkstra.ex.c

Go to the documentation of this file.
00001 /* EGlib "Efficient General Library" provides some basic structures and
00002  * algorithms commons in many optimization algorithms.
00003  *
00004  * Copyright (C) 2005 Daniel Espinoza and Marcos Goycoolea.
00005  * 
00006  * This library is free software; you can redistribute it and/or modify it
00007  * under the terms of the GNU Lesser General Public License as published by the
00008  * Free Software Foundation; either version 2.1 of the License, or (at your
00009  * option) any later version.
00010  *
00011  * This library is distributed in the hope that it will be useful, but 
00012  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 
00013  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public 
00014  * License for more details.
00015  *
00016  * You should have received a copy of the GNU Lesser General Public License
00017  * along with this library; if not, write to the Free Software Foundation,
00018  * Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA 
00019  * */
00020 /** @file 
00021  * @ingroup EGalgDijkstra */
00022 /** @addtogroup EGalgDijkstra */
00023 /** @{ */
00024 /* ========================================================================= */
00025 #include "EGlib.h"
00026 static char fname[1024];
00027 static int32_t source=0;
00028 static int verbose=1;
00029 /* ========================================================================= */
00030 static inline void djk_usage(const char*const progname)
00031 {
00032   fprintf(stderr,"Usage: %s [options]\n",progname);
00033   fprintf(stderr,"\t-h    print this message and exit\n");
00034   fprintf(stderr,"\t-v n  verbosity level, default %d\n",verbose);
00035   fprintf(stderr,"\t-f s  input file to use, must be a graph as in concorde's x-format (mandatory argument)\n");
00036   fprintf(stderr,"\t-s n  node from where start dijkstra\n");
00037   return;
00038 }
00039 /* ========================================================================= */
00040 /** @brief parse-args */
00041 static inline void djk_parseargs(int argc,char**argv)
00042 {
00043   int c, has_file=0;
00044   while((c=getopt(argc,argv,"f:v:hs:"))!=EOF)
00045   {
00046     switch(c)
00047     {
00048       case 'f':
00049         snprintf(fname,1023,"%s",optarg);
00050         has_file=1;
00051         break;
00052       case 'v':
00053         verbose=atoi(optarg);
00054         break;
00055       case 'h':
00056         djk_usage(argv[0]);
00057         exit(EXIT_SUCCESS);
00058       case 's':
00059         source=atoi(optarg);
00060         break;
00061       default:
00062         fprintf(stderr,"Unknown parameter %c\n",c);
00063         djk_usage(argv[0]);
00064         exit(EXIT_FAILURE);
00065     }
00066   }
00067   if(!has_file)
00068   {
00069     djk_usage(argv[0]);
00070     exit(EXIT_FAILURE);
00071   }
00072   fprintf(stderr,"\tInput file   : %s\n",fname);
00073   fprintf(stderr,"\tverbose level: %d\n",verbose);
00074   fprintf(stderr,"\tsource       : %"PRId32"\n",source);
00075   return;
00076 }
00077 /* ========================================================================= */
00078 /** @brief A simple example of a directed graph using (EGdEgraph) structures.
00079  * @return zero on success, non-zero- otherwise.
00080  * @par Description:
00081  * Show how to use a directed graph, modify it and display it's contents */
00082 int main (int argc,char**argv)
00083 {
00084   int rval=0,i;
00085   EGtimer_t rt,pp,dt;
00086   int32_t n,m,*edges=0,*in_perm=0,*in_d=0,*in_beg=0,*in_e=0,*t=0,*father=0;
00087   EGlpNum_t*weight=0,*sweight=0,*dist=0;
00088   EGioFile_t* input=0;
00089   EGtimerReset(&dt);
00090   EGtimerReset(&rt);
00091   EGtimerReset(&pp);
00092   EGtimerStart(&rt);
00093   EGlib_info();
00094   EGlib_version();
00095   EGlpNumStart();
00096   /* set signal and limits */
00097   EGsigSet(rval,CLEANUP);
00098   EGsetLimits(3600.0,4294967295UL);
00099   djk_parseargs(argc,argv);
00100   input = EGioOpen(fname,"r");
00101   EGcallD(EGguReadXgraph(input,&n,&m,&edges,&weight));
00102   EGioClose(input);
00103   EGtimerStop(&rt);
00104   EGtimerStart(&pp);
00105   t=EGsMalloc(int32_t,n);
00106   father=EGsMalloc(int32_t,n);
00107   memset(t,1,sizeof(int32_t)*n);
00108   dist=EGlpNumAllocArray(n);
00109   sweight=EGlpNumAllocArray(m);
00110   in_e=EGsMalloc(int32_t,m);
00111   in_d=EGsMalloc(int32_t,n);
00112   in_beg=EGsMalloc(int32_t,n);
00113   in_perm=EGsMalloc(int32_t,m);
00114   EGcallD(EGguDegree(n,m,edges,in_d,in_beg,in_e,in_perm,0,0,0,0));
00115   for(i=m;i--;)
00116     EGlpNumCopy(sweight[in_perm[i]],weight[i]);
00117   EGtimerStop(&pp);
00118   EGtimerStart(&dt);
00119   EGcallD(EGalgDJK(n,m,in_d,in_beg,in_e,sweight,source,n,t,father,dist));
00120   EGtimerStop(&dt);
00121   fprintf(stderr,"Stats:\n");
00122   fprintf(stderr,"\tnnodes %"PRId32" nedges %"PRId32"\n",n,m);
00123   fprintf(stderr,"\tread time       : %.3lf\n",rt.time);
00124   fprintf(stderr,"\tpre-process time: %.3lf\n",pp.time);
00125   fprintf(stderr,"\tdijkstra time   : %.3lf\n",dt.time);
00126   if(verbose>1)
00127   {
00128     for(i=0;i<n;i++)
00129     {
00130       fprintf(stderr,"\t\tNode %d father %"PRId32" dist %.3lf\n",i,father[i],EGlpNumToLf(dist[i]));
00131     }
00132   }
00133   CLEANUP:
00134   EGlpNumFreeArray(weight);
00135   EGlpNumFreeArray(sweight);
00136   EGlpNumFreeArray(dist);
00137   EGfree(edges);
00138   EGfree(in_d);
00139   EGfree(in_e);
00140   EGfree(in_beg);
00141   EGfree(in_perm);
00142   EGfree(t);
00143   EGfree(father);
00144   EGlpNumClear();
00145   return rval;
00146 }
00147 
00148 
00149 
00150 /* ========================================================================= */
00151 /** @} */
00152 
00153