GRASS Programmer's Manual  6.5.svn(2014)-r66266
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
Vlib/graph.c
Go to the documentation of this file.
1 
22 #include <stdlib.h>
23 #include <string.h>
24 #include <grass/gis.h>
25 #include <grass/dbmi.h>
26 #include <grass/Vect.h>
27 #include <grass/glocale.h>
28 
29 static int From_node; /* from node set in SP and used by clipper for first arc */
30 
31 static int clipper(dglGraph_s * pgraph,
32  dglSPClipInput_s * pargIn,
33  dglSPClipOutput_s * pargOut, void *pvarg)
34 { /* caller's pointer */
35  dglInt32_t cost;
36  dglInt32_t from;
37 
38  G_debug(3, "Net: clipper()");
39 
40  from = dglNodeGet_Id(pgraph, pargIn->pnNodeFrom);
41 
42  G_debug(3, " Edge = %d NodeFrom = %d NodeTo = %d edge cost = %d",
43  (int)dglEdgeGet_Id(pgraph, pargIn->pnEdge),
44  (int)from, (int)dglNodeGet_Id(pgraph, pargIn->pnNodeTo),
45  (int)pargOut->nEdgeCost);
46 
47  if (from != From_node) { /* do not clip first */
48  if (dglGet_NodeAttrSize(pgraph) > 0) {
49  memcpy(&cost, dglNodeGet_Attr(pgraph, pargIn->pnNodeFrom),
50  sizeof(cost));
51  if (cost == -1) { /* closed, cannot go from this node except it is 'from' node */
52  G_debug(3, " closed node");
53  return 1;
54  }
55  else {
56  G_debug(3, " EdgeCost += %d (node)", (int)cost);
57  pargOut->nEdgeCost += cost;
58  }
59  }
60  }
61  else {
62  G_debug(3, " don't clip first node");
63  }
64 
65  return 0;
66 }
67 
76 void Vect_graph_init(GRAPH * graph, int nodes_costs)
77 {
78  dglInt32_t opaqueset[16] =
79  { 360000, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
80 
81  G_debug(3, "Vect_graph_init()");
82 
83  if (nodes_costs)
84  dglInitialize(graph, (dglByte_t) 1, sizeof(dglInt32_t),
85  (dglInt32_t) 0, opaqueset);
86  else
87  dglInitialize(graph, (dglByte_t) 1, (dglInt32_t) 0, (dglInt32_t) 0,
88  opaqueset);
89 }
90 
102 void Vect_graph_build(GRAPH * graph)
103 {
104  int ret;
105 
106  G_debug(3, "Vect_graph_build()");
107 
108  ret = dglFlatten(graph);
109  if (ret < 0)
110  G_fatal_error(_("GngFlatten error"));
111 }
112 
128 void
129 Vect_graph_add_edge(GRAPH * graph, int from, int to, double costs, int id)
130 {
131  int ret;
132  dglInt32_t dglcosts;
133 
134  G_debug(3, "Vect_add_edge() from = %d to = %d, costs = %f, id = %d", from,
135  to, costs, id);
136 
137  dglcosts = (dglInt32_t) costs *1000;
138 
139  ret =
140  dglAddEdge(graph, (dglInt32_t) from, (dglInt32_t) to, dglcosts,
141  (dglInt32_t) id);
142  if (ret < 0)
143  G_fatal_error(_("Unable to add network arc"));
144 }
145 
159 void Vect_graph_set_node_costs(GRAPH * graph, int node, double costs)
160 {
161  dglInt32_t dglcosts;
162 
163  /* TODO: Not tested! */
164  G_debug(3, "Vect_graph_set_node_costs()");
165 
166  dglcosts = (dglInt32_t) costs *1000;
167 
168  dglNodeSet_Attr(graph, dglGetNode(graph, (dglInt32_t) node), &dglcosts);
169 }
170 
188 int
189 Vect_graph_shortest_path(GRAPH * graph, int from, int to, struct ilist *List,
190  double *cost)
191 {
192  int i, line, *pclip, cArc, nRet;
193  dglSPReport_s *pSPReport;
194  dglInt32_t nDistance;
195 
196  G_debug(3, "Vect_graph_shortest_path(): from = %d, to = %d", from, to);
197 
198  /* Note : if from == to dgl goes to nearest node and returns back (dgl feature) =>
199  * check here for from == to */
200 
201  if (List != NULL)
202  Vect_reset_list(List);
203 
204  /* Check if from and to are identical, otherwise dglib returns path to neares node and back! */
205  if (from == to) {
206  if (cost != NULL)
207  *cost = 0;
208  return 0;
209  }
210 
211  From_node = from;
212 
213  pclip = NULL;
214  if (List != NULL) {
215  nRet =
216  dglShortestPath(graph, &pSPReport, (dglInt32_t) from,
217  (dglInt32_t) to, clipper, pclip, NULL);
218  }
219  else {
220  nRet =
221  dglShortestDistance(graph, &nDistance, (dglInt32_t) from,
222  (dglInt32_t) to, clipper, pclip, NULL);
223  }
224 
225  if (nRet == 0) {
226  if (cost != NULL)
227  *cost = PORT_DOUBLE_MAX;
228  return -1;
229  }
230  else if (nRet < 0) {
231  G_warning(_("dglShortestPath error: %s"), dglStrerror(graph));
232  return -1;
233  }
234 
235  if (List != NULL) {
236  for (i = 0; i < pSPReport->cArc; i++) {
237  line = dglEdgeGet_Id(graph, pSPReport->pArc[i].pnEdge);
238  G_debug(2, "From %ld to %ld - cost %ld user %d distance %ld",
239  pSPReport->pArc[i].nFrom, pSPReport->pArc[i].nTo,
240  /* this is the cost from clip() */
241  dglEdgeGet_Cost(graph, pSPReport->pArc[i].pnEdge) / 1000,
242  line, pSPReport->pArc[i].nDistance);
243  Vect_list_append(List, line);
244  }
245  }
246 
247  if (cost != NULL) {
248  if (List != NULL)
249  *cost = (double)pSPReport->nDistance / 1000;
250  else
251  *cost = (double)nDistance / 1000;
252  }
253 
254  if (List != NULL) {
255  cArc = pSPReport->cArc;
256  dglFreeSPReport(graph, pSPReport);
257  }
258  else
259  cArc = 0;
260 
261  return (cArc);
262 }
dglInt32_t dglNodeGet_Id(dglGraph_s *pGraph, dglInt32_t *pnNode)
Definition: dglib/graph.c:213
int dglShortestPath(dglGraph_s *pGraph, dglSPReport_s **ppReport, dglInt32_t nStart, dglInt32_t nDestination, dglSPClip_fn fnClip, void *pvClipArg, dglSPCache_s *pCache)
Definition: dglib/graph.c:785
int Vect_graph_shortest_path(GRAPH *graph, int from, int to, struct ilist *List, double *cost)
Find shortest path.
Definition: Vlib/graph.c:189
unsigned char dglByte_t
Definition: type.h:36
int dglAddEdge(dglGraph_s *pGraph, dglInt32_t nHead, dglInt32_t nTail, dglInt32_t nCost, dglInt32_t nEdge)
Definition: dglib/graph.c:610
dglInt32_t * pnEdge
Definition: graph.h:215
dglInt32_t * pnEdge
Definition: graph.h:96
void Vect_graph_add_edge(GRAPH *graph, int from, int to, double costs, int id)
Add edge to graph.
Definition: Vlib/graph.c:129
dglInt32_t nDistance
Definition: graph.h:216
void Vect_graph_set_node_costs(GRAPH *graph, int node, double costs)
Set node costs.
Definition: Vlib/graph.c:159
void Vect_graph_init(GRAPH *graph, int nodes_costs)
Initialize graph structure.
Definition: Vlib/graph.c:76
int dglShortestDistance(dglGraph_s *pGraph, dglInt32_t *pnDistance, dglInt32_t nStart, dglInt32_t nDestination, dglSPClip_fn fnClip, void *pvClipArg, dglSPCache_s *pCache)
Definition: dglib/graph.c:817
int dglGet_NodeAttrSize(dglGraph_s *pgraph)
Definition: dglib/graph.c:1231
dglInt32_t nTo
Definition: graph.h:214
dglInt32_t dglEdgeGet_Id(dglGraph_s *pGraph, dglInt32_t *pnEdge)
Definition: dglib/graph.c:438
dglInt32_t * dglGetNode(dglGraph_s *pGraph, dglInt32_t nNodeId)
Definition: dglib/graph.c:155
void dglNodeSet_Attr(dglGraph_s *pGraph, dglInt32_t *pnNode, dglInt32_t *pnAttr)
Definition: dglib/graph.c:275
dglSPArc_s * pArc
Definition: graph.h:229
int Vect_reset_list(struct ilist *list)
Reset ilist structure.
long dglInt32_t
Definition: type.h:37
int Vect_list_append(struct ilist *list, int val)
Append new item to the end of list if not yet present.
dglInt32_t nFrom
Definition: graph.h:213
dglInt32_t nEdgeCost
Definition: graph.h:104
dglInt32_t * dglNodeGet_Attr(dglGraph_s *pGraph, dglInt32_t *pnNode)
Definition: dglib/graph.c:255
return NULL
Definition: dbfopen.c:1394
G_warning("category support for [%s] in mapset [%s] %s", name, mapset, type)
dglInt32_t * pnNodeFrom
Definition: graph.h:95
dglInt32_t * pnNodeTo
Definition: graph.h:97
int dglInitialize(dglGraph_s *pGraph, dglByte_t Version, dglInt32_t NodeAttrSize, dglInt32_t EdgeAttrSize, dglInt32_t *pOpaqueSet)
Definition: dglib/graph.c:53
int G_debug(int level, const char *msg,...)
Print debugging message.
Definition: gis/debug.c:51
dglInt32_t dglEdgeGet_Cost(dglGraph_s *pGraph, dglInt32_t *pnEdge)
Definition: dglib/graph.c:418
dglInt32_t cArc
Definition: graph.h:228
char * dglStrerror(dglGraph_s *pgraph)
Definition: dglib/graph.c:1160
void dglFreeSPReport(dglGraph_s *pgraph, dglSPReport_s *pSPReport)
Definition: dglib/graph.c:1106
int G_fatal_error(const char *msg,...)
Print a fatal error message to stderr.
dglInt32_t nDistance
Definition: graph.h:227
int dglFlatten(dglGraph_s *pGraph)
Definition: dglib/graph.c:139
void Vect_graph_build(GRAPH *graph)
Build network graph.
Definition: Vlib/graph.c:102