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 {
00054     dglInt32_t node_to_discard;
00055 } ClipperContext_s;
00056 
00057 static int clipper(dglGraph_s * pgraph, dglSPClipInput_s * pIn, dglSPClipOutput_s * pOut, void *pvarg   /* caller's pointer */
00058     )
00059 {
00060     ClipperContext_s *pclip = (ClipperContext_s *) pvarg;
00061 
00062 #if 0
00063     dglInt32_t *pnFromXYZ =
00064         (dglInt32_t *) dglNodeGet_Attr(pgraph, pIn->pnNodeFrom);
00065     dglInt32_t *pnToXYZ =
00066         (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],
00071            pnFromXYZ[2]);
00072     printf("        to   node: %ld - attributes x=%ld y=%ld z=%ld\n",
00073            dglNodeGet_Id(pgraph, pIn->pnNodeTo), pnToXYZ[0], pnToXYZ[1],
00074            pnToXYZ[2]);
00075     printf("        edge     : %ld\n", dglEdgeGet_Id(pgraph, pIn->pnEdge));
00076 #endif
00077 
00078     if (pclip) {
00079         if (dglNodeGet_Id(pgraph, pIn->pnNodeTo) == pclip->node_to_discard) {
00080             /*
00081                printf( "        discarder.\n" );
00082              */
00083             return 1;
00084         }
00085     }
00086     /*
00087        printf( "        accepted.\n" );
00088      */
00089     return 0;
00090 }
00091 
00092 
00093 
00094 int main(int argc, char **argv)
00095 {
00096     dglGraph_s graph;
00097     dglInt32_t from, to;
00098 
00099     int fd, nret, version;
00100     dglSPReport_s *pReport;
00101     dglInt32_t nDistance;
00102     dglSPCache_s spCache;
00103     ClipperContext_s clipctx, *pclipctx;
00104 
00105     /* program options
00106      */
00107     char *pszFilein;
00108     char *pszFrom;
00109     char *pszTo;
00110     char *pszDiscard;
00111     char *pszVersion;
00112     Boolean fDistance;
00113     Boolean fUnflatten;
00114 
00115     GNO_BEGIN                   /*short       long        default     variable        help */
00116         GNO_OPTION("g", "graph", NULL, &pszFilein, "graph file to view")
00117         GNO_OPTION("v", "version", NULL, &pszVersion, "alter graph version")
00118         GNO_OPTION("f", "from", NULL, &pszFrom, "from-node id")
00119         GNO_OPTION("t", "to", NULL, &pszTo, "to-node id")
00120         GNO_OPTION("d", "discard", NULL, &pszDiscard,
00121                    "node to discard in clipper")
00122         GNO_SWITCH("D", "distance", False, &fDistance,
00123                    "Report shortest distance only")
00124         GNO_SWITCH("U", "unflatten", False, &fUnflatten,
00125                    "Unflatten the graph before processing")
00126     GNO_END if (GNO_PARSE(argc, argv) < 0)
00127     {
00128         return 1;
00129     }
00130     /* options parsed
00131      */
00132 
00133     if (pszFilein == NULL || pszFrom == NULL || pszTo == NULL) {
00134         GNO_HELP("incomplete parameters");
00135         return 1;
00136     }
00137 
00138     if (pszDiscard) {
00139         clipctx.node_to_discard = atol(pszDiscard);
00140         pclipctx = &clipctx;
00141     }
00142     else
00143         pclipctx = NULL;
00144 
00145     if (pszVersion) {
00146         version = atoi(pszVersion);
00147     }
00148 
00149     fd = open(pszFilein, O_RDONLY);
00150     if (fd < 0) {
00151         perror("open");
00152         return 1;
00153     }
00154 
00155     nret = dglRead(&graph, fd);
00156 
00157     close(fd);
00158 
00159     if (nret < 0) {
00160         fprintf(stderr, "dglRead error: %s\n", dglStrerror(&graph));
00161         return 1;
00162     }
00163 
00164     if (fUnflatten)
00165         dglUnflatten(&graph);
00166 
00167     if (pszVersion)
00168         dglSet_Version(&graph, version);
00169 
00170     from = atol(pszFrom);
00171     to = atol(pszTo);
00172 
00173     printf("shortest path: from-node %ld - to-node %ld\n\n", from, to);
00174 
00175     dglInitializeSPCache(&graph, &spCache);
00176 
00177     if (fDistance == False) {
00178         nret =
00179             dglShortestPath(&graph, &pReport, from, to, clipper, pclipctx,
00180                             &spCache);
00181 
00182         if (nret == 0) {
00183             printf("destination node is unreachable\n\n");
00184         }
00185         else if (nret < 0) {
00186             fprintf(stderr, "dglShortestPath error: %s\n",
00187                     dglStrerror(&graph));
00188         }
00189         else {
00190             int i;
00191 
00192             printf
00193                 ("shortest path report: total edges %ld - total distance %ld\n",
00194                  pReport->cArc, pReport->nDistance);
00195 
00196             for (i = 0; i < pReport->cArc; i++) {
00197                 printf("edge[%d]: from %ld to %ld - travel cost %ld - user edgeid %ld - distance from start node %ld\n", i, pReport->pArc[i].nFrom, pReport->pArc[i].nTo, dglEdgeGet_Cost(&graph, pReport->pArc[i].pnEdge),     /* this is the cost from clip() */
00198                        dglEdgeGet_Id(&graph, pReport->pArc[i].pnEdge),
00199                        pReport->pArc[i].nDistance);
00200             }
00201             dglFreeSPReport(&graph, pReport);
00202         }
00203     }
00204     else {
00205         nret =
00206             dglShortestDistance(&graph, &nDistance, from, to, clipper,
00207                                 pclipctx, &spCache);
00208 
00209         if (nret == 0) {
00210             if (dglErrno(&graph) == 0) {
00211                 printf("destination node is unreachable\n\n");
00212             }
00213         }
00214         else if (nret < 0) {
00215             fprintf(stderr, "dglShortestDistance error: %s\n",
00216                     dglStrerror(&graph));
00217         }
00218         else {
00219             printf("shortest distance: %ld\n", nDistance);
00220         }
00221     }
00222 
00223     dglReleaseSPCache(&graph, &spCache);
00224     dglRelease(&graph);
00225 
00226     return 0;
00227 
00228 }