shortest_path.c

Go to the documentation of this file.
00001 /* LIBDGL -- a Directed Graph Library implementation
00002  * Copyright (C) 2002 Roberto Micarelli
00003  *
00004  * This program is free software; you can redistribute it and/or modify
00005  * it under the terms of the GNU General Public License as published by
00006  * the Free Software Foundation; either version 2 of the License, or
00007  * (at your option) any later version.
00008  *
00009  * This program is distributed in the hope that it will be useful,
00010  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00011  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00012  * GNU General Public License for more details.
00013  *
00014  * You should have received a copy of the GNU General Public License
00015  * along with this program; if not, write to the Free Software
00016  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
00017  */
00018 
00019 /* best view tabstop=4
00020  */
00021 
00022 #include <stdio.h>
00023 #include <sys/types.h>
00024 #include <sys/stat.h>
00025 #include <unistd.h>
00026 #include <stdlib.h>
00027 #include <fcntl.h>
00028 #include <time.h>
00029 #include <errno.h>
00030 
00031 #include "../type.h"
00032 #include "../graph.h"
00033 
00034 #include "opt.h"
00035 
00036 
00037 extern int errno;
00038 
00039 /* If the clipper function returns 1 , the node is discarded and
00040  * the traversing of the graph toward its direction is abandoned.
00041  * Try to change the return value to 1 and see that the program
00042  * will not find any more paths to destinations.
00043  * The clipper receives data relating the network segment being examinated.
00044  * The pvarg is a user pointer registered to dglShortestPath() and
00045  * passed back to the clipper.
00046  * As a demo, the main uses the ClipperContext_s structure to store a nodeid
00047  * that must be discarded during the search. The clipper receives
00048  * that pointer and checks every node against the one specified there.
00049  * If the node matches return 1 , otherwise return 0.
00050  */
00051 
00052 typedef struct {
00053         dglInt32_t node_to_discard;
00054 } ClipperContext_s;
00055 
00056 static int      clipper         (
00057                                                 dglGraph_s *    pgraph ,
00058                                                 dglSPClipInput_s * pIn ,
00059                                                 dglSPClipOutput_s * pOut ,
00060                                                 void *                  pvarg           /* caller's pointer */
00061                                                 )
00062 {
00063         ClipperContext_s * pclip = (ClipperContext_s*) pvarg;
00064 #if 0
00065         dglInt32_t * pnFromXYZ = (dglInt32_t*) dglNodeGet_Attr( pgraph, pIn->pnNodeFrom );
00066         dglInt32_t * pnToXYZ   = (dglInt32_t*) dglNodeGet_Attr( pgraph, pIn->pnNodeTo );
00067 
00068         printf( "clipper called:\n" );
00069         printf( "        from node: %ld - attributes x=%ld y=%ld z=%ld\n",
00070                 dglNodeGet_Id(pgraph, pIn->pnNodeFrom), pnFromXYZ[0], pnFromXYZ[1], pnFromXYZ[2]);
00071         printf( "        to   node: %ld - attributes x=%ld y=%ld z=%ld\n",
00072                 dglNodeGet_Id(pgraph, pIn->pnNodeTo), pnToXYZ[0], pnToXYZ[1], pnToXYZ[2]);
00073         printf( "        edge     : %ld\n",
00074                 dglEdgeGet_Id(pgraph, pIn->pnEdge) );
00075 #endif
00076 
00077         if ( pclip )
00078         {
00079                 if ( dglNodeGet_Id(pgraph, pIn->pnNodeTo) == pclip->node_to_discard )
00080                 {
00081                         /*
00082                         printf( "        discarder.\n" );
00083                         */
00084                         return 1;
00085                 }
00086         }
00087         /*
00088         printf( "        accepted.\n" );
00089         */
00090         return 0;
00091 }
00092 
00093 
00094 
00095 int main( int argc , char ** argv )
00096 {
00097         dglGraph_s              graph;
00098         dglInt32_t                      from , to;
00099 
00100         int                                     fd , nret , version;
00101         dglSPReport_s *         pReport;
00102         dglInt32_t                      nDistance;
00103         dglSPCache_s            spCache;
00104         ClipperContext_s        clipctx , * pclipctx;
00105 
00106         /* program options
00107          */
00108         char    *       pszFilein;
00109         char    *       pszFrom;
00110         char    *       pszTo;
00111         char    *       pszDiscard;
00112         char    *       pszVersion;
00113         Boolean         fDistance;
00114         Boolean         fUnflatten;
00115  
00116         GNO_BEGIN /*short       long        default     variable        help */
00117         GNO_OPTION( "g",        "graph",        NULL ,          & pszFilein ,   "graph file to view" )
00118         GNO_OPTION( "v",        "version",      NULL ,          & pszVersion ,  "alter graph version" )
00119         GNO_OPTION( "f",        "from",         NULL ,          & pszFrom ,             "from-node id" )
00120         GNO_OPTION( "t",        "to",           NULL ,          & pszTo ,               "to-node id" )
00121         GNO_OPTION( "d",        "discard",      NULL ,          & pszDiscard ,  "node to discard in clipper" )
00122         GNO_SWITCH( "D",        "distance",     False ,         & fDistance ,   "Report shortest distance only" )
00123         GNO_SWITCH( "U",        "unflatten",False ,             & fUnflatten ,  "Unflatten the graph before processing" )
00124         GNO_END
00125  
00126 
00127         if ( GNO_PARSE( argc , argv ) < 0 )
00128         {
00129                 return 1;
00130         }
00131         /* options parsed
00132          */
00133 
00134         if ( pszFilein == NULL || pszFrom == NULL || pszTo == NULL )
00135         {
00136                 GNO_HELP( "incomplete parameters" );
00137                 return 1;
00138         }
00139 
00140         if ( pszDiscard )
00141         {
00142                 clipctx.node_to_discard = atol( pszDiscard );
00143                 pclipctx = & clipctx;
00144         }
00145         else
00146                 pclipctx = NULL;
00147 
00148         if ( pszVersion ) {
00149                 version = atoi(pszVersion);
00150         }
00151 
00152         fd = open( pszFilein , O_RDONLY );
00153         if ( fd < 0 )
00154         {       
00155                 perror( "open" ); return 1;
00156         }
00157 
00158         nret = dglRead( & graph , fd );
00159 
00160         close( fd );
00161 
00162         if ( nret < 0 )
00163         {
00164                 fprintf( stderr , "dglRead error: %s\n" , dglStrerror( & graph ) );
00165                 return 1;
00166         }
00167 
00168         if ( fUnflatten ) dglUnflatten( &graph );
00169 
00170         if ( pszVersion ) dglSet_Version(&graph, version);
00171 
00172         from = atol( pszFrom );
00173         to = atol( pszTo );
00174 
00175         printf( "shortest path: from-node %ld - to-node %ld\n\n" , from , to );
00176 
00177         dglInitializeSPCache( & graph, & spCache );
00178 
00179         if ( fDistance == False ) {
00180                 nret = dglShortestPath( & graph , & pReport , from , to , clipper , pclipctx , & spCache );
00181 
00182                 if ( nret == 0 )
00183                 {
00184                         printf( "destination node is unreachable\n\n" );
00185                 }
00186                 else if ( nret < 0 ) 
00187                 {
00188                         fprintf( stderr , "dglShortestPath error: %s\n", dglStrerror( & graph ) );
00189                 }
00190                 else
00191                 {
00192                         int i;
00193         
00194                         printf( "shortest path report: total edges %ld - total distance %ld\n" , pReport->cArc , pReport->nDistance );
00195         
00196                         for( i = 0 ; i < pReport->cArc ; i ++ )
00197                         {
00198                                 printf( "edge[%d]: from %ld to %ld - travel cost %ld - user edgeid %ld - distance from start node %ld\n" ,
00199                                                 i,
00200                                                 pReport->pArc[i].nFrom,
00201                                                 pReport->pArc[i].nTo,
00202                                                 dglEdgeGet_Cost(&graph, pReport->pArc[i].pnEdge), /* this is the cost from clip() */
00203                                                 dglEdgeGet_Id(&graph, pReport->pArc[i].pnEdge),
00204                                                 pReport->pArc[i].nDistance
00205                                                 );
00206                         }
00207                         dglFreeSPReport( & graph , pReport );
00208                 }
00209         }
00210         else {
00211                 nret = dglShortestDistance( & graph , & nDistance , from , to , clipper , pclipctx , & spCache );
00212 
00213                 if ( nret == 0 )
00214                 {
00215                         if ( dglErrno(& graph) == 0 )
00216                         {
00217                                 printf( "destination node is unreachable\n\n" );
00218                         }
00219                 }
00220                 else if ( nret < 0 ) 
00221                 {
00222                         fprintf( stderr , "dglShortestDistance error: %s\n", dglStrerror( & graph ) );
00223                 }
00224                 else
00225                 {
00226                         printf( "shortest distance: %ld\n" , nDistance );
00227                 }
00228         }
00229 
00230         dglReleaseSPCache( & graph, & spCache );
00231         dglRelease( & graph );
00232 
00233         return 0;
00234 
00235 }

Generated on Sun Apr 6 17:32:44 2008 for GRASS by  doxygen 1.5.5