GRASS GIS 7 Programmer's Manual  7.5.svn(2017)-r71933
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
vector/Vlib/graph.c
Go to the documentation of this file.
1 /*!
2  \file lib/vector/Vlib/graph.c
3 
4  \brief Vector library - graph manipulation
5 
6  Higher level functions for reading/writing/manipulating vectors.
7 
8  \todo Vect_graph_free ( dglGraph_s *graph )
9 
10  (C) 2001-2009 by the GRASS Development Team
11 
12  This program is free software under the GNU General Public License
13  (>=v2). Read the file COPYING that comes with GRASS for details.
14 
15  \author Radim Blazek
16  */
17 
18 #include <stdlib.h>
19 #include <string.h>
20 #include <grass/dbmi.h>
21 #include <grass/vector.h>
22 #include <grass/glocale.h>
23 
24 static int From_node; /* from node set in SP and used by clipper for first arc */
25 
26 static int clipper(dglGraph_s * pgraph,
27  dglSPClipInput_s * pargIn,
28  dglSPClipOutput_s * pargOut, void *pvarg)
29 { /* caller's pointer */
30  dglInt32_t cost;
31  dglInt32_t from;
32 
33  G_debug(3, "Net: clipper()");
34 
35  from = dglNodeGet_Id(pgraph, pargIn->pnNodeFrom);
36 
37  G_debug(3, " Edge = %d NodeFrom = %d NodeTo = %d edge cost = %d",
38  (int)dglEdgeGet_Id(pgraph, pargIn->pnEdge),
39  (int)from, (int)dglNodeGet_Id(pgraph, pargIn->pnNodeTo),
40  (int)pargOut->nEdgeCost);
41 
42  if (from != From_node) { /* do not clip first */
43  if (dglGet_NodeAttrSize(pgraph) > 0) {
44  memcpy(&cost, dglNodeGet_Attr(pgraph, pargIn->pnNodeFrom),
45  sizeof(cost));
46  if (cost == -1) { /* closed, cannot go from this node except it is 'from' node */
47  G_debug(3, " closed node");
48  return 1;
49  }
50  else {
51  G_debug(3, " EdgeCost += %d (node)", (int)cost);
52  pargOut->nEdgeCost += cost;
53  }
54  }
55  }
56  else {
57  G_debug(3, " don't clip first node");
58  }
59 
60  return 0;
61 }
62 
63 /*!
64  \brief Initialize graph structure
65 
66  \param graph pointer to graph structure
67  \param nodes_costs use node costs
68 
69  \return void
70  */
71 void Vect_graph_init(dglGraph_s * graph, int nodes_costs)
72 {
73  dglInt32_t opaqueset[16] =
74  { 360000, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
75 
76  G_debug(3, "Vect_graph_init()");
77 
78  if (nodes_costs)
79  dglInitialize(graph, (dglByte_t) 1, sizeof(dglInt32_t),
80  (dglInt32_t) 0, opaqueset);
81  else
82  dglInitialize(graph, (dglByte_t) 1, (dglInt32_t) 0, (dglInt32_t) 0,
83  opaqueset);
84 }
85 
86 /*!
87  \brief Build network graph.
88 
89  Internal format for edge costs is integer, costs are multiplied
90  before conversion to int by 1000. Costs -1 for infinity i.e. arc
91  or node is closed and cannot be traversed.
92 
93  \param graph pointer to graph structure
94 
95  \return void
96  */
98 {
99  int ret;
100 
101  G_debug(3, "Vect_graph_build()");
102 
103  ret = dglFlatten(graph);
104  if (ret < 0)
105  G_fatal_error(_("GngFlatten error"));
106 }
107 
108 /*!
109  \brief Add edge to graph.
110 
111  Internal format for edge costs is integer, costs are multiplied
112  before conversion to int by 1000. Costs -1 for infinity i.e. arc
113  or node is closed and cannot be traversed.
114 
115  \param graph pointer to graph structure
116  \param from from node
117  \param to to node
118  \param costs costs value
119  \param id edge id
120 
121  \return void
122  */
123 void
124 Vect_graph_add_edge(dglGraph_s * graph, int from, int to, double costs, int id)
125 {
126  int ret;
127  dglInt32_t dglcosts;
128 
129  G_debug(3, "Vect_add_edge() from = %d to = %d, costs = %f, id = %d", from,
130  to, costs, id);
131 
132  dglcosts = (dglInt32_t) costs *1000;
133 
134  ret =
135  dglAddEdge(graph, (dglInt32_t) from, (dglInt32_t) to, dglcosts,
136  (dglInt32_t) id);
137  if (ret < 0)
138  G_fatal_error(_("Unable to add network arc"));
139 }
140 
141 /*!
142  \brief Set node costs
143 
144  Internal format for edge costs is integer, costs are multiplied
145  before conversion to int by 1000. Costs -1 for infinity i.e. arc
146  or node is closed and cannot be traversed.
147 
148  \param graph pointer to graph structure
149  \param node node id
150  \param costs costs value
151 
152  \return void
153  */
154 void Vect_graph_set_node_costs(dglGraph_s * graph, int node, double costs)
155 {
156  dglInt32_t dglcosts;
157 
158  /* TODO: Not tested! */
159  G_debug(3, "Vect_graph_set_node_costs()");
160 
161  dglcosts = (dglInt32_t) costs *1000;
162 
163  dglNodeSet_Attr(graph, dglGetNode(graph, (dglInt32_t) node), &dglcosts);
164 }
165 
166 /*!
167  \brief Find shortest path.
168 
169  Costs for 'from' and 'to' nodes are not considered (SP found even if
170  'from' or 'to' are 'closed' (costs = -1) and costs of these
171  nodes are not added to SP costs result.
172 
173  \param graph pointer to graph structure
174  \param from from node
175  \param to to node
176  \param List list of line ids
177  \param cost costs value
178 
179  \return number of segments
180  \return 0 is correct for from = to, or List == NULL ), ? sum of costs is better return value,
181  \return -1 destination unreachable
182  */
183 int
184 Vect_graph_shortest_path(dglGraph_s * graph, int from, int to, struct ilist *List,
185  double *cost)
186 {
187  int i, line, *pclip, cArc, nRet;
188  dglSPReport_s *pSPReport;
189  dglInt32_t nDistance;
190 
191  G_debug(3, "Vect_graph_shortest_path(): from = %d, to = %d", from, to);
192 
193  /* Note : if from == to dgl goes to nearest node and returns back (dgl feature) =>
194  * check here for from == to */
195 
196  if (List != NULL)
197  Vect_reset_list(List);
198 
199  /* Check if from and to are identical, otherwise dglib returns path to neares node and back! */
200  if (from == to) {
201  if (cost != NULL)
202  *cost = 0;
203  return 0;
204  }
205 
206  From_node = from;
207 
208  pclip = NULL;
209  if (List != NULL) {
210  nRet =
211  dglShortestPath(graph, &pSPReport, (dglInt32_t) from,
212  (dglInt32_t) to, clipper, pclip, NULL);
213  }
214  else {
215  nRet =
216  dglShortestDistance(graph, &nDistance, (dglInt32_t) from,
217  (dglInt32_t) to, clipper, pclip, NULL);
218  }
219 
220  if (nRet == 0) {
221  if (cost != NULL)
222  *cost = PORT_DOUBLE_MAX;
223  return -1;
224  }
225  else if (nRet < 0) {
226  G_warning(_("dglShortestPath error: %s"), dglStrerror(graph));
227  return -1;
228  }
229 
230  if (List != NULL) {
231  for (i = 0; i < pSPReport->cArc; i++) {
232  line = dglEdgeGet_Id(graph, pSPReport->pArc[i].pnEdge);
233  G_debug(2, "From %ld to %ld - cost %ld user %d distance %ld",
234  pSPReport->pArc[i].nFrom, pSPReport->pArc[i].nTo,
235  /* this is the cost from clip() */
236  dglEdgeGet_Cost(graph, pSPReport->pArc[i].pnEdge) / 1000,
237  line, pSPReport->pArc[i].nDistance);
238  Vect_list_append(List, line);
239  }
240  }
241 
242  if (cost != NULL) {
243  if (List != NULL)
244  *cost = (double)pSPReport->nDistance / 1000;
245  else
246  *cost = (double)nDistance / 1000;
247  }
248 
249  if (List != NULL) {
250  cArc = pSPReport->cArc;
251  dglFreeSPReport(graph, pSPReport);
252  }
253  else
254  cArc = 0;
255 
256  return (cArc);
257 }
dglInt32_t * dglGetNode(dglGraph_s *pGraph, dglInt32_t nNodeId)
unsigned char dglByte_t
Definition: type.h:36
dglInt32_t * pnEdge
Definition: graph.h:215
void dglNodeSet_Attr(dglGraph_s *pGraph, dglInt32_t *pnNode, dglInt32_t *pnAttr)
dglInt32_t * pnEdge
Definition: graph.h:96
dglInt32_t dglNodeGet_Id(dglGraph_s *pGraph, dglInt32_t *pnNode)
dglInt32_t nDistance
Definition: graph.h:216
dglInt32_t dglEdgeGet_Cost(dglGraph_s *pGraph, dglInt32_t *pnEdge)
#define NULL
Definition: ccmath.h:32
void G_fatal_error(const char *msg,...)
Print a fatal error message to stderr.
Definition: gis/error.c:159
dglInt32_t nTo
Definition: graph.h:214
int dglInitialize(dglGraph_s *pGraph, dglByte_t Version, dglInt32_t NodeAttrSize, dglInt32_t EdgeAttrSize, dglInt32_t *pOpaqueSet)
char * dglStrerror(dglGraph_s *pgraph)
int G_debug(int level, const char *msg,...)
Print debugging message.
Definition: debug.c:65
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
void Vect_graph_build(dglGraph_s *graph)
Build network graph.
int dglShortestDistance(dglGraph_s *pGraph, dglInt32_t *pnDistance, dglInt32_t nStart, dglInt32_t nDestination, dglSPClip_fn fnClip, void *pvClipArg, dglSPCache_s *pCache)
void Vect_graph_init(dglGraph_s *graph, int nodes_costs)
Initialize graph structure.
dglInt32_t nEdgeCost
Definition: graph.h:104
#define PORT_DOUBLE_MAX
Limits for portable types.
Definition: dig_defines.h:66
void Vect_graph_set_node_costs(dglGraph_s *graph, int node, double costs)
Set node costs.
int Vect_graph_shortest_path(dglGraph_s *graph, int from, int to, struct ilist *List, double *cost)
Find shortest path.
dglInt32_t * pnNodeFrom
Definition: graph.h:95
dglInt32_t * pnNodeTo
Definition: graph.h:97
int dglAddEdge(dglGraph_s *pGraph, dglInt32_t nHead, dglInt32_t nTail, dglInt32_t nCost, dglInt32_t nEdge)
dglInt32_t cArc
Definition: graph.h:228
dglInt32_t * dglNodeGet_Attr(dglGraph_s *pGraph, dglInt32_t *pnNode)
#define _(str)
Definition: glocale.h:13
List of integers.
Definition: gis.h:650
void Vect_graph_add_edge(dglGraph_s *graph, int from, int to, double costs, int id)
Add edge to graph.
int dglFlatten(dglGraph_s *pGraph)
dglInt32_t nDistance
Definition: graph.h:227
void G_warning(const char *msg,...)
Print a warning message to stderr.
Definition: gis/error.c:203
dglInt32_t dglEdgeGet_Id(dglGraph_s *pGraph, dglInt32_t *pnEdge)
void dglFreeSPReport(dglGraph_s *pgraph, dglSPReport_s *pSPReport)
int dglGet_NodeAttrSize(dglGraph_s *pgraph)
int dglShortestPath(dglGraph_s *pGraph, dglSPReport_s **ppReport, dglInt32_t nStart, dglInt32_t nDestination, dglSPClip_fn fnClip, void *pvClipArg, dglSPCache_s *pCache)