GRASS Programmer's Manual
6.4.2(2012)
|
00001 00022 #include <stdlib.h> 00023 #include <string.h> 00024 #include <grass/gis.h> 00025 #include <grass/dbmi.h> 00026 #include <grass/Vect.h> 00027 #include <grass/glocale.h> 00028 00029 static int From_node; /* from node set in SP and used by clipper for first arc */ 00030 00031 static int clipper(dglGraph_s * pgraph, 00032 dglSPClipInput_s * pargIn, 00033 dglSPClipOutput_s * pargOut, void *pvarg) 00034 { /* caller's pointer */ 00035 dglInt32_t cost; 00036 dglInt32_t from; 00037 00038 G_debug(3, "Net: clipper()"); 00039 00040 from = dglNodeGet_Id(pgraph, pargIn->pnNodeFrom); 00041 00042 G_debug(3, " Edge = %d NodeFrom = %d NodeTo = %d edge cost = %d", 00043 (int)dglEdgeGet_Id(pgraph, pargIn->pnEdge), 00044 (int)from, (int)dglNodeGet_Id(pgraph, pargIn->pnNodeTo), 00045 (int)pargOut->nEdgeCost); 00046 00047 if (from != From_node) { /* do not clip first */ 00048 if (dglGet_NodeAttrSize(pgraph) > 0) { 00049 memcpy(&cost, dglNodeGet_Attr(pgraph, pargIn->pnNodeFrom), 00050 sizeof(cost)); 00051 if (cost == -1) { /* closed, cannot go from this node except it is 'from' node */ 00052 G_debug(3, " closed node"); 00053 return 1; 00054 } 00055 else { 00056 G_debug(3, " EdgeCost += %d (node)", (int)cost); 00057 pargOut->nEdgeCost += cost; 00058 } 00059 } 00060 } 00061 else { 00062 G_debug(3, " don't clip first node"); 00063 } 00064 00065 return 0; 00066 } 00067 00076 void Vect_graph_init(GRAPH * graph, int nodes_costs) 00077 { 00078 dglInt32_t opaqueset[16] = 00079 { 360000, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; 00080 00081 G_debug(3, "Vect_graph_init()"); 00082 00083 if (nodes_costs) 00084 dglInitialize(graph, (dglByte_t) 1, sizeof(dglInt32_t), 00085 (dglInt32_t) 0, opaqueset); 00086 else 00087 dglInitialize(graph, (dglByte_t) 1, (dglInt32_t) 0, (dglInt32_t) 0, 00088 opaqueset); 00089 } 00090 00102 void Vect_graph_build(GRAPH * graph) 00103 { 00104 int ret; 00105 00106 G_debug(3, "Vect_graph_build()"); 00107 00108 ret = dglFlatten(graph); 00109 if (ret < 0) 00110 G_fatal_error(_("GngFlatten error")); 00111 } 00112 00128 void 00129 Vect_graph_add_edge(GRAPH * graph, int from, int to, double costs, int id) 00130 { 00131 int ret; 00132 dglInt32_t dglcosts; 00133 00134 G_debug(3, "Vect_add_edge() from = %d to = %d, costs = %f, id = %d", from, 00135 to, costs, id); 00136 00137 dglcosts = (dglInt32_t) costs *1000; 00138 00139 ret = 00140 dglAddEdge(graph, (dglInt32_t) from, (dglInt32_t) to, dglcosts, 00141 (dglInt32_t) id); 00142 if (ret < 0) 00143 G_fatal_error(_("Unable to add network arc")); 00144 } 00145 00159 void Vect_graph_set_node_costs(GRAPH * graph, int node, double costs) 00160 { 00161 dglInt32_t dglcosts; 00162 00163 /* TODO: Not tested! */ 00164 G_debug(3, "Vect_graph_set_node_costs()"); 00165 00166 dglcosts = (dglInt32_t) costs *1000; 00167 00168 dglNodeSet_Attr(graph, dglGetNode(graph, (dglInt32_t) node), &dglcosts); 00169 } 00170 00188 int 00189 Vect_graph_shortest_path(GRAPH * graph, int from, int to, struct ilist *List, 00190 double *cost) 00191 { 00192 int i, line, *pclip, cArc, nRet; 00193 dglSPReport_s *pSPReport; 00194 dglInt32_t nDistance; 00195 00196 G_debug(3, "Vect_graph_shortest_path(): from = %d, to = %d", from, to); 00197 00198 /* Note : if from == to dgl goes to nearest node and returns back (dgl feature) => 00199 * check here for from == to */ 00200 00201 if (List != NULL) 00202 Vect_reset_list(List); 00203 00204 /* Check if from and to are identical, otherwise dglib returns path to neares node and back! */ 00205 if (from == to) { 00206 if (cost != NULL) 00207 *cost = 0; 00208 return 0; 00209 } 00210 00211 From_node = from; 00212 00213 pclip = NULL; 00214 if (List != NULL) { 00215 nRet = 00216 dglShortestPath(graph, &pSPReport, (dglInt32_t) from, 00217 (dglInt32_t) to, clipper, pclip, NULL); 00218 } 00219 else { 00220 nRet = 00221 dglShortestDistance(graph, &nDistance, (dglInt32_t) from, 00222 (dglInt32_t) to, clipper, pclip, NULL); 00223 } 00224 00225 if (nRet == 0) { 00226 if (cost != NULL) 00227 *cost = PORT_DOUBLE_MAX; 00228 return -1; 00229 } 00230 else if (nRet < 0) { 00231 G_warning(_("dglShortestPath error: %s"), dglStrerror(graph)); 00232 return -1; 00233 } 00234 00235 if (List != NULL) { 00236 for (i = 0; i < pSPReport->cArc; i++) { 00237 line = dglEdgeGet_Id(graph, pSPReport->pArc[i].pnEdge); 00238 G_debug(2, "From %ld to %ld - cost %ld user %d distance %ld", 00239 pSPReport->pArc[i].nFrom, pSPReport->pArc[i].nTo, 00240 /* this is the cost from clip() */ 00241 dglEdgeGet_Cost(graph, pSPReport->pArc[i].pnEdge) / 1000, 00242 line, pSPReport->pArc[i].nDistance); 00243 Vect_list_append(List, line); 00244 } 00245 } 00246 00247 if (cost != NULL) { 00248 if (List != NULL) 00249 *cost = (double)pSPReport->nDistance / 1000; 00250 else 00251 *cost = (double)nDistance / 1000; 00252 } 00253 00254 if (List != NULL) { 00255 cArc = pSPReport->cArc; 00256 dglFreeSPReport(graph, pSPReport); 00257 } 00258 else 00259 cArc = 0; 00260 00261 return (cArc); 00262 }