GRASS GIS 8 Programmer's Manual  8.4.0dev(2024)-7d4cd0c030
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
25  From_node; /* from node set in SP and used by clipper for first arc */
26 
27 static int clipper(dglGraph_s *pgraph, dglSPClipInput_s *pargIn,
28  dglSPClipOutput_s *pargOut, void *pvarg UNUSED)
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), (int)from,
39  (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
47  'from' node */
48  G_debug(3, " closed node");
49  return 1;
50  }
51  else {
52  G_debug(3, " EdgeCost += %d (node)", (int)cost);
53  pargOut->nEdgeCost += cost;
54  }
55  }
56  }
57  else {
58  G_debug(3, " don't clip first node");
59  }
60 
61  return 0;
62 }
63 
64 /*!
65  \brief Initialize graph structure
66 
67  \param graph pointer to graph structure
68  \param nodes_costs use node costs
69 
70  \return void
71  */
72 void Vect_graph_init(dglGraph_s *graph, int nodes_costs)
73 {
74  dglInt32_t opaqueset[16] = {360000, 0, 0, 0, 0, 0, 0, 0,
75  0, 0, 0, 0, 0, 0, 0, 0};
76 
77  G_debug(3, "Vect_graph_init()");
78 
79  if (nodes_costs)
80  dglInitialize(graph, (dglByte_t)1, sizeof(dglInt32_t), (dglInt32_t)0,
81  opaqueset);
82  else
83  dglInitialize(graph, (dglByte_t)1, (dglInt32_t)0, (dglInt32_t)0,
84  opaqueset);
85 }
86 
87 /*!
88  \brief Build network graph.
89 
90  Internal format for edge costs is integer, costs are multiplied
91  before conversion to int by 1000. Costs -1 for infinity i.e. arc
92  or node is closed and cannot be traversed.
93 
94  \param graph pointer to graph structure
95 
96  \return void
97  */
99 {
100  int ret;
101 
102  G_debug(3, "Vect_graph_build()");
103 
104  ret = dglFlatten(graph);
105  if (ret < 0)
106  G_fatal_error(_("GngFlatten error"));
107 }
108 
109 /*!
110  \brief Add edge to graph.
111 
112  Internal format for edge costs is integer, costs are multiplied
113  before conversion to int by 1000. Costs -1 for infinity i.e. arc
114  or node is closed and cannot be traversed.
115 
116  \param graph pointer to graph structure
117  \param from from node
118  \param to to node
119  \param costs costs value
120  \param id edge id
121 
122  \return void
123  */
124 void Vect_graph_add_edge(dglGraph_s *graph, int from, int to, double costs,
125  int id)
126 {
127  int ret;
128  dglInt32_t dglcosts;
129 
130  G_debug(3, "Vect_add_edge() from = %d to = %d, costs = %f, id = %d", from,
131  to, costs, id);
132 
133  dglcosts = (dglInt32_t)costs * 1000;
134 
135  ret = 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
181  better return value, \return -1 destination unreachable
182  */
183 int Vect_graph_shortest_path(dglGraph_s *graph, int from, int to,
184  struct ilist *List, double *cost)
185 {
186  int i, line, *pclip, cArc, nRet;
187  dglSPReport_s *pSPReport;
188  dglInt32_t nDistance;
189 
190  G_debug(3, "Vect_graph_shortest_path(): from = %d, to = %d", from, to);
191 
192  /* Note : if from == to dgl goes to nearest node and returns back (dgl
193  * feature) => check here for from == to */
194 
195  if (List != NULL)
196  Vect_reset_list(List);
197 
198  /* Check if from and to are identical, otherwise dglib returns path to
199  * nearest 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 = dglShortestPath(graph, &pSPReport, (dglInt32_t)from,
211  (dglInt32_t)to, clipper, pclip, NULL);
212  }
213  else {
214  nRet = dglShortestDistance(graph, &nDistance, (dglInt32_t)from,
215  (dglInt32_t)to, clipper, pclip, NULL);
216  }
217 
218  if (nRet == 0) {
219  if (cost != NULL)
220  *cost = PORT_DOUBLE_MAX;
221  return -1;
222  }
223  else if (nRet < 0) {
224  G_warning(_("dglShortestPath error: %s"), dglStrerror(graph));
225  return -1;
226  }
227 
228  if (List != NULL) {
229  for (i = 0; i < pSPReport->cArc; i++) {
230  line = dglEdgeGet_Id(graph, pSPReport->pArc[i].pnEdge);
231  G_debug(2, "From %ld to %ld - cost %ld user %d distance %ld",
232  pSPReport->pArc[i].nFrom, pSPReport->pArc[i].nTo,
233  /* this is the cost from clip() */
234  dglEdgeGet_Cost(graph, pSPReport->pArc[i].pnEdge) / 1000,
235  line, pSPReport->pArc[i].nDistance);
236  Vect_list_append(List, line);
237  }
238  }
239 
240  if (cost != NULL) {
241  if (List != NULL)
242  *cost = (double)pSPReport->nDistance / 1000;
243  else
244  *cost = (double)nDistance / 1000;
245  }
246 
247  if (List != NULL) {
248  cArc = pSPReport->cArc;
249  dglFreeSPReport(graph, pSPReport);
250  }
251  else
252  cArc = 0;
253 
254  return (cArc);
255 }
#define NULL
Definition: ccmath.h:32
void void void void G_fatal_error(const char *,...) __attribute__((format(printf
void G_warning(const char *,...) __attribute__((format(printf
int G_debug(int, const char *,...) __attribute__((format(printf
int Vect_list_append(struct ilist *, int)
Append new item to the end of list if not yet present.
int Vect_reset_list(struct ilist *)
Reset ilist structure.
#define PORT_DOUBLE_MAX
Limits for portable types.
Definition: dig_defines.h:66
#define UNUSED
A macro for an attribute, if attached to a variable, indicating that the variable is not used.
Definition: gis.h:47
#define _(str)
Definition: glocale.h:10
dglInt32_t nDistance
Definition: graph.h:196
dglInt32_t nTo
Definition: graph.h:194
dglInt32_t * pnEdge
Definition: graph.h:195
dglInt32_t nFrom
Definition: graph.h:193
dglInt32_t * pnNodeTo
Definition: graph.h:90
dglInt32_t * pnNodeFrom
Definition: graph.h:88
dglInt32_t * pnEdge
Definition: graph.h:89
dglInt32_t nEdgeCost
Definition: graph.h:96
dglInt32_t nDistance
Definition: graph.h:205
dglInt32_t cArc
Definition: graph.h:206
dglSPArc_s * pArc
Definition: graph.h:207
List of integers.
Definition: gis.h:706
unsigned char dglByte_t
Definition: type.h:35
long dglInt32_t
Definition: type.h:36
void Vect_graph_init(dglGraph_s *graph, int nodes_costs)
Initialize graph structure.
void Vect_graph_add_edge(dglGraph_s *graph, int from, int to, double costs, int id)
Add edge to graph.
void Vect_graph_set_node_costs(dglGraph_s *graph, int node, double costs)
Set node costs.
void Vect_graph_build(dglGraph_s *graph)
Build network graph.
int Vect_graph_shortest_path(dglGraph_s *graph, int from, int to, struct ilist *List, double *cost)
Find shortest path.
int dglGet_NodeAttrSize(dglGraph_s *pgraph)
int dglAddEdge(dglGraph_s *pGraph, dglInt32_t nHead, dglInt32_t nTail, dglInt32_t nCost, dglInt32_t nEdge)
int dglShortestPath(dglGraph_s *pGraph, dglSPReport_s **ppReport, dglInt32_t nStart, dglInt32_t nDestination, dglSPClip_fn fnClip, void *pvClipArg, dglSPCache_s *pCache)
char * dglStrerror(dglGraph_s *pgraph)
dglInt32_t dglEdgeGet_Id(dglGraph_s *pGraph, dglInt32_t *pnEdge)
void dglNodeSet_Attr(dglGraph_s *pGraph, dglInt32_t *pnNode, dglInt32_t *pnAttr)
int dglInitialize(dglGraph_s *pGraph, dglByte_t Version, dglInt32_t NodeAttrSize, dglInt32_t EdgeAttrSize, dglInt32_t *pOpaqueSet)
dglInt32_t * dglNodeGet_Attr(dglGraph_s *pGraph, dglInt32_t *pnNode)
void dglFreeSPReport(dglGraph_s *pgraph UNUSED, dglSPReport_s *pSPReport)
int dglShortestDistance(dglGraph_s *pGraph, dglInt32_t *pnDistance, dglInt32_t nStart, dglInt32_t nDestination, dglSPClip_fn fnClip, void *pvClipArg, dglSPCache_s *pCache)
int dglFlatten(dglGraph_s *pGraph)
dglInt32_t dglEdgeGet_Cost(dglGraph_s *pGraph, dglInt32_t *pnEdge)
dglInt32_t dglNodeGet_Id(dglGraph_s *pGraph, dglInt32_t *pnNode)
dglInt32_t * dglGetNode(dglGraph_s *pGraph, dglInt32_t nNodeId)