GRASS Programmer's Manual
6.4.1(2011)
|
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 }