GRASS Programmer's Manual 6.4.1(2011)
Vlib/graph.c
Go to the documentation of this file.
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 }
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Defines