00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
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
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
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
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
00082
00083 return 1;
00084 }
00085 }
00086
00087
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
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
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
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),
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 }