GRASS Programmer's Manual  6.4.2(2012)
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
shortest_path.c
Go to the documentation of this file.
1 /* LIBDGL -- a Directed Graph Library implementation
2  * Copyright (C) 2002 Roberto Micarelli
3  *
4  * This program is free software; you can redistribute it and/or modify
5  * it under the terms of the GNU General Public License as published by
6  * the Free Software Foundation; either version 2 of the License, or
7  * (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software
16  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
17  */
18 
19 /* best view tabstop=4
20  */
21 
22 #include <stdio.h>
23 #include <sys/types.h>
24 #include <sys/stat.h>
25 #include <unistd.h>
26 #include <stdlib.h>
27 #include <fcntl.h>
28 #include <time.h>
29 #include <errno.h>
30 
31 #include "../type.h"
32 #include "../graph.h"
33 
34 #include "opt.h"
35 
36 
37 extern int errno;
38 
39 /* If the clipper function returns 1 , the node is discarded and
40  * the traversing of the graph toward its direction is abandoned.
41  * Try to change the return value to 1 and see that the program
42  * will not find any more paths to destinations.
43  * The clipper receives data relating the network segment being examinated.
44  * The pvarg is a user pointer registered to dglShortestPath() and
45  * passed back to the clipper.
46  * As a demo, the main uses the ClipperContext_s structure to store a nodeid
47  * that must be discarded during the search. The clipper receives
48  * that pointer and checks every node against the one specified there.
49  * If the node matches return 1 , otherwise return 0.
50  */
51 
52 typedef struct
53 {
56 
57 static int clipper(dglGraph_s * pgraph, dglSPClipInput_s * pIn, dglSPClipOutput_s * pOut, void *pvarg /* caller's pointer */
58  )
59 {
60  ClipperContext_s *pclip = (ClipperContext_s *) pvarg;
61 
62 #if 0
63  dglInt32_t *pnFromXYZ =
64  (dglInt32_t *) dglNodeGet_Attr(pgraph, pIn->pnNodeFrom);
65  dglInt32_t *pnToXYZ =
66  (dglInt32_t *) dglNodeGet_Attr(pgraph, pIn->pnNodeTo);
67 
68  printf("clipper called:\n");
69  printf(" from node: %ld - attributes x=%ld y=%ld z=%ld\n",
70  dglNodeGet_Id(pgraph, pIn->pnNodeFrom), pnFromXYZ[0], pnFromXYZ[1],
71  pnFromXYZ[2]);
72  printf(" to node: %ld - attributes x=%ld y=%ld z=%ld\n",
73  dglNodeGet_Id(pgraph, pIn->pnNodeTo), pnToXYZ[0], pnToXYZ[1],
74  pnToXYZ[2]);
75  printf(" edge : %ld\n", dglEdgeGet_Id(pgraph, pIn->pnEdge));
76 #endif
77 
78  if (pclip) {
79  if (dglNodeGet_Id(pgraph, pIn->pnNodeTo) == pclip->node_to_discard) {
80  /*
81  printf( " discarder.\n" );
82  */
83  return 1;
84  }
85  }
86  /*
87  printf( " accepted.\n" );
88  */
89  return 0;
90 }
91 
92 
93 
94 int main(int argc, char **argv)
95 {
96  dglGraph_s graph;
97  dglInt32_t from, to;
98 
99  int fd, nret, version;
100  dglSPReport_s *pReport;
101  dglInt32_t nDistance;
102  dglSPCache_s spCache;
103  ClipperContext_s clipctx, *pclipctx;
104 
105  /* program options
106  */
107  char *pszFilein;
108  char *pszFrom;
109  char *pszTo;
110  char *pszDiscard;
111  char *pszVersion;
112  Boolean fDistance;
113  Boolean fUnflatten;
114 
115  GNO_BEGIN /*short long default variable help */
116  GNO_OPTION("g", "graph", NULL, &pszFilein, "graph file to view")
117  GNO_OPTION("v", "version", NULL, &pszVersion, "alter graph version")
118  GNO_OPTION("f", "from", NULL, &pszFrom, "from-node id")
119  GNO_OPTION("t", "to", NULL, &pszTo, "to-node id")
120  GNO_OPTION("d", "discard", NULL, &pszDiscard,
121  "node to discard in clipper")
122  GNO_SWITCH("D", "distance", False, &fDistance,
123  "Report shortest distance only")
124  GNO_SWITCH("U", "unflatten", False, &fUnflatten,
125  "Unflatten the graph before processing")
126  GNO_END if (GNO_PARSE(argc, argv) < 0)
127  {
128  return 1;
129  }
130  /* options parsed
131  */
132 
133  if (pszFilein == NULL || pszFrom == NULL || pszTo == NULL) {
134  GNO_HELP("incomplete parameters");
135  return 1;
136  }
137 
138  if (pszDiscard) {
139  clipctx.node_to_discard = atol(pszDiscard);
140  pclipctx = &clipctx;
141  }
142  else
143  pclipctx = NULL;
144 
145  if (pszVersion) {
146  version = atoi(pszVersion);
147  }
148 
149  fd = open(pszFilein, O_RDONLY);
150  if (fd < 0) {
151  perror("open");
152  return 1;
153  }
154 
155  nret = dglRead(&graph, fd);
156 
157  close(fd);
158 
159  if (nret < 0) {
160  fprintf(stderr, "dglRead error: %s\n", dglStrerror(&graph));
161  return 1;
162  }
163 
164  if (fUnflatten)
165  dglUnflatten(&graph);
166 
167  if (pszVersion)
168  dglSet_Version(&graph, version);
169 
170  from = atol(pszFrom);
171  to = atol(pszTo);
172 
173  printf("shortest path: from-node %ld - to-node %ld\n\n", from, to);
174 
175  dglInitializeSPCache(&graph, &spCache);
176 
177  if (fDistance == False) {
178  nret =
179  dglShortestPath(&graph, &pReport, from, to, clipper, pclipctx,
180  &spCache);
181 
182  if (nret == 0) {
183  printf("destination node is unreachable\n\n");
184  }
185  else if (nret < 0) {
186  fprintf(stderr, "dglShortestPath error: %s\n",
187  dglStrerror(&graph));
188  }
189  else {
190  int i;
191 
192  printf
193  ("shortest path report: total edges %ld - total distance %ld\n",
194  pReport->cArc, pReport->nDistance);
195 
196  for (i = 0; i < pReport->cArc; i++) {
197  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() */
198  dglEdgeGet_Id(&graph, pReport->pArc[i].pnEdge),
199  pReport->pArc[i].nDistance);
200  }
201  dglFreeSPReport(&graph, pReport);
202  }
203  }
204  else {
205  nret =
206  dglShortestDistance(&graph, &nDistance, from, to, clipper,
207  pclipctx, &spCache);
208 
209  if (nret == 0) {
210  if (dglErrno(&graph) == 0) {
211  printf("destination node is unreachable\n\n");
212  }
213  }
214  else if (nret < 0) {
215  fprintf(stderr, "dglShortestDistance error: %s\n",
216  dglStrerror(&graph));
217  }
218  else {
219  printf("shortest distance: %ld\n", nDistance);
220  }
221  }
222 
223  dglReleaseSPCache(&graph, &spCache);
224  dglRelease(&graph);
225 
226  return 0;
227 
228 }